Towards Constraint-based Explanations for Answers and Non-Answers

Explaining why an answer is present (traditional provenance) or absent (missing answer provenance) from a query result is important for many use cases. Most existing approaches 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 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 question. For instance, to explain why no non-US citizen is in the answer of a query returning US presidents we could list all possible combinations of persons and countries of citizenship that are missing from the input. However, a more concise and insightful explanation is that the constraint that US presidency implies US citizenship prevents any results from being returned by our query. We demonstrate how a taxonomy expressed as inclusion dependencies can provide meaningful justifications for (non-) answers and outline how to find a most general such explanation for a given query 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.