一种支持动态XML文档上关键字查询的索引结构

在关键字查询领域,目前提出的大多数索引结构主要考虑的是静态的XML文档.当XML文档出现频繁更新时,这些索引结构可能面临着大范围的重新编码,从而增加了数据库索引维护的代价.为了能在XML文档动态更新的环境下保持其索引结构的稳定,提出了一种支持动态XML文档上关键字查询的索引结构DLSS( DDE Level Structure Summary).该索引结构采用了一种针对动态更新改进的Dewey编码,该编码只需在文档更新时对新的节点赋予相应的编码,而不需要调整原有的编码结构.实验证明,DLSS索引结构可以在XML文档频繁更新或者较少更新时都能保持索引结构的相对稳定,并能在其上实现较高的关键字查询效率.     

基于扩展倒排索引的不确定XML关键字查询算法

现有的不确定XML关键字查询算法均需遍历不确定XML文档,并且算法在执行过程中需要频繁的字符串比较,造成时间浪费。针对上述问题,提出基于扩展倒排索引的不确定XML关键字查询算法Pr E。扩展倒排索引有效地存储了不确定XML文档中节点的相关信息,根据扩展倒排索引即可初始化动态哈希表和序号编码链表,并且Pr E算法在执行过程中利用整数的比较代替了字符串的比较。理论分析与实验结果表明,Pr E算法是一种高效的不确定XML关键字查询算法。     

一种新的基于Dewey编码的XML路径索引

建立高效的索引来快速定位满足要求的节点是提高XML数据查询效率的一个必要手段.文中以降低复杂度和提高查询效率为目标,以基于路径的XML索引原理为基础,提出了一种新型的基于Dewey编码的索引结构RTL-Index.RTL-Index通过对文档节点编码来表示结构信息,利用前缀路径匹配操作完成结构查询,支持含通配符" 和后代轴"//"的查询以及兄弟节点无序的模式树的查询.仿真实验结果表明RTL-Index索引具有较低的时间和空间复杂度,解决了XML文档分支路径查找问题,是一种较为有效的XML索引结构.     

基于Schema的XML混合编码索引查询技术

Web中存在着越来越多的XML的文档,如何高效地从XML文档查询出有效信息已经成为当前在半结构化数据研究领域中的热点问题。针对XML文档节点进行编码和建立索引结构可以有效地提高查询速度,提出一种SBXHCI(Schema-Based XML Hybrid Coding Indexing)查询技术,该方法充分利用Schema信息对XML文档进行编码和构建索引。对创建索引所花费的时间和空间,查询响应的时间进行大量的实验分析,结果表明SBXHCI方法的编码机制降低了索引结构在时间和空间的资源消耗,并且在路径查询的响应速度有着显著的提高。     

一种基于DTD的XML索引方法

路径查询是XML查询的一个主要特征,现已提出了多种XML索引方法．DTD的结构信息对于XML索引的建立及查询效率的提高很重要,但现有的大部分索引方法没有利用DTD这一有效资源,提出一种利用DTD的XML索引方法——DBXI(DTD-based XML indexing),该方法采用了新的编码方法,可使路径查询具备如下特征：对于由N个元素／属性组成的具有1个谓词约束的路径表达式,DBXI处理每个XML文档仅需0次或1次元素／属性结点集的结构连接操作;对于在XML文档中不存在匹配结构的路径查询,DBXI能够在比现有的XML索引方法较短的时间内给出无查询结果的判断．实验表明,与Lore,SphinX和XISS等索引方法相比,DBXI能够缩短路径查询的响应时间．     

基于F&B索引的XML查询处理算法

XML已成为信息交换和表示的标准.对XML数据的查询将返回满足特定约束的XML节点子集.对于大文件的XML数据的查询处理通常分为两步:1.为该XML数据建立一个索引;2.在索引上完成查询处理无需访问源文档.XML索引为查询处理提供了高效的帮助,其中F&B索引是已知的处理分枝查询最小的索引,但快速创建F&B索引和利用F&B索引完成查询处理的算法却很少有人研究.提出了一种素数序列标记法,这种标记法不仅有助于快速地建立F&B索引,更可以高效地完成F&B索引上的查询处理.此外,还给出了F&B索引上的区间标记法与CCPI的创建过程,这两种编码创建过程无需在建立F&B索引后二次创建,仅需与F&B索引创建过程一起对文档使用SAX解析器分析一次即可得到.这样,可以在F&B索引的区间标记法上使用TwigStack算法执行查询处理,在F&B索引的CCPI标记法上使用关联路径连接算法执行查询处理.还给出了基于素数序列标记法的查询处理算法,即素数整除匹配算法,该算法可以高效地判定某节点是否有某分枝子结构.实验表明基于素数序列标记法的F&B索引创建方法比SAM算法快,在多个数据集F&B索引上素数整除匹配算法优于关联路径连接算法和Twi...     

基于素数编码Schema的XML索引结构的研究

针对XML文档查询,提出了一种基于素数编码Schema的XML索引技术.该索引是对XML模式采用素数编码,对XML文档采用Li-Moon编码,这样在建立XML文档的节点索引时,也可对该节点的路径信息进行记录.在节点类索引的基础上,记录路径信息,既可以很好地支持正则路径表达式,同时又避免了节点类索引在处理长路径表达式时可能造成高昂的连接操作代价.实验结果表明,该索引的性能总体上要好于传统的节点类索引.     

基于结构摘要的XML关键字检索

基于最低最小公共祖先(SLCA)的XML关键字搜索语义,提出一种使用XML结构摘要(summary)对关键字进行索引的方法XKSS.XKSS索引方法通过避免重复存储大量XML树上的含义相同的节点,大幅度降低了索引的空间耗费,并提高了查询性能.基于XKSS建立的索引,提出一个算法SSB-SLCA来计算SLCA节点.实验表明,基于XKSS的关键字搜索方法能够更高效地寻找关键字的SLCA.     

一种基于XML结构索引的模式匹配改进算法

XML已经成为Internet上数据交换和数据集成的事实标准.随着XML的广泛应用,XML文档数量不断增多.如何高效地查询XML数据变得越来越重要.针对目前分支查询中普遍采用的基于堆栈的查询处理算法所存在的问题,提出了一种基于XML结构索引的模式匹配改进算法,通过选择合适的标签编码方式,利用XML结构索引,快速判断出元素之间的相互关系,防止大量不必要节点放入堆栈,从而提高查询处理效率.实验结果证明,文中改进的模式匹配算法Twig-Modify相比TwigStack以及TwigINLAB在查询处理的性能上有所提高     

面向XML文档检索的索引技术

XML文档的查询索引是当前研究的热点.该文探讨XML文档的索引技术,包括索引结构的设计等问题,给出了一个高效的XML索引方法,采用独特的编码方法,对XML文档及其遵循的DTD同时建立索引,有效支持内容和结构的双重检索;该方法结合了区间编码、倒排表和路径索引的思想,利用DTD结构信息来提高查询的效率.实验结果表明,本文提出的方法可以有效地降低建立XML数据索引的代价,能够缩短查询的响应时间.     

An adaptive path index for XML data using the query workload

Due to its flexibility, XML is becoming the de facto standard for exchanging and querying documents over the Web. Many XML query languages such as XQuery and XPath use label paths to traverse the irregularly structured XML data. Without a structural summary and efficient indexes, query processing can be quite inefficient due to an exhaustive traversal on XML data. To overcome the inefficiency, several path indexes have been proposed in the research community. Traditional indexes generally record all label paths from the root element in XML data and are constructed with the use of data only. Such path indexes may result in performance degradation due to large sizes and exhaustive navigations for partial matching path queries which start with the self-or-descendent axis(“//”). To improve the query performance, we propose an adaptive path index for XML data (termed APEX). APEX does not keep all paths starting from the root and utilizes frequently used paths on query workloads. APEX also has a nice property that it can be updated incrementally according to the changes of query workloads. Experimental results with synthetic and real-life data sets clearly confirm that APEX improves the query processing cost typically 2–69 times compared with the traditional indexes, with the performance gap increasing with the irregularity of XML data.     

一种高效的XML路径查询索引

XML文档的查询索引是当前研究的热点。提出一种高效的XML路径查询索引KDXI,首先对XML文档进行编码,然后建立结构索引并对结构索引进行编码。研究了基于KDXI索引结构的半结构连接算法和路径查询处理过程。通过KDXI索引机制,可以有效执行一般的路径查询语句,并避免冗余的结构连接操作。实验证明了KDXI索引机制的优越性。     

Adaptive Index Utilization in Memory-Resident Structural Joins

We consider adaptive index utilization as a fine-grained problem in autonomic databases in which an existing index is dynamically determined to be used or not in query processing. As a special case, we study this problem for structural joins, the core operator in XML query processing, in the main memory. We find that index utilization is beneficial for structural joins only under certain join selectivity and distribution of matching elements. Therefore, we propose adaptive algorithms to decide whether to use an index probe or a data scan for each step of matching during the processing of a structural join operator. Our adaptive algorithms are based on the history, the look-ahead information, or both. We have developed a cost model to facilitate this adaptation and have conducted experiments with both synthetic and real-world data sets. Our results show that adaptively utilizing indexes in a structural join improves the performance by taking advantage of both sequential scans and index probes.     

Secure XML querying based on authorization graphs

XML is rapidly emerging as a standard for data representation and exchange over the World Wide Web and an increasing amount of sensitive business data is processed in XML format. Therefore, it is critical to have control mechanisms to restrict a user to access only the parts of XML documents that she is authorized to access. In this paper, we propose the first DTD-based access control model that employs graph matching to analyze if an input query is fully acceptable, fully rejectable, or partially acceptable. In this way, there will be no further security overhead for the processing of fully acceptable and rejectable queries. For partially acceptable queries, we propose a graph-matching based authorization model for an optimized rewriting procedure in which a recursive query (query with descendant axis ‘//’) will be rewritten into an equivalent recursive one if possible and into a non-recursive one only if necessary, resulting queries that can fully take advantage of structural join based query optimization techniques. Moreover, we propose an index structure for XML element types to speed up the query rewriting procedure, a facility that is potentially useful for applications with large DTDs. Our performance study results showed that our algorithms armed with rewriting indexes are promising.     

Bayesian Networks for Knowledge-Based Authentication

We consider adaptive index utilization as a fine-grained problem in autonomic databases in which an existing index is dynamically determined to be used or not in query processing. As a special case, we study this problem for structural joins, the core operator in XML query processing, in the main memory. We find that index utilization is beneficial for structural joins only under certain join selectivity and distribution of matching elements. Therefore, we propose adaptive algorithms to decide whether to use an index probe or a data scan for each step of matching during the processing of a structural join operator. Our adaptive algorithms are based on the history, the look-ahead information, or both. We have developed a cost model to facilitate this adaptation and have conducted experiments with both synthetic and real-world data sets. Our results show that adaptively utilizing indexes in a structural join improves the performance by taking advantage of both sequential scans and index probes     

面向对象的XML查询系统的设计与实现

设计和开发了面向对象的XML数据查询系统原型OOX(object-oriented XML).OOX系统中包括了面向对象XML数据查询系统的一些核心功能,如存储、索引、查询等.其最大的特点是:它是一个可以实现对富含面向对象XML数据进行查询的XML查询系统;支持用继承扩展的XML模式语言DTD的解析,支持用继承扩展的XML查询语言XML-RL;采用了先进的路经仓索引模式以及高效的查询处理技术,可以实现高效的查询处理.     

A multiple-depth structural index for branching query

XML structural index, which acts as a schema, plays an important role in XML query optimization and formulation. To provide a reasonable structural index for branching path query under space constraint, we propose an adaptive index of multiple local branching depths and multiple local bisimilarities, which is constructed by maximizing marginal gain for given query load. It cannot only give good support to branching path queries but also have much smaller size compared with that of same sort of index. Detailed experiments have shown that the index is effective and efficient for XML branching path query.     

Clustered Chain Path Index for XML Document: Efficiently Processing Branch Queries

Branch query processing is a core operation of XML query processing. In recent years, a number of stack based twig join algorithms have been proposed to process twig queries based on tag stream index. However, in tag stream index, each element is labeled separately without considering the similarity among elements. Besides, algorithms based on tag stream index perform inefficiently on large document. This paper proposes a novel index, named Clustered Chain Path Index, based on a novel labeling scheme. This index provides efficient support for processing branch queries. It also has the same cardinality as 1-index against tree structured XML document. Based on CCPI, efficient algorithms, KMP-Match-Path and Related-Path-Segment-Join, are proposed to process queries efficiently. Analysis and experimental results show that proposed query processing algorithms based on CCPI outperform other algorithms and have good scalability. This paper is partially supported by Natural Science Foundation of Heilongjiang Province, Grant No. zjg03-05 and National Natural Science Foundation of China, Grant No. 60473075 and Key Program of the National Natural Science Foundation of China, Grant No. 60533110.     

Indexing XML documents for XPath query processing in external memory

Existing encoding schemes and index structures proposed for XML query processing primarily target the containment relationship, specifically the parent–child and ancestor–descendant relationship. The presence of preceding-sibling and following-sibling location steps in the XPath specification, which is the de facto query language for XML, makes the horizontal navigation, besides the vertical navigation, among nodes of XML documents a necessity for efficient evaluation of XML queries. Our work enhances the existing range-based and prefix-based encoding schemes such that all structural relationships between XML nodes can be determined from their codes alone. Furthermore, an external-memory index structure based on the traditional B+-tree, XL+-tree(XML Location+-tree), is introduced to index element sets such that all defined location steps in the XPath language, vertical and horizontal, top-down and bottom-up, can be processed efficiently. The XL+-trees under the range or prefix encoding scheme actually share the same structure; but various search operations upon them may be slightly different as a result of the richer information provided by the prefix encoding scheme. Finally, experiments are conducted to validate the efficiency of the XL+-tree approach. We compare the query performance of XL+-tree with that of R-tree, which is capable of handling comprehensive XPath location steps and has been empirically shown to outperform other indexing approaches.     

Secure query processing against encrypted XML data using Query-Aware Decryption

Dissemination of XML data on the internet could breach the privacy of data providers unless access to the disseminated XML data is carefully controlled. Recently, the methods using encryption have been proposed for such access control. However, in these methods, the performance of processing queries has not been addressed. A query processor cannot identify the contents of encrypted XML data unless the data are decrypted. This limitation incurs overhead of decrypting the parts of the XML data that would not contribute to the query result. In this paper, we propose the notion of Query-Aware Decryption for efficient processing of queries against encrypted XML data. Query-Aware Decryption allows us to decrypt only those parts that would contribute to the query result. For this purpose, we disseminate an encrypted XML index along with the encrypted XML data. This index, when decrypted, informs us where the query results are located in the encrypted XML data, thus preventing unnecessary decryption for other parts of the data. Since the size of this index is much smaller than that of the encrypted XML data, the cost of decrypting this index is negligible compared with that for unnecessary decryption of the data itself. The experimental results show that our method improves the performance of query processing by up to six times compared with those of existing methods. Finally, we formally prove that dissemination of the encrypted XML index does not compromise security.