XML文件树状路径查询优化研究

1、XML文件树状途径查询优化研究摘要XL查询优化成为XL数据库研究热门，此中的布局毗连是其重要操纵。毗连挨次的选择是XL查询的焦点题目。本文提出在片断途径树的底子上，提出了一种毗连及组合途径表达式的计谋，该计谋是起首得到最优化途径序列，末了将最优化序列组合成完备的查询效果。关键词XL；查询优化；途径表达XQuery是由3订定的，其目的是提供一种查询语言，让利用者可以从XL文档中寻出所必要的资料。XQuery根本上包罗三个子句，在Fr语句中，利用者可以利用XPath指定所要依序处置惩罚的元素并将其设置给一个变量，here语句那么是可以对每个变量举行条件限定，而Return语句那么是可以指定所盼望返

2、回的元素及其格式。在XL查询中，可以将XPath转化为一棵树，称为查询树。从初始查询树开始，选择查询树中的某一条边，对该边上相毗连的两个结点做毗连，毗连的效果用一个新的结点表现，并取代原树中的两个结点。每次毗连时都市使结点淘汰一个，同时产生一个新的树。当树只包罗一个结点时，整个求解历程便竣事。在查询树中，可以将树中的结点分为五种范例，别离是：根节点(Rt)，叶节点(LN)，分支节点(GN)，孙子节点(DN)，孩子节点(N)。此中与通常环境差异的是，孙子节点是指在查询树中与其下一个节点为祖孙干系的节点。孩子节点是指在查询树中与下一个节点为父子干系的节点。将查询中必要返回的结点，界说为返回节点。界

3、说1：给定一个查询树QT(N，E)，及节点NiN，假设Ni为GN或LN或DN，那么将此节点称为GLDNde。界说2：给定一个查询树QT(N，E)，及QT中的一条途径P为EiNi.Ni+nEi+nNi+n+1，假设Ni与Ni+n+1为GLDNde或根节点，且对付全部的节点Nj属于Ni+1到Ni+n皆不为GLDNde或根节点，那么我们称EiNi.Ni+nEi+nNi+n+1为一个后置途径SuffixPath。界说3：给定一个查询树，由根节点开始向下拜候，假设走访的节点属于GLDNde，那么将其创立在片断途径树中，PT(N，E)，N是节点的聚集，E是边的聚集。对付每个niN都有一个TagNae，且n

4、i的范例只属于GN或LN或DN。对付每个eiE为“/，代表节点与节点之间的相邻干系为父子干系。称如许的树为片断途径树。界说4：假设A为SuffixPath的末了一个节点，那么XL文档中切合SuffixPath的文件所构成的聚集，称之为A的PartialData，记作Ap。界说5：在片断途径树FPT(FN，FE)中，假设NiFN且以Ni为起始点的途径P为EiNiEi+1Ni+1Ei+2Ei+nNi+n，假设Ni为叶节点或分支节点，Ni+n为最靠近Ni的根节点或分支节点，那么称途径P为一个片断途径，并以“Ni-Ni+n表现。图1所表现的是将XQueryTree拆分成SuffixPath，即“/a、

5、“/b、“/、“/d。图1环境1：假设我们“/b/、“/b/d、“/a/b组合文件，那么/b/的效果有(b1，1)、(b2，2)、(b3，3)共三种选择，其次切合“/b/d的有(b1，d1)一种选择，以是，没有对应文件的b2，b3会从b中删除。/a/b有一种选择。在此挨次下必要五次选择毗连。末了将其组合成末了效果，显然只有一种选择。以是根据如上方法一共做了六次选择毗连。环境2：假设创立的挨次为“/b/d、“/b/、“/a/b，根据环境1的阐发方法，得到3种选择，末了根据“/a/b、“/b/、“/b/d的方法组合只有一种选择。显然通过四次选择毗连就得到了末了效果。通过上例，可以看到差异的创立及组

6、合挨次对查询效果确有影响。这正是本文所研究的内容。本文所研究的要领是基于片断途径树的。根本框架为：起首寻到最优化的片断途径序列，然后根据PartialData创立切合片断途径布局的文档，末了得到具有完备布局的查询效果。本文根据文献1的要领得到片断途径树及树中每个节点所对应的PartialData。起首根据途径树及对应的PartialData举行最正确化处置惩罚。根本头脑是：根据起始点和中心点两种差异的范例节点举行拜候。PartialData大的先拜候大概小的先拜候。算法的终极目的是输出最正确片断途径序列。算法3.1funtin()输入：带有PartialData的片断途径树PT_TREE；st

7、artNde(PT_TREE)；/从根节点大概叶节点开始拜候set(PatatialData)；/设置拜候计谋，选择PartialData大的先拜候或小的先拜候startNde.ark()；/将起始点为标识下一个要拜候的节点fpList.reate()；/创立一个表用来存放已拜候结点fpSequene(ptiizatin(startNde，fpList，set)；/举行最优化处置惩罚输出：fpSequene；通过算法3.1可以得到最优化片断途径序列。那么此中的ptiizatin算法是怎样实现的呢，我们将在算法3.2给出详细求解历程。在树拜候历程中，会有遗漏的结点临时未被拜候，用单向链表link

8、List来存储这些节点。链表中每个节点的内容是两个指向途径树的指针，别离为urrentGTNde、PGNde，urrentGTNde指向当前节点，PGNde指向一个相邻的范例为GN的节点。算法3.2ptiizatin(startNde，fpList，set)输入：startNde，fpList，set；fpList.add(urrentNde)；/将当前节点放入fpList表中，并断定当前节点的环境if(父亲节点儿子节点都已拜候过)if(fpList.size()0)调解fpList，将fpList放入fpSequene中；if(linkList为空)输出fpSequene；else/将PGN

9、de放入表中，由于linkList中的节点是由于该节点而遗漏的，将PGNde/放入表中，表现是从该PGNde节点走向linkList中的节点的ptiizatin(urrentGTNde，fpList，set)；if(节点范例为DN)探求下一节点，递归ptiizatin(nextNde，fpList，set)；继承拜候下一节点nextNde；elsenextNde.set()；/设置下一节点拜候计谋探求邻近当前节点，且被遗漏拜候的节点；将临时遗漏节点安排在linkList中；/linkList的元素根据PartialData举行摆列ptiizatin(nextNde，fpList，set)；接下

10、来对得到的最优化片断途径序列举行处置惩罚，重要是对每一个节点的PartialData举行组合，创立切合片断途径布局的文档。假设有些片断无法匹配，将其删除。并将匹配效果存到FP_TABLE表中。创立片断途径的详细要领拜见参考文献1。下面根据FP_TABLE组合出完备的效果。在题目的提出那一节，我们清楚的看到，差异的组合效果，所必要的代价是差异的。因此，本文接纳组合挨次方法为由数目小的FP_TABLE到数目大的FP_TABLE。如容许以最大程度上淘汰组合代价。因此必要将得到的FP_TABLE举行由小到大的摆列。下面通过算法3.3探究详细组合历程。算法3.3输入：片断序列中第一个节点所构成的聚集FN

11、de；/缘故原由在于这些节点与FP_TABLE对应FNde.getIndex(0)；/获得第一个节点fr(该节点的FP_TABLE中每一笔切合的片断GT)FNde.urrentGT=GT；/保存第一笔GT记载，以便在递归调用时得到前次处置惩罚的记载假设必要返回效果，那么将效果放到效果表中；if(Fnde的比来的邻节点为根节点)Result=Rebine(Fnde，index，Result)；/index为节点编号，Result需返回的节点寻到一组切合的答案，将其参加到ResultTable中；/邻近的节点为GNelse获得上方邻近的GN获得在该节点的FP_TABLE中和urrentGT可以或许

12、组合的记载GTTable；对GTTable中的每一笔GT举行递归处置惩罚Result=Rebine(Fnde，index，Result)；继承探求下一节点，并针对FP_TABLE举行组合；/endfrRebine算法为组合片断途径，算法历程如下：算法：3.4输入：片断序列中第一个节点所构成的聚集FNde；假设全部途径都已处置惩罚完，那么返回处置惩罚效果；获得下一个需处置惩罚节点及与该节点在布局上比来的GN节点lastNde。if(lastNde为空)Rebine(Fnde，index，Result)；/对根节点递归处置惩罚Reset(FNde.urrentGT)；if(存在GN且GN.urre

13、ntGT尚未被拜候)获得GN节点FP_TABLE中和urrentGT可以或许组合的序列；针对这些记载举行递归处置惩罚；if(GN存在，但urrentGT已被拜候)获得该节点的FP_TABLE中和其上GN节点的urrentGT可以或许组合的序列；递归处置惩罚这些记载，并探求下一组合节点；小我私家盘算机作为实行的平台，其PU为Pentiu42.40GHz，内存为512B，接纳的操纵体系为irsftinds2000，接纳V+编程，对本文所接纳的最正确化计谋与文献1及穷举法举行比力。得到的实行效果是本文所接纳的计谋要快于文献1及穷举法。本文探究了最优化的组合计谋，包罗最正确化算法处置惩罚片断途径树及将所得到的途径序列举行最优化组合。进步了查询的服从，到达了查询优化的目的。将来可以对查询语句举行更准确的阐发，可以在无文档布局下快速寻到最正确处置惩罚计谋。2NingZhang，VarunKahlia，.Taerzsu，“ASuintPh