XQuery的实现机制
程雷朱茂盛
（clei@software.ict.ac, zhums@software.ict.ac）
简介
随着XML数据越来越广泛的应用，它的查询语言也就成为目前研究的热点。XQuery 由w3c提出，将成为以后的XML查询标准。本文讨论XQuery的实现机制及其优化。
关键字：XQuery 优化 XML
Abstract
With the growing use of XML data, its query language has become the focus of current research. XQuery is now considered by w3c, and will be the XML query standard of future. The implementation mechanism and optimization of XQuery will be discussed in this paper.
Keywords：XQuery optimization XML
1. XML查询语言简介
近年来，XML格式的数据使用越来越广泛。XML的数据存储方式和其查询语言就成为当前的研究热点。XML的存储目前主要有两种方式：基于数据库和本地存储（native XML）[1]。而XML查询语言则经历了一个比较复杂的发展过程。
人们提出并使用过的查询语言有XSL[2]，XQL[3]，XML-QL[4]，YATL[5]，Lorel[6]等。每种语言都有自己的优点，满足一定的需要，但作为一个通用的查询语言又有些不足。在这种情况下Don Chamberlin等人提出了Quilt语言[7]，它结合了上述语言的优点，现在已经被w3c采用，作为XQuery语言的基础。
一个通用的XML查询语言应该满足以下几点要求：要有一个可读并且可以用XML 格式来表示的语法结构；语言应该是说明性的（也就是说这个语言不应该强制一种实现算法）；应该有错误处理机制；协议无关性；有更新机制；对有限的文档定义[8]。目前XQuery还不能满足所有这些条件，还处于一种草案的状态，主要是由于更新的语法不好确定。XQuery具有上述很多语言的优点，如XQuery吸收了XQL语言的路径表达式，XQuery的变量取自于XML-QL语言，XQuery根据SQL的select-from-where模式定义了(for|let)+-where-return表达式，XQuery还接收了OQL中的函数概念。
XQuery主要有以下几个组成部分：
1.路径表达式(Path expressions)
2.元素构建表达式(Element constructors)
3.FLWR表达式(FLWR expressions)
4.带运算符和函数的表达式(Expressions involving operators
and functions)
5.条件表达式(Conditional expressions)
6.量化表达式(Quantified expressions)
7.数据类型的测试和修改表达式(Expressions that test or modify
datatypes)
下图是ＸＱｕｅｒｙ的一个例子
<bib>
{
FOR $b IN document("www.bn")/bib/book
WHERE $b/publisher = "Addison-Wesley" AND $b/@year > 1991
RETURN
<book year={ $b/@year }>
{ $b/title }
</book>
}
</bib>
图1. XQuery的例子
本文中描述XQuery语言实现的总体结构和具体算法，以及一些优化的方法。本文第2部分描述XQuery语言的总体实现结构，第3部分给出XQuery 主要部分的实现算法，第4部分段介绍一下优化算法，最后是结束语。
2．XQuery实现的总体结构
XQuery语言实现的总体结构由图2所示。主要分为3个部分：词法分析，语法分析和查询计算求值。以下分别讲述。
2.1 XQuery的词法分析
XQuery的词法分析比较简单。唯一需要考虑的问题是不同的词在不同的上下文环境下有不同的语义，需要单独分析。比如FOR在一般情况下为关键字，但是如果作为元素标签或元素构建表达式里的内容则不是关键字。所以分析时需要记住当前的上下文状态，根据不同的上下文状态选择不同的词法分析函数。我们给词法分析分了四个状态，分别是一般表达式的状态，元素标签中的状态，元素属性中的状态和元素内部状态。由于篇幅有限，就不做详细介绍了。
2.2 XQuery的语法分析
XQuery的语法分析根据词法分析器提供的语法单元构造查询的语法树表示。语法树和XQuery语言的对应是一对一的，这里也不做详细介绍。由于XQuery支持名字空间[9]，所以需要用名字空间映射表记录各个名字空间的前缀标识。我们对XQuery中外部函数（用户定义函数）的处理和对内部函数的处理是不一样的。语法分析时如果遇到内部函数，我们直接从内部函数表中查相应函数并进行绑定。而外部函
数由于存在递归和引用时还未定义等问题，我们采用了两遍扫描的技术，第一遍我们记录函数定义和引用的
位置，第二遍我们将函数的引用和函数的定义进行绑定。
2.3 查询的计算
查询结果的计算是本文的重点，我们将在第三部分做详细的介绍。这里做一些基本的说明。由于在XQuery的语义中有很多地方需要一个默认的结果，比如相对路径就要一个当前默认的节点集，所以用中间结果保存这个值。
XQuery支持嵌套的FLWR表达式和函数，他们中的某些变量可能重名，我们用栈来保存这些变量，当从函数或底层的FLWR表达式退出时，再恢复这些变量的值。
3．XQuery实现的详细算法
相对于SQL查询部分表达式的简洁，XQuery的查询部分比较复杂，它的实现算法也比较复杂。下面我们将给出其中几个复杂算法的实现。
3.1 Path表达式的实现
Path表达式主要取自XPath的规范[10]。每个Path表达式由多个步进表达式（step）组成，而步进表达式由节点产生式和谓词构成。节点产生式根据当前节点的值生成一些候选节点集，再经过谓词过滤产生该步的节点集。
当所有步进表达式都计算完后，最后生成的节点集就是该Path表达式的结果。图3是算法的流程图。
xpath注入是针对xml数据应用吗
3.2 函数表达式的实现
XQuery 中的函数有两类，内部函数和外部函数。内部函数是XQuery 自带的函数，外部函数是用户自定义的函数。这两种函数的实现是不一样的，内部函数在编译时和具体的函数绑定，求值时直接调用，外部函数实现的算法由图4所示。调用外部函数时，需要保存当前节点和函数要定值的变量的值，在退出函数时在恢复它们，除此外外部函数和一般的表达式没有太大的区别。
另一个需要提及的问题是参数的传递，我们采用的方法类似于为C 中的main 函数传参数的方法。所有的参数都有统一的类型（基类型，实际类型派生于此），传给函数的实际是参数的个数和参数的数组。
3.3 FLWR 表达式的算法
FLWR 表达式是
XQuery 语言中非常重要的一部分，XQuery 查询语言中绝大部分都是FLWR 结构的。它的算法实现见图5。其中FLWR 表达式定值的变量是指表达式中FOR 或LET 子句中的变量。算法直观上很简单，将FLWR 定值的所有的变量看作一个变量组，求出所有的变量组绑定，然后对每一个变量组的绑定计算一下where 表达式的值，如果为真则计算Return 子表达式，作图3. Path 表达式算法 图4. 函数表达式算法
为结果的一部分。
图5.FLWR表达式的算法
3.4 元素构建表达式
元素构建表达式是XQuery语言的另一个重要的部分，它定义了输出的结果的格式，一般和FLWR表达式一起用。元素构建表达式常出现在FLWR表达式的return子表达式中，而FLWR表达式也可以作为元素构建表达式中的一

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。