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 (Meliou et al., 2010a), on the basis of the deeper concept of actual causation. 1 Intuitively, a 1 In contrast with general causal claims, such as "smoking tuple (of constants) t is an actual cause for an answer ā to a conjunctive query Q from a relational database instance D if there is a "contingent" subset of tuples Γ, accompanying t, such that, after removing Γ from D, removing t from D Γ causes ā to switch from being an answer to being a non-answer (i.e. not being an answer). Usually, 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.

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 (Meliou et al., 2010a). It reflects the relative degree of actual causality. In applications involving large data sets, it is crucial to rank potential causes according to their responsibilities (Meliou et al., 2010b,a). Furthermore, view-conditioned causality was proposed in (Meliou et al., 2010b(Meliou et al., , 2011) ) as a restricted form of query causality, to determine causes for a set of unexpected query results, but conditioned to the correctness of prior knowledge about some other set of results.

Actual causation, as used in (Meliou et al., 2010a(Meliou et al., ,b, 2011)), can be traced back to (Halpern & Pearl, 2001, 2005), which provides a model-based account of causation on the basis of counterfactual dependence. 2 Causal responsibility was introduced in Chockler & Halpern (2004), to provide a graded, quantitative notion of causality when multiple causes may over-determine an outcome.

Model-based diagnosis (Struss, 2008, sec. 10.3), an area of causes cancer", which refer some sort of related events, actual causation specifies a particular instantiation of a causal relationship, e.g., "Joe's smoking is a cause for his cancer". 2 As discussed in (Salimi & Bertossi, 2015), some objections to the Halpern-Pearl model of causality and the corresponding changes (Halpern, 2014(Halpern, , 2015) ) do not affect results in the context of databases. knowledge representation, addresses the problem of, given the specification of a system in some logical formalism and a usually unexpected observation about the system, obtaining explanations for the observation, in the form of a diagnosis for the unintended behavior. Since this and causality are related to explanations, a first connection between causality and consistency-based diagnosis (Reiter, 1987), a form of model-based diagnosis, was established in (Salimi & Bertossi, 2014, 2015): Causality and the responsibility problem can be formulated as consistency-based diagnosis problems, which allowed to extend the results in (Meliou et al., 2010a). However, no precise connection has been established so far between causality and abductive diagnosis (Console et al., 1991;Eiter & Gottlob, 1995), another form of model-based diagnosis.

The definition of causality for query answers applies to monotone queries (Meliou et al., 2010a,b). However, all complexity and algorithmic results in (Meliou et al., 2010a;Salimi & Bertossi, 2015) have been restricted to first-order (FO) monotone queries. Other important classes of monotone queries, such as Datalog queries (Ceri et al., 1989;Abiteboul et al., 1995), possibly with recursion, require further investigation.

In (Salimi & Bertossi, 2015) connections were established between query causality, database repairs (Bertossi, 2011), and consistency-based diagnosis. In particular, complexity results for several causality problems were obtained from the repair connection. In the line of this kind of research, in this work we unveil natural connections between actual causation and abductive diagnosis, and also the viewupdate problem in databases (more on this latter connection later in the section).

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 (Denecker & Kakas, 2002;Eiter et al., 1997;Gottlob et al., 2010b). Since Datalog can be seen as a form of LP, we manage to extend and formulate the notion of query-answer causality to Datalog queries via the abductive diagnosis connection, in this way extending causality to a new class of queries, e.g. recursive queries, and obtaining complexity results on causality for them.

Abductive reasoning/diagnosis has been applied to the view update problem in databases (Kakas & Mancarella, 1990;Console et al., 1995), which is about characterizing and computing updates of physical database relations that give an account of (or have as result) the intended updates on views. The idea is that abductive diagnosis provides (abduces) the reasons for the desired view updates, and they are given as changes on base tables.

In this work we also explore fruitful connections of causality with this view-update problem (Abiteboul et al., 1995), i.e. about updating a database through views. An important aspect of the problem is that one want the base, source database, i.e. the base relations, to change in a minimally way while still producing the view updates. Put in different terms, it is an update propagation problem, from views to base relations. This classical and important problem in databases.

The delete-propagation problem (Buneman et al., 2002;Kimelfeld, 2012;Kimelfeld et al., 2012) is a particular case of the view-update problem where only tuple deletions are allowed on/from the views. If the views are defined by monotone queries, only database deletions can give an account of view deletions. So, in this case, a minimal set (in some sense) of deletions from the base relations is expected to be performed. This is "minimal source-side-effect" case. It is also possible to consider minimizing the side-effect on the view, which also requires that other tuples in the (virtual) view contents are not affected (deleted) (Buneman et al., 2002).

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 (Salimi & Bertossi, 2015); and also that the "minimal view sideeffect problem" is related to view-conditioned causality we already mentioned above.

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.

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 (c 1 , ..., c n ), where P ∈ P has arity n, and the constants c 1 , . . . , c n ∈ U .

A conjunctive query (CQ) is a formula Q(x) of the firstorder (FO) language L(S) associated to S of the form ∃ȳ(P 1 (s 1 ) ∧

e. the set of answers grows monotonically with the instance. For example, CQs and unions of CQ (UCQs) are monotone queries. Datalog queries (Ceri et al., 1989;Abiteboul et al., 1995), although not FO, are also monotone (cf. Section 1.1 for more details).

In the rest of this work, unless otherwise stated, we will assume that a database instance D is split in two disjoint sets, D = D n ∪ D x , where D n and D x denote the sets of endogenous and exogenous tuples, respectively; and Q is a monotone query.

denotes the set of actual causes for ā. This set is non-empty on the assumption that Q(ā) 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, ā is an answer to query Π on E when Π ∪ E |= Ans(ā). 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, Π(ā))

or Causes(E, Π), depending on whether Π has a Ans(x)

or ans as answer predicate, resp.

Given a τ ∈ Causes(D, Q(ā)), we collect all subsetminimal contingency sets associated with τ :

The responsibility of actual cause τ for answer ā, denoted

, where |Γ| is the size of the smallest contingency set for τ . Responsibility can be extend to all tuples in D n by setting their value to 0, and they are not actual causes for Q. which has the following answers:

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 1 2 . Likewise, Journal (TKDE,XML,32), Author(John, TKDE), Journal (TODS,XML,32) are actual causes for John, XML with responsibility 1 2 . 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

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) ← P 1 (s 1 ), . . . , P m (s m ). Now, ā is an answer to query Π on E when Π ∪ E |= Ans(ā). 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 ← P 1 (s 1 ), . . . , P m (s m ). In this case, the query is true if Π∪D |= ans, equivalently, if ans belongs to the minimal model of Π ∪ E (Ceri et al., 1989;Abiteboul et al., 1995).

CQs can be expressed as Datalog queries, e.g. (1) becomes:

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, Π(ā)) or Causes(E, Π), depending on whether Π has a Ans(x) or ans as answer predicate, resp.

In (Meliou et al., 2010a), causality for non-query answers is defined on basis of sets of potentially missing tuples that account for the missing answer. Computing actual causes and their responsibilities for non-answers becomes a rather simple variation of causes for answers. In this work we focus on causality for query answers.

The complexity of the computational and decision problems that arise in query causality have been investigated in (Meliou et al., 2010a;Salimi & Bertossi, 2015). Here we present some problems and results that we use throughout this paper. The first is the causality problem, about deciding whether a tuple is an actual cause for a query answer. Definition 1.2. For a boolean monotone query Q, the causality decision problem (CDP) is (deciding about membership of):

This problem is tractable for UCQs (Salimi & Bertossi, 2015). The next is the responsibility problem, about deciding responsibility (above a given bound) of a tuple for a query result.

Definition 1.3. For a boolean monotone query Q, the responsibility decision problem (RDP) is (deciding about membership of):

This problem is NP-complete for UCQs (Salimi & Bertossi, 2015), but tractable for linear CQs (Meliou et al., 2010a). Roughly speaking, a CQ is linear if its atoms can be ordered in a way that every variable appears in a continuous sequence of atoms that does not contain a self-join (i.e. a join involving the same predicate), e.g.

for which RDP is NP-complete. The class of CQs for which RDP is tractable can be extended to weakly linear. 5The functional, non-decision version of RDP, about computing the responsibility, i.e. an optimization problem, is complete for FP NP (log(n)) for UCQs (Salimi & Bertossi, 2015).

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:

For UCQs this problem is complete for P NP (log(n)) (Salimi & Bertossi, 2015).

A form of conditional causality was informally introduced in (Meliou et al., 2010b), to characterize causes for a query answer that are conditioned by the other answers to the query. The notion was made precise in (Meliou et al., 2011), in a more general, non-relational setting that in particular includes the case of several queries. In them the notion of view-conditioned causality was used, and we adapt it in the following to the case of a single query, possibly with several answers.

Consider an instance D = D n ∪ D x , and a monotone query Q with Q(D) = {ā 1 , . . . ān }. Fix an answer, say āk ∈ Q(D), while the other answers will be used as a condition on āk 's causality. Intuitively, ā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 āk at hand.

denotes the set of all VC causes for āk .

Intuitively, a tuple τ is a VC-cause for āk if there is a contingent state of the database that entails all the answers to Q and τ is a counterfactual cause for āk , but not for the rest of the answers. Obviously, VC-causes for āk are also actual causes, but not necessarily the other way around:

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):

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 (Psillos, 1996;Denecker & Kakas, 2002).

Under the abductive approach to diagnosis (Console et al., 1991;Eiter & Gottlob, 1995;Poole, 1992Poole, , 1994)), it is common that the system specification rather explicitly describes causality information, specially in action theories where the effects of actions are directly represented by Horn formulas. By restricting the explanation formulas to the predicates describing primitive causes (action executions), an explanation formula which entails an observation gives also a cause for the observation (Denecker & Kakas, 2002). In this case, and is some sense, causality information is imposed by the system specifier (Poole, 1992).

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.

A Datalog abduction problem (Eiter et al., 1997) 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 NPcomplete combined complexity of the relevance problem for Propositional Datalog Abduction (PDA) (established in (Friedrich et al., 1990)), coincides with the data complexity of the relevance problem for (non-propositional) Datalog Abduction. For this, techniques developed in (Eiter et al., 1997) can be used.

Proposition 2.1. For every Datalog program Π, RLDP (Π) ∈ NP, and there are programs Π for which RLDP(Π ) is NP-hard.

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 (Gottlob et al., 2010b), on the basis of the notions of tree-decomposition and bounded tree-width, which we now briefly present.

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

The width of a tree decomposition (T , λ) of

The tree-width t w (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 (Gottlob et al., 2010a). 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. (Gottlob et al., 2010b) Let k be an integer.

For Datalog abduction problems AP = Π, E, Hyp, Obs where Π is guarded, and t w (H(E)) ≤ k, relevance can be decided in polynomial time in |AP|. 9More precisely, the decision problem:

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.

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.

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 ∪ D n , D x := E, and D n := 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:

This result should be contrasted with the tractability of same problem for UCQs (Salimi & Bertossi, 2015).

We now introduce a fixed-parameter tractable case of this problem. For this we take advantage of the tractable case of Datalog abduction presented in Section 2.1. The following is a consequence of Theorem 2.2 and Proposition 2.3. Proposition 2.7. For guarded Datalog queries Π and a extensional instances D = D x ∪ D n , with D x of bounded tree-width, CDP is fixed-parameter tractable in combined complexity, with the parameter being the tree-width bound.

There is a close relationship between query causality and the view-update problem in the form of delete-propagation, which was first suggested in (Kimelfeld, 2012;Kimelfeld et al., 2012) (see also (Buneman et al., 2002)). We start by formalizing some specific computational problems related to the general delete-propagation problem.

Given a monotone query Q, we can think of it as defining a view with virtual contents Q(D). If ā ∈ Q(D), which may not be intended, we may try to delete some tuples from D, so that ā disappears from Q(D). This is a common case of the problem of database updates through views (Abiteboul et al., 1995). In this work we consider some variations of this problem, in both their functional and the decision versions.

Definition 3.1. For an instance D, and a monotone query Q:

(b) The minimal source-side-effect decision problem is (deciding about the membership of):

, and D is subset-maximal}.

(The superscript s stands for subset-minimal.)

(c) For ā ∈ Q(D), the minimum source side-effect problem is about computing a minimum-cardinality Λ ⊆ D, such that ā / ∈ Q(D Λ). (d) The minimum source side-effect decision problem is (deciding about the membership of):

, and D has maximum cardinality}.

(Here c stands for minimum cardinality.)

Definition 3.2. (Buneman et al., 2002) For an instance D, and a monotone query Q:

The view side-effect-free decision problem is (deciding about the membership of):

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 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 ā ∈ 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 ā / ∈ V(D ). It is natural to expect that the deletion of ā from the view can be achieved through deletions from D of the causes for ā 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 ā 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 ā ∈ V(D): D ⊆ D is a solution to the minimal source-side-effect problem, i.e.

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 ā with any of its minimumcardinality contingency sets. Next, we show that in order to check if there exists a solution to the view side-effect-free problem for ā ∈ V(D) (cf. Definition 3.2), it is good enough to check if ā has a view-conditioned cause.10 Each of the subinstances D S i , 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. Similarly, most-responsible causes for a query answer can be obtained from solutions to the corresponding minimum source-side-effect problem. 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 = D n ∪ D x , a view V defined by a monotone query Q, and ā ∈ V(D), endogenous delete-propagations for ā (in all of its flavors) can be obtained from actual causes for ā 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 (Buneman et al., 2002) and Proposition 3.3. Proposition 3.7. For CQs, the view-conditioned causality decision problem, VCP, 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 (Salimi & Bertossi, 2015)) and Proposition 3.2. Proposition 3.8. Computing the size of a solution to the minimum source-side-effect problem is FP NP (log(n))hard.

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 (Buneman et al., 2002). 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 (Buneman et al., 2002) it has been shown that the minimum source-side-effect decision problem is tractable for the class of project-join queries with chain joins. Now, a join on k atoms with different predicates, say R 1 , ..., R k , is a chain join if there are no attributes (variables) shared by any two atoms R i and R j with j > i + 1. That is, only consecutive relations may share attributes. For example, ∃xvyu(A(x) ∧ S 1 (x, v) ∧ S 2 (v, y) ∧ R(y, u) ∧ S 3 (y, z)) is a project-join query with chain joins.

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 (Meliou et al., 2010a;Buneman et al., 2002). As a consequence, the result in Proposition 3.9 extends that in (Buneman et al., 2002), from linear queries to weakly-linear queries. For example, ∃xyz(R(x, y) ∧ S(y, z) ∧ T (z, x) ∧ V (x)) is not linear (then, nor with chain joins), but it is weakly linear (Meliou et al., 2010a).

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 (Kakas & Mancarella, 1990;Console et al., 1995). The idea is to "abduce" the presence of tuples in the base tables that explain the presence of those tuples in the view extension that one would like, e.g. to get rid of.

In combination with the results reported in (Salimi & Bertossi, 2015), we can see that there are deeper and multiple connections between the areas of query causality, abductive and consistency-based diagnosis, view updates, and database repairs. Results for any of these areas can be profitably applied to the others. 11We point out that database repairs are related to the viewupdate problem. Actually, answer set programs (ASPs) (Brewka et al., 2011) for database repairs (Bertossi, 2011) implicity repair the database by updating conjunctive combinations of intentional, annotated predicates. Those logical combinations -views after all-capture violations of integrity constraints in the original database or along the (implicitly iterative) repair process (a reason for the use of annotations).

Even more, in (Bertossi & Li, 2013), in order to protect sensitive information, databases are explicitly and virtually "repaired" through secrecy views that specify the information that has to be kept secret. In order to protect information, a user is allowed to interact only with the virtually repaired versions of the original database that result from making those views empty or contain only null values. Repairs are specified and computed using ASP, and an explicit connection to prioritized attribute-based repairs (Bertossi, 2011) is made (Bertossi & Li, 2013).

Finally, we should note that abduction has also been explicitly applied to database repairs (Arieli et al., 2004). The idea, again, is to "abduce" possible repair updates that bring the database to a consistent state.