Extended XML Tree Pattern Matching: Theories and Algorithms
Extended XML Tree Pattern Matching: Theories and Algorithms
复制标题
DOI：
10.1109/tkde.2010.126
复制
发表时间：
2011-03
影响因子：
8.9
通讯作者：
Jiaheng Lu;T. Ling;Z. Bao;Chen Wang
中科院分区：
文献类型：
--
作者：
Jiaheng Lu;T. Ling;Z. Bao;Chen Wang
随着业务和企业更频繁地生成和交换XML数据，对有效处理XML数据查询的需求也越来越大。在XML数据库中搜索出现的树模式查询是XML查询处理中的核心操作。已有研究表明，整体小枝模式匹配算法能够有效地控制查询过程中中间结果的大小，是解决具有父子（P-C）和祖先-后代（A-D）关系的XML树模式的一种有效技术。但是，XML查询语言（例如XPath和XQuery）定义了更多的轴和函数，例如否定函数、基于顺序的轴和通配符。本文研究了一种包含P-C关系、a - d关系、否定函数、通配符和顺序限制的大型XML树模式，称为扩展XML树模式。建立了一个关于“匹配交叉”的理论框架，说明了整体算法最优性证明的内在原因。基于这些定理，我们提出了一组新的算法来有效地处理三类扩展XML树模式。在真实和合成数据集上的一系列实验结果证明了我们提出的理论和算法的有效性和效率。
As business and enterprises generate and exchange XML data more often, there is an increasing need for efficient processing of queries on XML data. Searching for the occurrences of a tree pattern query in an XML database is a core operation in XML query processing. Prior works demonstrate that holistic twig pattern matching algorithm is an efficient technique to answer an XML tree pattern with parent-child (P-C) and ancestor-descendant (A-D) relationships, as it can effectively control the size of intermediate results during query processing. However, XML query languages (e.g., XPath and XQuery) define more axes and functions such as negation function, order-based axis, and wildcards. In this paper, we research a large set of XML tree pattern, called extended XML tree pattern, which may include P-C, A-D relationships, negation functions, wildcards, and order restriction. We establish a theoretical framework about “matching cross” which demonstrates the intrinsic reason in the proof of optimality on holistic algorithms. Based on our theorems, we propose a set of novel algorithms to efficiently process three categories of extended XML tree patterns. A set of experimental results on both real-life and synthetic data sets demonstrate the effectiveness and efficiency of our proposed theories and algorithms.