一种XML数据流小枝模式查询算法

针对传统XML文档小枝模式查询算法系统开销大的问题,提出一种XML数据流小枝模式查询算法。该算法结合SAX数据流解析技术,将层次关系队列结构应用于XML文档查询中,采用动态生成区间编码的方式,免除建立编码索引文件的步骤。实验结果表明,在对相关数据集进行查询时,该算法可减少I/O操作,缩短查询响应时间,提高查询效率。     

改进的XML小枝模式匹配方法

近年来, XML数据查询成为一个重要的研究课题。处理小枝查询是XML查询实现的核心操作,针对小枝模式查询,提出了一种改进的小枝模式匹配算法。该算法通过剪去无用的数据流以减少待处理结点的数目,从而节省处理时间,提高查询的准确率。实验结果表明,该算法能够有效提高查询效率。     

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

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

一种非归并不确定XML小枝模式查询算法

针对目前不确定XML小枝模式查询需要存储大量中间结果和归并中间结果的情况,提出一种非归并不确定XML小枝模式查询算法ProTwigList。该算法查询之前通过Tag+Level流进行剪枝,以减少待处理节点的数目;并扩展了区间编码来对剪枝后剩余的普通节点进行编码,用一定规则对分布节点进行标识;查询时采用公共分布节点路径的方法处理分布结点,最后结合最低公共祖先节点的概率计算查询结果的概率值。理论分析和实验结果证明了ProTwigList算法的查询效率。     

一种基于扩展区间编码的结构连接算法TwigELM

由于XML具有格式良好,自描述,可扩展等优点,使得XML成为网络上信息表达和数据交换事实上的标准。随着XML格式数据的广泛应用,如何有效地存储和查询XML格式数据成为当前研究的热点。为了有效支持XML结构查询,研究者已经提出了XML数据的各种编码方案。通过编码的方式将XML结构查询的计算转化为结构连接的计算。该文提出了一种新的XML文档树编码方案,并基于该编码方案给出了一种新的小枝模式查询算法TwigELM,实验表明,该算法可有效提高结构连接操作的效率。     

一种改进的基于小枝模式的XML数据库查询算法

XML已经成为Internet上一种普遍的数据交换标准,目前已经出现了多种对XML文档的查询方法。针对小枝模式的XML查询,提出了一种改进的小枝栈算法。该算法将路径栈算法的思想应用到它的主算法中实现了小枝模式查询。与仅使用路径栈算法相比,改进后的小枝栈算法在运行过程中不会产生中间结果,而且提高了找到小枝模式根元素后的查询效率。     

TwigEN：一种新的小枝模式匹配算法

随着互联网的迅速发展,XML已经成为网上通用的数据表示与交换的标准。因此,如何有效地查询XML数据成为一个重要的研究课题。近年来,小枝模式匹配问题已被广泛地研究,提出了不少小枝模式匹配算法。在汲取各种小枝模式匹配算法优点的基础上,提出了一种新的小枝模式匹配算法TwigEN。根据XML文档结构它可以跳过那些在结构连接中无用的元素结点,这样不仅减少了待处理结点的数目,缩短了处理时间,而且也节省了内存空间。     

一种基于序列的不确定XML小枝匹配方法

针对目前不确定XML小枝模式查询处理方法中繁复的结构连接操作和不便于概率阈值过滤的缺点,提出一种新颖的基于序列的不确定XML小枝模式查询处理方法。该方法包括不确定XML序列索引的建立以及基于序列匹配的查询算法,与现有的不确定XML查询处理方法相比不需要繁复的结构连接操作,而且可以灵活地进行三次概率阈值过滤。理论分析和实验表明,该方法便于概率阈值过滤,同时具有较高的查询效率。     

sTwig——一种基于流的XML小枝匹配算法

结构连接是处理XML查询的主要方法,目前已经有一系列有效的结构连接算法被提出.但是已经存在的结构连接算法,在处理仅含有祖先后裔边的小枝模式查询方面,会访问不必要的元素节点,提出了一种新的小枝匹配算法sTwig.sTwig算法基于"流"的思想,实现简单,不需要归并操作,且避免了对不必要元素节点的访问,TwigNME算法是目前在处理仅含有祖先后裔边的小枝查询方面表现最优的结构连接算法,通过实验,将sTwig算法与TwigNME算法进行了比较,实验结果表明sTwig算法在时间和空间上都存在优势.     

基于模糊XML的小枝查询处理

现实世界中存在大量的不精确和不确定信息,因此,针对模糊数据的表示和处理的研究工作已经广泛展开.作为下一代Web语言,XML已经成为当前Web数据表示与交换的标准.不精确和不确定数据的出现对XML提出了新的挑战,现有的研究成果已不能满足模糊XML环境下智能化数据管理的迫切需求.为此,文中在模糊XML数据模型的基础上,从编码技术入手,讨论模糊XML环境下的结点编码问题,进而研究模糊XML环境下的小枝查询问题.文中提出了基于模糊XML的小枝模式匹配算法,给出了加速小枝匹配的索引算法,并最终通过实验证明了所提方法的优越性.     

Matching twigs in fuzzy XML

A considerable amount of twig pattern matching algorithms have been proposed to holistically process a twig query. Those algorithms mainly focus on twig pattern query with the AND-logic. However, there is often a need to process a twig query with the OR-predicates. Furthermore, the existing algorithms fall short in their ability to support twig query with OR-logic in fuzzy XML. To overcome this limitation, in this paper, we first introduce a novel encoding scheme to represent node information in fuzzy XML. Based on the encoding scheme, we then propose an effective algorithm for matching a twig pattern query with the AND/OR-logic in fuzzy XML. Our approach adopts a compact stack technique to process the complicated twig query consisting of both AND-logic and OR-logic. More importantly, our method eliminates re-scanning unnecessary portions of XML documents and redundant intermediate results. Finally, the experimental results demonstrate the performance advantages of our approach.     

一种有效的XML数据库的小枝模式匹配算法

目前,XML文档查询是研究的热点,其中小枝模式匹配方法是重要的研究方向,但是大多数基于这种思想的算法只能处理包含祖先／后代关系的查询。为此,提出了一种新的小枝模式匹配算法——TwigStackPC,它能够有效地处理包含祖先／后代和父／子关系的查询。     

Querying and ranking incomplete twigs in probabilistic XML

As the next generation language of the Internet, XML has been the de-facto standard of information exchange over the web. A core operation for XML query processing is to find all the occurrences of a twig pattern in an XML database. In addition, the study of probabilistic data has become an emerging topic for various applications on the Web. Therefore, researching the combination of XML twig pattern and probabilistic data is quite significant. In prior work of probabilistic XML, the answers of a given twig query are always complete. However, complete answers with low probabilities may be deemed irrelevant while incomplete answers with high probabilities are of great significance because incomplete answers may be the potential answers that interest the users. Different from complete evaluation, evaluating incomplete twigs in probabilistic XML introduces some new challenges. On one hand, incomplete queries do not only obtain complete matches, but also return answers that contain considerable incomplete matches. On the other hand, the processing of incomplete evaluation is more complicated. It is obvious that a ranking approach should be adopted along with evaluating incomplete answers. In this paper, we propose an efficient algorithm to handle the problem of querying incomplete twigs over the probabilistic XML database. We also present a novel algorithm for ranking the incomplete answers. The experimental results show that our proposed algorithms can improve the performance of querying and ranking incomplete twigs significantly.     

A syntactic approach to twig-query matching on XML streams

Query matching on XML streams is challenging work for querying efficiency when the amount of queried stream data is huge and the data can be streamed in continuously. In this paper, the method Syntactic Twig-Query Matching (STQM) is proposed to process queries on an XML stream and return the query results continuously and immediately. STQM matches twig queries on the XML stream in a syntactic manner by using a lexical analyzer and a parser, both of which are built from our lexical-rules and grammar-rules generators according to the user's queries and document schema, respectively. For query matching, the lexical analyzer scans the incoming XML stream and the parser recognizes XML structures for retrieving every twig-query result from the XML stream. Moreover, STQM obtains query results without a post-phase for excluding false positives, which are common in many streaming query methods. Through the experimental results, we found that STQM matches the twig query efficiently and also has good scalability both in the queried data size and the branch degree of the twig query. The proposed method takes less execution time than that of a sequence-based approach, which is widely accepted as a proper solution to the XML stream query.     

Efficient Processing of Distributed Twig Queries Based on Node Distribution

Massive XML data are increasingly generated for the representation, storage and exchange of web information. Twig query processing over massive XML data has become a research focus. However, most traditional algorithms cannot be directly implemented in a distributed manner. Some of the existing distributed algorithms generate a lot of useless intermediate results and execute many join operations of partial results in most cases; others require the priori knowledge of query pattern before XML partition, storage and query processing, which is impractical in the cases of large-scale data or frequent incoming new queries. To improve efficiency and scalability, in this paper, we propose a 3-phase distributed algorithm DisT3 based on node distribution mechanism to avoid unnecessary intermediate results. Furthermore, we propose a lightweight local index ReP with an enhanced XML partitioning approach using arbitrary partitioning strategy, and based on ReP we propose an improved 2-phase distributed algorithm DisT2ReP to further reduce the communication cost. After the performance guarantees are analyzed, extensive experiments are conducted to verify the efficiency and scalability of our proposed algorithms in distributed twig query applications.     

Efficiently Querying Large XML Data Repositories: A Survey

Extensible markup language (XML) is emerging as a de facto standard for information exchange among various applications on the World Wide Web. There has been a growing need for developing high-performance techniques to query large XML data repositories efficiently. One important problem in XML query processing is twig pattern matching, that is, finding in an XML data tree D all matches that satisfy a specified twig (or path) query pattern Q. In this survey, we review, classify, and compare major techniques for twig pattern matching. Specifically, we consider two classes of major XML query processing techniques: the relational approach and the native approach. The relational approach directly utilizes existing relational database systems to store and query XML data, which enables the use of all important techniques that have been developed for relational databases, whereas in the native approach, specialized storage and query processing systems tailored for XML data are developed from scratch to further improve XML query performance. As implied by existing work, XML data querying and management are developing in the direction of integrating the relational approach with the native approach, which could result in higher query processing performance and also significantly reduce system reengineering costs.