On the coNP hardness of computing certain answers over locally specified incomplete DOM-trees

DOI10.1016/J.IPL.2010.06.001zbMATH Open1234.68125OpenAlexW2024034679MaRDI QIDQ407530FDOQ407530

Authors: Shun'ichi Amano 

Publication date: 27 March 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.06.001

Recommendations

• Certain answers over incomplete XML documents: extending tractability boundary
• XML with incomplete information
• Static analysis and query answering for incomplete data trees with constraints
• Trees in trees: is the incomplete information about a tree consistent?
• Conjunctive query containment over trees

zbMATH Keywords

databasesincomplete informationcertain answers

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Database theory (68P15)

Cites Work

• Incomplete Information in Relational Databases
• On the representation and querying of sets of possible worlds
• Complexity of Data Tree Patterns over XML Documents

Cited In (3)

• Certain answers over incomplete XML documents: extending tractability boundary
• Trees in trees: is the incomplete information about a tree consistent?
• XML with incomplete information

This page was built for publication: On the coNP hardness of computing certain answers over locally specified incomplete DOM-trees

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