Complexity of Data Tree Patterns over XML Documents

DOI10.1007/978-3-540-85238-4_22zbMath1173.68477OpenAlexW1927596640MaRDI QIDQ3599134

Claire David

Publication date: 3 February 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85238-4_22

Mathematics Subject Classification ID

Database theory (68P15) Specification and verification (program logics, model checking, etc.) (68Q60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (6)

Future-Looking Logics on Data Words and Trees ⋮ XML Schema Mappings ⋮ Solutions in XML data exchange ⋮ On the coNP hardness of computing certain answers over locally specified incomplete DOM-trees ⋮ On the complexity of tree pattern containment with arithmetic comparisons ⋮ Conjunctive query containment over trees using schema information

Cites Work

• The complexity of facets (and some facets of complexity)
• XML with data values: Typechecking revisited.
• Two-variable logic on data trees and XML reasoning
• On XML integrity constraints in the presence of DTDs
• Conjunctive queries over trees
• XML data exchange
• XPath satisfiability in the presence of DTDs
• Optimizing Conjunctive Queries over Trees Using Schema Information

This page was built for publication: Complexity of Data Tree Patterns over XML Documents