Abstract
One of the most common scenarios of handling incomplete information occurs in relational
databases. They describe incomplete knowledge
with three truth values, using Kleene’s logic for
propositional formulae and a rather peculiar extension to predicate calculus. This design by a committee from several decades ago is now part of the
standard adopted by vendors of database management systems. But is it really the right way to
handle incompleteness in propositional and predicate logics? Our goal is to answer this question.
Using an epistemic approach, we first characterize
possible levels of partial knowledge about propositions, which leads to six truth values. We impose
rationality conditions on the semantics of the connectives of the propositional logic, and prove that
Kleene’s logic is the maximal sublogic to which the
standard optimization rules apply, thereby justifying this design choice. For extensions to predicate
logic, however, we show that the additional truth
values are not necessary: every many-valued extension of first-order logic over databases with incomplete information represented by null values is
no more powerful than the usual two-valued logic
with the standard Boolean interpretation of the connectives. We use this observation to analyze the
logic underlying SQL query evaluation, and conclude that the many-valued extension for handling
incompleteness does not add any expressiveness to
it