XML文件树状路径查询优化研究
发布时间：2015-07-11 10:01
摘 要 XML查询优化成为XML数据库研究热点，其中的结构连接是其主要操作。连接顺序的选择是XML查询的核心问题。本文提出在片段路径树的基础上，提出了一种连接及组合路径表达式的策略，该策略是首先得到最优化路径序列，最后将最优化序列组合成完整的查询结果。
关键词 XML；查询优化；路径表达
1 相关定义
XQuery是由W3C制定的，其目的是提供一种查询语言，让使用者可以从XML文档中找出所需要的资料。XQuery基本上包含三个子句，在For语句中，使用者可以使用XPath指定所要依序处理的元素并将其配置给一个变量，Where语句则是可以对每个变量进行条件限定，而Return语句则是可以指定所希望返回的元素及其格式。
在XML查询中，可以将XPath转化为一棵树，称为查询树。从初始查询树开始，选择查询树中的某一条边，对该边上相连接的两个结点做连接，连接的结果用一个新的结点表示，并代替原树中的两个结点。每次连接时都会使结点减少一个，同时产生一个新的树。当树只包括一个结点时，整个求解过程便结束。
在查询树中，可以将树中的结点分为五种类型，分别是：根节点 (Root)，叶节点 (LN)，分支节点 (GN)，孙子节点 (DN)，孩子节点 (CN)。其中与通常情况不同的是，孙子节点是指在查询树中与其下一个节点为祖孙关系的节点。孩子节点是指在查询树中与下一个节点为父子关系的节点。将查询中需要返回的结点，定义为返回节点。
定义1：给定一个查询树QT (N，E)，及节点NiÎN，若Ni为GN或LN或DN，则将此节点称为GLD Node。
定义2：给定一个查询树QT (N，E)，及QT中的一条路径P为EiNi….Ni+nEi+nNi+n+1，若Ni与Ni+n+1为GLD Node或根节点，且对于所有的节点Nj属于Ni+1到Ni+n皆不为GLD Node或根节点，则我们称EiNi….Ni+nEi+nNi+n+1为一个后置路径（Suffix Path）。
定义3：给定一个查询树，由根节点开始向下访问，若走访的节点属于GLD Node，则将其建立在片段路径树中，PT (N，E)，N是节点的集合，E是边的集合。对于每个ni ∈N都有一个TagName，且ni的类型只属于GN或LN或DN。对于每个ei ∈E为 “/”，代表节点与节点之间的相邻关系为父子关系。称这样的树为片段路径树。
定义4：假设A为Suffix Path的最后一个节点，则XML文档中符合Suffix Path的文件所构成的集合，称之为A的Partial Data，记作Ap。
定义5：在片段路径树 FPT (FN，FE) 中，假设NiÎFN且以Ni为起始点的路径P为EiNiEi+1Ni+1Ei+2…Ei+nNi+n，若Ni为叶节点或分支节点，Ni+n为最接近Ni的根节点或分支节点，则称路径P为一个片段路径，并以 “Ni-Ni+n” 表示。
2 问题提出
图1（c）所显示的是将XQuery Tree拆分成Suffix Path，即 “/a” 、“//b” 、“//c” 、“//d” 。
图1
情况1：如果我们“//b//c” 、“//b//d” 、“/a//b”组合文件，则//b//c的结果有(b1，c1) 、(b2，c2) 、(b3，c3)共三种选择，其次符合 “//b//d” 的有 (b1，d1)一种选择，所以，没有对应文件的b2，b3会从b中删除。/a//b有一种选择。在此顺序下需要五次选择连接。最后将其组合成最后结果，显然只有一种选择。所以按照如上方式一共做了六次选择连接。
情况2：假设建立的顺序为 “//b//d” 、“//b//c” 、“/a//b”，按照情况1的分析方式，得到3种选择，最后按照“/a//b” 、“//b//c”、“//b//d”的方式组合只有一种选择。显然通过四次选择连接就得到了最后结果。
通过上例，可以看到不同的建立及组合顺序对查询结果确有影响。这正是本文所研究的内容。本文所研究的方法是基于片段路径树的。基本框架为：首先找到最优化的片段路径序列，然后根据Partial Data建立符合片段路径结构的文档，最后得到具有完整结构的查询结果。
3 主要研究方法
本文依据文献[1]的方法得到片段路径树及树中每个节点所对应的Partial Data。首先根据路径树及对应的Partial Data 进行最佳化处理。基本思想是：按照起始点和中间点两种不同的类型节点进行访问。Partial Data大的先访问或者小的先访问。算法的最终目的是输出最佳片段路径序列。
算法3.1
function ()
{
输入：带有Partial Data的片段路径树PT_TREE；
startNode(PT_TREE)；//从根节点或者叶节点开始访问
set(Patatial Data)；//设置访问策略，选择Partial Data大的先访问或小的先访问
()；//将起始点为标识下一个要访问的节点
()；//建立一个表用来存放已访问结点
fpSequence(optimization(startNode，fpList，set))；//进行最优化处理
输出：fpSequence；
}
通过算法3.1可以得到最优化片段路径序列。那么其中的optimization算法是如何实现的呢，我们将在算法3.2给出详细求解过程。在树访问过程中，会有
遗漏的结点暂时未被访问，用单向链表linkList来存储这些节点。链表中每个节点的内容是两个指向路径树的指针，分别为CurrentGTNode、PGNode，CurrentGTNode指向当前节点，PGNode指向一个相邻的类型为GN的节点。
算法3.2
Optimization (startNode，fpList，set){
输入：startNode，fpList，set；
(currentNode)；//将当前节点放入fpList表中，并判断当前节点的情况
if(父亲节点&&儿子节点都已访问过){
if( ()0) 调整fpList，将fpList放入fpSequence中；
if(linkList为空) 输出fpSequence；
else{
从linkList中取出第一个节点，& (PGNode)继续进行递归优化
//将PGNode放入表中，因为linkList中的节点是因为该节点而遗漏的，将PGNode
//放入表中，表示是从该PGNode节点走向linkList中的节点的
Optimization(CurrentGTNode，fpList，set)；
}
}
if(节点类型为DN) 寻找下一节点，递归Optimization(nextNode，fpList，set)；
if(节点类型为GN) 调整fpList，将fpList放入fpSequence中，&()；
继续访问下一节点nextNode；
if(nextNode取自linkList) linkList指针后移，& (PGNode)；
else ()；//设置下一节点访问策略
寻找临近当前节点，且被遗漏访问的节点；
将暂时遗漏节点放置在linkList中；//linkList的元素按照Partial Data进行排列
Optimization(nextNode，fpList，set)；
}
接下来对得到的最优化片段路径序列进行处理，主要是对每一个节点的Partial Data进行组合，建立符合片段路径结构的文档。如果有些片段无法匹配，将其删除。并将匹配结果存到FP_TABLE表中。
建立片段路径的详细方法参见参考文献[1]。
下面根据FP_TABLE组合出完整的结果。在问题的提出那一节，我们清晰的看到，不同的组合结果，所需要的代价是不同的。因此，本文采用组合顺序方式为由数量小的FP_TABLE到数量大的FP_TABLE。这样可以最大程度上减少组合代价。因此需要将得到的FP_TABLE进行由小到大的排列。下面通过算法3.3探讨具体组合过程。
算法3.3
输入：片段序列中第一个节点所组成的集合FNode；//原因在于这些节点与FP_TABLE对应
ex(0)；//取得第一个节点
for(该节点的FP_TABLE中每一笔符合的片段GT){
FNode .CurrentGT=GT；//保存第一笔GT记录，以便在递归调用时得到上次处理的记录
如果需要返回结果，则将结果放到结果表中；
if(Fnode的最近的邻节点为根节点){
Result=Recombine(Fnode，index，Result)；//index为节点编号，Result需返回的节点
找到一组符合的答案，将其加入到ResultTable中；
}
//临近的节点为GN
else{
取得上方临近的GN
取得在该节点的FP_TABLE中和CurrentGT能够组合的记录GTTable；
对GTTable中的每一笔GT进行递归处理（Result=Recombine(Fnode，index，Result)）；
继续寻找下一节点，并针对FP_TABLE进行组合；
}
}//end for
Recombine算法为组合片段路径，算法过程
算法：3.4
输入：片段序列中第一个节点所组成的集合FNode；
如果所有路径都已处理完，则返回处理结果；
取得下一个需处理节点及与该节点在结构上最近的GN节点lastNode。
if(lastNode为空) {
Recombine(Fnode，index，Result)；//对根节点递归处理
Reset(FNode .CurrentGT)；
}
if(存在GN且tGT尚未被访问){
取得GN节点FP_TABLE中和CurrentGT能够组合的序列；
针对这些记录进行递归处理；
}
if(GN存在，但CurrentGT已被访问){
取得该节点的FP_TABLE中和其上GN节点的CurrentGT能够组合的序列；
递归处理这些记录，并寻找下一组合节点；
}
4 实验结果
个人计算机作为实验的平台，其CPU为Pentium 4 2.40GHz，内存为512MB，采用的操作系统为Microsoft Windows 2000，采用VC++编程，对本文所采用的最佳化策略与文献[1]及穷举法进行比较。得到的实验结果是本文所采用的策略要快于文献[1]及穷举法。
5 结论及未来研究方向
本文探讨了最优化的组合策略，包括最佳化算法处理片段路径树及将所得到的路径序列进行最优化组合。提高了查询的效率，达到了查询优化的目的。未来可以对查询语句进行更精确的分析，可以在无文档结构下快速找到最佳处理策略。
参考文献
[1]李政达.XML文件树状路径查询之研究.硕士论文，国立台湾海洋大学资讯工程系，2004
Ning Zhang，Varun Kacholia，M. Tamer Ozsu，“A Succinct Physical Storage Scheme for Efficient Evaluation of Path Queries in XML”，ICDE 2004
Barbara Catania，Wen Qiang Wang，Beng Chin Ooi，Xiaoling Wang，“Lazy XML Updates：Laziness as a Virtue of Update and Structural Join Efficiency”，SIGMOD 2005
Shurug Al-Khalifa，H. V. Jagadish，Nick Koudas，Jignesh M. Patel，Divesh Srivastava，Yuqing Wu，“Structural Joins：A Primitive for Efficient XML Query Pattern Matching”，ICDE 2002
下一篇：Vega扩展模块的设计与研究