一种基于多模态索引结构的XML查询方法

摘要

本发明公开了一种基于多模态索引结构的XML查询方法。该方法将编码方案和名字外延的思想相结合，提出了一种包含类型索引集，名字索引集和外延索引的多模态XML索引结构，它既可支持结构联结计算，用以判断任意结点之间的祖先后代关系，也可支持基于名字外延的路径连接算法，用以判断任意结点之间的父子关系，同时可支持包含拥有关系的小枝查询；进而提出了基于该索引结构的外延连接算法，并通过对XPath查询表达式进行面向索引的查询路径分割，使得对于一条长度为n的XPath绝对路径查询，最多只需要n/2－1次外延连接，且能够根据双亲结构等信息利用外延索引尽可能跳过不需要参与连接的结点，从而提高了对XML数据的查询效率。

说明书

技术领域

本发明属于计算机设计与应用技术领域，涉及计算机软件、信息检索技术、半结构化数据处理技术、人工智能技术以及XML描述语言，特别涉及一种基于多模态索引结构的XML查询方法。

背景技术

可扩展标记语言-XML是Internet上一种新的数据表示、存储和交换标准。近年来，随着XML相关技术的迅速发展，网络上出现了越来越多的XML格式的数据。由于XML数据的嵌套结构和模式信息不全的特点，传统的基于树的遍历的方法不能满足在线用户的及时性查询要求，这对高效的查询XML数据查询提出了严峻的挑战。由此，使得XML数据的索引技术对XML查询处理起着至关重要的作用。

目前面向XML的查询语言有XQuery，XPath，XML-QL等等。其中基于XPath语言的查询表达式在实际中应用非常广泛。这些查询语言的共同特点是基于REP来查询XML数据。为了有效的支持针对REP的查询处理和优化，对XML数据的各种索引技术被提出，其中有代表性的XML索引结构大体上可分为两类：基于结构连接的索引和路径索引。然而，大多数文献针对它们设计的索引结构要么采用路径法，要么采用逐步结构联结对XML文档进行查询，没能将两种方法的优势和特定索引结构相结合用于判断元素结点之间的AD，PC和拥有(BR)关系。

针对基于多模态索引结构的XML查询方法，申请人经过查新，检索到与本发明紧密相关的专利1个，国内文献1篇，国外相关文献1篇：

(一)相关专利(名称、申请人或发明者)1个：

1.专利名称：一种基于XML数据的高效路径索引方法

专利申请人：复旦大学

(二)国内相关文献(标题、作者或机构、出处)1篇：

1.标题：基于DOM的XML数据库的索引技术研究

作者：贾福林，王国仁

出处：计算机研究与发展，2004，41(1)：176-186.

(三)国外相关文献(标题、作者或机构、出处)1篇：

1.Title：Indexing and Querying XML Data for Regular Path ExpressionsAuthor(s)：Li Q and Moon B.

Source：Proceedings of the 27^th International Conference on Very LargeDatabases.Rome.San Francisco：Morgan Kaufinaml Publishers，September11-14，2001：361-370.

对上述文献分析如下：

在专利1中，发明人提出了一种新型的XML路径索引-UD(k，1)索引，这是一种高效的近似索引结构，数据节点的归类根据其k长度的向上路经和1长度的向下路径。该索引全面的利用了XML数据节点的向上局部相似度和向下局部相似度的信息，所以能够用来高效的执行路径表达式，特别是用来执行分支路径表达式。

国内文献[1]中，贾福林等人提出了基于DOM的xml数据库的索引技术，该技术利用名字外延作为索引项的路径连接索引，引用索引和值索引来确定给定元素之间的父子关系，并通过使用基于名字外延的值索引来处理带有谓词的XPath查询，以很小的代价减少了连接操作的次数。然而，基于名字外延的索引系统很难判断给定元素结点间的AD关系，而且对于长XPath查询路径的处理由于需要较多的外延连接从而会降低索引查询的性能；

国外文献[1]中，Q.Li等人提出了3种索引结构：元素索引，属性索引和结构索引。通过元素索引可以找到所有具有相同元素名字的元素实例。通过属性索引可以找到具有相同属性名的属性实例。结构索引用来查找某一给定元素的父元素和子元素。然而，基于这种设计提出的快速确定XML文档层次结构中，祖先后代关系的编码机制很难从一般的祖先后代关系区分出父亲孩子关系，因此很难建立结构索引。祖先后代关系可以从父亲孩子关系演化而来，反之则不能。这将无法支持表示路径中父子关系的元素/元素的连接操作。同样，元素/属性间的连接操作也存在同样的问题。

发明内容

为了克服上述现有技术存在的缺陷或不足，本发明提供了一种基于多模态索引结构的XML查询方法，它既可以有效地支持结构连接的计算以快速地判断任意结点之间的子孙后代关系，也可以有效地支持基于名字外延的路径连接算法以快速地判断任意结点之间的父子关系，然后还可以快速地支持对包含拥有关系的小枝查询，使得对于一条长度为n的XPath绝对路径查询，最多只需要n/2-1次外延连接，从而有效提高了对XML数据的查询速度。

本发明的技术方案是这样实现的：

本发明中提出的一种基于多模态索引结构的XML查询方法主要由多模态XML索引构建，索引数据存储，查询路径分割和基于多模态XML索引的外延连接四个模块构成。多模态XML索引构建和索引数据存储模块负责多模态XML索引数据的生成和存储，在此基础之上，查询路径分割和基于多模态XML索引的外延连接模块进一步根据用户提出的XPath查询表达式，对生成的多模态XML索引数据进行有效查询。其中，多模态XML索引模块采用名字外延及区间编码的方法，建立了包含类型索引集，名字索引集和外延索引的多模态XML索引结构；索引数据存储模块采用关系数据库存储模式对多模态XML索引数据进行存储；查询路径分割模块根据多模态XML索引结构的特点，对XPath查询表达式实现了面向索引的查询路径分割，生成了索引查询表达式；基于多模态XML索引的外延连接模块根据索引查询表达式，采用基于多模态索引的外延连接算法MIEJ(Multi-Modal Index based ExtensionJoin)实现了对多模态XML索引数据的有效查询。

所述的多模态XML索引构建模块采用名字外延及区间编码的方法建立三级多模态XML索引体系结构的实现步骤如下：

1)对XML文档树中的所有元素结点，属性结点以及文本结点和属性值结点进行先序遍历，产生这些结点的先序遍历序号以及由它和它的兄弟结点，它的父结点以及其父结点的父结点构成的一条三元父子关系实例路径；

2)建立外延索引：外延索引由两部分构成：名字外延和局部路径外延，其中，名字外延由孩子结点名cName在XML文档树中对应的结点实例instanceID构成，主要包括：元素外延，属性外延，元素文本内容外延和属性值外延，局部路径外延则仅仅抓住XML文档树中一个结点的父结点唯一的特点，以孩子结点为导向，采用自底向上的方法建立三元父子(Parent-Child，PC)关系名字路径以及该路径所对应的实例路径；

3)根据外延索引中孩子结点实例cinstanceID类型进行聚类，从而形成以结点类型为入口项的四种类型索引集，包括元素索引集，属性索引集，文本内容索引集，属性索引集，结点实例cinstanceID类型对应XPath查询路径中查询结点的类型，可以是元素结点，属性结点，文本内容结点，属性值结点；

4)在类型索引集中，四种索引根据结点实例的名字进行聚类，从而形成多个以结点名为入口项的名字索引集。在每种类型索引集中都有指向不同名字索引集的指针，而名字索引集直接指向某一种类型的外延索引，如指向元素索引或属性索引等；

5)根据查询结点的类型找到对应的类型索引集是整个索引系统中的第一级索引；根据结点名找到对应的名字索引集，构成了整个索引系统中的第二级索引；最后，根据给定的查询路径找到相应的外延索引构成了整个索引系统中的第三级索引。至此，建立了从类型索引集到名字索引集，再从名字索引集到外延索引的三级索引系统。

索引数据存储模块将多模态XML索引数据按如下关系数据库模式进行存储：

名字列表Name(NameID，NodeType，DocName，Nodename)；

结点实例列表InstaCode(NameID，BeginNum，EndNum，LayerNum)；

三元PC关系名字列表PIR(APCID，aNameID，pNameID，cNameID)；

三元PC关系外延列表PIE(IID，APCID，aInstan，pInstan，cInstan)；

临时父连接实例列表TePaJoInst(IID，aInstance)；

临时子连接实例列表TeChJoInst(IID，cInstance)；

局部路径索引外延兄弟列表PIS(IID，SibNameID，SibInstan)。

在查询路径分割模块中，为了在查询算法中利用多模态索引来提高查询效率，根据多模态索引结构的特点，按如下步骤对RPE(Regular Path Expression，正则路径表达式)形式的XPath查询路径进行分割：

1)尽可能按两步长对XPath主路径进行分割；

2)将带有分支路径的查询结点，连同其分支分割为分支查询单元；

3)将祖先后代(Ancestor-Descendant，AD)关系查询所涉及的两结点分割为一个查询单元；

4)将分支查询单元按以上三步再嵌套分割；

5)根据查询单元所要采用的索引方式的不同，利用索引操作符LPE，NE，BR对经以上四步得到的查询单元进行标识，生成索引查询单元；

6)利用索引操作符将这些索引查询单元连接在一起，构成一条面向多模态索引结构的索引查询表达式。

在基于多模态XML索引的外延连接模块中按如下步骤对MIEJ算法进行了实现：

1)对XPath查询表达式QE进行面向索引的解析，将其转化成语义等价的由多个索引操作符相连接的索引表达式QE’；

2)令P为指向索引表达式QE’的字符串指针；

3)While(P！＝null)

4)指针P下移；

5)If(P遇到连续的字符串＝＝“LPE”)then

6)指针P继续下移，直到遇到“)”停止，提取“LPE(”和“)”之间的内容作为索引操作符LPE所标识的索引查询单元.

7)调用算法FindByLPE处理提取出的索引查询单元，并返回满足条件的结点实例对.

8)EndIf；

9)If(P遇到连续的字符串＝＝“NE”)then

10)指针P继续下移，直到遇到“)”停止，提取“NE(”和“)”之间的内容作为索引操作符NE所标识的索引查询单元.

11)调用算法FindByNE处理提取出的索引查询单元，并返回满足条件的结点实例对.

12)EndIf；

13)If(P遇到连续的字符串＝＝“BR”)then

14)指针P继续下移，直到遇到“)”停止，并提取“BR(”和“)”之间的内容作为索引操作符NE所标识的索引查询单元.

15)调用算法FindByBR处理提取出的索引查询单元，并返回满足条件的结点实例对.

16)EndIf；

17)EndWhile；

18)调用算法ResultJoin对以上每个索引查询单元的处理结果进行一致性连接.若执行结束后，存在结点实例作为连接结果，则返回1，否则返回0.

采用本发明，可实现一种基于XML文档的结构化查询系统。该系统可广泛应用于各种领域中基于XML文档格式描述的信息内容的结构化查询。在利用该系统进行查询时，事先需要利用多模态XML所引构建模块在离线状态下对XML文档集进行预处理，生成基于类型索引集，名字索引集和外延索引三层架构的多模态XML索引数据。其中，通过类型索引集和名字索引集，使得可根据查询结点的类型和标记名预先对XML文档进行有效过滤，进而通过外延索引，使得在面对XPath查询路径表达式所提出的PC关系，AD关系以及拥有关系的多种查询需求时，可动态地选取合适的索引结构来支持当前查询，从而达到整体查询性能的优化；通过建立的三元PC关系名字外延有效地降低了外延连接的次数，并且通过在三元PC关系名字外延中引入兄弟结点实例信息，使得只需对外延列表进行一次遍历就可解决双亲/孩子拥有关系的查询，从而达到局部查询性能的优化。当用户提出REP形式的Xpath查询表达式后，系统在查询路径分割模块和基于多模态XML索引的外延连接模块的支持下，既可有效地支持结构联结计算以快速地判断任意结点之间的祖先后代关系，也可有效地支持三元PC关系名字外延以判断任意三个结点之间的父子关系，然后还可支持对包含拥有关系的小枝查询。对于一条长度为n的XPath绝对路径查询，最多只需要n/2-1次外延连接就返回给用户和查询需求一致的查询结果文档，并且能够根据双亲结构信息等利用外延索引尽可能跳过不需要参与连接的结点，从而使多模态索引结构的特性在该算法中得到了充分的体现。

附图说明

图1为本发明组成结构图；

图2为多模态索引体系结构图；

图3为外延索引结构图；

图4为汽车外形XML文档树；

表1为查询路径分割实例；

下面结合附图对本发明的内容作进一步详细说明。

具体实施方式

图1中，首先利用XML文档解析器对XML文档集中的所有文档进行解析，生成在程序中可操作的文档对象树。在此基础上，通过对文档对象树的多次遍历，按照多模态索引结构，抽取需要的数据信息，建立包含类型索引集，名字索引集和外延索引的XML索引数据，并将其以索引关系表的形式存储于关系数据库中。接着，当收到索引查询请求后，由查询路径分割模块将传递进来的XPath查询路径转换为索引查询表达式，最后由基于多模态索引的外延连接模块利用索引查询表达式在已建立的索引关系表的基础上完成XML精确查询。

图2显示了包含外延索引，名字索引集和类型索引集的三层多模态XML索引体系结构。其中，外延索引包括元素外延索引，属性外延索引，元素文本内容外延索引和属性值外延索引；名字索引集包括元素名索引，属性名索引，元素文本内容索引和属性值索引；类型索引集包括元素索引集，属性索引集，元素文本内容索引集和属性值索引集。

图3显示了外延索引的组成结构。位于图3左边的列表框是结点名cName的名字外延列表，位于右边的列表框是结点名cName的局部路径外延列表。名字外延列表中的<InstanCode>代表一个名为cName的结点实例在一棵XML文档树中对应的区间编码；局部路径外延列表中，建立了cName在XML文档树中的三元PC关系名字外延组，每个组由cName的一个三元PC关系名字路径及其实例路径构成。如图中<aName1，pName1，cName>就是一个名字外延组中以cName为孩子的一个三元PC关系名字路径，其中包括当前的索引入口结点名cName，cName的一个父结点名pName1以及pName1的一个父结点名aName1，后面紧跟的(<instance0，instance1，instance2>...<instance17instance6，instance8>)则是名字路径<aName1，pName1，cName>在XML文档树中对应的所有实例路径，而<aName2，pName2，cName>是结点名cName在另一个组中的名字路径。

图4显示了一棵带有编码的汽车外形XML文档树，其中，空心圆结点代表XML文档中的元素，方形框结点代表属性，实心圆结点代表文本内容或属性值，结点框中的数字代表每个结点的前序编码。

基于多模态索引结构的XML查询方法的组成与工作原理：

如图1所示，基于多样性XML文档的近似查询方法主要由多模态XML索引构建，索引数据存储，查询路径分割和基于多模态索引的外延连接四个部分构成。为了更清楚地对各部分的组成及工作原理进行介绍，先定义如下几个概念：

定义1由XML文档按照特定的映射关系转化成的有向多叉树结构称为XML文档树，记为T_D＝(Node，Edge，label，type，root(T_D))。其中：

1)Node代表结点的集合，Node＝Node_EYNode_AYNode_T，其中，Node_E，Node_A，Node_T分别表示元素结点，属性结点和语词结点的集合；

2)Edge代表结点之间边的集合，满足：①v_i∈Node_E，v_j∈Node，若v_i是v_j的父元素，则(v_i，v_j)∈Edge；②v_i∈Node_A，v_j∈Node_T，若v_i是v_j的父元素，则(v_i，v_j)∈Edge；③Edge＝Edge_EYEdge_AYEdge_T，其中，Edge_E，Edge_A，Edge_T分别表示从元素结点指向子元素结点的元素边，指向属性结点的属性边，指向语词结点的语词边；

3)映射label：Node→string，给每个结点赋予一个字符串，满足：①若v_i∈Node_E，则label(v_i)代表元素的标记名；②若v_i∈Node_A，则label(v_i)代表属性名；③v_i∈Node_T，则label(v_i)代表语词(字符串值)；

4)映射type：Node→{E，A，T}，给每个结点赋予结点类型，包括元素类型E，属性类型A和语词类型T等等。对于任意结点v_i∈Node，如果type(v_i)E，v_i称为元素结点，如果type(v_i)＝A，v_i称为属性结点，如果type(v_i)＝T，v称为语词结点；

5)root(T_D)代表T_D的根。

如图4所示的XML文档树中的每个结点实例具有唯一标识号，一般情况下，它是通过对XML文档树中结点进行先序遍历产生的，记为instanceID。由于结点标识号和结点实例是一一对应的，为了描述的方便，根据XML文档树中结点类型的不同，分别用einstanceID，ainstanceID，tinstanceID和vinstanceID来标识XML文档树中的元素结点，属性结点，文本内容结点和属性值结点实例。

定义2元素外延(element extension)，记为EE(eName)，表示T_D中具有相同元素名eName的结点实例einstanID所组成的集合，其中eName是DTD中定义的元素名字(tagname)。

类似的，可定义属性外延AE(aName)，元素文本外延TE(eText)和属性值外延VE(aValue)。

定义3三元父子关系实例路径(instance path)，记作IP＝<ainstanceID，pinstanceID，cinstanceID>，表示T_D中由结点标识构成的三元结点实例对。其中，pinstanceID是cinstanceID的父结点，ainstanceID是pinstanceID的父结点，ainstanceID是cinstanceID的祖先结点。如图4中的<1，3，4>和<10，11，12>。

IP中包含两对父子关系<ainstanceID，pinstanceID>，<pinstanceID，cinstanceID>和一对祖先后代关系<ainstanceID，cinstanceID>。它们均可以代表四种不同类型结点之间的父子或祖先后代关系：元素和子元素，元素和属性，元素和文本内容，属性和属性值，其中ainstanceID可以代表元素结点实例，pinstanceID可以代表元素或属性结点实例，cinstanceID可以代表所有类型的结点实例。例如图4中的<1，3>，<1，7>，<3，4>和<1，8>。

定义4三元父子关系名字路径(name path)，记作Np＝<aName，pName，cName>，它表示T_D中由结点标记名构成的三元结点名字对。其中，aName代表元素名，是pName结点的父亲结点名；pName代表元素名或属性名，是cName结点的父亲结点名；cName代表元素名，属性名，元素文本内容或属性值，是底层孩子结点名。

在XML文档树中一条名字路径可对应多条实例路径。

定义5三元父子关系名字外延(triple name extension)，记作TNE(NP)＝{IP}，它表示XML文档树中和名字路径NP＝<aName，pName，cName>对应的所有实例路径IP＝<ainstanceID，pinstanceID，cinstanceID>的集合。其中，ainstanceID对应元素名aName，pinstanceID对应元素或属性名pName，cinstanceID对应的结点名cName。

如图4中，TNE(Car，Parts，Wheel)＝{<1，9，10>}。如果aName为空，形如TNE(&，pName，cName)则表示二元PC关系名字外延，是所有名字路径为<pName，cName>的二元PC关系实例路径构成的集合。如图4中，TNE(&，Car，Type)＝{<1，5>}。

多模态XML索引构建

总体索引结构

在索引系统中设计了四种类型索引：元素索引、属性索引、元素文本内容索引和属性值索引来支持不同XPath路径的查询需求。例如，元素/子元素，元素/属性，元素/文本内容，属性/属性值之间代表不同语义的父子关系，祖先后代关系和拥有关系。利用元素索引和属性索引可实现对查询条件中结构关系的判断，利用属性值索引和元素文本内容索引可实现对查询条件中查询内容的判断。四种索引的入口项各不相同，但索引值都是IP或者instanceID的集合。每种索引均由两部分构成：名字外延和局部路径外延，统称为外延索引。其中，名字外延由cName在XML文档树中对应的结点实例构成，主要包括：元素外延，属性外延，元素文本内容外延和属性值外延。局部路径外延则仅仅抓住XML文档中一个结点的父结点唯一，以子结点为导向，采用自底向上的方法建立三元PC关系名字路径以及该路径所对应的实例路径构成。

四种索引根据索引值IP中的孩子结点实例cinstanceID类型进行聚类，从而形成了以结点类型为入口项的四种类型索引集，包括元素索引集，属性索引集，文本内容索引集，属性索引集。结点实例cinstanceID类型对应XPath查询路径中查询结点的类型，可以是元素结点，属性结点，文本内容结点，属性值结点。根据查询结点的类型找到对应的类型索引集是整个索引系统中的第一级索引；

接着，在类型索引集中，四种索引根据结点实例instanceID的名字进行聚类，从而形成多个以结点名为入口项的名字索引集。在每种类型索引集中都有指向不同名字索引集的指针，而名字索引集直接指向某一种类型的外延索引，如指向元素索引或属性索引等。根据结点名找到对应的名字索引集，构成了整个索引系统中的第二级索引。

最后，根据给定的查询路径找到相应的外延索引构成了整个索引系统中的第三级索引。至此，建立了从类型索引集到名字索引集，再从名字索引集到外延索引的三级索引系统，其总体结构如图2所示。

外延索引结构

在图2中，外延索引位于多模态索引体系结构的第三级，其组成结构如图3所示。位于图3左边的列表框是结点名cName的名字外延列表，位于右边的列表框是结点名cName的局部路径外延列表。名字外延列表中的<InstanCode>代表一个名为cName的结点实例在一个XML文档树中对应的区间编码，比如Zhang编码；局部路径外延列表中建立了cName在XML文档树中的三元PC关系名字外延组，每个组由cName的一个三元PC关系名字路径及其实例路径构成。如图3中<aName1，pName1，cName>就是一个名字外延组中以cName为孩子的一个三元PC关系名字路径，其中包括当前的索引入口结点名cName，cName的一个父结点名pName1以及pName1的一个父结点名aName1，后面紧跟的(<instance0，instance1，instance2>...<instance17instance6，instance8>)则是名字路径<aName1，pName1，cName>在XML文档树中对应的所有实例路径，而<aName2，pName2，cName>是结点名cName在另一个组中的名字路径。

在XPath中，有一类特殊的查询需求，即包含拥有关系的小枝查询。为支持拥有关系，将索引入口结点名cName在XML文档中所对应的每个结点实例的兄弟结点也纳入到局部路径外延列表中，如：<aName，pName，cName>＝(<instance0，instance1，instance2(@name:instance20；”name”:instance21；name:instance22)>)，其中instance2是cName所对应的一个符合三元PC关系的结点实例，(@name: instance20；”name”:instance21；name:instance22)包含了instance2的所有兄弟结点实例信息，@name代表instance2的属性兄弟结点名，“name”代表instance2的值兄弟结点名，name代表instance2的元素兄弟结点名，而instance20，instance21和instance22分别是这些兄弟结点名在XML文档树中所对应的结点实例。通过兄弟结点关系的纳入，使得对拥有关系地判断变得非常方便。

索引数据存储

为了更为方便的将多模态索引结构的应用于随后的查询算法实现中，根据其索引结构特点设计了如下的关系数据库存储模式：

名字列表Name(NameID，NodeType，DocName，Nodename)：用来存放XML文档树的结点名称及类型。其中DocName代表结点所在的XML文档的名称；NodeName代表结点名；NodeType代表结点类型；NameID是名字的唯一标识号，也是该表的主键；

结点实例列表InstaCode(NameID，BeginNum，EndNum，LayerNum)：用来存放XML文档树中任意结点名所对应的实例编码。其中BeginNum，EndNum，LayerNum分别是实例结点的前序遍历号，二次访问遍历号和当前层号；NameID和BeginNum一起作为该表的主键。

三元PC关系名字列表PIR(APCID，aNameID，pNameID，cNameID)：用来存放XML文档树中的两元或三元PC关系的名字路径，其中aNameID，pNameID，cNameID代表名字路径上的结点名在名字列表中对应的nameID，cNameID字段在列表元组中可重复，APCID是名字路径的唯一标识号，也是该表的主键。

三元PC关系外延列表PIE(IID，APCID，aInstan，pInstan，cInstan)：用来存放三元PC关系名字路径在XML文档中对应的实例路径，其中IID是每条实例路径的唯一标识号，它也是该表的主键；aInstan，pInstan和cInstan是实例路径上每个结点的前序遍历号。

临时父连接实例列表TePaJoInst(IID，aInstance)：用于存放查询过程中符合条件的索引查询单元之间的连接部分的aName的结点实例，其中aInstance代表aName对应的实例结点的前序遍历号。

临时子连接实例列表TeChJoInst(IID，cInstance)：用于存放查询过程中符合条件的索引查询单元间的连接部分的cName的结点实例，其中cInstance代表cName对应的实例结点的前序遍历号。

局部路径索引外延兄弟列表PIS(IID，SibNameID，SibInstan)：用来存放三元PC关系外延中，cName结点在XML文档树中对应的兄弟结点实例。其中SibNameID代表cName结点的兄弟结点名字ID，SibInstan代表兄弟结点实例的前序遍历号。

查询路径分割

定义6(索引查询单元)给定一条RPE形式的XPath查询路径，按查询路径分割方法对其进行解析后得到的查询单元称为索引查询单元。

根据索引查询单元所采用的索引方式的不同，设计了在查询路径分割过程中所用到的几种索引操作符，如下所示：

LPE：局部路径外延索引操作符，用来标识需用局部路径索引来处理的索引查询单元，该索引查询单元中只包含PC关系；

NE：名字外延索引操作符，用来标识需要用名字外延列表来处理的索引查询单元，该索引查询单元中只包含AD关系；

BR：拥有关系索引操作符，用来标识需要局部路径外延列表和名字外延列表相结合来处理的索引查询单元，该索引查询单元只包含拥有关系，它进一步可细分为：

BR_LPE：只需用局部路径索引来处理拥有关系的索引操作符；

BR_NE：只需用名字外延列表来处理拥有关系的索引操作符。

进一步，根据索引结点类型的不同，以上的索引操作符又可以细分为：

元素索引结点：E_LPE，E_NE，E_BR_LPE，E_BR_NE(缺省情况下默认为LPE，NE，BR_LPE，BR_NE)；

属性索引结点：A_LPE，A_NE，A_BR_LPE，A_BR_NE；

元素文本内容索引结点：C_LPE，C_NE，C_BR_LPE，C_BR_NE；

属性值索引结点：V_LPE，V_NE，V_BR_LPE，V_BR_NE。

根据查询路径分割方法和索引操作符对几组RPE形式的XPath查询路径的分割实例如表1所示。

表1

    查询路径分割结果    a/b/c/“d”    a/b/c/@d/“e”    a/b/c/d/e/@f    a/b/c[d，@e]/f    a/b/c//d/e/f    a/b/c//d/e[f，@g]/hE_LPE(a，b，c)，C_LPE(c，“d”)E_LPE(a，b，c)，V_LPE(c，@d，“e”)E_LPE(a，b，c)，E_LPE(c，d，e)，A_LPE(e，@f)E_LPE(a，b，c)，BR([d，@e]，c)，E_LPE(c，f)E_LPE(a，b，c)，NE(c，d)，E_LPE(d，e，f)E_LPE(a，b，c)，NE(c，d)，E_LPE(d，e，h)，BR([f，@g]，e)

分割完成后，利用以上几种索引操作符将这些索引查询单元重新连接在一起，从而构成一条面向多模态索引结构的索引查询表达式，其定义如下：

定义7(索引查询表达式)给定一条RPE形式XPath查询路径表达式，由多个索引查询单元连接而成的和其查询语义等价的表达式称为索引查询表达式，简称为索引表达式。如表1中的查询路径“a/b/c//d/e[f，@g]/h”对应的索引表达式为E_LPE(a，b，c)&NE(c，d)&E_LPE(d，e，h)&BR([f，@g]，e)。基于多模态索引结构的外延连接

在基于多模态索引的外延连接算法(Multi-Modal Index based ExtensionJoin，MIEJ)中调用到的五种算法的实现步骤分别如下：

FindByLPE算法：

输入：索引操作符LPE标识的索引查询单元(aName，pName，cName)

输出：满足结构条件aName/pName/cName的所有结点实例对

1)孩子结点名cName的类型选择合适的类型索引集；

2)利用结点名cName从类型索引集中找到其对应的名字索引集；

3)从名字索引集中定位到cName对应的局部路径外延列表，即结点名cName在索引关系数据库中对应的关系表；

4)利用关系表PIR和结点名cName查找三元PC关系名字路径<aName，pName，cName>对应的PCID号；

5)利用关系表PIR和PIE以及第四步得到的PCID号，进一步查找存在于PIE表中中满足结构关系aName/pName/cName的所有结点实例对，并将其作为结果返回。

FindByBR算法：

输入：索引操作符BR标识的索引查询单元([condition]，aName)输出：满足拥有条件condition的结点名aName对应的所有结点实例

1)令指针P是指向输入字符串condition的指针；

//拥有条件condition的形式如：(//b，c，@d，//e，“f”)

2)While(P！＝NULL)

3)If(P遇到连续字符＝＝“//”)then

4)指针P下移，提取“，”间带有前缀“//”的结点名cName，并和目标结点名aName构成索引操作符BR_NE标识的子索引查询单元BR_NE(aName，cName)，同时利用算法FindByNE处理该子索引查询单元，返回满足aName//cName关系的目标结点名aName对应的所有结点实例.

5)Else

6)指针P下移，记录“，”间没带有前缀“//”的结点名，形成孩子结点名串childNameString.

//childNameString形如：c，@d，“f”

7)EndIf；

8)EndWhile；

9)将孩子结点名串childNameString和目标结点名aName构成索引操作符BR标识的子索引查询单元([childNameString]，aName)，同时利用算法FindBySubBR处理该子索引查询单元，返回满足childNameString条件的目标结点名aName对应的所有实例；

10)将同时出现在算法FindByAD和算法FindBySubBR处理结果中的

目标结点名aName对应的结点实例作为最终结果返回.

FindBySubBR算法：

输入：BR标识的索引查询单元([childNameString]，aName)输出：满足childNameString拥有条件的目标结点名aName对应的所有结点实例

1)令指针P是指向输入字符串childNameString的指针；

2)While(P！＝NULL)

3)If(P遇到childNameString中的第一个孩子结点名)then

4)保存该孩子结点名cName于字符串变量FirstName.

5)Else

6)累记剩下的孩子结点名作为cName的兄弟结点保存于字符串变量sName.

7)EndIf；

8)指针P下移；

9)EndWhile；

10)根据变量FirstName中的孩子结点类型选择合适的类型索引集；

11)根据变量FirstName中的孩子结点名从类型索引集中找到对应的名字索引集；

12)从名字索引集中定位到该结点名对应的局部路径外延列表，即结点名cName在索引关系数据库中对应的关系表；

13)利用关系表PIR和结点名cName查找两元PC关系名字路径<aName，cName>对应的PCID号；

14)利用关系表PIR和PIE以及第11步得到的PCID号，进一步查找存在于PIE表中满足结构关系aName/cName的结点实例的IID号；

15)利用字符串变量sName以及第12步得到的IID号到关系表PIS中进行匹配查找，若匹配成功，利用匹配元组所在的IID号再到关系表PIE中查找目标结点名aName对应的结点实例作为结果返回。

FindByNE算法：

输入：索引操作符NE所标识的索引查询单元(aName，cName)输出：满足结构关系aName//cName的所有结点实例对

1)由结点名aName的类型选择合适的类型索引集；

2)依据结点名aName从类型索引集中找到对应的名字索引集；

3)从名字索引集中定位到该结点名对应的局部路径外延列表，即结点名aName在索引关系数据库中对应的关系表；

4)在关系表InstCode中查找结点名aName对应的所有结点实例及其编码；

5)对结点名cName重复1～4步；

6)调用结构化连接算法Structure Join来确定存在于结点名aName和cName的结点实例中满足aName//cName关系的结点实例对，并将这些结点实例对作为结果返回。

ResultJoin算法：

输入：多模态索引表达式中第一对相临索引查询单元的查询结果：两组结点实例对A和D

输出：满足XPath查询表达式的目标查询结点名所对应的结点实例

1)将两组结点实例A和D对分别输入到关系表TePaJoInst和TeChJoInst；

2)对关系表TePaJoInst和TeChJoInst执行连接操作，若连接结果为空，则返回0，并终止该算法，否则执行下一步；

3)清空关系表TePaJoInst，将上一步得到的结点实例对输入到关系表TePaJoInst中；

4)若已处理完最后一个索引查询单元，则转步5；否则清空关系表TeChJoInst，将下一个索引查询单元的查询结果输入到关系表TeChJoInst中，并转步2；

5)将保存于关系表TePaJoInst中的目标结点实例作为结果返回。