Computing possible and certain answers over order-incomplete data

DOI10.1016/J.TCS.2019.05.013MaRDI QIDQ2334598zbMATH OpenOpenAlexWikidataFDO

Authors Antoine Amarilli, Mouhamadou Lamine Ba, Daniel Deutch, Pierre Senellart

Publication date 7 November 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.06396

zbMATH Keywords

partial orderuncertain datacertain answerpossible answer

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Database theory (68P15)

Abstract: This paper studies the complexity of query evaluation for databases whose relations are partially ordered; the problem commonly arises when combining or transforming ordered data from multiple sources. We focus on queries in a useful fragment of SQL, namely positive relational algebra with aggregates, whose bag semantics we extend to the partially ordered setting. Our semantics leads to the study of two main computational problems: the possibility and certainty of query answers. We show that these problems are respectively NP-complete and coNP-complete, but identify tractable cases depending on the query operators or input partial orders. We further introduce a duplicate elimination operator and study its effect on the complexity results.

Recommendations

• Possible and certain answers for queries over order-incomplete data
• The complexity of querying indefinite data about linearly ordered domains
• Top-\(k\) querying of unknown values under order constraints
• An initial approach to the evaluation of possibilistic queries addressed to possibilistic databases.
• Certain answers over incomplete XML documents: extending tractability boundary

Cites work

• scientific article; zbMATH DE number 3916273 (Why is no real title available?)
• scientific article; zbMATH DE number 3983158 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 1862431 (Why is no real title available?)
• scientific article; zbMATH DE number 789816 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• scientific article; zbMATH DE number 7376042 (Why is no real title available?)
• scientific article; zbMATH DE number 3318593 (Why is no real title available?)
• scientific article; zbMATH DE number 2207163 (Why is no real title available?)
• A decomposition theorem for partially ordered sets
• An algebra for pomsets.
• An extension of the relational data model to incorporate ordered domains
• Determining possible and necessary winners given partial orders
• Incomplete Information in Relational Databases
• Note on Dilworth's Decomposition Theorem for Partially Ordered Sets
• On the complexity of iterated shuffle
• Probabilistic databases
• Query languages for bags and aggregate functions
• Relational queries computable in polynomial time
• SQL's three-valued logic and certain answers
• Sequences, datalog, and transducers
• Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules
• The complexity of querying indefinite data about linearly ordered domains
• Towards a characterization of order-invariant queries over tame graphs
• Towards a dichotomy for the possible winner problem in elections based on scoring rules
• Towards tractable algebras for bags
• Using powerdomains to generalize relational databases
• XML with incomplete information

Cited in

(1)

• Possible and certain answers for queries over order-incomplete data

This page was built for publication: Computing possible and certain answers over order-incomplete data

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