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 firstorder queries.
Original language  English 

Title of host publication  2018 ACM SIGMOD/PODS Conference 
Place of Publication  Houston, TX, USA 
Publisher  ACM 
Pages  195207 
Number of pages  13 
ISBN (Print)  9781450347068 
DOIs  
Publication status  Published  27 May 2018 
Event  ACM SIGMODSIGACTSIGAI Symposium on Principles of Database Systems (PODS), 2018  Texas, Houston, United States Duration: 10 Jun 2018 → 15 Jun 2018 https://sigmod2018.org/ 
Conference
Conference  ACM SIGMODSIGACTSIGAI Symposium on Principles of Database Systems (PODS), 2018 

Country/Territory  United States 
City  Houston 
Period  10/06/18 → 15/06/18 
Internet address 
Fingerprint
Dive into the research topics of 'Certain Answers meet ZeroOne Laws'. Together they form a unique fingerprint.Profiles

Leonid Libkin
 School of Informatics  Chair of Foundations of Data Management
 Laboratory for Foundations of Computer Science
 Foundations of Computation
Person: Academic: Research Active