Complexity of Data Tree Patterns over XML Documents

DOI10.1007/978-3-540-85238-4_22MaRDI QIDQ3599134zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• XPath satisfiability in the presence of DTDs
• XML with data values: Typechecking revisited.
• The complexity of XPath query evaluation and XML typing
• Two-variable logic on data trees and XML reasoning
• scientific article; zbMATH DE number 1950751

Cites work

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

Cited in

(18)

• Conjunctive query containment over trees using schema information
• On the complexity of tree pattern containment with arithmetic comparisons
• scientific article; zbMATH DE number 1696860 (Why is no real title available?)
• Validity of tree pattern queries with respect to schema information
• Verifying recursive active documents with positive data tree rewriting
• Decidable classes of documents for XPath
• Consistency of injective tree patterns
• Future-Looking Logics on Data Words and Trees
• XML schema mappings, data exchange and metadata management
• Check on consistency of tree pattern queries under DTD constraints
• Tree Components Programming: An Application to XML
• Tree Pattern Rewriting Systems
• The complexity of XPath query evaluation and XML typing
• Solutions in XML data exchange
• On the coNP hardness of computing certain answers over locally specified incomplete DOM-trees
• scientific article; zbMATH DE number 1950751 (Why is no real title available?)
• scientific article; zbMATH DE number 7360256 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2004

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

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