Causality in databases (DBs) was introduced in [15]; and, building on work on causality as found in artificial intelligence, appeals to the notions of counterfactuals, interventions and structural models [14]. More specifically, [15] introduces the notions of: (a) a DB tuple as an actual cause for a query result, (b) a contingency set for a cause, as a set of tuples that must accompany the cause for it to be such, and (c) the responsibility of a cause as a numerical measure of its strength [11]. In our research on causality in DBs we have attempted to understand causality from different angles of data and knowledge management. In [5], precise reductions between causality in DBs, DB repairs, and consistency-based diagnosis were established; and the relationships were investigated and exploited. In [6], causality in DBs was related to view-based DB updates and abductive diagnosis, establishing fruitful connections. This work summarizes some directions and results of our recent and ongoing research in DB causality. Causality in databases. A notion of cause as an explanation for a query result was introduced in [15], as follows. For a relational instance D, a tuple 2 Dn is called a counterfactual cause for a Boolean conjunctive query (BCQ) Q, if D j= Q and D r f g 6j= Q. Now, 2 D is an actual cause for Q if there exists D, called a contingency set for , such that is a counterfactual cause for Q in D r . The notion of responsibility reflects the relative degree of causality of a tuple for a query result [15] (based on [11]). The responsibility of an actual cause for Q, is ( ) := j j1+1 , where j j is the size of a smallest contingency set for . If is not an actual cause, ( ) := 0. Tuples with higher responsibility are stronger explanations. The notion of cause can be applied to any monotonic query with free variables, e.g. conjunctive queries (CQs) with built-ins, unions of CQs (UCQs) [5], Datalog queries [6], etc. Here we consider only conjunctive queries. Example 1. Consider the relational DB D = fR(a4; a3); R(a2; a1); R(a3; a3); S(a4); S(a2); S(a3)g, and the query Q : 9x9y(S(x) ^ R(x; y) ^ S(y)). It holds, D j= Q. S(a3) is a counterfactual cause for Q: if S(a3) is removed from D, Q is no longer true. Its responsibility is 1. So, it is an actual cause with empty contingency set. R(a4; a3) is an actual cause for Q with contingency set fR(a3; a3)g: if R(a3; a3) is removed from D, Q is still true, but further removing R(a4; a3) makes Q false. The responsibility of R(a4; a3) is 21 . R(a3; a3) and S(a4) are actual causes, with responsibility 12 . Database repairs and causes. We introduce the main ideas around DB repairs [2] by means of an example. The ICs that we consider here can be enforced only by tupledeletions from the DB (as opposed to tuple-insertions). Example 2. The DB D = fP (a); P (e); Q(a; b); R(a; c)g is inconsistent with respect to the (set of) denial constraints (DCs) 1 : :9x9y(P (x) ^ Q(x; y)), and 2 : :9x9y(P (x) ^ R(x; y)). It holds D 6j= f 1; 2g. ? Member of the “Millenium Institute for Foundational Research on Data”, bertossi@scs.carleton.ca. Supported by NSERC Discovery Grant #06148.
Chile.
A subset-repair, in short an S-repair, of D wrt. the set of DCs is a -maximal subset of D that is consistent, i.e. no proper superset is consistent. The following are S-repairs: D1 = fP (e); Q(a; b); R(a; b)g and D2 = fP (e); P (a)g. A cardinality-repair, in short a C-repair, of D wrt. the set of DCs is a maximum-cardinality, consistent subset of D, i.e. no subset of D with larger cardinality is consistent. D1 is the only C-repair.
For an instance D and a set of DCs, the sets of S-repairs and C-repairs are denoted with Srep(D; ) and Crep(D; ), resp.
Now, consider a BCQ Q : 9x(P1(x1) ^ ^ Pm(xm)) with D j= Q. Notice that
:Q is logically equivalent to the DC: (Q) : :9x(P1(x1) ^ ^ Pm(xm)). So, if Q
is true in D, D is inconsistent wrt. (Q), giving rise to repairs of D wrt. (Q). In [
For tuple R(a4; a3), Di s(D; (Q); R(a4; a3)) = fD r D2g = ffR(a4; a3);
R(a3; a3)gg. So, R(a4; a3) is an actual cause, with responsibility 21 . Similarly, R(a3; a3)
is an actual cause, with responsibility 12 . For tuple S(a3), Di c(D; (Q); S(a3)) =
fD r D1g = fS(a3)g. So, S(a3) is an actual cause, with responsibility 1.
Specification of causes with ASP. A DB may have several repairs wrt. a class of ICs.
Since we are mainly interested in reasoning with whole class of them, e.g. for consistent
query answering [
Repairing the DB by changing attribute values is also possible [
Causality under ICs. The interventions at the basis of [
Example 4. For the DB instance D and the open, i.e. non-Boolean, CQ, Q in (3).
Course CName TStaff DName Dep DName TStaff t4 COM08 John Computing t1 Computing John t5 Math01 Kevin Math t2 Philosophy Patrick t6 HIST02 Patrick Philosophy t3 Math Kevin t7 Math08 Eli Math
t8 COM01 John Computing
AnsQ(TSta ) Dep(DName; TSta ); Course(CName; TSta ; DName): (3) Q(D) = fJohn; Patrick; Keving, and hJohni has the actual causes: t1, t4 and t8. t1 is a counterfactual cause, t4 has a single minimal contingency set 1 = ft8g; and t8 has a single minimal contingency set 2 = ft4g. Now, for the query
hJohni is still an answer from D, but it has a single cause, t1, which is also a counterfactual cause. Now, if the following inclusion dependency is satisfied by D, : 8x8y (Dep(x; y) ! 9u Course(u; y; x)); (5) Q is equivalent to Q0. The question is whether t4 and t8 should still be considered as causes for answer hJohni in the presence of . Finally, consider the query Q1:
which, among others, has hJohni as an answer, with t4 and t8 as the only actual causes, with contingency sets 1 = ft8g and 2 = ft4g, resp. In the presence of , one should wonder if also t1 would be a cause (it contains the referring value John in table Dept ), or, if not, whether its presence would make the previous causes less responsible.
A definition of query-answer cause was introduced and investigated in [6, sec. 7], as follows. For an instance D that satisfies a set of ICs, i.e. D j= , and a monotone query Q with D j= Q(a), a tuple 2 D is an actual cause for a under if there is
D, such that: (a) D r j= Q(a); (b) D r j= ; (c) D r ( [ ftg) 6j= Q(a); and (d) D r ( [ ftg) j= . The responsibility of as a cause for an answer a to query Q under a set of ICs, denoted by QD(;a) ( ), is defined exactly as above. Example 5. (ex. 4 cont.) For query Q in (3) and its answer hJohni, without in (5), t4 was a cause with minimal contingency set 1 = ft8g. Now, it holds D r 1 j= , but D r ( 1 [ ft4g) 6j= . So, in presence of , t4 is not an actual cause for hJohni. Notice that Q and Q0 in (4) have the same actual cause t1 for hJohni under .
For Q1 in (6), and its answer hJohni, t4 and t8 are still (non-counterfactual) actual causes under . However, their previous contingency sets are not such anymore: D r ( 1 [ ft4g) 6j= , D r ( 2 [ ft8g) 6j= . Actually, the smallest contingency set for t4 is 3 = ft8; t1g; and for t8, 4 = ft4; t1g. Accordingly, the causal responsibilities of t4; t8 decrease under : QD1(John) (t4) = 21 , but QD1;(John) (t4) = 13 . Under , tuple t1 is still not an actual cause for answer hJohni to Q1.
Since denial constraints are never violated by tuple deletions, they do not affect
the causes. However, inclusion dependencies (INDs) may make a set of causes grow,
together with sizes of minimal contingency sets, and then, responsibilities decrease.
Intuitively, the responsibility is spread through INDs. Also, causes are preserved under
logically equivalent query rewriting under ICs. (Cf. [6, prop. 20] for general properties.)
For some classes of CQs, the complexity of deciding responsibility of causes (under
causality without ICs) may decrease from NP-complete to tractability when the DB
satisfies certain key constraints [
In [
As part of our ongoing research, as an extension of [