Containment for conditional tree patterns

DOI10.2168/LMCS-11(2:4)2015MaRDI QIDQ2941752zbMATH OpenOpenAlexFDO

Authors Alessandro Facchini, Yoichi Hirai, Maarten Marx, Evgeny Sherkhonov

Publication date 25 August 2015

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.02210

zbMATH Keywords

complexityconditional tree patterncontainmentXMLXpath

Mathematics Subject Classification ID

Data structures (68P05) Database theory (68P15)

Abstract: 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: $\ast setminusa$, 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.

Recommendations

• On the complexity of tree pattern containment with arithmetic comparisons
• scientific article; zbMATH DE number 1953139
• Conjunctive query containment over trees using schema information
• scientific article; zbMATH DE number 1953140
• Conjunctive query containment over trees

Cited in

(5)

• On the complexity of tree pattern containment with arithmetic comparisons
• Noncontiguous pattern containment in binary trees
• Containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons
• On the complexity of XPath containment in the presence of disjunction, DTDs, and variables
• Least common container of tree pattern queries and its applications

Describes a project that uses

Uses Software

• XPath

This page was built for publication: Containment for conditional tree patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941752)