zbMATH — the first resource for mathematics

Containment for conditional tree patterns. (English) Zbl 1391.68027
Summary: A Conditional Tree Pattern (\mathsf CTP) expands an XML tree pattern with labels attached to the descendant edges. These labels can be XML element names or Boolean \mathsf CTPs. The meaning of a descendant edge labelled by \(A\) and ending in a node labelled by \(B\) is a path of child steps ending in a \(B\) node such that all intermediate nodes are \(A\) nodes. In effect this expresses the until \(B\), \(A\) holds construction from temporal logic.
This paper studies the containment problem for \mathsf CTP. For tree patterns (\mathsf TP), this problem is known to be coNP-complete. We show that it is PSpace-complete for \mathsf CTP. This increase in complexity is due to the fact that \mathsf CTP is expressive enough to encode an unrestricted form of label negation: \(\ast \backslash a\), meaning “any node except an a-node”. Containment of \mathsf TP expanded with this type of negation is already PSpace-hard.
\mathsf CTP is a positive, forward, first order fragment of Regular XPath. Unlike \mathsf TP, \mathsf CTP expanded with disjunction is not equivalent to unions of \mathsf CTP’s. Like \mathsf TP, \mathsf CTP is a natural fragment to consider: \mathsf CTP is closed under intersections and \mathsf CTP with disjunction is equally expressive as positive existential first order logic expanded with the until operator.
Reviewer: Reviewer (Berlin)

68P15 Database theory
68P05 Data structures
Full Text: DOI