基于素数标记的XML图可达性查询的评价

EgyptianInformatics Journal（2012）13，209开罗大学埃及信息学杂志www.elsevier.com/locate/eijwww.sciencedirect.com原创文章基于素数标记模式的有向无环XML图可达性查询的有效性评价Awny Sayeda，*，Mohammed Kayedb，Mayyada Hammoshica埃及Minia大学理学院b埃及Beni-Suef大学理学院c阿曼，Ibri，应用科学学院收稿日期：2011年6月29日;修订日期：2012年9月17日;接受日期：2012年2012年11月9日在线发布摘要许多模式标记方法被设计用来方便XML文档的查询。所提出的算法是基于这样一个事实，即模式标签是一系列广泛用于索引树、图或结构化XML图的技术然后，生成的标识符用于索引，作为对实际节点的引用，以便可以快速捕获节点之间的结构关系。在本文中，我们扩展了标记DAG XML图的素数模式标记算法。我们的主要贡献是基于强连接组件（SCC）原则，大大缩小了原始XML图的大小。使用整数标记DAG中的每个节点，该整数是与节点及其父标签相关联的素数的算术乘法。架构不依赖于生成树。因此，通过检查标签之间的可分性，可以有效地探索DAG中表示的包容层次结构。同时，它继承了其前身的动态更新能力和紧凑的尺寸特性.我们的理论分析和实验结果表明，生成的标记模式是一个有效的和可扩展的处理大型XML图上的可达性查询。©2012计算机和信息学院，开罗大学。由爱思唯尔公司制作和主持All rights reserved.1. 介绍*通讯作者。手机：+20 968 98838296。电子邮件地址：awny. cas.edu.om（A. Sayed）。开罗大学计算机和信息系负责同行审查。最近对XML、生物数据库、社会网络分析、语义Web、Web本体和许多其他新兴应用的兴趣已经引发了对图结构数据库（或简单的图）和相关问题（例如，查询处理和优化[1]）。可达性查询在图结构数据库中有着广泛的应用。例如，1110-8665© 2012计算机和信息学院，开罗大学。制作和主办Elsevier B.V.保留所有权利。http://dx.doi.org/10.1016/j.eij.2012.10.002关键词XML;标注模式;可达性查询;有向圈图210A. Sayed等人可达性查询问题。有两种替代的评估可达性查询的方法。第一种使用图遍历原理的方法的运行时间是O（|G|），其中|G|是图G的大小。在第二种方法中，可达性查询可以通过预编译底层图的传递闭包（TC）来评估。在最坏的情况下，运行时间与图的大小成二次方。很明显，如果底层图是一个具有许多循环的大图，如XML图，则这些方法不合格。在本文中，我们重点关注在解析过程中通过考虑链接（ID/IDREF、XLink和XPointer）来最小化多个循环的底层XML图。因此，作为这种最小化的结果，生成有向无环图（DAG）。采用了强连通分量（SCC）原理。然后，我们为DAG中的每个顶点分配一个标签。这个标签是基于素数的特征。所提出的标签将用于有效地确定祖先-后代关系“”或可达性查询“”、“祖先或自身”“后代或自身"”、“兄弟”“路径表达式。此外，DAG的模式标记的一个主要类别是生成树。首先，我们找到生成树，并根据树的边缘标记树中的每个节点。其次，提出了附加标签来记录通过非树边表示的关系。许多标记方法被提出来解决这个问题，例如基于区间的[2]和基于前缀的[3]标记。用这种方法生成的标签仍然有一些缺点。首先，非树边隐含的关系的评估不能利用确定性树标签特征的优势。第二，非树边需要额外的查询处理技术。此外，基于区间的方法遭受更新问题。两个Hop[4]和bit-vector[5]不关心生成树。最近，又提出了两种基于素数的方法[5]和[6]。这两种方法中的每个树节点都被赋予一个唯一的素数，并且节点由节点父节点的标签与节点素数的乘积作为标签。这些方法仍然受到更新问题的困扰。据我们所知，没有进一步的工作提出来扩展素数的想法与DAG XML图。我们的标签方法的主要组成部分（部分）可总结如下：将具有许多循环的底层大型xml图分解为具有少量顶点和边的DAG。为DAG中的每个顶点分配一个包含两部分的素数;第一部分包含自标签，第二部分包含顶点父标签。创建两个数据库表;第一个表用于存储有关SCC的信息，而第二个表用于存储有关标签的信息。为每个表构建B树索引以加快查询计算。将建议的模式与PLSD-FULL模式进行比较[7]根据效率和存储要求。本文的其余部分组织如下。第二节回顾了相关的工作。中讨论了SCC原则和提出的DAG素数标记模式第3款.大小估计和优化技术在第4节中给出。第5节说明了实验结果。最后，我们在第6节中总结并给出未来的工作2. 相关工作编号和标记方案主要用于避免为查询处理而对文档进行穷举遍历许多建议的标签都集中在树型（而不是图型）数据和简单路径表达式（如电影/导演/名字，其中必须将包含多个分支的分支解析为多个子查询;每个子查询对应于原始结构中的单个分支然后，这些子查询的结果必须通过昂贵的连接操作进行组合，以产生最终答案。这些方法不能有效地处理带有长路径的任意XML图上的带前缀（“//”）的祖先-后代2.1. 以树为中心的自然我们讨论的建议，促进编号和标签计划的祖先-后代查询的有效评估。XML模式标记已在[4，8，9]中提出。通过比较分配给XML树节点的标签，可以确定任意两个节点之间的关系。作者在[10，11]中提出了动态标签方案，其中节点继承其父标签作为其自己标签的前缀。可达性查询可以简单地通过检查两个节点的标签中是否存在前缀关系来确定。在[12]中，提出了一种嵌套循环连接算法，它要求输入元素集上有B+树索引。[13]中的建议也依赖于B+树，然而，它还要求元素集被排序。然后，不参与联接的那些元素将被删除。作者在[10，14]中描述了一种XML树的标记方案，该方案支持祖先查询的有效评估以及新节点的有效插入。在[15，16]中，提出了一种基于树2.2. Prefix schema节点的标签是其父标签和自己标签的拼接对于任意两个给定的节点u和v; u是v的祖先当且仅当label（u）是label（v）的前缀。有两种前缀方案：基于整数[10]和基于二进制字符串[11]。素数模式，Wu等人[5]提出了一种用素数标记XML树的新方法。节点的标签对于任意两个节点u和v;u是v的祖先当且仅当label（u）%label（v）=0;其中%是模运算符。2.3. 图中心性质与此同时，已经提出了几种方法来处理类似图的XML文档。例如，APEX索引[17]使用数据挖掘算法来总结查询工作负载中频繁出现的路径。它不保留从根节点开始的所有路径，而是只保留长度为2的路径。因此，它对于祖先-●●●●●基于素数标记模式的有向无环XML图可达性查询的有效性评估2112标题“）。许多其他方法依赖于结构化摘要以及存储的从这些摘要节点到数据节点的映射。这样的索引用于通过修剪搜索空间直接评估路径表达式。数据指南[18]仅限于简单的标签路径，并且在具有多个正则表达式的复杂路径查询中没有用处。 索引结构[19]在概念上类似于数据指南，因为它保留了从根元素开始的所有标签路径。它将每个XML元素的标签路径与数据值编码为字符串，并将编码后的标签路径和数据值插入到字符串的有效索引中。索引块和XML数据都存储在关系数据库系统中。索引结构丢失了所有的 与Index Fabric类似，F+ B Index[20]优化了一组分支查询。它基于向前和向后索引（F B索引[21]），并且与索引Fabric存在相同的问题。像1-index[22]，A（k）-index[23]和D（k）-index[24]这样的索引方案是基于节点的相似性和双相似性的概念。这些索引适用于文档内链接（ID和IDREF（S）类型）。但它们忽略了文档间的链接（XLink[25]和XPointer[26]的链接）。此外，已经提出了许多索引技术来优化树[5，27，28]，DAG图[7，29-32]和任意图[4，14，33，34]上的可达性查询在具有一定结构特征的图上，这种索引的性能得到了改善3. 标记有向无环XML图在讨论3.2节中的符号和模式标记方法之前，我们将在3.1节中展示如何使用强连接组件的思想将大型XML图压缩为小型DAG。3.1. 强连通分量（SCC）确定输入图的强连通分支的问题是一个一个常见的解决方案是基于两个深度优先遍历算法[35]。检测在SCC中，底层图被遍历两次。在第一次遍历中，即深度优先搜索，访问所有边以构建深度优先生成森林。一旦找到强连接组件的根（最顶端的节点），所有不是先前找到的组件的元素的后代都被标记为这些组件的元素。第二次遍历是通过一个“堆栈”来实现的在组件的根从堆栈中压入之前，根以下的所有节点都将从堆栈中移除。这些节点形成所讨论的组件。图1a描述了用于计算输入图G=（V，E）的强连通分量的算法。它由一个递归过程visit和主过程（SCC）组成，主过程以深度优先的被识别为SCC的组成部分的第一个节点被称为SCC的根。visit过程中的MIN操作（第5行）使用visit（）输入节点的顺序比较节点第10行的Comp操作用于区分属于同一组件的节点以及属于其他组件的节点。该过程的时间复杂度SCC是O（V+E），其中V是底层图中的节点集，E是边集。强连通分量的大小定义为它所包含的节点数。不包含在循环中的基础图的任何节点形成大小为1的SCC 从图 1 b很明显，（标题，电影，导演）将构建一个SCC。3.2. DAG的表示法和标记模式有向图G可以表示为G=（V，E），其中V表示节点的数量，E表示边的数量。对于G中任意两对节点u和u0，节点序列v0，v1， . . . ，vk≠v称为路，如果u=v0，u0=vk，且（vi-1，vi）对于i= 1，2，.. . ，k+1。底层-如果不存在起始于节点u且终止于同一节点的路径，则环图是有向无环图（DAG）。图1示出 来自电影数据库的XML图形表示。图1（a）SCC算法和（b）电影数据库示例（MDB）。212A. Sayed等人2定义1（SCC）。设G=（V，E）是一个有向图（有向图），G的一个强连通分支是G的一个极大顶点集CcV，使得对所有u，v2C，u，v和v，u，即u和v彼此之间是可达的。在换句话说，有向图的两个顶点在同一个分支中当且仅当它们彼此可达定义2（可分割财产）。如果一个整数A的素因子不是另一个整数B的素因子，则B不能被A整除。这个属性可以应用于图节点，使得对于具有标签L（u）和L（v）的DAG中的每两个节点u和v，节点u是节点v的祖先，当且仅当L（u）可被L（v）整除，否则，u不是v的祖先或者不存在可达性。定义3. 给定DAG G =（V，E），DAG的素数标记模式是为每个顶点v V分配一个素数P，并将标签L（v）与顶点v关联为：L（v）= P（v），其中P（v）是所有祖先的素数的乘积。定义4（图分解）。一个图G被分解为H中的图，如果边集E（G）可以被划分为子集，使得每个子集在H中导出一个图。H. 为了简单起见，我们说G有一个H-分解.图 2，每个顶点被赋予一个唯一的素数和它所有父节点的乘积的标签（根节点的标签是2）。这意味着每个标签是两个因子的乘积：第一个因子是基于素数标签模式分配给每个顶点的标签编号。第二部分是从父标签继承的数字。这种标记方法的一个优点是动态更新。使得插入一个新的顶点;很容易给出一个以前没有给出的素数作为插入节点的自标记。因此，无需重新贴标。定理1.设G=（V，E）是有向无圈图.对于任意两个给定的节点（u，v）eV和两个标签L（u）和L（v），图2 DAG图的素数标记模式两个节点u和v。如果L（u）mod L（v）=0，则节点u是节点v的祖先，或者两个节点之间存在路径。证据 这意味着分配给节点v的标签L（v）是分配给节点u的标签L（u）的因子。 现在假设u不是v的祖先。设pv是分配给节点v的唯一素数。当L（u）mod L（v）=0时，我们必须有L（u）mod pv=0。由于pv对于v是唯一的，并且在初始化步骤中它没有与u相关联，所以pv必须从作为u的子节点的节点v1之一传播。继续对v1和v进行同样的论证，pv必须是从v1的一个子节点v2传来的。继续同样的论证，我们得出结论，有一条从u到v的路径，因为没有v，数pv就不可能传播到u，这是一个矛盾。因此，它被证明。H定理2.如果节点u是节点v的祖先，则L（u）mod L（v）=0。证据我们通过归纳证明，与节点v相关联的标签L（v）将仅是与作为v的祖先的所有节点相关联的标签的因子。H根据定义1，节点v的任何父节点k只有在v进入L之后才会进入L。现在对于边（k，v），我们将计算N（k）=L.C.M（ N （ k） ， N（ v） ） 。 我 们 有 L（ Parent ）=L.C.M（N（Parent），N（Child）），即 L（父）modL（子）= 0。因此，L（k）mod L（v）= 0。假说. 设P是v的祖先集合。那么P中的所有节点都将包含与v相关联的唯一素数。迭代步骤：现在，任何节点m是P中任何节点p的父节点，必须具有L（m）mod L（p）=0。同样根据假设N（p）mod L（v）= 0，因此，L（m）mod L（v）= 0。因此，通过归纳得出的结果是正确的。4. 优化技术在本节中，我们讨论我们提出的标签模式的大小要求。这是因为存储大小和XML查询处理的性能之间有直接的影响。此外，我们的实验结果表明，SCC的想法减少了原始图的大小超过30%。在素数标记方案中，我们对XML树进行深度优先遍历，并为每个节点分配一个素数。4.1. 主标签标签所需的最大位数由XML文件中的节点总数决定。给定一个有N个节点的XML文件，我们使用hN来表示用于标记节点的最大素数。如果对应的XML图中的最大级别是D，则每个级别的节点标签所需的最大比特数由Dlog（hN）给出。我们假设两个数乘积的位长是两个数位长之和由素数的性质可知，对于一个整数N，小于等于N的素数个数为基于素数标记模式的有向无环XML图可达性查询的有效性评估213.. X.XN（1/log（N））。因此，第N个素数近似为Nlog（N），并且表示第N个素数所需的比特数为log（Nlog（N））。注意，使用log（Nlog（N））来预测第N个素数的二进制表示的长度的错误率是Nlog（N）和第N个实际素数之间的差因此，尽管在实际素数和估计素数之间的差异中存在波动，但误差率很小。图3显示了前10，000个实际素数的二进制表示长度与估计素数之间的差异。在最坏的情况下，素数标签gi的最大大小甚至到一个节点，是一个正整数na和nb，使得na·a=nb·b=m。例如，3和4的公倍数是0，12，24等。两个数字的最小公倍数是两个数字的倍数的最小数字（不为零）。例如，3的倍数是0，3，6，9，12，15，18，21，24，.4的倍数是0、4、8、12、16、20、24、28等。然后是LCM3和4这两个数字中的一个是12，24，等等。5. 实验结果5.1. 实验平台Lmax¼DlogD1/4菲！日志D1/4Fi！！实验在两种环境下进行。第一个实验是在Pentium IV-2GHz平台上进行的，具有Windows-XP和788 MB RAM。Oracle 9.2其中（F=扇出），D=XML文件的深度显然从上面的等式可以看出，它取决于XML文件的深度。作者在[5，36]中证明，真正的XML数据是低的，具有相对扇出，他们对200，000个XML文档进行了统计分析，发现这些文档中的99%具有少于8级的嵌套这也导致底层XMLDAG图的最大层数不会增加约8层。这导致存储XML图所需的大小很小4.2.最小公倍数在本节中，我们将介绍一种优化技术，以最小化每个节点的标签大小;我们的技术基于最小公倍数（LCM）。从图2中，我们注意到，在标签的第二部分（祖先标签）中存在冗余给定一系列S的素数是可用的（2，3，5，7，. . ），我们通过为DAG中的每个节点分配一个不同的素数来开始编号。现在，对于每个parent节点，我们根据以下规则分配编号。如果父节点P有许多子节点，比如C1，C2，并且与它们相关联的编号分别为N（C1），N（C2），则与P相关联的标签由下式给出：L（P）= LCM（N（C1），N（C2））。如果父节点P有一个子节点C1，子节点C1的编号为N（ C1 ） ， 则与 父节 点P 相关联的标号为L （ P ） = N（C1）。两个数a和b的最小公倍数，即LCM（a，b），是最小的数m，20181614121086420用作数据库服务器。第二个实验是在Pentium 1V-3 GHz平台上进行的，使用Linux Suse 9.1和3 GB RAM。IBM DB28.1用作数据库服务器和120 GB的单个硬盘我们的标签模式的所有策略都作为数据库应用程序（表集）实现，使用基于java的应用程序将信息存储到表中。我们将我们的标记方案与PLSD-FULL[7]进行了比较;比较基于空间要求和响应时间。此外，在实验中，XML的标签存储在一个关系数据库中的表结构（自标签，标签，父标签，URI），这是更类似于PLSD-Full结构。为了加快查询的计算速度，我们在自标签上建立B树，尽管索引是必要的。5.2. 数据集互联网电影数据库（IMDB）[37]是一个使用XML数据和链接的现实例子。这些数据的一般特征如下。IMDB的中心文件有一个电影列表，每个电影都有一个唯一的标识符。这些电影的演员与他们的角色在一个单独的文件中列出。所有的导演都在一个独立的文件中列出，还有一些重要的制片人，作家和摄影师。使用IMDB是因为它被认为是一个高度循环的数据库，可能会对路径索引算法造成压力。现在，从这些数据生成链接的XML文档。一小部分电影和所有人（演员、导演等）与这些电影相关联的是随机选择的。为每部电影生成一个XML文档，并添加到底层电影的演员和导演的XLink。所使用的数据库的部分围绕电影元素和出现在电影演职员表中的人的类别（例如，演员、导演、作曲家等）的元素来组织。以及关于电影的各种各样的信息。循环性的出现是因为每个电影元素被用作ID引用，并且具有指向在电影中表演的个人的指针，并且每个元素表示指向她或他表演的电影的个人指针。该数据集由40，211个节点和44，349条边组成，其中2718条是IDREF类型5.3. 空间要求0 100200300400500600700800900第N个质数图3估计的和实际的素数。首先，通过使用来自如上所述生成的集合的电影数据库的小片段来研究概念。这个小片段有1235个节点，1411条边，53个Xlinks，实素数估计d素数BIT上二进制表示的长度●●214A. Sayed等人表3测试查询。查询查询英文路径表达式我们提出的方案PLDS-full表1数据集描述。顶点数边缘数量#全球链接#内部链接循环次数最大循环中的节点数XML图1235141146130––DAG78286225552415表2不同节点的数据集描述。节点数#全球链接#内部链接循环次数循环中的节点数标签尺寸我们提出的方案PLSD-FULL250094141301540位49位320011020951546位55位500013719613218752位70位624016321014015255位85位710021339217419564位97位831228740121328669位110位953039247024236483位127位140120100806040200PLSD-全我们提出的方案2500 3200 5000 6240 7100 8312 9530数据集图4空间要求。Time（s）#结果时间#结果Q1找到一部电影的所有后代视频//\0.544081.21064Q2找到所有演员的后代演员//\0.616511.42011Q3查找所有具有其名称的title的后代动物本能（Animal Instinct） 0.210.31Q4根据某个导演的名字查找其所有后代导演0.211Q5查找铸造节点的所有后代铸造//\0.452091.1879Q6找到标识符8的所有后代8//\0.110.11Q7找到标识符100的所有后代100//\0.1110.161Q8找到标识符300的所有后代300//\0.210.281Q9找到标识符1000的所有后代1000//\0.210.21Q10找到标识符4000的所有后代4000//\0.3110.41123 IDREFS。然后，我们应用SCC原则;从原始XML图中删除循环。下面的小片段有24个周期。一个周期中的最大节点数为15个节点。结果是一个有782个节点和862条边的DAG。表1描述了这些信息。这意味着，基于SCC原理的优化技术，与原始XML图相比，DAG图的大小减少了30%以上。 减少节点数量将在以后减少标签的大小为了评估我们建议的标记模式的空间需求，我们定期增加底层XML片段的大小（见表2）。从表2和图4中，我们注意到我们提出的标签模式与PLSD-FULL模式相比，能够实现最大标签大小减少27%。主要原因是PLSD-Full使用了三个外部表来存储除生成树之外的附加信息;每个表需要一个独立的索引。第二个原因是我们的想法标签尺寸（BIT））基于素数标记模式的有向无环XML图可达性查询的有效性评估215基于在处理XML文件时创建XML的标签。但是，PLSD-Full会等待为非生成树创建其他表。5.4. 响应时间在这组实验中，我们使用表2中描述的电影数据库的子集来研究我们提出的标记模式对PLSD- full的查询性能。向数据库提交了十个路径表达式查询。表3显示了这10个路径表达式。前五个路径表达式测试节点名称的可达性，后五个路径表达式测试节点标识符的可达性。最后两列解释了使用我们建议的标签模式和PLSD- Full模式的每个路径表达式的执行时间。该表显示，通过仅查看SCC表，可以在线性时间内确定大约“30%”的可达性查询。此外，据观察，建议的标签模式提供了显着更好的性能比PLSD-Full。在测试可达性查询时，它比PLSD-Full模式好一个数量级以上还观察到，测试两个节点之间的可达性所需的执行时间取决于这些节点之间的距离。例如，执行路径查询6. 结论和今后的工作标签模式是一系列广泛用于索引树或图结构XML图的技术，它为树或图中的每个节点分配唯一的标识符。我们的主要目标是为DAG XML图设计标签模式，以允许任何两个给定的节点之间的快速可达性测试。这种标记模式是基于素数的思想，并与成分原理密切相关。此外，DAG上的操作，如祖先，后代和兄弟也可以很容易地覆盖。优化技术减少了空间需求和时间消耗。我们的标签模式可以应用于任何XML图。我们的实验结果表明，提出的标签模式DAG XML 需 要 更少 的 空 间 和 更少 的 建 设 时 间相 比 ，PLSD-全模式。其主要原因是，不需要存储额外的信息，为非生成树的边缘和利用的基本算术运算避免时间消耗的数据库操作。此外，对于具有许多链接的复杂XML集合，这种类型的标记是不有效的。引用[1] McHug J，Wisdom J. XML查询优化。在：Proceedings的第25届国际会议非常大的数据库（VLDB），爱丁堡，苏格兰;1999年。[2] Santoro N，Katib R.网络中的标记和隐式路由。Comput J1985;28（1）：5[3] O.C.L.中心Deweydecimalclassification;2009..[4] 科恩，霍尔珀林·埃兰，卡普兰·哈林，兹威克·乌里. 通过2跳标签的可达性和距离查询。在：会议记录第十三届年度ACM-SIAM离散算法研讨会。北京：人民出版社，2002. p. 937-46[5] 吴晓，李明，徐伟.一种用于动态有序XML树的素数标记方案。在：第20届国际数据工程会议（ICDE），波士顿，美国;2004年。[6] 赛义德·奥尼复杂XML集合可达性查询的素数标记方案。第四届印度国际人工智能会议（IICAI-09）; 2009年。[7] 吴刚，张阔，刘灿，李娟子。有向无环图的适应素数标记方案。DASFAA; 2006。p. 787-96[8] 李Q，Moon B.为XML数据建立索引和查询正则路径表达式。2001年第27届超大型数据库国际会议p. 361比70[9] Yoshikawa M，Amagasa T. XRel：一种使用关系数据库存储 和 检 索 XML 文 档 的 基 于 路 径 索 引 的 方 法 。 ACMTransactions on Internet Technology（TOIT），2001年。[10] Cohen E等人，Labeling dynamic XML trees。在：数据库原理研讨会（POSD）; 2002年。p. 271比81[11] 放大图片作者：Tatarinov SD，Zhang C.使用关系数据库系统存 储 和 查 询 有 序 XML 。 In ： ACM SIGMOD internationalconference on management of data; 2002.p. 204-15[12] Zhang C，Naughton JF，DeWitt DJ，Luo Q，Lohman G.关系数据库管理系统对包含查询的支持在：ACM SIGMOD数据管理国际会议;2001年。[13] Chein Shu-Yaho 等，Efficient structural joins on indexed XMLdocuments。2002年第28届超大型数据库国际会议（VLDB）[14] Kaplan H，Milo Tova，Shabo Ronen祖先查询的标记方案的比较 。 2002 年 ， 第 13 届 ACM-SIAM 离 散 算 法 研 讨 会（SODA）。p. 954-963。[15] 放大图片作者：J.短而简单的标签计划，用于小距离和其他功能。第七届国际算法和数据结构研讨会（WADS）;2001年。p. 246比57[16] 阿比特布尔祖先查询的紧凑标记方案。2001年，第12届ACM-SIAM离散算法研讨会（SODA）。p. 547-56[17] 郑C-W，闵J-K，沈K. APEX：一个XML数据的自适应路径索引。In：ACM SIGMD 2002，USA; 2002.[18] Goldman R，Widom J. DataGuides：在半结构化数据库中实现查询公式化和优化。In：Jarke M，Carey MJ，Dittrich KR，Lochovsky FH ， Loucopoulos P ， Jeusfeld MA ， editors.VLDB'97，第23届超大型数据库国际会议论文集，1997年8月25-29日，希腊雅典，Morgan Kaufmann; 1997。第436- 445页。[19] 库 珀 布 赖 恩 F ， 样 本 尼 尔 ， 富 兰 克 林 迈 克 尔 J ，HjaltasonGGilsliR ， 沙 蒙 摩 西 。 半 结 构 化 数 据 的 快 速 索引;VLDB 2001. 在：第27届超大型数据库国际会议的会议记 录 Morgan Kaufmann 2001 ， ISBN 1-55860-804-4; 2001年。[20] Kaushik R 等 . 覆 盖 分 支 路 径 查 询 的 索 引 2002 年 ACMSIGMOD数据管理国际会议。p. 133比44[21] Abiteboul S，Bunmen P，Suciu D. Web上的数据：从关系到半结构化数据和XML Los Atlos ，CA 94022，USA ：MorganKaufmann Publishers; 1999.[22] Milo T，Suciu D.路径表达式的索引结构。第七届国际数据库理论会议（ICDT），1999年。第277- 295页。[23] Kaushik R等.利用局部相似性为图结构数据中的路径建立第18届国际数据工程会议（ICDE）; 2002年。[24] Qun C et al.D（K）-Index：an adaptive structural summaryfor graph-based data. 2003年ACM SIGMOD数据管理国际会议。p. 134比44[25] XML链接语言（XLink）版本1.0，W3C推荐（2001年6月27日），请参见http://www.W3.org/TR/xlink>。216A. Sayed等人[26] XML指针语言（XPointer），W3C工作草案（2002年8月16日），参见http://www.w3.org/TR/xptr>。[27] Jiang H，Luz H，Wang W，Chin Ooi B. XR-tree：索引XML数据以实现有效的结构连接。ICDE; 2003年。[28] Dietz PF.维护链表中的顺序。In：STOC; 1982.第122- 127页。[29] Chen L，Gupta A，Kurul ME.有向无环图模式匹配的有效算法。见：ICDE; 2005年。p. 384-5[30] 陈L，Gupta A，Kurul ME.基于堆栈的模式匹配算法。见：VLDB; 2005年。p. 493-504.[31] 金荣，向英，阮南，王宏.有效地回答非常大的有向图上的可达性查询。见：SIGMOD; 2008年。p. 595-608[32] 安东灿朴锡XML数据的基于组的素数标记方案第十届IEEE国际会议计算机和信息技术，CIT 2010，英国西约克郡布拉德福德，2010年6月29日[33] Schenkel R等.HOPI：一个用于复杂XML文档集合的高效连接 索 引 2004 年 第 九 届 国 际 数 据 库 扩 展 技 术 会 议（EDBT）。p. 237比55[34] Sayed A，Unland R.对包含链接的XML文档的索引支持。IEEE Midwest Symposium on Circuits and System，2003。[35] Nuutila Esko， Soisalon-Soininen. 有效的传递闭包计算。技术，报告TKO-B113; 1993年。[36] Yoshikawa M，Amagasa T. XRel：一种使用关系数据库存储 和 检 索 XML 文 档 的 基 于 路 径 的 方 法 。 In ： ACMtransactions on internet technology（TOIT）; 2001.[37] Mondial 数 据 库 .