Constant Delay Enumeration for Acyclic Conjunctive Queries over X-Doublebar Structures

We present an efficient answer enumeration algorithm for a fragment of Conditional XPath with variables, which is a first-order complete query language for unranked trees of bounded depth. Our algorithm requires linear precomputation time and constant delay for fixed queries, while depending linearly on the size of the query. It is based on a new enumeration algorithm for disjunctions of acyclic conjunctive queries on so called X-doublebar-structures that we introduce. Keywords: Logic, databases, enumeration, XML http://www.grappa.univ-lille3.fr/~niehren/Papers/X-doublebar/0.pd