Certain Answers meet Zero-One Laws

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Query answering over incomplete data invariably relies on the standard notion of certain answers which gives a very coarse classification of query answers into those that are certain and those that are not. Here we propose to refine it by measuring how close an answer is to certainty. This measure is defined as the probability that the query is true under a random interpretation of missing information in a database. Since there are infinitely many such interpretations, to pick one at random we adopt the approach used in the study of asymptotic properties of logical sentences, and define the measure as the limit of a sequence. We show that in the standard model of missing data, this limit always exists and can be only 0 or 1 for a very large class of queries. When it is 1, query answers are almost certainly true, and we prove that those are precisely the answers returned by the naïve evaluation of the query. When databases satisfy constraints, we define the measure as the conditional probability of the query being true if the constraints are true. This too is defined as a limit, and we prove that it always exists, can be an arbitrary rational number, and is computable. For some constraints, such as functional dependencies, the 0–1 dichotomy continues to hold. As another refinement of the notion of certainty, we introduce a comparison of query answers: an answer with a larger set of interpretations that make it true is better. We identify the precise complexity of such comparisons, and of finding sets of best answers, for first-order queries.
Original languageEnglish
Title of host publication2018 ACM SIGMOD/PODS Conference
Place of PublicationHouston, TX, USA
Number of pages13
ISBN (Print)978-1-4503-4706-8
Publication statusPublished - 27 May 2018
EventACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 2018 - Texas, Houston, United States
Duration: 10 Jun 201815 Jun 2018


ConferenceACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 2018
Country/TerritoryUnited States
Internet address


Dive into the research topics of 'Certain Answers meet Zero-One Laws'. Together they form a unique fingerprint.

Cite this