Skip to Main content Skip to Navigation
Conference papers

Knowledge-Preserving Certain Answers for SQL-like Queries

Etienne Toussaint 1 Paolo Guagliardo 1 Leonid Libkin 2, 1
2 VALDA - Value from Data
DI-ENS - Département d'informatique - ENS Paris, Inria de Paris
Abstract : 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 reallife 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 in 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 valueinventing queries on incomplete databases, addressing the key shortcomings of previous approaches.
Document type :
Conference papers
Complete list of metadata
Contributor : Pierre Senellart Connect in order to contact the contributor
Submitted on : Tuesday, February 2, 2021 - 11:41:57 AM
Last modification on : Friday, January 21, 2022 - 3:17:27 AM
Long-term archiving on: : Monday, May 3, 2021 - 6:33:03 PM


Files produced by the author(s)




Etienne Toussaint, Paolo Guagliardo, Leonid Libkin. Knowledge-Preserving Certain Answers for SQL-like Queries. KR 2020 - 17th International Conference on Principles of Knowledge Representation and Reasoning, Sep 2020, Rhodes / Virtual, Greece. pp.758-767, ⟨10.24963/kr.2020/78⟩. ⟨hal-03128504⟩



Les métriques sont temporairement indisponibles