Loading...
Please wait, while we are loading the content...
Similar Documents
Extended XML Tree Pattern Matching: Theories and Algorithms
| Content Provider | Semantic Scholar |
|---|---|
| Author | Hemanth, S. V. Keerthi, Suneel Kumar Prasad, Devendra |
| Copyright Year | 2012 |
| Abstract | 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. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.ijcst.com/vol32/2/skeerthi.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
