|
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. |
