Knowledge-preserving Certain Answers for SQL-like Queries

Etienne Toussaint, Paolo Guagliardo, Leonid Libkin

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


Answering queries over incomplete data is based on finding answers that are certainly true, independently of how missing values are interpreted. This informal description has given rise to several different mathematical definitions of certainty. To unify them, a framework based on ”explanations”, or extra information about incomplete data, was recently proposed. It partly succeeded in justifying query answering methods for relational databases under set semantics, but had two major limitations. First, it was firmly tied to the set data model, and a fixed way of comparing incomplete databases with respect to their information content. These assumptions fail for real-life database queries in languages such as SQL that use bag semantics instead. Second, it was restricted to queries that only manipulate data, while in practice most analytical SQL queries invent new values, typically via arithmetic operations and aggregation.

To leverage our understanding of the notion of certainty for queries for SQL-like languages, we consider incomplete databases whose information content may be enriched by additional knowledge. The knowledge order among them is derived from their semantics, rather than being fixed a priori. The resulting framework allows us to capture and justify existing notions of certainty, and extend these concepts to other data models and query languages. As natural applications, we provide for the first time a well-founded definition of certain answers for the relational bag data model, and for value-inventing queries on incomplete databases, addressing the key shortcomings of the previous approaches.
Original languageEnglish
Title of host publicationProceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning — Main Track
EditorsDiego Calvanese, Esra Erdem, Michael Thielscher
PublisherInternational Joint Conferences on Artificial Intelligence Organization
Number of pages10
ISBN (Print)978-0-9992411-7-2
Publication statusPublished - 12 Sep 2020
Event17th International Conference on Principles of Knowledge Representation and Reasoning - Rhodes, Greece
Duration: 12 Sep 202018 Sep 2020

Publication series

ISSN (Print)2334-1033


Conference17th International Conference on Principles of Knowledge Representation and Reasoning
Abbreviated titleKR 2020
Internet address


Dive into the research topics of 'Knowledge-preserving Certain Answers for SQL-like Queries'. Together they form a unique fingerprint.

Cite this