Towards constraint-based explanations for answers and non-answers

Boris Glavic, Sven Köhler, Sean Riddle, Bertram Ludäscher

Research output: Contribution to conferencePaperpeer-review

Abstract

Explaining why an answer is present (traditional provenance) or absent (why-not provenance) from a query result is important for many use cases. Most existing approaches for positive queries use the existence (or absence) of input data to explain a (missing) answer. However, for realistically-sized databases, these explanations can be very large and, thus, may not be very helpful to a user. In this paper, we argue that logical constraints as a concise description of large (or even infinite) sets of existing or missing inputs can provide a natural way of answering a why- or why-not provenance question. For instance, consider a query that returns the names of all cities which can be reached with at most one transfer via train from Lyon in France. The provenance of a city in the result of this query, say Dijon, will contain a large number of train connections between Lyon and Dijon which each justify the existence of Dijon in the result. If we are aware that Lyon and Dijon are cities in France (e.g., an ontology of geographical locations is available), then we can use this information to generalize the query output and its provenance to provide a more concise explanation of why Dijon is in the result. For instance, we may conclude that all cities in France can be reached from each other through Paris. We demonstrate how an ontology expressed as inclusion dependencies can provide meaningful justifications for answers and non-answers, and we outline how to find a most general such explanation for a given UCQ query result using Datalog. Furthermore, we sketch several variations of this framework derived by considering other types of constraints as well as alternative definitions of explanation and generalization.

Original languageEnglish (US)
StatePublished - 2015
Event7th USENIX Workshop on the Theory and Practice of Provenance, TaPP 2015 - Edinburgh, United Kingdom
Duration: Jul 8 2015Jul 9 2015

Conference

Conference7th USENIX Workshop on the Theory and Practice of Provenance, TaPP 2015
CountryUnited Kingdom
CityEdinburgh
Period7/8/157/9/15

Keywords

  • Databases
  • Datalog
  • Missing Answers
  • Ontology
  • Provenance

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Towards constraint-based explanations for answers and non-answers'. Together they form a unique fingerprint.

Cite this