一种将XPath查询转换为树形数据结构的查询优化方法

技术领域

本发明涉及XML查询优化领域，尤其涉及一种有位置谓词的 XPath查询转换为树形数据结构的查询优化方法。

背景技术

XML因其具有自描述性，可扩展性以及开放性等优点使其得到 了广泛的应用，随着XML数据的不断增长，对大规模XML数据的 管理需求也日渐迫切，出现了XML数据库等商业产品。XML数据 的查询因此而显得尤为重要，而XML查询标准之一XPath也得到了 广泛研究和实现。因XML文档半结构化的特性使得传统的关系数据 库的查询算法对其并不适用，因此相继提出了一些针对XPath查询的 算法。目前研究比较广泛的有小枝模式匹配算法，即将XPath查询表 示成一棵用节点和边进行标记的小枝模式查询树，XPath查询也就变 成了在XML数据中找出所有和这个小枝模式匹配的数据片段。

目前有不少有关小枝模式查询处理的方法，每种方法都有其小枝 模式的内部表示，但针对有位置谓词的小枝模式查询方法涉及甚少。

在XPath中，带位置谓词的表达式的查询语义是求满足特定结构 和位置条件的节点集。特别值得注意的是，表达式外是否有圆括号， 和位置谓词的求值有着密切的关系。例如，XPath查询语句Q1和Q2：

Q1=//bookstore/book[title=“计算机”and price<30]/author[2]

Q2=(//bookstore/book[title=“计算机”and price<30]/author)[2]

Q1表示在图书库中查找书名为《计算机》且售价小于30元每本 书的第二作者信息，位置求职是相对于book这个步而言的；Q2表示 在书名为《计算机》且售价小于30元的书的所有作者信息中取第二 个作者信息，位置求职是相对于XML数据文档的根。由这两个例子 可以看出加圆括号和不加圆括号的求职语义是完全不同的，这也需要 在查询处理时区别对待。

在实际应用中，位置谓词查询的使用场合非常广泛，如何在小枝 模式中有效地处理位置谓词查询有着其重要的意义。

发明内容

为解决上述中存在的问题与缺陷，本发明提供了一种将XPath 查询转换为树形数据结构的查询优化方法。所述技术方案如下：

一种将XPath查询转换为树形数据结构的查询优化方法，包括：

A将带有位置谓词的XPath查询语句转换为抽象语法树AST；

B将抽象语法树AST中不同类型的节点对象转换成小枝模式树 形结构中的节点对象。

本发明提供的技术方案的有益效果是：

小枝模式树形数据结构以及小枝模式转换方法在一定程度上优 化了小枝模式查询；且本发明提出的在位置谓词节点对象中存储其 参考位置的方法，在小枝查询时，能够快速定位相对求值节点，加 快了小枝模式查询处理中对位置查询的求值。

附图说明

图1是将XPath查询转换为树形数据结构的查询优化方法流程 图；

图2是为查询Q1的小枝模式查询树结构图；

图3是为查询Q2的小枝模式查询树结构图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面将结合附图 对本发明实施方式作进一步地详细描述：

本实施例提供了一种将XPath查询转换为树形数据结构的查询优 化方法的方法，如图1所示该方法包括：

步骤10将带有位置谓词的XPath查询语句转换为抽象语法树 AST（Abstract Syntax Tree）；

上述XPath查询语句通过词法、语法分析并简化为抽象语法树。

步骤20将抽象语法树AST中不同类型的节点对象转换成小枝模 式树形结构中的节点对象。

自顶向下遍历抽象语法树，每种AST节点对象调用其对应的转换 接口，将其转换成小枝模式查询树中对应的节点对象。其过程具体包 括如下：

步骤201定义一个ASTVisitor抽象类，通过一转换接口实现对所 有AST节点转换的总控制，和通过AST节点类型调用对应的具体转换 虚接口。

步骤202实现一个继承ASTVisitor抽象类的具体转换类，并实现 每个具体的转换接口，根据AST节点对象的组成部分，分别制定转换 规则，将其转换为正确的小枝模式查询节点对象。

步骤203在查询过程中，计算并标记出位置谓词PQNode节点的 参考位置集。先在转换类型中定义一个集合变量LeveI，用来存储转 换过程中的当前模式树层次集，为了支持路径的集合运算，当前树层 次值需要用集合来存储。树层次采用从0开始计数，每转换生成一个 有效的定位步EQNode节点，树层次就加1，特殊的查询节点生成时， 树的层次不变，如SQNode节点不包含在计数内。接着在谓词转换时， 对于有位置谓词的语法树节点，其参考位置集用RefLevel存储，其值 等于位置谓词应用到的表达式的上一层模式树层次集Level。

抽象语法树AST：XPath查询语句通过词法语法分析后，得到符 合要求的语法树，然后通过简化形成本发明的抽象语法树，它体现了 查询语句的树状语法结构。抽象语法树中的节点类型是按照XPath标 准中表达式类型进行定义的。每个类型的表达式都有其特定的组成部 分，故AST中每个节点类型也有其对应的组成部分。如导航节点由步 节点集合组成；步节点由轴，节点测试等组成；谓词节点由谓词表达 式和其限定的表达式组成；逻辑表达式节点由其包含的项节点集合组 成。

小枝模式查询树：由查询节点和边组成的树形结构。查询节点主 要包括SQNode，FQNode，PQNode和EQNode。

SQNode：表示AND/OR逻辑表达式以及UNION集合表达式的节 点。

FQNode：描述XPath查询中函数的节点。

PQNode：描述位置谓词信息以及值比较谓词中的比较运算符和 常量值信息的节点。

EQNode：描述一个定位步信息的节点,主要包含了定位步的轴、 自身节点、谓词节点和next节点。

边描述了小枝模式查询树中自顶向下前后两个查询节点间的关 系，包括：

next关系：两个查询节点间先后关系,后者是前者的下一个定位 步。

谓词关系：两个查询节点间后者是前者的谓词节点。

包含关系：后者是前者中的一个包含项节点。

图2和图3分别展示了查询Q1和Q2对应的小枝模式查询树结构 图。查询Q1和Q2的区别是Q2多了一个括号限定，在抽象语法树AST 中将位置谓词前的括号内容整体作为一个位置谓词应用到的表达式， Q2中“//bookstore/book[title=“计算机”and price<30]/author”被看 作位置谓词“2”应用到的表达式，位置谓词的参考位置集就等于这 个表达式的上一层，也就是文档根的模式树层次集{0}。Q1中，位置 谓词“2”应用到的表达式是author步，其参考位置集等于author步的 上一层book步所在的模式树层次集{2}。其中：//,bookstore、/,book、 and、/,author、/,title、/,price、表示除PQNode以外的查询节点QNode； =,2,pos、=,计算机和<,30表示PQNode含有比较操作符，具体的值， 位置谓词标记；虚线表示谓词关系；箭头表示next关系；实线表示包 含关系。

以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在 本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均 应包含在本发明的保护范围之内。