SQL's Three-Valued Logic and Certain Answers

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

Abstract / Description of output

SQL uses three-valued logic for evaluating queries on databases with nulls. The standard theoretical approach to evaluating queries on incomplete databases is to compute certain answers. While these two cannot coincide, due to a significant complexity mismatch, we can still ask whether the two schemes are related in any way. For instance, does SQL always produce answers we can be certain about?

This is not so: SQL's and certain answers semantics could be totally unrelated. We show, however, that a slight modification of the three-valued semantics for relational calculus queries can provide the required certainty guarantees. The key point of the new scheme is to fully utilize the three-valued semantics, and classify answers not into certain or non-certain, as was done before, but rather into certainly true, certainly false, or unknown. This yields relatively small changes to the evaluation procedure, which we consider at the level of both declarative (relational calculus) and procedural (relational algebra) queries. We also introduce a new notion of certain answers with nulls, which properly accounts for queries returning tuples containing null values.
Original languageEnglish
Title of host publication18th International Conference on Database Theory (ICDT 2015)
EditorsMarcelo Arenas, Martín Ugarte
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
Pages94-109
Number of pages16
ISBN (Print)978-3-939897-79-8
DOIs
Publication statusPublished - 2015

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Volume31

Fingerprint

Dive into the research topics of 'SQL's Three-Valued Logic and Certain Answers'. Together they form a unique fingerprint.

Cite this