Causality has been recently introduced in databases, to model, characterize and possibly compute causes for query results (answers). Connections between query causality and consistency-based diagnosis and database repairs (wrt. integrity constrain violations) have been established in the literature. In this work we establish connections between query causality and abductive diagnosis and the view-update problem. The unveiled relationships allow us to obtain new complexity results for query causality -the main focus of our work- and also for the two other areas.
In this work we concentrate on causality as defined forand applied to relational databases. Most of the work on causality has been developed in the context of knowledge representation, and little has been said about causality in data management. Furthermore, in a world of big uncertain data, the necessity to understand the data beyond simple query answering, introducing explanations in different forms, has become particularly relevant.
The notion of causality-based explanation for a query
result was introduced in
A cause t may have different associated contingency sets Γ.
Intuitively, the smaller they are the strongest is t as a cause
(it need less company to undermine the query answer). So,
some causes may be stronger than others. This idea is
formally captured through the notion of causal responsibility,
and introduced in
Actual causation, as used in
Model-based diagnosis
2As discussed in
The definition of causality for query answers applies to
monotone queries
In
As opposed to consistency-based diagnoses, which is
usually practiced with FO specifications, abductive diagnosis
is commonly performed under a logic programming (LP)
approach (in the general sense of LP) to knowledge
representation
Abductive reasoning/diagnosis has been applied to the view
update problem in databases
In this work we also explore fruitful connections of
causality with this view-update problem
The delete-propagation problem
In this work we provide a precise connection between
different variants of the delete-propagation problem and query
causality. In particular, we show that the minimal
sourceside-effect problem is related to the most-responsible cause
problem, which was formulated and investigated in
The established connections between abductive diagnoses, query causality and delete-propagation problems allow us to adopt (and possibly adapt) established results for some of them for application to the others. In this way we obtain some new complexity results.
More precisely, our main results are as follows:3 1. We establish precise connections between causality for Datalog queries and abductive diagnosis. More precisely, we establish mutual characterizations of each in terms of the other, and computational reductions, between actual causes for Datalog queries and abductive diagnosis from Datalog specifications. We profit from these connections to obtain new algorithmic and complexity results for each of the two problems separately. (a) We characterize and obtain causes in terms ofand from abductive diagnoses. (b) We show that deciding tuple causality for Datalog queries, possibly recursive, is NP-complete in data.
(c) We identify a class of Datalog queries for which deciding causality is tractable in combined complexity. 2. We establish and profit from precise connections between delete-propagation and causality. More precisely, we show that: (a) Most-responsible causes and view-conditioned causes can obtained from solutions to different variants of the delete-propagation problem and vice-versa. (b) Computing the size of the solution to a minimum source-side-effect problem is hard for F P NP(log(n)). (c) Deciding weather an answer has a viewconditioned cause is NP-complete. (d) We can identify some new classes of queries for which computing minimum source-side-effect delete-propagation is tractable. 1
PRELIMINARIES AND CAUSALITY DECISION PROBLEMS We consider relational database schemas of the form S = (U, P ), where U is the possibly infinite database domain and P is a finite set of database predicates4 of fixed arities. A database instance D compatible with S can be seen as a finite set of ground atomic formulas (in databases aka. atoms or tuples), of the form P (c1, ..., cn), where P ∈ P has arity n, and the constants c1, . . . , cn ∈ U .
A conjunctive query (CQ) is a formula Q(x¯) of the firstorder (FO) language L(S) associated to S of the form ∃y¯(P1(s¯1) ∧ · · · ∧ Pm(s¯m)), where the Pi(s¯i) are atomic formulas, i.e. Pi ∈ P , and the s¯i are sequences of terms, i.e. variables or constants of U . The x¯ in Q(x¯) shows all the free variables in the formula, i.e. those not appearing in y¯. A sequence c¯ of constants is an answer to query Q(x¯) if D |= Q[c¯], i.e. the query becomes true in D when the variables are replaced by the corresponding constants in c¯. We denote the set of all answers to an open conjunctive query Q(x¯) with Q(D).
A conjunctive query is boolean (a BCQ), if x¯ is empty, i.e. the query is a sentence, in which case, it is true or false in D, denoted by D |= Q and D |= Q, respectively. When Q is a BCQ, or contains no free variables, Q(D) = {yes } if Q is true, and Q(D) = ∅, otherwise.
A query Q is monotone if for every two instances D 1 ⊆
D2, Q(D1) ⊆ Q(D2), i.e. the set of answers grows
monotonically with the instance. For example, CQs and unions
of CQ (UCQs) are monotone queries. Datalog queries
4As opposed to built-in predicates (e.g. =) that we assume do not appear, unless explicitly stated otherwise. In the rest of this work, unless otherwise stated, we will assume that a database instance D is split in two disjoint sets, D = Dn ∪ Dx, where Dn and Dx denote the sets of endogenous and exogenous tuples, respectively; and Q is a monotone query.
Definition 1.1. A tuple τ ∈ Dn is a counterfactual cause for an answer a¯ to Q in D if D |= Q(a¯) and D {τ } |= Q(a¯). A tuple τ ∈ Dn is an actual cause for a¯ if there exists Γ ⊆ Dn, called a contingency set, such that τ is a counterfactual cause for a¯ in D Γ.
Causes(D, Q(a¯)) denotes the set of actual causes for a¯. This set is non-empty on the assumption that Q(a¯) is true in D. When the query Q is boolean, Causes (D, Q) contains the causes for the answer yes in D.
The definition of query-answer causality can be applied without any conceptual changes to Datalog queries. In the case of a Datalog, the query Q(x¯) is a whole program Π that accesses an underlying extensional database E that is not part of the query. Program Π contains a rule that defines a top answer-collecting predicate Ans(x¯). Now, a¯ is an answer to query Π on E when Π ∪ E |= Ans(a¯). Here, entailment (|=) means that the RHS belongs to the minimal model of the LHS. A Datalog query is boolean if the top answer-predicate is propositional, say ans . In the case of Datalog, we sometimes use the notation Causes (E, Π(a¯)) or Causes(E, Π), depending on whether Π has a Ans(x¯) or ans as answer predicate, resp.
Given a τ ∈ Causes (D, Q(a¯)), we collect all subsetminimal contingency sets associated with τ : Cont (D, Q(a¯), τ ) := {Λ ⊆ Dn | D
D ∀Λ
Λ |= Q(a¯), (Λ ∪ {τ }) |= Q(a¯), and Λ, D (Λ ∪ {τ }) |= Q(a¯)}.
The responsibility of actual cause τ for answer a¯, denoted ρQ(a¯)(τ ), is (|Γ|1+1) , where |Γ| is the size of the smallest contingency set for τ . Responsibility can be extend to all tuples in Dn by setting their value to 0, and they are not actual causes for Q.
Example 1.1. Consider a database D with relations Author(Name,Journal) and Journal(JName,Topic,#Paper), and contents as below:
Author
Name Joe John Tom John
JName TKDE TKDE TKDE TODS
Journal
JName TKDE TKDE TODS
Topic XML CUBE XML #Paper 30 31 32
Q(Name, Topic) : ∃Journal JName #Paper(Author(Name,JName) ∧ Journal(JName,Topic,#Paper), (1) which has the following answers: Q(D)
Name Joe Joe Tom Tom John John Assume John, XML is an unexpected answer to Q, and we want to compute its causes assuming that all tuples are endogenous.
It turns out that Author(John, TODS) is an actual cause, with contingency sets Γ1 = {Author(John, TKDE)} and Γ2={Journal(TKDE, XML, 32)}, because Author(John, TODS) is a counterfactual cause for answer John, XML in both of D Γ1 and D Γ2. Therefore, the responsibility of Author(John, TODS) is 12 . Likewise, Journal(TKDE, XML, 32), Author(John, TKDE), Journal(TODS,XML, 32) are actual causes for John, XML with responsibility 12 .
Now, under the assumption that the tuples in Journal are the endogenous tuples, the only actual causes for answer John, XML are Author(John, TKDE) and Author(John, TODS).
A Datalog query Q(x¯) is a whole program Π consisting of positive rules that accesses an underlying extensional database E that is not part of the query. Program Π contains a rule that defines a top answer-collecting predicate Ans(x¯), by means of a rule of the form Ans(x¯) ← P1(s¯1), . . . , Pm(s¯m). Now, a¯ is an answer to query Π on E when Π ∪ E |= Ans(a¯). Here, entailment (|=) means that the RHS belongs to the minimal model of the LHS. So, the extension Ans(D) of Ans in the minimal model of the program contains the answers to the query.
A Datalog query is boolean if the top answer-predicate is
propositional, say ans , i.e. defined by a rule of the form
ans ← P1(s¯1), . . . , Pm(s¯m). In this case, the query is true
if Π∪D |= ans , equivalently, if ans belongs to the minimal
model of Π ∪ E
Author(Name,JName),
Journal(JName,Topic,#Paper).
The definition of query-answer causality can be
applied without any conceptual changes to Datalog queries.
In the case of Datalog, we sometimes use the
notation Causes(E, Π(a¯)) or Causes(E, Π), depending on
whether Π has a Ans(x¯) or ans as answer predicate, resp.
In
The complexity of the computational and decision
problems that arise in query causality have been investigated in
Dn, and τ
∈
This problem is tractable for UCQs
Definition 1.3. For a boolean monotone query Q, the responsibility decision problem (RDP) is (deciding about membership of): RDP (Q) = {(D, τ, v) | τ ∈ Dn, v ∈ {0} ∪
{ k1 | k ∈ N+}, D |= Q and ρQ(τ ) > v}.
This problem is NP-complete for UCQs
Finally, we have the problem of deciding weather a tuple is a most responsible cause: Definition 1.4. For a boolean monotone query Q, the most responsible cause decision problem (MRDP) is: MRCD(Q) = {(D, τ ) | τ ∈ Dn and
0 < ρQ(τ ) is a maximum for D}.
For UCQs this problem is complete for P NP(log(n))
A form of conditional causality was informally introduced
in
Consider an instance D = Dn ∪ Dx, and a monotone query Q with Q(D) = {a¯1, . . . a¯n}. Fix an answer, say a¯k ∈ Q(D), while the other answers will be used as a condition on a¯k’s causality. Intuitively, a¯k is somehow unexpected, and we look for causes, by considering the other answers as “correct”. The latter assumption has, in technical terms, the effect of reducing the spectrum of contingency sets, by keeping Q(D)’s extension fixed, as a view, modulo the answer a¯k at hand.
Definition 1.5. (a) A tuple τ ∈ Dn is called a viewconditioned counterfactual cause (VCC-cause) for answer a¯k to Q if D {τ } |= Q(a¯k) and D {τ } |= Q(a¯i), for i ∈ {1, . . . , n} {k}. (b) A tuple τ ∈ Dn is an view-conditioned actual cause (VC-cause) for a¯k if there exists a contingency set, Γ ⊆ Dn, such τ is a VCC-cause for a¯k in D Γ. (c) vc-Causes(D, Q(a¯k)) denotes the set of all VC causes for a¯k.
Intuitively, a tuple τ is a VC-cause for a¯k if there is a contingent state of the database that entails all the answers to Q and τ is a counterfactual cause for a¯k, but not for the rest of the answers. Obviously, VC-causes for a¯k are also actual causes, but not necessarily the other way around: vc-Causes(D, Q(ak)) ⊆ Causes (D, Q(ak)).
Example 1.2. (ex. 1.1 cont.) Consider the same instance D, query Q, and the answer John, XML , which does not have any VC-cause. To see this, take for example, the tuple Author(John, TODS) that is an actual cause for John, XML , with two contingency sets, Γ1 and Γ2. It is easy to verify that none of these contingency sets satisfies the condition in Definition 1.5, e.g. the original answer John, CUBE is not such anymore from D Γ1. The same argument can be applied to all actual causes for John, XML .
This example shows that it makes sense to study the complexity of deciding whether a query answer has a VC-actual cause or not.
Definition 1.6. For a monotone query Q, the viewconditioned cause problem is (deciding about membership of): V CP(Q) = {(D, a¯) | a¯ ∈ Q(D) and
vc-Causes(D, Q(a¯)) = ∅ }. 2
In general logical terms, an abductive explanation of an
observation is a formula that, together with the background
logical theory, entails the observation. So, one could see an
abductive explanation as a cause for the observation.
However, it has been argued that causes and abductive
explanations are not necessarily the same
Under the abductive approach to diagnosis
In database causality we do not have, at least not initially, a system description,6 but just a set of tuples. It is when we pose a query that we create something like a description, and the causal relationships between tuples are captured by the combination of atoms in the query. If the query is a Datalog query (in particular, a CQ), then we have a Horn specification too.
In this section we will establish connections between abductive diagnosis and database causality.7 For that, we have to be more precise about the kind of abduction problems we will consider. 2.1
BACKGROUND ON DATALOG ABDUCTIVE
DIAGNOSIS
A Datalog abduction problem
The abduction problem is about computing a minimal Δ ⊆
Hyp (under certain minimality criterion), such that Π ∪ E ∪
Δ |= Obs. More specifically:
Definition 2.1. Consider a Datalog abduction problem
AP = Π, E, Hyp, Obs
(a) An abductive diagnosis (or simply, a solution) for AP
is a subset-minimal Δ ⊆ Hyp, such that Π ∪ E ∪ Δ |=
Obs. This requires that no proper subset of Δ has this
6Having integrity constraints would go in that direction, but
we are not considering their presence in this work. However, see
7In
8It is common to accept as hypothesis all the possible ground instantiations of abducible predicates. We assume abducible predicates do not appear in rule heads. property. Sol (AP ) denotes the set of abductive diagnoses for problem AP. (b) A hypothesis h ∈ Hyp is relevant for AP if h contained in at least one diagnosis of AP. Rel (AP ) collects all relevant hypothesis for AP .
We are interested in deciding, for a fixed Datalog program, if an hypothesis is relevant or not, with all the data as input. More precisely, we consider the following decision problem.
Definition 2.2. Given a Datalog program Π, the relevance decision problem (RLDP) for Π is (deciding about the membership of): RLDP (Π) = {(E , Hyp, Obs , h) | h ∈ Rel (AP ), with
AP = Π, E, Hyp, Obs and h ∈ Hyp}.
As it is common, we will assume that |Obs |, i.e. the number of atoms in the conjunction, is bounded above by a numerical parameter p. It is common that p = 1 (a single atomic observation).
Definition 2.2 suggests that we are interested in the data complexity of the relevance problem for Datalog abduction. That is, the Datalog program is fixed and hypotheses and input structure may change and maybe regarded as data. In contrast, under combined complexity the program is also part of the input, and the complexity is measured also in terms of the program size.
The following result is obtained by showing that the NP
complete combined complexity of the relevance problem
for Propositional Datalog Abduction (PDA) (established in
Proposition 2.1. For every Datalog program
RLDP (Π) ∈ NP , and there are programs Π
which RLDP (Π ) is NP-hard.
Π,
for
It is clear from this result that the combined complexity
of deciding relevance for Datalog abduction is also
intractable. However, a tractable case of combined
complexity is identified in
Let H = V, H be a hypergraph. V is the set of vertices, and H the set of hyperedges, i.e. of subsets of V . A treedecomposition T of H is a pair (T , λ), where T = N, E is a tree and λ is a labeling function that assigns to each node n ∈ N , a subset λ(n) of V (λ(n) is aka. bag), i.e. λ(n) ⊆ V , such that, for every node n ∈ N , the following hold: (a) For every v ∈ V , there exists n ∈ N with v ∈ λ(n). (b) For every h ∈ H, there exists a node n ∈ N John Joe TKDE
XML Tom (a)
CUBE 30 32 31
John, TODS, TKDE, XML, 30, 32 Joe, TKDE Tom, TKDE
TKDE, CUBE, 31 (b) with h ⊆ λ(n). (c) For every v ∈ V , the set of nodes {n | v ∈ λ(n)} induces a connected subtree of T . The width of a tree decomposition (T , λ) of H = V, H , with T = N, E , is defined as max {|λ(n)|−1 : n ∈ N }. The tree-width tw(H) of H is the minimum width over all its tree decompositions.
Intuitively, the tree-width of a hypergraph H is a measure
of the “tree-likeness” of H. A set of vertices that form a
cycle in H are put into a same bag, which becomes (the
bag of a) node in the corresponding tree-decomposition.
If the tree-width of the hypergraph under consideration
is bounded by a fixed constant, then many otherwise
intractable problems become tractable
Example 2.1. Consider instance D in Example 1.1. The hypergraph H(D) associated to D is shown in Figure 1(a). Its vertices are the elements of adom (D) = {John, Jone, Tom, TODS , TKDE , XML, Cube, 30 , 31 , 32 }, the active domain of D. For example, since Journal (TKDE , XML, 30 ) ∈ D, {TKDE , XML, 30 } is one of the hyperedges.
The dashed ovals show four sets of vertices, i.e. hyperedges, that together form a cycle. Their elements are put into the same bag of the tree-decomposition. Figure 1(b) shows a possible tree-decomposition of H(D). In it, the maximum |λ(n)| − 1 is 6 − 1, corresponding to the top box bag of the tree. So, tw(H(D)) ≤ 5.
The following is a fixed-parameter tractability result for the relevance decision problem for Datalog abduction problems with a program Π that is guarded, which means that in every rule body there is an atom that contains (guards) all the variables appearing in that body.
Theorem 2.2.
More precisely, the decision problem: RLDP = {( Π, E , Hyp, Obs , h) | h ∈ Rel ( Π, E , Hyp, Obs ), h ∈ Hyp, Π is guarded, and tw(H(E)) ≤ k} is tractable. This is a case of tractable combined complexity with a fixed parameter that is the tree-width of the extensional database. In this section we first show that, for the class of Datalog theories (system specifications), abductive inference corresponds to actual causation for monotone queries. That is, abductive diagnoses for an observation essentially contain actual causes for the observation.
Assume that Π is a boolean, possibly recursive Datalog query. Consider the relational instance D = D x ∪ Dn. Also assume that Π ∪ D |= ans . So, the decision problem in Definition 1.2 takes the form CDP(Π) := {(D, τ ) | τ ∈ Dn, and τ ∈ Causes(D, Π)}.
We now show that actual causes for ans can be obtained from abductive diagnoses of the associated causal Datalog abduction problem (CDAP): AP c := Π, Dx, Dn, ans , where Dx is the extensional database for Π (and then Π ∪ Dx becomes the background theory), D n becomes the set of hypothesis, and atom ans is the observation.
Proposition 2.3. t ∈ Dn is an actual cause for ans iff t ∈ Rel (AP c).
Example 2.2. Consider the instance D with relations R and S as below, and the query Π : ans ← R(x, y), S(y), which is true in D. Assume all tuples are endogenous.
R
X AP c = Π, ∅, D, ans has two (subset-minimal) abductive diagnoses: Δ1 = {S(a1), R(a2, a1)} and Δ2 = {S(a3), R(a3, a3)}. Then, Rel (AP c) = {S(a3), R(a3, a3), S(a1), R(a2, a1)}. It is easy to see that the relevant hypothesis are actual causes for ans .
We are interested in obtaining responsibilities of actual causes for ans .
Definition 2.3. Given a CDAP, AP c = Π, Dx, Dn, ans , with Sol (AP c) = ∅, N ⊆ Dn is a necessary-hypothesis set if N is subset-minimal such that Sol (AP cN ) = ∅, with AP cN := Π, Dx, Dn N, ans .
Proposition 2.4. The responsibility of a tuple t for ans is |N1 | , where N is a necessary-hypothesis set with minimum cardinality for AP c and t ∈ N .
In order to represent Datalog abduction in terms of queryanswer causality, we show that abductive diagnoses from Datalog programs are formed essentially by actual causes for the observation.
More precisely, consider a Datalog abduction problem AP = Π, E, Hyp, Obs , where E is the underlying extensional database, and Obs is a conjunction of ground atoms. Now we construct a query-causality setting: D := D x ∪ Dn, Dx := E, and Dn := Hyp. Consider the program Π := Π ∪ {ans ← Obs } (with ans a fresh propositional atom). So, Π is seen as a monotone query on D. Proposition 2.5. A hypothesis h is relevant for AP , i.e. h ∈ Rel (AP ), iff h is an actual cause for ans wrt. Π , D. Now we will use the results obtained so far in this section to obtain new complexity results for Datalog query causality. Actually, the following result is obtained from Propositions 2.1 and 2.3: Proposition 2.6. For boolean Datalog queries Π, CDP(Π) is NP-complete (in data).
This result should be contrasted with the tractability of
same problem for UCQs
There is a close relationship between query causality and
the view-update problem in the form of delete-propagation,
which was first suggested in
Given a monotone query Q, we can think of it as defining a
view with virtual contents Q(D). If a¯ ∈ Q(D), which may
not be intended, we may try to delete some tuples from D,
so that a¯ disappears from Q(D). This is a common case of
the problem of database updates through views
Definition 3.1. For an instance D, and a monotone query Q: (a) For a¯ ∈ Q(D), the minimal source-side-effect problem is about computing a subset-minimal Λ ⊆ D, such that a¯ ∈/ Q(D Λ). (b) The minimal source-side-effect decision problem is (deciding about the membership of): MSSE P s(Q) = {(D, D , a¯) | a¯ ∈ Q(D), D ⊆ D, a¯ ∈ Q(D ), and D is subset-maximal}.
(The superscript s stands for subset-minimal.)
(c) For a¯ ∈ Q(D), the minimum source side-effect
problem is about computing a minimum-cardinality Λ ⊆
D, such that a¯ ∈/ Q(D Λ).
(d) The minimum source side-effect decision problem is
(deciding about the membership of):
MSSE P c(Q) = {(D, D , a¯) | a¯ ∈ Q(D), D ⊆ D,
a¯ ∈/ Q(D ), and D has maximum cardinality}.
(Here c stands for minimum cardinality.)
Definition 3.2.
D ⊆ D with Q(D) {a¯} = Q(D )}. 3.2
In this section we first establish mutual reductions between the different variants of the delete propagation problem and both query and view-conditioned causality. On this basis, we obtain next some complexity results for viewconditioned causality and the minimum source-side-effect problem.
In this section all tuples in the instances involved are assumed to be endogenous. Consider a relational database D, a view V defined by a monotone query Q. So, the virtual view extension, V (D), is Q(D).
For a tuple a¯ ∈ V (D), the delete-propagation problem, in its most general form, is the task of deleting a set of tuples from D, and so obtaining a subinstance D of D, such that a¯ ∈/ V (D ). It is natural to expect that the deletion of a¯ from the view can be achieved through deletions from D of the causes for a¯ to be in the view extension. However, to obtain solutions to the different variants of this problem introduced in Section 3.1, different sets of actual causes must be considered.
First, we show that an actual cause for a¯ to be in V (D) forms, with any of its contingency sets, a solution to the minimal source-side-effect problem (cf. Definition 3.1). Proposition 3.1. Consider an instance D, a view V defined by a monotone query Q, and a¯ ∈ V (D): D ⊆ D is a solution to the minimal source-side-effect problem, i.e. (D, D , a¯) ∈ MSSE P s(Q), iff there is a t ∈ D D , such that t ∈ Causes (D, Q(a¯)) and D (D ∪ {t}) ∈ Cont (D, Q(a¯), t).
Now we show that, in order to minimize the side-effect on the source (cf. Definition 3.1(c)), it is good enough to pick a most responsible cause for a¯ with any of its minimumcardinality contingency sets.
Proposition 3.2. Consider an instance D, a view V defined by a monotone query Q, and a¯ ∈ V (D): D ⊆ D is a solution to the minimum source-side-effect problem, i.e. (D, D , a¯) ∈ MSSE P c(Q), iff there is a t ∈ D D , such that t ∈ MRC(D, Q(a¯)), Λ := D (D ∪ {t}) ∈ Cont (D, Q(a¯), t), and there is no Λ ∈ Cont (D, Q(a¯), t) with |Λ | < |Λ|.
Next, we show that in order to check if there exists a solution to the view side-effect-free problem for a¯ ∈ V (D) (cf. Definition 3.2), it is good enough to check if a¯ has a view-conditioned cause.10 Proposition 3.3. Consider an instance D, a view V defined by a monotone query Q, and a¯ ∈ V (D): There is a solution to the view side-effect-free problem for a¯, i.e. (D, a¯) ∈ V SE F P (Q), iff vc-Causes (D, Q(a¯)) = ∅.
Example 3.1. (ex. 1.1 cont.) Consider the same instance D, query Q, and answer John, XML .
S1={ Author(John, TKDE), Journal(TODS, XML, 32)}, S2={ Author(John, TODS), Journal(TKDE, XML, 30)}, S3={ Journal(TODS, XML, 30), Journal(TKDE, XML, 30)}, S4={ Author(John, TODS), Author(John, TKDE)}.
Each of the subinstances D Si, i = 1, . . . , 4, is a solution to both the minimum and minimal source-side-effect problems. These solutions essentially contain the actual causes for answer John, XML , as computed in Example 1.1. Moreover, there is no solution to the view sideeffect-free problem associated to this answer, which coincides with the result obtained in Example 1.2, and confirms Proposition 3.3.
Now we show, the other way around, that actual causes, most responsible causes, and VC causes can be obtained from solutions to different variants of the deletepropagation problem.
First, we show that actual causes for a query answer can be obtained from the solutions to the corresponding minimal source-side-effect problem.
Proposition 3.4. Consider an instance D, a view V defined by a monotone query Q, and a¯ ∈ V (D): Tuple t is an actual cause for a¯ iff there is a D ⊆ D with t ∈ (D D ) ⊆ Dn and (D, D , a¯) ∈ MSSE P s(Q).
Similarly, most-responsible causes for a query answer can be obtained from solutions to the corresponding minimum source-side-effect problem.
Proposition 3.5. Consider an instance D, a view V defined by a monotone query Q, and a¯ ∈ V (D): Tuple t is a most responsible actual cause for a¯ iff there is a D ⊆ D with t ∈ (D D ) ⊆ Dn and (D, D , a¯) ∈ MSSE P c(Q). Finally, VC-causes for an answer can obtained from solutions to the view side-effect-free problem.
Proposition 3.6. Consider an instance D, a view V defined by a monotone query Q, and a¯ ∈ V (D): Tuple t is a VCcause for a¯ iff there is a D ⊆ D with t ∈ (D D ) ⊆ Dn and D is a solution to the view side-effect-free problem associated to a¯.
The partition of a database into endogenous and exogenous tuples used in causality may also be of interest in the context of delete propagation. It makes sense to consider endogenous delete-propagation that are obtained through deletions on endogenous tuples only. Actually, given an instance D = Dn ∪ Dx, a view V defined by a monotone query Q, and a¯ ∈ V (D), endogenous delete-propagations for a¯ (in all of its flavors) can be obtained from actual causes for a¯ from the partitioned instance.
Example 3.2. (ex. 3.1 cont.) Consider again that tuple John, XML must be deleted from the query result; and assume now the data in Journal is reliable. Therefore, only deletions from Author make sense. This can be captured by considering Journal-tuples as exogenous and Author-tuples as endogenous. With this partitioning, only Author(John, TODS) and Author(John, TKDE) are actual causes for John, XML , and each of them forms a singleton and unique contingency set of the other as a cause (See Exampleex:cfex1). Therefore, D {Author(John, TODS), Author(John, TKDE)} is a solution to the associated minimal- and minimum endogenous deletepropagation of John, XML .
We now investigate the complexity of the view-conditioned
causality problem (cf. Definition 1.6). For this, we take
advantage of the connection between VC-causality and the
view side-effect-free problem. Actually, the following
result is obtained from the NP-completeness of view
sideeffect-free problem
Proposition 3.7. For CQs, the view-conditioned causality decision problem, V CP, is NP-complete.
Actually, this result also holds for UCQs. The next result is
obtained from the FP NP(log(n))-completeness of
computing the responsibility of the most responsible causes
(obtained in
As mentioned in Section 1.1, responsibility computation
(more precisely the RDP problem in Definition 1.3) is
tractable for weakly linear queries. We can take
advantage of this result and obtain, via Proposition 3.2, a new
tractability result for the minimum source-side-effect
problem, which has been shown to be NP-hard for general CQs
in
Proposition 3.9. For weakly linear queries, the minimum source-side-effect decision problem is tractable. The class of weakly linear queries generalizes that of linear queries (cf. Section 1.1). So, Proposition 3.9 also holds for linear queries.
In
We observe that project-join queries with chain joins
correspond linear queries. Actually, the tractability results
for these classes of queries are both obtained via a
reduction to maximum flow problem
We have related query causality to abductive diagnosis and
the view-update problem. Some connections between the
last two have been established before. More precisely, the
view-update problem has been treated from the point of
view of abductive reasoning
In combination with the results reported in
Even more, in
Finally, we should note that abduction has also been
explicitly applied to database repairs
Acknowledgments: Research funded by NSERC Discovery, and the NSERC Strategic Network on Business Intelligence (BIN).