Edinburgh Research Explorer

SQL’s Three-Valued Logic and Certain Answers

Research output: Contribution to journalArticle

Related Edinburgh Organisations

Open Access permissions

Open

Documents

http://dl.acm.org/citation.cfm?id=2877206
Original languageEnglish
Article number1
Number of pages28
JournalACM Transactions on Database Systems
Volume41
Issue number1
DOIs
Publication statusPublished - Mar 2016

Abstract

The goal of the paper is to bridge the difference between theoretical and practical approaches to answering queries over databases with nulls. Theoretical research has long ago identified the notion of correctness of query answering over incomplete data: one needs to find certain answers, which are true regardless of how incomplete information is interpreted. This serves as the notion of correctness of query answering, but carries a huge complexity tag. In practice, on the other hand, query answering must be very efficient, and
to achieve this, SQL uses three-valued logic for evaluating queries on databases with nulls. Due to the complexity mismatch, the two approaches cannot coincide, but perhaps they are related in some 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.

Download statistics

No data available

ID: 21912156