| Summary: | A Conditional Tree Pattern (CTP) expands an XML tree pattern with labels
attached to the descendant edges. These labels can be XML element names or
Boolean 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
CTP. For tree patterns (TP), this problem is known to be coNP-complete. We show
that it is PSPACE-complete for CTP. This increase in complexity is due to the
fact that CTP is expressive enough to encode an unrestricted form of label
negation: ${*}\setminus a$, meaning "any node except an a-node". Containment of
TP expanded with this type of negation is already PSPACE-hard. CTP is a
positive, forward, first order fragment of Regular XPath. Unlike TP, CTP
expanded with disjunction is not equivalent to unions of CTP's. Like TP, CTP is
a natural fragment to consider: CTP is closed under intersections and CTP with
disjunction is equally expressive as positive existential first order logic
expanded with the until operator.
|
|---|