-
When querying a database, a user may not always obtain the expected results,
and the system could provide some explanations. Explanations that could be
useful to further understand the data or check if the query is the intended one.
Actually, the notion of explanation for a query result was introduced in [
19
], on
the basis of the deeper concept of actual causation.
Intuitively, a tuple t is an actual cause for an answer a¯ to a conjunctive
query Q from a relational database instance D if there is a “contingent” set of
tuples , such that, after removing from D, removing/inserting t from/into D
causes a¯ to switch from being an answer to being a non-answer. Actual causes
and contingent tuples are restricted to be among a pre-specified set of
endogenous tuples, which are admissible, possible candidates for causes, as opposed to
exogenous tuples. (For a formalization of non-causality-based explanations for
query answers in DL ontologies, see [
3
].)
Some causes may be stronger than others. In order to capture this
observation, [
19
] also introduces and investigates a quantitative metric, called
responsibility, which reflects the relative degree of causality of a tuple for a query result.
In applications involving large data sets, it is crucial to rank potential causes by
their responsibility [
20, 19
].
Actual causation, as used in [
19
], can be traced back to [
11, 12
], which
provides a model-based account of causation on the basis of the
counterfactual dependence. Responsibility was also introduced in [
8
], to capture the
degree of causation. Apart from the explicit use of causality, research on
explanations for query results has focused mainly, and rather implicitly, on provenance
[
4, 5, 7, 9, 15, 14, 23
], and more recently, on provenance for non-answers [
6, 13
].
A close connection between causality and provenance has been established [
19
].
However, causality is a more refined notion that identifies causes for query
results on the basis of user-defined criteria, and ranks causes according to their
responsibility [
20
].
Consistency-based diagnosis [
21
] is an area of knowledge representation. The
main task here is, given the speci cation of a system in some logical formalism
and a usually unexpected observation about the system, to obtain explanations
for the observation, in the form of a diagnosis for the unintended behavior.
In a different direction, a database instance, D, that is expected to satisfy
certain integrity constraints (ICs) may fail to do so. In this case, a repair of D is
a database D′ that does satisfy the ICs and minimally departs from D. Different
forms of minimality can be applied and investigated. A consistent answer to a
query from D and wrt. the ICs is a query answer that is obtained from all possible
repairs, i.e. is invariant or certain under the class of repairs. These notions were
introduced in [
1
] (see [
2
] for a recent survey). We should mention that, although
not in the framework of database repairs, model-based diagnosis techniques have
been applied to restoring consistency of a database wrt. a set of ICs [
10
]
These three forms of reasoning, namely inferring causality in databases,
consistency-based diagnosis, and consistent query answers (and repairs) are all
non-monotonic. For example, a (most responsible) cause for a query result may
not be such anymore after the database is updated. In this work we establish
natural, precise, useful, and deeper connections between causality for query answers
in databases, database repairs wrt. denial constraints, and consistency-based
diagnosis. The first two are relatively new problems in databases, and the third one
is an established subject of model-based diagnosis in knowledge representation.
We show how to obtain database repairs from causes, and the other way
around. The vast body of research on database repairs can be applied to the
newer problem of determining actual causes for query answers. By formulating
a causality problem as a diagnosis problem, we manage to characterize causes
in terms of the system’s diagnoses. More specifically, we show that inferring
and computing actual causes and responsibility in a database setting become, in
different forms, consistency-based diagnosis reasoning problems and tasks.
Informally, a causal explanation for a conjunctive query answer can be viewed
as a diagnosis, where in essence the first-order logical reconstruction of the
relational database provides the system description [
22
], and the observation is the
query answer. Furthermore, we unveil a strong connection between computing
causes and their responsibilities for conjunctive queries, on the one hand, and
computing repairs in databases [
2
] wrt. denial constraints, on the other hand.
These computational problems can be reduced to each other. More precisely, we
report on the following results:
1. For a boolean conjunctive query and its associated denial constraint (which
is violated iff the query is true), we establish a precise connection between
actual causes for the query (being true) and the subset-repairs [
1
] of the
instance wrt. the constraint. Namely, we obtain causes from repairs.
2. In particular, we establish the connection between an actual cause’s
responsibility and cardinality repairs [
18
] wrt. the associated constraint.
3. We characterize and obtain subset- and cardinality- repairs for a database
under a denial constraint in terms of the causes for the associated query
being true.
4. We consider a set of denials constraints and a database that may be
inconsistent wrt. them. We obtain the database repairs by means of an algorithm
that takes as input the actual causes for constraint violations and their
contingency sets.
5. We establish a precise connection between consistency-based diagnosis for
a boolean conjunctive query being unexpectedly true according to a system
description, and causes for the query being true. In particular, we compute
actual causes, contingency sets, and responsibilities from minimal diagnosis.
6. As report on ongoing work, we discuss several extensions and open issues
that are under investigation.
Acknowledgements: Leo Bertossi is grateful to Benny Kimelfeld for
stimulating conversations at LogicBlox, and pointing out to [
16, 17
], where an interesting
connection between updates through views and causality is established. He also
appreciates the hospitality of LogicBlox during part of his sabbatical.