Edinburgh Research Explorer

Explainable Certain Answers

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

Related Edinburgh Organisations

Open Access permissions



Original languageEnglish
Title of host publicationProceedings of the 27th International Joint Conferences on Artificial Intelligence Organization (IJCAI 2018)
Place of PublicationStockholm, Sweden
PublisherIJCAI Inc
Number of pages8
ISBN (Electronic)978-0-9992411-2-7
Publication statusPublished - 2018
Event27th International Joint Conference on Artificial Intelligence: IJCAI 2018 - Stockholmsmässan, Stockholm, Sweden
Duration: 13 Jul 201819 Jul 2018


Conference27th International Joint Conference on Artificial Intelligence
Abbreviated titleIJCAI 2018
Internet address


When a dataset is not fully specified and can represent many possible worlds, one commonly answers queries by computing certain answers to them. A natural way of defining certainty is to say that an answer is certain if it is consistent with query answers in all possible worlds, and is furthermore the most informative answer with this property. However, the existence and complexity of such answers is not yet well understood even for relational databases. Thus in applications one tends to use different notions, essentially the intersection of query answers in possible worlds. However, justification of such notions has long been questioned. This leads to two problems: are certain answers based on informativeness feasible in applications? and can a clean justification be provided for intersection-based notions?
Our goal is to answer both. For the former, we show that such answers may not exist, or be very large, even in simple cases of querying incomplete data. For the latter, we add the concept of explanations to the notion of informativeness: it shows not only that one object is more informative than the other, but also says why this is so. This leads to a modified notion of certainty: explainable certain answers. We present a general framework for reasoning about them, and show that for open and closed world relational databases, they are precisely the common intersection-based notions of certainty.


27th International Joint Conference on Artificial Intelligence: IJCAI 2018


Stockholm, Sweden

Event: Conference

Download statistics

No data available

ID: 64278636