Explainable Certain Answers

Giovanni Amendola, Leonid Libkin

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


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.
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

Fingerprint Dive into the research topics of 'Explainable Certain Answers'. Together they form a unique fingerprint.

Cite this