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

DOI10.1016/J.IPL.2010.06.001MaRDI QIDQ407530zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

databasesincomplete informationcertain answers

Mathematics Subject Classification ID

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

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

Cites work

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

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)