To search, Click below search items. |
| All Published Papers Search Service |
|
|
|
Title |
TJP: A Modified Twig Join Algorithm Based on the Pri-order Labeling Scheme |
|
Author |
Ren JiaDong, Yue LiWen |
| Citation |
Vol. 6 No. 7 pp. 144-151 |
|
Abstract |
XML exploits a tree-structured data model for representing data, and XML queries specify patterns of selection predicates on multiple elements related by a tree structure. Finding all occurrences of such a twig pattern in an XML database is a core operation for XML query processing. A lot of algorithms have been proposed to process to XML twig pattern query based-on region labeling scheme, which can not support the updating of XML documents. In this paper, a new twig join algorithm TJP is proposed, for matching an XML query twig pattern, it is modification of TwigStackList based on a new labeling scheme. This labeling scheme is optimal to determine the relationships between nodes and can support efficiently dynamic updating of documents. TJP uses a list to cache some elements in input data streams; the length of list is not longer than that of the longest path in the XML documents. It is important technique for lists of branching nodes; we preserve the elements in list only when they contribute to the final query results. The algorithm is I/O and CPU optimal for queries with ancestor-descendant edge. When the twig pattern contains parent-child relationships below branching nodes, the algorithm TJP will get a much smaller set of intermediate results than previous join algorithms. |
|
Keywords |
XML, twig pattern, labeling scheme, join algorithm |
|
URL |
