Efficient algorithms for descendant-only tree pattern queries |
| |
Authors: | Michaela Gö tz,Christoph Koch,Wim Martens |
| |
Affiliation: | 1. Cornell University, Ithaca, NY 14853, United States;2. Technical University of Dortmund, Germany |
| |
Abstract: | Tree pattern matching is a fundamental problem that has a wide range of applications in Web data management, XML processing, and selective data dissemination. In this paper we develop efficient algorithms for the tree homeomorphism problem, i.e., the problem of matching a tree pattern with exclusively transitive (descendant) edges. We first prove that deciding whether there is a tree homeomorphism is LOGSPACE-complete, improving on the current LOGCFL upper bound. Furthermore, we develop a practical algorithm for the tree homeomorphism decision problem that is both space- and time-efficient. The algorithm is in LOGDCFL and space consumption is strongly bounded, while the running time is linear in the size of the data tree. This algorithm immediately generalizes to the problem of matching the tree pattern against all subtrees of the data tree, preserving the mentioned efficiency properties. |
| |
Keywords: | XML XPath Query processing Tree pattern queries Complexity |
本文献已被 ScienceDirect 等数据库收录! |
|