|
Title:
|
AN EFFICIENT ALGORITHM FOR TWIG JOINS |
|
Author(s):
|
Yangjun Chen |
|
ISBN:
|
978-972-8924-30-0 |
|
Editors:
|
Nuno Guimarães and Pedro Isaías |
|
Year:
|
2007 |
|
Edition:
|
Single |
|
Keywords:
|
XML databases, Trees, Paths, XML pattern matching, Twig joins. |
|
Type:
|
Short Paper |
|
First Page:
|
443 |
|
Last Page:
|
448 |
|
Language:
|
English |
|
Cover:
|
|
|
Full Contents:
|
click to dowload 
|
|
Paper Abstract:
|
The twig join, which is used to find all occurrences of a twig pattern in an XML database, is a core operation for XML query processing. A great many strategies for handling this problem have been proposed and can be roughly classified into two groups. The first group decomposes a twig pattern (a small tree) into a set of binary relationships between pairs of nodes, such as parent-child and ancestor-descendant relations; and transforms a tree matching problem into a series of simple relation look-ups. The second group decomposes a twig pattern into a set of paths and then extracts all the matching paths from documents. For all these methods, a series of costly joins are needed to construct final answers. In this paper, we propose a new algorithm to find all the answers in O(m⋅n) time, where m and n are the sizes of the query tree and document tree, respectively. More importantly, no joins are required. |
|
|
|
|
|
|
