Projects per year
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 manyvalued extension of firstorder logic over databases with incomplete information represented by null values is no more powerful than the usual twovalued 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 manyvalued extension for handling incompleteness does not add any expressiveness to it.
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 manyvalued extension of firstorder logic over databases with incomplete information represented by null values is no more powerful than the usual twovalued 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 manyvalued extension for handling incompleteness does not add any expressiveness to it.
Original language  English 

Title of host publication  Proceedings of the Sixteenth International Conference on Principles of Knowledge Representation and Reasoning (KR18) 
Place of Publication  Tempe, Arizona, USA 
Publisher  AAAI Press 
Pages  592601 
Number of pages  10 
ISBN (Print)  9781577358039 
Publication status  Published  2 Nov 2018 
Event  16th International Conference on Principles of Knowledge Representation and Reasoning  Tempe, United States Duration: 30 Oct 2018 → 2 Nov 2018 http://reasoning.eas.asu.edu/kr2018/ 
Publication series
Name  Principles of Knowledge Representation and Reasoning 

Publisher  AAAI Press 
ISSN (Print)  23341025 
ISSN (Electronic)  23341033 
Conference
Conference  16th International Conference on Principles of Knowledge Representation and Reasoning 

Abbreviated title  KR 2018 
Country/Territory  United States 
City  Tempe 
Period  30/10/18 → 2/11/18 
Internet address 
Fingerprint
Dive into the research topics of 'Propositional and Predicate Logics of Incomplete Information'. Together they form a unique fingerprint.Projects
 2 Finished


VADA: Value Added Data Systems: Principles and Architecture
Libkin, L., Buneman, P., Fan, W. & Pieris, A.
1/04/15 → 30/09/20
Project: Research
Research output
 1 Conference contribution

Do We Need Manyvalued Logics for Incomplete Information?
Console, M., Guagliardo, P. & Libkin, L., 31 Aug 2019, Proceedings of the TwentyEighth International Joint Conferences on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, p. 61416145 5 p.Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
Open AccessFile
Profiles

Leonid Libkin
 School of Informatics  Chair of Foundations of Data Management
 Laboratory for Foundations of Computer Science
 Foundations of Computation
Person: Academic: Research Active
Prizes

The 2018 Ray Reiter Best Paper Prize
Console, Marco (Recipient), Guagliardo, Paolo (Recipient) & Libkin, Leonid (Recipient), 25 Sep 2018
Prize: Prize (including medals and awards)