License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2015.94
URN: urn:nbn:de:0030-drops-49791
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4979/
Go to the corresponding LIPIcs Volume Portal

Libkin, Leonid

SQL's Three-Valued Logic and Certain Answers

pdf-format:
6.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{libkin:LIPIcs:2015:4979,
  author =	{Leonid Libkin},
  title =	{{SQL's Three-Valued Logic and Certain Answers}},
  booktitle =	{18th International Conference on Database Theory (ICDT 2015)},
  pages =	{94--109},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-79-8},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{31},
  editor =	{Marcelo Arenas and Mart{\'i}n Ugarte},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4979},
  URN =		{urn:nbn:de:0030-drops-49791},
  doi =		{10.4230/LIPIcs.ICDT.2015.94},
  annote =	{Keywords: Null values, incomplete information, query evaluation, three-valued logic, certain answers}
}

Keywords: Null values, incomplete information, query evaluation, three-valued logic, certain answers
Collection: 18th International Conference on Database Theory (ICDT 2015)
Issue Date: 2015
Date of publication: 19.03.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI