Edinburgh Research Explorer

Approximations and Refinements of Certain Answers via Many-Valued Logics

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

Original languageEnglish
Title of host publication15th International Conference on Principles of Knowledge Representation and Reasoning (KR2016)
PublisherAAAI Press
Pages349-358
Number of pages10
ISBN (Print)978-1-57735-755-1
Publication statusPublished - Jul 2016
Event15th International Conference on Principles of Knowledge Representation and Reasoning - Cape Town, South Africa
Duration: 25 Apr 201629 Apr 2016
http://kr2016.cs.uct.ac.za/
http://kr2016.cs.uct.ac.za/

Conference

Conference15th International Conference on Principles of Knowledge Representation and Reasoning
Abbreviated titleKR 2016
CountrySouth Africa
CityCape Town
Period25/04/1629/04/16
Internet address

Abstract

Computing certain answers is the preferred way of answering queries in scenarios involving incomplete data. This, however, is computationally expensive, so practical systems use efficient techniques based on a particular three-valued logic, although this often leads to incorrect results.
Our goal is to provide a general many-valued framework for correctly approximating certain answers. We do so by defining the semantics of many-valued answers and queries, following the principle that additional knowledge about the input must translate into additional knowledge about the output. This framework lets us compare query outputs and evaluation procedures in terms of their informativeness. For each many valued logic with a knowledge ordering on its truth values, one can build a syntactic evaluation procedure for all first-order queries that correctly approximates certain answers; additional truth values are used to refine information about certain answers. For concrete examples, we show that a recently proposed approach fixing some of the inconsistencies of SQL query evaluation is an immediate consequence of our framework, and we also refine it by adding a fourth truth value. We show that many-valuedness is essential: no evaluation procedure based on the usual two-valued logic delivers correctness guarantees. Finally, we study the relative power of evaluation procedures based on the informativeness of the answers they produce.

Event

15th International Conference on Principles of Knowledge Representation and Reasoning

25/04/1629/04/16

Cape Town, South Africa

Event: Conference

Download statistics

No data available

ID: 23712549