Computing possible and certain answers over order-incomplete data

DOI10.1016/J.TCS.2019.05.013zbMATH Open1434.68138arXiv1801.06396OpenAlexW2963195244WikidataQ127822820 ScholiaQ127822820MaRDI QIDQ2334598FDOQ2334598

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)

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.

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

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

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)

Cites Work

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

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)