一种基于编码的图模型XML数据的存储与查询处理方法

摘要

图查询的核心问题是图的匹配问题,由于图结构强大的表示能力,图上的查询在许多方面有着广泛的应用.有向图上两点间的可达查询即是给定两个节点u,v,判断图中是否存在从u到v的有向路径.而对于查询图Q而非两点间的可达查询,需要在数据图中找出所有满足Q的子图,其节点间应该满足Q中规定的可达关系.XML规范将数据以有向图的形式组织,随着XML的广泛应用,有向图上的可达查询变得日益重要. 基于可达编码的方法是树状XML数据查询处理中使用最广的方法之一,其基本思想是为图中的每个节点/边赋予特定信息,使得任两个节点通过彼此的信息就可在常数时间内判断可达关系.虽然针对树状数据的Interval编码已经被引入到图状XML数据的可达查询处理中,但是由于图的边可能会非常多,完全采用编码的方法将会占用大量的搜索和存储空间,因此是不适用的。