Satisfiability Algorithms for Conjunctive Queries Over Trees
The authors investigate the satisfiability problem for conjunctions of constraints over ordered, unranked trees, including child, descendant, following-sibling, root, leaf, and first/last child constraints. They introduce new, symbolic approaches based on graph transformations, which simplify and check the consistency of a problem first, and delay blind search as long as possible. They prove correctness and termination for these algorithms. They also analyze the complexity of important special cases: binary and k-ary intersection of certain classes of XPath expressions. Their main complexity result is that binary intersection (for positive, simple navigational XPath over all axes) is tractable for expressions with a bounded number of changes in direction in the path, which is typically small.