论文导读:：针对XML数据存储和查询的研究正方兴未艾。研究者已经由XML数据简单路径查询转移到复杂小枝查询的研究。基于层次树的小枝查询方法。
关键词：XML数据，小枝查询，层次树
1 引 言
XML作为基于WEB应用的一种电子数据交换标准，是Internet共通的语言与沟通的媒介。针对XML数据存储和查询的研究正方兴未艾。当前，研究者已经由XML数据简单路径查询转移到复杂小枝查询的研究。目前小枝查询方法中最有代表性的是Bruno等提出的基于整枝连接技术的TwigStack[1]算法，其思想是利用相互连接的多栈结构一次性生成查询结果文档。然而TwigStack算法对于含父亲-孩子边的查询不够有效[6]。
本文在发现文档树中与查询树中的同一个查询结点对应的结点间自然地形成树型结构关系的基础上，提出把文档树中与相同的查询结点匹配的元素组织成层次栈结构，从而得出了一种基于层次栈的新的XML数据小枝查询算法。
2 XML小枝查询
XML查询一般分为通过对限定在元素内容和属性值上的取值而进行选择的值查询和通过对文档中标记的元素之间的结构关系进行的结构查询。一般情况下，结构关系查询可以分为两种不同的类型：（1）路径表达式查询；（2）小枝查询。
在结构查询中，单斜线和双斜线边符号分别用来表示结点间的父亲-孩子关系和祖先-后代关系。例如查询Q1＝/dblp//inproceedings[/author=’Jon’]是用来匹配所有满足以下条件的路径表达式查询：1）由作者Jon写的；2）二元结构成分（inproceedings/author）是父亲-孩子关系，而（dblp//inproceedings）元素对是祖先-后代关系。小枝查询Q2=/article[./author=’Jon’AND /title=’XML’]是查找由Jon所写的在他们的题目中有’XML’词的文章。
前人的许多工作已经对XML小枝查询做了大量研究，文献[1]中的TwigStack算法可以将整棵模式树一起匹配处理层次树，避免保存无用的中间结果，它对于只有祖先-后代边的模式树匹配是最优的论文网。文献[2]在TwigStack算法的基础上使用了XR-Tree索引，可以快速跳过输入序列中的无用结点，但这种索引不能减少连接次数。BLAS[3]中提出的P-label可以直接找出满足连续父亲-孩子边路径的XML结点，从而避免了一部分父亲-孩子边的连接，并减少需处理的结点数。它的缺点是没有利用更多的结构信息。总之，以上算法没有从根本上改进小枝查询的效率。
3基于层次树的小枝查询方法
3.1 XML数据结点编码
XML文档具有丰富的内容和灵活的半结构化特征，它能有效的支持复杂查询。XML文档可以表示为每个结点对应相应的元素，每条边表示父亲-孩子关系或祖先-子孙关系的树型结构。图3.1（a）给出了一个简单的XML文档树的实例，图3.1（b）给出了一个简单的树模式查询的实例。
数据结点编码对于树模式的查询效率起着非常关键的作用[3,4]，本节后面提出的小枝查询方法所使用的编码方案为EDiezt-P编码。EDiezt-P编码每个结点看作是一个三元组(DocId，StartPos:EndPos，Parent)，为了对问题进行适当的简化从而便于说明，这里我们先讨论单文档查询。图3.1（a）中的结点编码即为EDiezt-P编码。
|
|
|
|
（a） 基于EDiezt-P编码的文档树实例
|
（b）小枝查询实例
|
|
图3.1 XML数据结点编码和小枝查询
|
3.2 PathStack和TwigStack算法处理小枝查询的不足
PathStack算法，考虑路径查询//B/T//S和图3.1中的数据路径B1，B2，T2，B4，T3，S2层次树，S3。整个路径查询的处理是自顶向下遍历文档。首先每个查询结点E关联到对应的栈S[E]，如果一个元素和其父亲栈栈顶中的元素的关系满足查询的轴需要，那么这个元素就被压入栈中。一旦被压入栈的数据结点对应于路径模式查询q的叶结点，则栈链中应该包含了路径模式查询q的整体匹配结果。
虽然Bruno等人之后进一步提出了处理整枝查询的TwigStack算法，但对于父亲-孩子关系却不能达到最优[5]。我们需要一种有效的机制来对部分/整体的小枝结果进行编码，从而使得中间结果和查询处理代价达到最小化。一种较好的改进方法，不仅记录下不同的查询结点在文档元素中对应结果的祖先-后代关系，也同时记录下同一个查询结点对应到文档元素中的解的祖先－后代关系，从而使得中间结果最小化。
整枝查询时，对于不同的查询结点在文档元素中的解可以像PathStack一样通过明显的边来标识祖先-后代关系。但是对于对应于同一个查询结点的元素，如果通过分解为不同的路径进行查询，那么在文档树中的同一路径上那还可以像PathStack算法一样通过在同一栈中的前后位置关系来判断他们之间的结构关系，但是对于整个文档树查询来说就无法准确得知他们之间的关系。然而，对于文档树中对应于同一个查询结点的元素，我们发现它们自然的形成树型结构关系。例如图3.1中的B2,B3,B4都是满足小枝查询中的结点B的。这里B2是B3和B4的祖先，而B3和B4间没有祖先-后代关系。
基于这个发现，本文提出了把文档树中与相同的查询结点匹配的元素组织成层次结构从而来明显地得到它们之间的祖先－后代关系的方法。
3.3新的小枝查询算法TwigStack-HST
TwigStack-HST（Hiberarchy Stack Tree）算法的实质为给定一个文档元素e，如果它满足以查询结点E为根的子小枝查询，那么将其压入层次栈HS[E]。此时只有E的孩子查询结点M需要被检查，因为在HS[M]中的元素已经满足以M为根的子小枝查询论文网。最后，层次栈结构将通过MergeStack算法进行维护。
给定文档元素e层次树，如果E的孩子结点M已经满足所有的查询条件，那么我们将e压入HS[E]。由于采用后序遍历扫描，e的所有子孙元素必须已经被访问并压入HS[M]中。因此，通过合并HS[M]可以完成查询步骤E→M的检查。
假定在HS[M]中有n个栈树，这些栈树为ST1，ST2，…，STn，首先假设STi （i=1…n）任何一个都不是e的子孙。由于采用后序遍历的方式，因此e的整个子树已经被访问，故我们可以很安全的得出e不满足E。
其次，假定STp，…，STn(![]() )是e的子孙。STi.top是栈树STi 的根栈的栈顶元素。注意到如果顶栈不包含任何元素，那么STi.top可能为空。在这种情况下，（1）当查询步骤E→M是祖孙关系时，栈STp，…，STn中的所有的元素满足查询步骤。通过从e到STp.top，…，STn.top创建边来对这个查询步骤进行结果编码。这样的边暗示着STi.top和它的子孙栈中的元素是e的子孙；（2）当查询步骤E→M是父子关系时层次树，显而易见只有STp.top，…，STn.top可能是e的孩子。如果它们的Parent值与e的StartPos值相等，那么将创建e到这些栈顶元素的边。
最后，当这个查询检查步骤完成后，将通过创建一个新的根栈来对栈树STp，…，STn进行合并。栈树合并步骤的目的是减少进一步的查询处理代价，因为在余下的文档元素中只有新的根栈需要被考虑。检查该查询步骤的伪代码见合并栈算法MergeStack的8到13行。
新的小枝查询算法TwigStack-HST的伪代码如下：
|
Procedure TwigStack-HST (docElement e)
[1]. {
[2]. Stack hStack;
[3]. docElement cElement ;
[4]. WHILE （ hStack不空 && hStack.top不是e的祖先）
[5]. {
[6]. cElement= hStack.pop( );
[7]. FOR (每个将与cElement匹配的查询结点E)
[8]. NodeMatch(cElement,HS[E]);
[9]. }
[10]. hStack.push(e);
[11]. }
Procedure NodeMatch(docElement e,HierarchicalStack HS[E])
[1]. {
[2]. Boolean Success=true;
[3]. FOR（E的每个孩子查询结点M && Success）
[4]. Success= MergeStack(HS[M], e, axis(E→M));
[5]. IF Success
[6]. MergeStack(HS[E], e,””);
[7]. Push(HS[E], e);
[8]. }
|
Boolean MergeStack(HierarchicalStack HS[M], docElement e, Axis axis)
[1]. {
[2]. Success=false;
[3]. StackTreeSet STS=empty; //初始化时栈树集为空
[4]. FOR HS[M]中的每个栈树ST
[5]. { //以ST.EndPos递减的顺序访问
[6]. IF ST.EndPos <e.StartPos
[7]. Break; //不可能存在子孙关系，故不再需要访问其他的栈树
[8]. IF axis=PC && ST.top. Parent =e. StartPos //满足父亲-孩子关系
[9]. Success=true;
[10]. AddPCEdge(e,M,ST.top);
[11]. ELSE IF axis=AD
[12]. Success=true;
[13]. AddADEdge(e,M,ST.top);
[14]. STS=STS∪ST;
[15]. MergedSTCreate(STS);
[16]. Return Success;
[16]. }
[17]. }
|
3.4 TwigStack-HST算法复杂性分析
对于给定的小枝查询Q和XML文档D，算法TwigStack-HST的空间和时间复杂度都为O（|D|·|T|）,这里的|D|是文档中的元素数量，|T|是①②中的最大值。①T1=max（查询Q中具有相同标签的查询结点的数量）②T2=max（查询Q中具有相同标签的查询结点的总的孩子数量）。显然|T|<|Q|。
当查询有不同的标签时，TwigStack-HST算法有两个不同的代价：合并栈代价和检查一个查询结点的所有不同的分枝的代价。至于合并代价，假定在一个层次栈中有n个元素，很容易得到合并代价为O（n）。因为一旦栈树被合并，就不再需要考虑合并。当查询有不同的标签，总的合并代价为O（|D|）。分枝检查代价是由查询结点的最大扇出决定的。
4 实验分析
由于TwigStack算法是经典的整枝连接算法，实验将对本文提出的TwigStack-HST算法与TwigStack算法在查询处理时间上进行比较分析论文网。查询处理时间是指进行结构匹配所耗费的时间。对于TwigStack-HST算法，就是执行层次栈合并的时间。对于TwigStack算法是路径匹配和最后的对路径匹配进行合并连接的执行时间。
实验的XML文档来源于用XMark数据集，大小分别为50KB，100KB层次树，150KB。查询语句为：
q1:/site/open_auction[.//bidder/personref]//reserve；q2://people//person[.//address/zipcode]/profile/education；q3://item[location]/description//keyword;
实验时首先对每个算法都用不同的查询语句对大小为50KB的数据集进行查询，并记录下查询处理时间。得到TwigStack-HST算法与TwigStack算法的查询处理时间对比图如图4.1所示。
为说明数据集大小不同对算法查询时间的影响情况，对XMark数据集大小为50KB，100KB，150KB的 XMark数据集中进行比较。选用查询语句q1，得到的实验结果如图4.2所示。
从实验可知，对同样大小的XML文档，TwigStack-HST算法在查询处理时间上要远远好于TwigStack算法。随着文档的增大，算法的查询处理时间不断增大。但TwigStack-HST算法的查询处理时间总是少于TwigStack算法。为此，TwigStack-HST算法的查询处理时间较少。 查询效率较高。
|
|
|
图4.1 50KB数据集上查询处理时间比较
|
图4.2 3个不同大小数据集上查询处理时间比较
|
5 结论
对于XML结构查询，其中的一种方法是对XML文档树中的结点进行编码，编码方案能对结构连接查询方法产生重要的影响，为此本文提出了一种高灵活性的、支持多文档的、易确定结点对之间结构关系的EDiezt-P编码，并在此基础上提出了一种新型的基于层次栈的TwigStack-HST算法。实验表明，TwigStack算法比PathStack和TwigStack算法在一定程度上减少了查询处理时间，提高了查询效率。
参考文献
[1]Machdi, I., Amagasa, T., andKitagawa, H（2009）. XML datapartitioning strategies to improve parallelism in parallel holistic twig joins. In Proceedings of ICUIMC:471-480
[2]Andreas M. Weiner,TheoH?rder（2010）. An integrative approach to query optimizationin native XML database management systems. Proceedings of the FourteenthInternational Database Engineering & Applications Symposium :64-73
[3]Kyong-Ha Lee, Bongki Moon (2009).Bitmap indexes for relational XML twig query processing .Proceeding of the 18thACM conference on Information and knowledge management : 465-474.
[4]Yu Qunai.（2010）.Hierarchical Stack-Based Twig Query Algorithm of XML Data . Proceedings of the2010 International Forum on Information Technology and Applications: 263-266.
[5]陶世群,富丽贞.(2009).一种高效非归并XML小枝模式匹配算法.软件学报，2009,20(4)：795-803.
[6]王瑞，陶世群.(2009).一种基于有序对的含父子边的小枝模式匹配算法.计算机应用，2009,29(10)：2778-2780.
|
