基于扩展前缀编码的左孩子右兄弟结构连接算法

为了更加有效实现XML文档的结构查询,加强结构连接操作的效率,提出一种新结构连接算法.该算法采用扩展的前缀编码方案,在编码中增加了type、index等字段以利于定位树中结点在祖先结点列表或者后裔结点列表中的位置.该算法通过将XML文档树转换成左孩子右兄弟树,并定位树中一个祖先元素的起始点下标和终结点下标来找到该祖先元素的后裔结点列表.算法时间复杂度分析表明了该算法比现有算法的性能更好.     

有效支持XML结构化连接的索引——CATI

结构化连接的效率直接影响着XML查询的性能,目前对XML的结构化连接大多都是基于编码的方法.介绍了一种全新的有效支持XML结构化连接的树索引CATI(compact ancestor tree index)CATI的基本思想是,对于给定的一个祖先后代查询(A-D查询)或Twig查询,遍历XML文档,找出所有的祖先A的实例,用以建立CATI的主干;对于每个A实例,找出它的直接后代D的实例链接在它的后面.因为经典的结构连接算法Stack-Tree算法效率较高且使用较广,因此应用基于CATI的结构连接算法和基于Stack-Tree的结构连接算法就A-D查询和Twig查询做了大量实验.实验结果表明,基于CATI的结构化连接在一般查询情况下性能明显优于基于Stack-Tree的结构化连接.     

基于改进B+树索引的结构连接算法

基本的结构连接是XML数据库查询处理的一个核心操作。Stack_Tree_Desc_B＋算法能够有效地跳过不参加连接的后代,但跳过祖先的能力不强。通过对B＋树叶子结点的每一项增加了parent和nextNeighbour指针,该文提出了一种改进算法Stack_Tree_Desc_B＋_pn。改进算法不但具有较强的跳过后代的能力,而且具有较强的跳过祖先的能力。实验表明Stack_Tree_Desc_B＋_pn算法可以有效地减少I/O次数,具有更高的性能。     

基于扩展Dewey编码的XML结构连接算法

为有效实现XML文档查询,减少查询时结构连接的扫描代价,分析了基于归并思想的结构连接算法查询效率低的原因,充分利用XML数据的结构特点,提出了能够直接判断结点间结构关系的扩展Dewey编码,基于该编码的改进的Stack-Tree-Desc结构连接算法.应用扩展的Dewey编码,缩短了编码长度,降低了空间成本.改进的Stack-Tree-Desc算法引入二分查找快速跳过不需要参与连接的结点,减少了AList和DList列表中被扫描的结点数量,提高了查询效率.理论分析和实验结果表明了该编码方案以及结构连接算法的准确性和有效性.     

对左兄弟／右兄弟结构连接算法的研究与改进

结合区间编码和结点模型映射方法提出一种用于关系数据库的扩展存储模式。通过按结点编码中的广度遍历序号建立聚集索引，实现左兄弟／右兄弟关系结构连接算法的改进。改进后的算法降低了内存空间的开销，缩小了列表的扫描范围，明显提高了查找匹配速度，达到了查询优化的目的。     

对双亲／孩子结构连接算法的研究与改进

结合区间编码和结点模型映射方法提出一种用于关系数据库的扩展存储模式.通过按广度优先遍历XML树实现对双亲/孩子关系结构连接算法的改进.改进后的算法降低了内存空间的开销,缩小了列表的扫描范围,明显提高了查找匹配速度,达到了查询优化的目的.     

Native XML数据库的文档编码机制研究

Native XML数据库快速查询的实现,可以采用基于XML文档编码的结构连接算法。而结构连接算法的实现需要对XML文档进行编码,以便于快速判断XML文档树结点之间的祖先后裔关系。在对现有编码机制进行综述的前提下,提出一种新的XML文档编码机制——前缀整除编码（PDIV）机制。该机制编码形式简单,只需要一个正整数即可充分表示结点在XML文档树中的位置信息;可以实现祖先后裔关系的快速查询;支持XML文档的更新操作;编码长度较短,编码长度约为o（ln（n））。     

一种高效的XML多分支路径查询算法

目前XML单路径查询和简单的分支路径查询已经得到了较好的解决,但如何高效地实现XML多分支路径查询还没有很好的方法。提出一种高效的XML多分支查询算法MBPQ。算法MBPQ首先对XML文档和被查询的多分支路径结点分别按照各自不同的方式进行编码,并将被查询的多分支路径拆分成单路径,最后将单路径查询匹配成多分支查询结果。在单路径查询结果匹配过程中,算法MBPQ利用栈控制匹配过程,按照查询树从左到右、自底向上的顺序匹配具有共同祖先结点的单路径查询结果,从而提高匹配效率。实验表明,与现有的XML多分支查询一般算法相比,算法MBPQ的查询效率高。     

一种基于有序对的小枝模式匹配算法

随着半结构化的数据在信息交换中越来越重要,近年来,在XML数据库中,研究工作者提出了很多匹配小枝查询的算法.这些算法对仅含祖先后裔边的查询是很有效的,但是当查询中同时含祖先后裔和父子边时,以前算法仍可能产生大量中间结果,尤其是输入和输出的规模很大时.为避免中间结果的产生,提出了一种新的算法OPTwig,它是基于有序对的,通过查询树和文档树中结点有序对的匹配来进行查询,且不需要进行归并操作.结果表明,该算法优于以前算法.     

基于二分法的XML结构连接

在XML数据的查询处理过程中，基于区域划分的连接算法在处理XML数据无序和不存在索引时，是一个效率较高的算法。该文利用区域编码的特点对输入集合进行穷尽的递归划分，在划分的代价下，逐步定位祖先-后代的结构关系。使用二分法进行划分后，再完成结构连接，提高了结构连接的效率，实验表明该算法在XML数据的查询处理上是一个有效的方法。     

一种新的XML数据库的索引机制

XML文档的路径查询通常是节点间关系的判断,其中最主要的是祖先、子孙关系的判断。该文通过借鉴R树的构造特点提出了一种新的基于R树的XML数据库的索引机制,解决了快速判断XML文档中节点间祖先、子孙关系的问题。     

基于图数据库的在线族谱编录系统

针对目前国内族谱系统中数据共享度不高、扩展性不好、编录效率较低等问题,提出并实现了一种基于浏览器/服务器(B/S)架构和图数据库的在线族谱编录系统.首先,该系统采用B/S架构,支持多人在线协同录入,提高了数据录入效率;其次,系统使用数据库存储数据,便于集中管理和统计检索,提高了数据的共享程度;然后,考虑到族谱数据具有图的结构特性,在系统中采用图数据库进行管理,大大提高了数据处理效率;最后,使用真实族谱数据进行了系统的效率对比,验证了系统的有效性.在实验中,使用了约20万人的刘氏族谱数据,对关系数据库PostgreSQL和图数据库Neo4j管理数据进行了存储和查询的效率对比.实验结果表明,Neo4j比PostgreSQL节省约50%的存储空间,而在人物后代查询、人物祖先查询、人物亲缘关系查询以及人物后代性别统计4种常见查询中,使用Neo4j的平均响应时间约为基于PostgreSQL数据库的20%、80%、16%和15%.由此可知,基于图数据库的在线族谱编录系统可用于高效处理大量族谱数据,并且支持多用户在线协同编录.     

路径分区编码优化小枝查询

有效地存储查询XML文档已经成为当今数据库领域的研究热点。从XML文档的路径统计出发,提出了路径分区存储编码方案,并依此消除了小枝查询的后裔边和通配符。针对这类不含//和*的小枝查询,利用路径分区编码的特性,给出了基于结构约束节点的Twig查询算法,极大地减少了结构连接次数。实验表明,该算法能有效滤除无关元素,提高小枝查询效率。     

Fast Smallest Lowest Common Ancestor Computation Based on Stable Match

In this paper, we focus on efficient processing of XML keyword queries based on smallest lowest common ancestor (SLCA) semantics. For a given query Q with m Key words we propose to use stable matches as the basis for SLCA computation, where each stable match M consists of m nodes that belong to the m distinct keyword inverted lists of Q. M satisfies that no other lowest common ancestor (LCA) node of Q can be found to be located after the first node of M and be a descendant of the LCA of M, based on which the operation of locating a stable match can skip more useless nodes. We propose two stable match based algorithms for SLCA computation, i.e., BSLCA and HSLCA. BSLCA processes two keyword inverted lists each time from the shortest to the longest, while HSLCA processes all keyword inverted lists in a holistic way to avoid the problem of redundant computation invoked by BSLCA. Our extensive experimental results verify the performance advantages of our methods according to various evaluation metrics.     

一种具有多模态索引结构的XML查询算法

将编码方案、路径索引和名字外延思想相结合,提出一种针对XML数据检索的多模态索引结构.它既可支持结构连接计算,用以判断任意结点之间的子孙后代关系,也可支持基于名字外延的路径连接算法,用以判断任意结点之间的父子关系,同时可支持包含拥有关系的小枝查询;进而给出基于该结构的外延连接算法,使得对于长度为n的Xpath绝对路径查询,最多只需n/2-1次外延连接.实验结果表明,本文提出的索引结构可有效提高查询处理性能.     

A bi-labeling based XPath processing system

We present BLAS, a Bi-LAbeling based XPath processing System. BLAS uses two labeling schemes to speed up query processing: P-labeling for processing consecutive child (or parent) axis traversals, and D-labeling for processing descendant (or ancestor) axis traversals. XML data are stored in labeled form and indexed. Algorithms are presented for translating XPath queries to SQL expressions. BLAS reduces the number of joins in the SQL query translated from a given XPath query and reduces the number of disk accesses required to execute the SQL query compared with the traditional XPath processing using D-labeling alone. We also propose an approximate P-labeling scheme and the corresponding query translation algorithm to handle XML data trees that contain a large number of distinct tag names, and/or are very deep. This extension captures a spectrum of XPath-to-SQL query translation schemes, ranging from existing schemes that do not use P-labels to the one that uses exact P-labels. Experimental results demonstrate the efficiency of the BLAS system.     

DTD约束下的XML树模式查询最小化

目前大部分XML查询语言都使用树模式来匹配待查询的XML文档树以得到所需要的、与模式树相吻合的查询结果,此效率在很大程度上取决于XML模式树的大小,那么尽可能快速地查找并删除查询模式树中的冗余节点就变得十分重要。重点讨论DTD约束下树模式的最小化问题,将DTD兄弟约束SC拓展成扩展兄弟约束ESC,使其能够表达DTD约束中的祖先-后代关系;并指出只包含{ESC,/,//,[],*}的查询树模式的最小化问题的复杂度是指数级的,且当模式树是分支受限的时候,其最小化问题的复杂度是多项式时间的;最后给出了一个多项式时间的受限分支的模式树最小化算法。     

一种基于快照管理的非一致性分析法

从数据库的观点看，在执行单一查询前进行复制数据集是容易实现的，但查询处理器指派一次查询给那些没有充分操作和存储合适副本的结点时，从而引起在同步机制中副本快照经常过时和副本定位时带来昂贵的网络开销。本文将讨论一种在全局数据网格中多个结点的非一致性及快照管理的量化分析方法。