Conjunctive query containment over trees

DOI10.1016/j.jcss.2010.04.005zbMath1215.68087OpenAlexW2157308304MaRDI QIDQ532363

Thomas Schwentick, Henrik Björklund, Wim Martens

Publication date: 4 May 2011

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2010.04.005

zbMATH Keywords

XMLdata managementquery optimization

Mathematics Subject Classification ID

Database theory (68P15) Logic in computer science (03B70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Certain answers over incomplete XML documents: extending tractability boundary ⋮ XML Schema Mappings ⋮ Conjunctive query containment over trees using schema information ⋮ Unnamed Item ⋮ The complexity of higher-order queries ⋮ The uniform measure of simple regular sets of infinite trees

Uses Software

• XQuery
• XPath

Cites Work

• On finding minimal length superstrings
• The shortest common supersequence problem over binary alphabet is NP- complete
• Conjunctive-query containment and constraint satisfaction
• The complexity of XPath query evaluation and XML typing
• Conjunctive queries over trees
• On deciding well-definedness for query languages on trees
• XML data exchange
• Optimizing Conjunctive Queries over Trees Using Schema Information
• Containment and Optimization of Object-Preserving Conjunctive Queries
• The complexity of satisfiability problems
• Containment and equivalence for a fragment of XPath