Reconciling Consistency-Based Diagnosis with Actual-Causality-Based Explanations

# Reconciling Consistency-Based Diagnosis with Actual-Causality-Based Explanations††thanks: Dedicated to the memory of Joseph Y. Halpern, a great scholar, a universal researcher.
Source: [https://arxiv.org/html/2605.08688](https://arxiv.org/html/2605.08688)
Leopoldo Bertossi Carleton UniversityCanada & IMFDChile

###### Abstract

We establish, from the point of view of Explainable AI \(XAI\), connections between Consistency\-Based Diagnosis \(CBD\), on one side, and Actual Causality and Causal Responsibility, on the other\. CBD has received little attention from the XAI community\. Connections between these two areas could have a fruitful impact on XAI and Explainable Data Management\.

## 1Introduction

Explainable AI \(XAI\), and in particular Explainable Machine Learning, have become relevant areas of research in AI\.Actual Causality, first proposed by Joe Halpern and Judea Pearl\[[17](https://arxiv.org/html/2605.08688#bib.bib17)\], andCausal Responsibility, first proposed by Hana Chockler and Joe Halpern\[[14](https://arxiv.org/html/2605.08688#bib.bib14)\], have been applied in XAI, to provide explanations for outcomes from machine\-learning \(ML\) models\[[6](https://arxiv.org/html/2605.08688#bib.bib6),[7](https://arxiv.org/html/2605.08688#bib.bib7),[13](https://arxiv.org/html/2605.08688#bib.bib13)\]\. They have also been applied in Explainable Data Management \(XDM\), to provide explanations for query answering\[[22](https://arxiv.org/html/2605.08688#bib.bib22),[4](https://arxiv.org/html/2605.08688#bib.bib4),[5](https://arxiv.org/html/2605.08688#bib.bib5)\]\(see\[[8](https://arxiv.org/html/2605.08688#bib.bib8)\]for a survey of some approaches\)\. Causality has gained prominence in ML, both for explaining and interpreting learned models, but also for learning itself\[[20](https://arxiv.org/html/2605.08688#bib.bib20),[25](https://arxiv.org/html/2605.08688#bib.bib25)\]\.

A more classic area of AI isModel\-Based Diagnosis\(MBD\)\[[26](https://arxiv.org/html/2605.08688#bib.bib26)\]\. It deals with providing explanations for the results from models found in knowledge representation\. One of its prominent forms,Consistency\-Based Diagnosis\(CBD\), proposed by Ray Reiter\[[24](https://arxiv.org/html/2605.08688#bib.bib24)\], is typically applied to obtaindiagnosesfor a system that exhibits an unintended behavior\. CBD has an interesting role to play in XAI\. Abduction, or sufficient explanations, is another form of MBD that has found its way into XAI\[[1](https://arxiv.org/html/2605.08688#bib.bib1),[15](https://arxiv.org/html/2605.08688#bib.bib15),[19](https://arxiv.org/html/2605.08688#bib.bib19),[13](https://arxiv.org/html/2605.08688#bib.bib13)\]; and also in XDM\[[5](https://arxiv.org/html/2605.08688#bib.bib5),[12](https://arxiv.org/html/2605.08688#bib.bib12),[11](https://arxiv.org/html/2605.08688#bib.bib11)\]\. Since there is larger body of recent research on the use of abduction in XAI , we do not consider abduction in this work\. CBD has received much less attention\.

In this work we explore connections between actual causality and CBD\. They haven’t received much attention; and we think the two areas can profit from each other\. Actually, in\[[4](https://arxiv.org/html/2605.08688#bib.bib4)\], an early connection allowed us to design algorithms for obtaining causal explanations in XDM, and to obtain complexity results for CBD\. For reasons of space, and to best convey intuitions, we unveil and formulate interesting connections by means of examples\. However, it should become clear how to formulate things in general terms\. We also show how the established connections can be exploited in technical terms\. Exploring them in more depth is is part of ongoing work\.

In this work we stick to the propositional case, that is, logical specifications, features, classifiers, and models on which CBD is performed are all written in propositional logic or are binary\.

In Section[2](https://arxiv.org/html/2605.08688#S2), we review and present actual causality and responsibility as used to explain outcomes from classification models, those usually learnt in machine learning\. In Section[3](https://arxiv.org/html/2605.08688#S3), we show how a typical problem of CBD can be recast as one of actual causality, and how responsibility could become a new ingredient in CBD\. On the basis of CBD problems we give a precise definition of actual causality, and responsibility\. Furthermore, we show how the CBD problem could be represented by means on a Structural Causal Model\[[23](https://arxiv.org/html/2605.08688#bib.bib23)\]\. In Section[4](https://arxiv.org/html/2605.08688#S4), we proceed the other way around\. We take a classification problem that would be normally approached via actual causality and responsibility \(or some other attribution method of XAI\), and formulate it a CBD problem\. In Section[5](https://arxiv.org/html/2605.08688#S5), we show an example of how CBD can borrow techniques to actual causality, and the other way around\.

## 2Actual Causality and Responsibility in XAI

The goal of this section is twofold\. We describe and illustrate, by means of an example, the main concepts ofactual causality; and we also show how to apply them in XAI, in this case, to obtain explanations from a ML\-based classifier\. Precise definitions in the context of CBD are given in Section[3](https://arxiv.org/html/2605.08688#S3)\.

The basic idea behindactual causality\[[17](https://arxiv.org/html/2605.08688#bib.bib17),[18](https://arxiv.org/html/2605.08688#bib.bib18)\]is that of performingcounterfactual interventionson the values of variables of a model, changing their values in order to detect if there are changes in other variables, typically the output of the model\. The interventions lead tocounterfactual and actual explanations\.

###### Example 1

Consider a classifier𝒞\\mathcal\{C\}an in Figure[1](https://arxiv.org/html/2605.08688#S2.F1)\(a\) that has been learned from training data\. After that, it can be complex enough for us to have an idea about what is going on inside\.𝒞\\mathcal\{C\}may well be \(or treated as\) a black\-box classifier, but we can use𝒞\\mathcal\{C\}’s input/output relation\. For an input entity𝐞=⟨𝐱1,𝐱2,𝐱3,𝐱4⟩∈\{0,1\}4\\mathbf\{e\}=\\langle\\mathbf\{x\}\_\{1\},\\mathbf\{x\}\_\{2\},\\mathbf\{x\}\_\{3\},\\mathbf\{x\}\_\{4\}\\rangle\\in\\\{0,1\\\}^\{4\}, with four binary feature values, the labelL​\(𝐞\)∈\{0,1\}L\(\\mathbf\{e\}\)\\in\\\{0,1\\\}is returned\.

![Refer to caption](https://arxiv.org/html/2605.08688v1/x1.png)![Refer to caption](https://arxiv.org/html/2605.08688v1/x2.png)

Figure 1:\(a\) A Binary Classifier\. \(b\) Particular Input/Output\.As shown in Figure[1](https://arxiv.org/html/2605.08688#S2.F1)\(b\), with input𝐞=⟨1,0,0,1⟩\\mathbf\{e\}=\\langle 1,0,0,1\\rangle, we obtain label0\. We want an explanation, as feature values in𝐞\\mathbf\{e\}that are actual causes for the outcome\. Do changes of \(interventions on\) feature values change the label from0to11?

![Refer to caption](https://arxiv.org/html/2605.08688v1/x3.png)![Refer to caption](https://arxiv.org/html/2605.08688v1/x4.png)

Figure 2:\(a\) Successful Intervention\. \(b\) Unsuccessful Intervention\.As shown in Figure[2](https://arxiv.org/html/2605.08688#S2.F2)\(a\), the change on𝐱𝟏\\mathbf\{x\_\{1\}\}from11to0changes the label\. The value𝐱𝟏=1\\mathbf\{x\_\{1\}\}=1is said to be acounterfactual causefor the initial label: A change on𝐱1\\mathbf\{x\}\_\{1\}alone already changes the label\.

Now, let’s concentrate on𝐱𝟐\\mathbf\{x\_\{2\}\}\. Figure[2](https://arxiv.org/html/2605.08688#S2.F2)\(b\) shows that𝐱2=0\\mathbf\{x\}\_\{2\}=0is not a counterfactual cause forL=0L=0\. Let’s keep it value for a moment, and consider the following unsuccessful intervention on𝐱3,𝐱4\\mathbf\{x\}\_\{3\},\\mathbf\{x\}\_\{4\}in Figure[3](https://arxiv.org/html/2605.08688#S2.F3)\(a\)\.

![Refer to caption](https://arxiv.org/html/2605.08688v1/x5.png)![Refer to caption](https://arxiv.org/html/2605.08688v1/x6.png)

Figure 3:\(a\) Unsuccessful Intervention\. \(b\) Successful Intervention\.If, in addition to those two changes, we change again𝐱2\\mathbf\{x\}\_\{2\}to11, we are now successful, as shown in Figure[3](https://arxiv.org/html/2605.08688#S2.F3)\(b\)\. We say that𝐱2=0\\mathbf\{x\}\_\{2\}=0is anactual causefor the original label, andΓ=\{𝐱3=0,𝐱4=1\}\\Gamma=\\\{\\mathbf\{x\}\_\{3\}=0,\\mathbf\{x\}\_\{4\}=1\\\}is acontingency set\(CS\) for𝐱2=0\\mathbf\{x\}\_\{2\}=0: In order for the change on𝐱2\\mathbf\{x\}\_\{2\}to change the label, it needs an additional, contingent set of changes\. However, those two contingent changes alone do not change the label\. We say that𝐞′=⟨0,0,0,1⟩\\mathbf\{e\}^\{\\prime\}=\\langle\{\\color\[rgb\]\{1,0,0\}0\},0,0,1\\rangleand𝐞′′=⟨1,1,1,0⟩\\mathbf\{e\}^\{\\prime\\prime\}=\\langle 1,\{\\color\[rgb\]\{1,0,0\}1\},\{\\color\[rgb\]\{1,0,0\}1\},\{\\color\[rgb\]\{1,0,0\}0\}\\ranglearecounterfactuals\(counterfactual versions\) of the original entity𝐞\\mathbf\{e\}\.■\\blacksquare

Thecausal responsibilityof an actual cause is a numerical quantification of its strength as a cause\. It is based on the number of additional changes an actual cause needs to change the label\. Actually, for an actual cause𝐱=v\\mathbf\{x\}=v, its responsibility is defined by𝑅𝑒𝑠𝑝​\(𝐱\):=1/\(1\+\|Γ\|\)\{\\it Resp\}\(\\mathbf\{x\}\):=1/\(1\+\|\\Gamma\|\), whereΓ\\Gammais a minimum\-size CS for𝐱\\mathbf\{x\}\. Feature values that are not actual causes have, by definition, responsibility0\.

###### Example 2

\(ex\.[1](https://arxiv.org/html/2605.08688#Thmexample1)cont\.\) Since𝐱1=1\\mathbf\{x\}\_\{1\}=1in𝐞\\mathbf\{e\}does not need additional changes,Γ=∅\\Gamma=\\emptysetis its minimum CS, and then, its responsibility is𝑅𝑒𝑠𝑝​\(𝐱1\)=1\{\\it Resp\}\(\\mathbf\{x\}\_\{1\}\)\\ =\\ 1, the maximum possible responsibility\. If we assume thatΓ=\{𝐱3=0,𝐱4=1\}\\Gamma=\\\{\\mathbf\{x\}\_\{3\}=0,\\mathbf\{x\}\_\{4\}=1\\\}, as above, is a minimum CS for𝐱2=0\\mathbf\{x\}\_\{2\}=0,𝑅𝑒𝑠𝑝​\(𝐱2\)=1/\(1\+2\)=1/3\{\\it Resp\}\(\\mathbf\{x\}\_\{2\}\)=1/\(1\+2\)=1/3\.■\\blacksquare

Actual causality provides counterfactual explanations to observations\. In general terms, they are “components” of a system that are a cause for an observed behavior\. Counterfactual causes are actual causes with an empty CS\. Accordingly, counterfactual causes arestrongcauses in that they, by themselves, explain the observation\. Actual causes that are not counterfactual causes areweakercauses, they require the company of other components to explain the observation\.

In some applications of actual causality, there may be variables that are declaredendogenous, while the others areexogenous\. The former are of interest for causality purposes\. In particular, only endogenous variables can be actual causes and members of CSs\. In our example, we could have declared𝐱3\\mathbf\{x\}\_\{3\}as exogenous; for example, if we know that its value has to be0, no matter what\. This value is not subject to interventions\. In that case,𝐱3\\mathbf\{x\}\_\{3\}could not have been a member of the CS any longer\. We would have to look for contingencies somewhere else\. The choice of endogenous/exogenous variables is application dependent\. See\[[23](https://arxiv.org/html/2605.08688#bib.bib23), sec\. 5\]for a relevant discussion\.

Actual causality and responsibility can be applied without necessarily knowing “the internals” of the classifier, which can be \(or be treated as\) a “black box”\. Only the input/output relation is needed\. Responsibility has become, as more generally called in XAI, anattribution score\. The kind of explanations obtained arelocalin that they apply to values in a single input entity\. As defined, responsibility does not provide aglobalexplanation for the behavior of the classifier\.

The computation of the responsibility score in explainable ML is known to be intractable, already in the binary case\[[7](https://arxiv.org/html/2605.08688#bib.bib7)\]\. Above we introduced responsibility in a binary setting\. When feature values are not binary, its definition has to be extended\. This was done, analyzed and experimented with in\[[6](https://arxiv.org/html/2605.08688#bib.bib6)\]\(see also\[[9](https://arxiv.org/html/2605.08688#bib.bib9)\]\)\.

## 3Consistency\-Based Diagnosis as Actual Causality

We will first introduce and illustrateconsistency\-based diagnosis\(CBD\)\[[24](https://arxiv.org/html/2605.08688#bib.bib24),[16](https://arxiv.org/html/2605.08688#bib.bib16)\]by means of an example\. After that, we will show how to cast it as an actual causality problem related to classification\.

If we are confronting a system that is exhibiting an unexpected or abnormal behavior, we want to obtain adiagnosisfor this, i\.e\. some sort of explanation\. Diagnoses are obtained from a model of the system\.

###### Example 3

Figure[4](https://arxiv.org/html/2605.08688#S3.F4)\(a\) shows a very simple Boolean circuit with anAnd\-gate,AA, and anOr\-gate,OO\. The input variables area,b,ca,b,c, the intermediate output variable forAAisxx, and the final, output variable isdd; all of them taking values0or11\. The intended meaning of the propositional variableaais “inputaais true” \(or takes value11\), etc\. With the indicated inputs and output, the circuit seems to be behaving as expected\.

![Refer to caption](https://arxiv.org/html/2605.08688v1/x7.png)![Refer to caption](https://arxiv.org/html/2605.08688v1/x8.png)

Figure 4:\(a\) Boolean Circuit\. \(b\) Faulty Boolean Circuit\.Figure[4](https://arxiv.org/html/2605.08688#S3.F4)\(b\) shows an unintended behavior: with those inputs, the output should be11\. We need adiagnosisfor the abnormal behavior of the circuit\. Diagnoses have to be characterized; for this we need a model\.

In this example, a logical model of the circuit, when it works properly, is a set of propositional formulas:\{\(x⟷\(a∧b\)\),\(d⟷\(x∨c\)\)\}\\\{\(x\\longleftrightarrow\(a\\wedge b\)\),\\ \(d\\longleftrightarrow\(x\\vee c\)\)\\\}\. However, our circuit at hand, by working abnormally, isnotmodeled by these formulas\. Furthermore, theobservation,𝑂𝑏𝑠=\{a,¬b,c,¬d\}\{\\it Obs\}=\\\{a,\\neg b,c,\\neg d\\\}, indicating thataaandccare true, butbbandddare false, is mutually inconsistent with this ideal model: there is no assignment of truth values to the propositional variables that makes the combination true\. From their combination we cannot logically obtain any useful information\.

We may want insteada model that allows failures, or abnormal behaviors\. From such a model, we could try to obtain explanations for them\. A better, more flexible model that allows failures, and specifies how components behave under normal conditions is:

ℳ=\{¬abA⟶\(x↔\(a∧b\)\),¬abO⟶\(d↔\(x∨c\)\)\}\.\\mathcal\{M\}=\\\{\\neg abA\\longrightarrow\(x\\leftrightarrow\(a\\wedge b\)\),\\ \\ \\neg abO\\longrightarrow\(d\\leftrightarrow\(x\\vee c\)\)\\\}\.\(1\)
The first formula says“WhenAAis not abnormal, it works as an And\-gate”, etc\. Here,𝑎𝑏𝐴\{\\it abA\}and𝑎𝑏𝑂\{\\it abO\}are new propositional variables\. This is a “weak model of failure” in that it specifies how things behave under normal conditions, but not under abnormal ones\. This is common kind of models under CBD\[[16](https://arxiv.org/html/2605.08688#bib.bib16)\]\.

Modelℳ\\mathcal\{M\}assumes that the only potentially faulty components are, in this case, the gates \(but not the wires connecting them\), a modeling choice\. Now gates could be abnormal \(or faulty\), and𝑂𝑏𝑠∪ℳ\{\\it Obs\}\\ \\cup\\ \\mathcal\{M\}is a perfectly consistent set of formulas\. When one specifies, in addition, that the gates are not abnormal, we reobtain that:

\{a,¬b,c,¬d\}∪ℳ∪\{¬𝑎𝑏𝐴,¬𝑎𝑏𝑂\}​is inconsistent\.\\\{a,\\neg b,c,\\neg d\\\}\\ \\cup\\ \\mathcal\{M\}\\ \\cup\\\{\\neg\{\\it abA\},\\neg\{\\it abO\}\\\}\\ \\mbox\{ is \\ inconsistent\}\.\(2\)
Then, something has to be abnormal, and it is throughconsistency restorationthat we will be able to characterize and compute diagnoses\. If we make gateO\{\\color\[rgb\]\{0,0,1\}O\}abnormal in \([2](https://arxiv.org/html/2605.08688#S3.E2)\), we restore consistency, that is, in contrast to \([2](https://arxiv.org/html/2605.08688#S3.E2)\),𝑂𝑏𝑠∪ℳ∪\{¬𝑎𝑏𝐴,𝑎𝑏𝑂¯\}​is consistent\{\\it Obs\}\\ \\cup\\ \\mathcal\{M\}\\ \\cup\\\{\\neg\{\\it abA\},\\ \\underline\{\{\\it abO\}\}\\\}\\ \\mbox\{ is \\ consistent\}\(underlying the change made\)\. Accordingly, and by definition,Δ=\{𝑎𝑏𝑂\}\\Delta=\\\{\{\\it abO\}\\\}is a diagnosis\. Similarly,Δ′=\{𝑎𝑏𝑂,𝑎𝑏𝐴\}\\Delta^\{\\prime\}=\\\{\{\\it abO\},\{\\it abA\}\\\}is a diagnosis, because making every gate abnormal also restores consistency:𝑂𝑏𝑠∪ℳ∪\{𝑎𝑏𝐴¯,𝑎𝑏𝑂¯\}​is consistent\{\\it Obs\}\\ \\cup\\ \\mathcal\{M\}\\ \\cup\\\{\\underline\{\{\\it abA\}\},\\ \\underline\{\{\\it abO\}\}\\\}\\ \\mbox\{ is \\ consistent\}\.

We may considerΔ\\Deltaas a “better” diagnosis thanΔ′\\Delta^\{\\prime\}, because it makes fewer assumptions; it is more informative by providing narrower and more focused diagnosis\.Δ\\Deltais aminimal diagnosisin that it is not set\-theoretically included in any other diagnosis\. It is also aminimum diagnosisin that it has a minimum cardinality\.■\\blacksquare

### 3\.1CBD as a Causal Problem

Now, we are going to cast the CBD problem as an actual causality problem, and as applied to a classification problem\. We do this by appealing to our example\.

###### Example 4

\(ex\.[3](https://arxiv.org/html/2605.08688#Thmexample3)cont\.\) The classification problem is that of deciding if an input \-with a model\- is satisfiable or not\. The model isℳ\\mathcal\{M\}in \([1](https://arxiv.org/html/2605.08688#S3.E1)\)\. Our classifier, with its binary inputs and output, is shown in Figure[5](https://arxiv.org/html/2605.08688#S3.F5)\. It consists of modelℳ\\mathcal\{M\}plus a SAT solver that verifies ifℳ\\mathcal\{M\}is consistent with the input𝐞\\mathbf\{e\}, whose last component,dd, stands for the output of the circuit\.

𝐞=⟨a​b​A,a​b​O,a,b,c,d⟩\\mathbf\{e\}=\\langle abA,abO,a,b,c,d\\rangle

⟶\\longrightarrow

\(propositional feature vector\)

S​A​T​?\\displaystyle SAT?~~~~~~~~~~~~~¬abA⟶\(x↔\(a∧b\)\)¬abO⟶\(d↔\(x∨c\)\)\+SAT solver\\displaystyle\\hskip 79\.6678pt\\boxed\{\\begin\{aligned\} &\\neg abA\\longrightarrow\(x\\leftrightarrow\(a\\wedge b\)\)\\\\ &\\neg abO\\longrightarrow\(d\\leftrightarrow\(x\\vee c\)\)\\\\ &~~~~~~~\+\\ \\mbox\{ SAT solver\}\\end\{aligned\}\}
⟶𝑦𝑒𝑠/𝑛𝑜\\longrightarrow\\ \{\\it yes\}/\{\\it no\}

Figure 5:A Consistency ClassifierAs we saw in Example[3](https://arxiv.org/html/2605.08688#Thmexample3), with𝐞=⟨0,0,1,0,1,0⟩\\mathbf\{e\}=\\langle 0,0,1,0,1,0\\rangle, representing⟨¬𝑎𝑏𝐴,\\langle\\neg\{\\it abA\},¬𝑎𝑏𝑂,a,\\neg\{\\it abO\},a,,¬b,c,¬d⟩,\\neg b,c,\\neg d\\rangle, the classifier returns “no” \(or0\)\. Then, we can apply actual causality by first declaring “features”𝑎𝑏𝐴,𝑎𝑏𝑂\{\\it abA\},\{\\it abO\}as endogenous, subject to interventions, while the others,a,b,c,da,b,c,d, are exogenous\. They provide context and are not subject to interventions\. By counterfactually intervening𝐞\\mathbf\{e\}, producing𝐞′=⟨0,1,1,0,1,0⟩\\mathbf\{e\}^\{\\prime\}=\\langle 0,\{\\color\[rgb\]\{1,0,0\}1\},1,0,1,0\\rangle, indicating that𝑎𝑏𝑂\{\\it abO\}is true, we manage to change the classifier’s output to𝑦𝑒𝑠\{\\it yes\}\. This does not happen with𝑎𝑏𝐴\{\\it abA\}though\. Then, “𝑎𝑏𝑂=0\{\\it abO\}=0” is a counterfactual cause\. Intervening both𝑎𝑏𝑂\{\\it abO\}and𝑎𝑏𝑂\{\\it abO\}also changes the output, but this set of changes includes one that is already a counterfactual cause\. Accordingly,𝑎𝑏𝐴\{\\it abA\}is neither a counterfactual nor an actual cause\.

Now we can apply responsibility to our CBD scenario:𝑅𝑒𝑠𝑝​\(𝑎𝑏𝑂\):=1\{\\it Resp\}\(\{\\it abO\}\):=1, and𝑅𝑒𝑠𝑝​\(𝑎𝑏𝐴\):=0\{\\it Resp\}\(\{\\it abA\}\):=0\.■\\blacksquare

Our example suggests a correspondence between actual causes with their minimal/minimum contingency sets and minimal/minimum diagnoses\. To formulate this connection, we need a formal definition of actual cause, which in Section[2](https://arxiv.org/html/2605.08688#S2)we did not provide\. We do this now, but grounding the general definition in the CBD setting\.

### 3\.2Revisiting the Connection

Let us start with aweak model of failureof a system, as in Example[3](https://arxiv.org/html/2605.08688#Thmexample3), that is, a specification in propositional logic,ℳ\\mathcal\{M\}, of the form:

ℳ=\{¬a​b​C1→φ1,¬a​b​C2→φ2,…​¬a​b​Cn→φn\},\\mathcal\{M\}=\\\{\\neg abC\_\{1\}\\rightarrow\\varphi\_\{1\},\\ \\neg abC\_\{2\}\\rightarrow\\varphi\_\{2\},\\ \\ldots\\neg abC\_\{n\}\\rightarrow\\varphi\_\{n\}\\\},\(3\)
fornnpotentially faulty componentsℭ=\{C1,…,Cn\}\\mathfrak\{C\}=\\\{C\_\{1\},\\ldots,C\_\{n\}\\\}in the system\. Noa​b​Ci\{abC\_\{i\}\}propositional variables appear in the consequents of the implications\. This is what makes the model a weak model; nothing is said about how the system behaves under abnormality\. This is not the only kind of specifications in CBD\. They could also have𝑎𝑏\{\\it ab\}atoms in places of the formulas\. However, those we are considering are common, and enjoy of some good properties\. See\[[16](https://arxiv.org/html/2605.08688#bib.bib16), sec\. 7\]for a discussion\.

In we also have an observation,𝑂𝑏𝑠\{\\it Obs\}, a set of non\-ab\-literals, i\.e\. inputs and outputs, we may consider the system is not working properly in that:

ℳ∪𝑂𝑏𝑠∪\{¬𝑎𝑏𝐶i\|i=1,…,n\}​is inconsistent\.\\mathcal\{M\}\\ \\cup\\ \{\\it Obs\}\\ \\cup\\ \\\{\\neg\{\\it abC\}\_\{i\}~\|~i=1,\\ldots,n\\\}\\ \\mbox\{ is inconsistent\.\}\(4\)
Adiagnosisis a subsetΔ\\Deltaof\{𝑎𝑏𝐶1,𝑎𝑏𝐶2,…,𝑎𝑏𝐶n\}\\\{\{\\it abC\}\_\{1\},\{\\it abC\}\_\{2\},\\ldots,\{\\it abC\}\_\{n\}\\\}such that the assumption that they are true restores the consistency in \([4](https://arxiv.org/html/2605.08688#S3.E4)\), that is,

ℳ∪O​b​s∪Δ∪\{¬𝑎𝑏𝐶\|C∈ℭ​and​𝑎𝑏𝐶∉Δ\}​is consistent\.\{\\mathcal\{M\}~\\cup~Obs~\\cup~\\Delta~\\cup~\\\{\\neg\{\\it abC\}~\|~C\\in\\mathfrak\{C\}\\mbox\{ and \}\{\\it abC\}\\notin\\Delta\\\}\}\\ \\mbox\{ is consistent\}\.\(5\)
Aminimal diagnosisΔ\\Deltais a diagnosis, such that no proper subset ofΔ\\Deltais also a diagnosis\. In general, we wantminimal diagnoses\. They are the most informative ones\. Sometimes we concentrate on the subclass ofminimum diagnoses, those with minimum cardinality\.

Approaching the CBD problem as one about actual causality, \([4](https://arxiv.org/html/2605.08688#S3.E4)\) becomes a natural scenario for performingcounterfactual interventionson the¬𝑎𝑏\\neg\{\\it ab\}literals, the only ones declared as endogenous; to detect if they falsify the inconsistency, returning to the expected consistency\. On this basis, and according to\[[17](https://arxiv.org/html/2605.08688#bib.bib17)\], we can give the following definition\.

###### Definition 1

For a diagnosis setting⟨ℭ,ℳ,𝑂𝑏𝑠⟩\\langle\\mathfrak\{C\},\\mathcal\{M\},\{\\it Obs\}\\rangleas in \([4](https://arxiv.org/html/2605.08688#S3.E4)\):

\(a\) An atom𝑎𝑏𝐶i\{\\it abC\}\_\{i\}is a counterfactual cause iffℳ∪𝑂𝑏𝑠∪\{𝑎𝑏𝐶i\}∪\{¬𝑎𝑏𝐶j\|j=1,…,i−1,i\+1,…​n\}\\mathcal\{M\}\\ \\cup\\ \{\\it Obs\}\\ \\cup\\ \\\{\{\\it abC\}\_\{i\}\\\}\\ \\cup\\ \\\{\\neg\{\\it abC\}\_\{j\}~\|~j=1,\\ldots,i\-1,i\+1,\\ldots n\\\}is consistent\.

\(b\) An atom𝑎𝑏𝐶i\{\\it abC\}\_\{i\}is an actual cause iff there isΓ⊆\(\{𝑎𝑏𝐶\|C∈ℭ\}∖\{𝑎𝑏𝐶i\}\)\\Gamma\\subseteq\(\\\{\{\\it abC\}~\|~C\\in\\mathfrak\{C\}\\\}\\smallsetminus\\\{\{\\it abC\}\_\{i\}\\\}\), such that: \(b1\)ℳ∪𝑂𝑏𝑠∪\{¬𝑎𝑏𝐶i\}∪Γ∪\{¬𝑎𝑏𝐶\|C∈ℭ,𝑎𝑏𝐶∉\(Γ∪\{𝑎𝑏𝐶i\}\)\}\\mathcal\{M\}\\ \\cup\\ \{\\it Obs\}\\ \\cup\\ \\\{\\neg\{\\it abC\}\_\{i\}\\\}\\ \\cup\\ \\Gamma\\ \\cup\\ \\\{\\neg\{\\it abC\}~\|~C\\in\\mathfrak\{C\},\{\\it abC\}\\notin\(\\Gamma\\cup\\\{\{\\it abC\}\_\{i\}\\\}\)\\\}is inconsistent, but \(b2\)ℳ∪𝑂𝑏𝑠∪\{𝑎𝑏𝐶i\}∪Γ∪\{¬𝑎𝑏𝐶\|C∈ℭ,𝑎𝑏𝐶∉\(Γ∪\{𝑎𝑏𝐶i\}\)\}\\mathcal\{M\}\\ \\cup\\ \{\\it Obs\}\\ \\cup\\ \\\{\{\\it abC\}\_\{i\}\\\}\\ \\cup\\ \\Gamma\\ \\cup\\ \\\{\\neg\{\\it abC\}~\|~C\\in\\mathfrak\{C\},\{\\it abC\}\\notin\(\\Gamma\\cup\\\{\{\\it abC\}\_\{i\}\\\}\)\\\}is consistent\.Γ\\Gammais called a contingency set for𝑎𝑏𝐶i\{\\it abC\}\_\{i\}\.

\(c\) The responsibility of an actual cause𝑎𝑏𝐶\{\\it abC\}is𝑅𝑒𝑠𝑝​\(𝑎𝑏𝐶\):=1/\(1\+\|Γ\|\)\{\\it Resp\}\(\{\\it abC\}\):=1/\(1\+\|\\Gamma\|\), withΓ\\Gammaa minimum contingency set for𝑎𝑏𝐶\{\\it abC\}\. A non\-actual cause has responsibility0\.■\\blacksquare

Notice that the definition can be applied with a model of which we only know the normal input/output behavior\. Notice also that every counterfactual cause is also an actual cause with empty contingency set\. The following proposition holds\.

###### Proposition 1

For a diagnosis setting⟨ℭ,ℳ,𝑂𝑏𝑠⟩\\langle\\mathfrak\{C\},\\mathcal\{M\},\{\\it Obs\}\\rangle: \(a\) A literal𝑎𝑏𝐶\{\\it abC\}is a counterfactual cause iffΔ=\{𝑎𝑏𝐶\}\\Delta=\\\{\{\\it abC\}\\\}is a diagnosis\. \(b\) A literal𝑎𝑏𝐶\{\\it abC\}is an actual cause with minimal contingency setΓ\\Gammaiff𝑎𝑏𝐶\{\\it abC\}belongs to a minimal diagnosisΔ\\Delta, andΓ=Δ∖\{𝑎𝑏𝐶\}\\Gamma=\\Delta\\smallsetminus\\\{\{\\it abC\}\\\}\.■\\blacksquare

###### Example 5

\(example[3](https://arxiv.org/html/2605.08688#Thmexample3)cont\.\) We had\{a,¬b,c,¬d\}∪ℳ∪\{¬𝑎𝑏𝐴,¬𝑎𝑏𝑂\}\\\{a,\\neg b,c,\\neg d\\\}\\ \\cup\\ \\mathcal\{M\}\\ \\cup\\\{\\neg\{\\it abA\},\\neg\{\\it abO\}\\\}as inconsistent\. Switching¬𝑎𝑏𝑂\\neg\{\\it abO\}into𝑎𝑏𝑂\{\\it abO\}, reestablishes consistency:\{a,¬b,c,¬d\}∪ℳ∪\{¬𝑎𝑏𝐴,𝑎𝑏𝑂¯\}\\\{a,\\neg b,c,\\neg d\\\}\\ \\cup\\ \\mathcal\{M\}\\ \\cup\\\{\\neg\{\\it abA\},\\underline\{\{\\it abO\}\}\\\}is consistent\. Then,𝑎𝑏𝑂\{\\it abO\}is acounterfactual causefor the malfunctioning of the circuit\.

However, when we switch𝑎𝑏𝐴\{\\it abA\},\{a,¬b,c,¬d\}∪ℳ∪\{𝑎𝑏𝐴¯,¬𝑎𝑏𝑂\}\\\{a,\\neg b,c,\\neg d\\\}\\ \\cup\\ \\mathcal\{M\}\\ \\cup\\\{\\underline\{\{\\it abA\}\},\\neg\{\\it abO\}\\\}is still inconsistent\. Accordingly,𝑎𝑏𝐴\{\\it abA\}is not a counterfactual cause\. It is not an actual cause either: its only potential contingency setΓ=\{𝑎𝑏𝑂\}\\Gamma=\\\{\{\\it abO\}\\\}does not satisfy condition \(b1\) in Definition[1](https://arxiv.org/html/2605.08688#Thmdefinition1)\(b\)\.■\\blacksquare

We restrict Proposition[1](https://arxiv.org/html/2605.08688#Thmproposition1)to minimal diagnoses, because for models of the form \([3](https://arxiv.org/html/2605.08688#S3.E3)\), every superset of a diagnosis is a diagnosis\[[16](https://arxiv.org/html/2605.08688#bib.bib16), sec\. 7\]\. However, not every superset of a contingency set is a contingency set for a tuple, due to condition \(b1\) in Definition[1](https://arxiv.org/html/2605.08688#Thmdefinition1)\. Furthermore, the minimal diagnoses are those of interest\.

### 3\.3Causal Structural Models

Those who are more familiar with causality represented bystructural models\[[23](https://arxiv.org/html/2605.08688#bib.bib23)\]may be missing them here\. Actually, the diagnosis problems can also be cast in those terms\. A purely logical model, as in the previous examples, does not distinguish causal directions, or between causes and effects\. They can be better represented by a structural model that takes the form of a \(directed\)causal network\.

![Refer to caption](https://arxiv.org/html/2605.08688v1/x9.png)

Figure 6:Causal Network###### Example 6

\(ex\.[4](https://arxiv.org/html/2605.08688#Thmexample4)cont\.\) The causal network in Figure[6](https://arxiv.org/html/2605.08688#S3.F6)represents our possibly faulty circuit\. In it,𝑎𝑏𝐴,𝑎𝑏𝑂\{\\it abA\},\{\\it abO\}are endogenous variables, which can be subject to counterfactual interventions; in this case, making𝐴𝑏𝐴\{\\it AbA\}and𝐴𝑏𝑂\{\\it AbO\}true or false\. Variablesxxandddare endogenous, and havestructural equationsassociated to them, as shown in Fig\.[6](https://arxiv.org/html/2605.08688#S3.F6), capturing the circuit’s logic\. They are used unidirectionally, consistently with the edge directions\. In this case, we use by choice \-contrary to the weak model of failure in Figure \([5](https://arxiv.org/html/2605.08688#S3.F5)\)\- equations that also specify the behaviour under abnormal conditions\.■\\blacksquare

## 4CBD for Explainable Boolean Classification

To fix and convey the main ideas, we concentrate here on Boolean\-circuit classifiers that take Boolean features as inputs, and return a binary label,11or0\.

![Refer to caption](https://arxiv.org/html/2605.08688v1/x10.png)

![Refer to caption](https://arxiv.org/html/2605.08688v1/x11.png)

Figure 7:Boolean Classification Circuit###### Example 7

Consider the Boolean circuit in Figure[7](https://arxiv.org/html/2605.08688#S4.F7)\(a\)\.111Adeterministic and decomposable Boolean circuit\(d\-DBC\) used in\[[2](https://arxiv.org/html/2605.08688#bib.bib2)\]\. d\-DBCs can encode decision trees, several classes of binary decision diagrams, binary neural networks\[[10](https://arxiv.org/html/2605.08688#bib.bib10)\], etc\.The set of propositional input features isℱ=\{𝐱𝟏,𝐱𝟐,𝐱𝟑,𝐱𝟒\}\\mathcal\{F\}=\\\{\\mathbf\{x\_\{1\}\},\\mathbf\{x\_\{2\}\},\\mathbf\{x\_\{3\}\},\\mathbf\{x\_\{4\}\}\\\}\. The output,𝐎\\mathbf\{O\}, is at the top node\. The circuit on the right\-hand side shows variables for the gate outputs\. The BC can be logically specified:ℬ=\{\(¬𝐱𝟐⟷y\),\(y∧𝐱𝟑∧𝐱𝟒⟷x\),\(𝐱𝟐∨x⟷z\),\(𝐱𝟏∧z⟷𝐎\)\\mathcal\{B\}=\\\{\(\\neg\\mathbf\{x\_\{2\}\}\\longleftrightarrow y\),\\ \(y\\wedge\\mathbf\{x\_\{3\}\}\\wedge\\mathbf\{x\_\{4\}\}\\longleftrightarrow x\),\\ \(\\mathbf\{x\_\{2\}\}\\vee x\\longleftrightarrow z\),\\ \(\\mathbf\{x\_\{1\}\}\\wedge z\\longleftrightarrow\\mathbf\{O\}\)\. As shown in Figure[7](https://arxiv.org/html/2605.08688#S4.F7)\(b\), withℬ\\mathcal\{B\}and input entity𝐞\\mathbf\{e\}with:

𝐞​\(𝐱𝟏\):=1,𝐞​\(𝐱𝟐\):=0,𝐞​\(𝐱𝟑\):=1,𝐞​\(𝐱𝟒\):=0,\\mathbf\{e\}\(\\mathbf\{x\_\{1\}\}\):=1,\\ \\mathbf\{e\}\(\\mathbf\{x\_\{2\}\}\):=0,\\ \\mathbf\{e\}\(\\mathbf\{x\_\{3\}\}\):=1,\\ \\mathbf\{e\}\(\\mathbf\{x\_\{4\}\}\):=0,\(6\)we obtainy=1,x=0,z=0y=1,x=0,z=0, and the output𝐎​\(𝐞\)=0\\mathbf\{O\}\(\\mathbf\{e\}\)=0\.■\\blacksquare

We want to find input values as actual causes for the observed output\. To approach the problem as CBD, we consider the output as something unexpected under normal circumstances\. Since we have no reason to assume that the logical gates of the classifier are working abnormally; we assume they are not faulty\. Accordingly, and departing from Section[3](https://arxiv.org/html/2605.08688#S3), we allow the inputs to the classifier to be faulty in that they do not produce the “expected output”, in this case,𝐎¯=1\\mathbf\{\\bar\{O\}\}=1, the complementary literal of𝐎\\mathbf\{O\}\. We denote the original classifier withℬ\(𝐱𝟏,𝐱𝟐,𝐱𝟑,\\mathcal\{B\}\(\\mathbf\{x\_\{1\}\},\\mathbf\{x\_\{2\}\},\\mathbf\{x\_\{3\}\},𝐱𝟒;𝐎\)\\mathbf\{x\_\{4\}\};\\mathbf\{O\}\), indicating that, with inputs𝐱𝟏,𝐱𝟐,𝐱𝟑,\\mathbf\{x\_\{1\}\},\\mathbf\{x\_\{2\}\},\\mathbf\{x\_\{3\}\},𝐱𝟒\\mathbf\{x\_\{4\}\}, it returns \-actually, it becomes\- the binary value𝐎\\mathbf\{O\}\.

###### Example 8

\(ex\.[7](https://arxiv.org/html/2605.08688#Thmexample7)cont\.\) We want to explain the output𝐎=0\\mathbf\{O\}=0by identifying the input values that are most relevant for the outcome\. As in Section[3](https://arxiv.org/html/2605.08688#S3), we introduce, for each input features𝐱𝐢\\mathbf\{x\_\{i\}\}, a corresponding propositional variable𝑎𝑏​\(𝐱𝐢\)\{\\it ab\}\(\\mathbf\{x\_\{i\}\}\), standing for “𝐱𝐢\\mathbf\{x\_\{i\}\}takes an abnormal value”\. With them, we have the base model of failure:

ℳ\\displaystyle\\mathcal\{M\}\\:=\\displaystyle:=ℬ\(𝐱𝟏,𝐱𝟐,𝐱𝟑,𝐱𝟒;𝐨\)∪\{\(¬𝑎𝑏\(𝐱𝟏\)⟷𝐱𝟏\),\(¬𝑎𝑏\(𝐱𝟐\)⟷¬𝐱𝟐\),\\displaystyle\\ \\mathcal\{B\}\(\\mathbf\{x\_\{1\}\},\\mathbf\{x\_\{2\}\},\\mathbf\{x\_\{3\}\},\\mathbf\{x\_\{4\}\};\\mathbf\{o\}\)\\cup\\\{\(\\neg\{\\it ab\}\(\\mathbf\{x\_\{1\}\}\)\\longleftrightarrow\\mathbf\{x\_\{1\}\}\),\\ \(\\neg\{\\it ab\}\(\\mathbf\{x\_\{2\}\}\)\\longleftrightarrow\\neg\\mathbf\{x\_\{2\}\}\),\(7\)\(¬𝑎𝑏\(𝐱𝟑\)⟷𝐱𝟑\),\(¬𝑎𝑏\(𝐱𝟒\)⟷¬𝐱𝟒\)\},\\displaystyle~~~~~\(\\neg\{\\it ab\}\(\\mathbf\{x\_\{3\}\}\)\\longleftrightarrow\\mathbf\{x\_\{3\}\}\),\\ \(\\neg\{\\it ab\}\(\\mathbf\{x\_\{4\}\}\)\\longleftrightarrow\\neg\\mathbf\{x\_\{4\}\}\)\\\},where the polarity of the variables on the RHSs of the double implications correspond to those in \([6](https://arxiv.org/html/2605.08688#S4.E6)\)\. That set in the second disjunct becomes the “observed inputs under normal circumstances”\.

Depending on the truth values of the𝑎𝑏​\(𝐱𝐢\)\{\\it ab\}\(\\mathbf\{x\_\{i\}\}\)in the double implications, the corresponding values of the associated RHSs, are meant to be the inputs toℬ\(𝐱𝟏,𝐱𝟐,\\mathcal\{B\}\(\\mathbf\{x\_\{1\}\},\\mathbf\{x\_\{2\}\},𝐱𝟑,𝐱𝟒;𝐨\)\\mathbf\{x\_\{3\}\},\\mathbf\{x\_\{4\}\};\\mathbf\{o\}\)\. From this model not much can be obtained: We do not have observations for the classifier, everything is conditional\. However, the extended model:

𝒯=\{¬𝑎𝑏​\(𝐱𝟏\),¬𝑎𝑏​\(𝐱𝟐\),¬𝑎𝑏​\(𝐱𝟑\),¬𝑎𝑏​\(𝐱𝟒\)\}∪ℳ∪\{𝐎¯\}\\mathcal\{T\}=\\\{\\neg\{\\it ab\}\(\\mathbf\{x\_\{1\}\}\),\\neg\{\\it ab\}\(\\mathbf\{x\_\{2\}\}\),\\neg\{\\it ab\}\(\\mathbf\{x\_\{3\}\}\),\\neg\{\\it ab\}\(\\mathbf\{x\_\{4\}\}\)\\\}\\cup\\mathcal\{M\}\\cup\\\{\\mathbf\{\\bar\{O\}\}\\\}\(8\)is inconsistent\. In fact, under the assumption of normality, the inputs to the circuit becomes as in \([6](https://arxiv.org/html/2605.08688#S4.E6)\), and then, the circuits evaluates to𝐎=0\\mathbf\{O\}=0, but in𝒯\\mathcal\{T\}we are requesting the output to be its opposite, i\.e\.𝐎¯=1\\mathbf\{\\bar\{O\}\}=1\.

Now, we can again proceed as in Section[3](https://arxiv.org/html/2605.08688#S3), obtaining from𝒯\\mathcal\{T\}diagnoses that contain abnormality propositional atoms\. Accordingly,Δ⊆\{𝑎𝑏​\(𝐱𝐢\)\|𝐱𝐢∈ℱ\}\\Delta\\subseteq\\\{\{\\it ab\}\(\\mathbf\{x\_\{i\}\}\)~\|~\\mathbf\{x\_\{i\}\}\\in\\mathcal\{F\}\\\}is a diagnosis if, changing in𝒯\\mathcal\{T\}the¬𝑎𝑏​\(𝐱𝐢\)\\neg\{\\it ab\}\(\\mathbf\{x\_\{i\}\}\)into𝑎𝑏​\(𝐱𝐢\)\{\\it ab\}\(\\mathbf\{x\_\{i\}\}\)when𝑎𝑏​\(𝐱𝐢\)∈Δ\{\\it ab\}\(\\mathbf\{x\_\{i\}\}\)\\in\\Delta, restores consistency\.

Notice that due to the formulas\(¬𝑎𝑏​\(𝐱1\)⟷𝐱𝟏\)\(\\neg\{\\it ab\}\(\\mathbf\{x\}\_\{1\}\)\\longleftrightarrow\\mathbf\{x\_\{1\}\}\), etc\., declaring𝑎𝑏​\(𝐱i\)\{\\it ab\}\(\\mathbf\{x\}\_\{i\}\)to be true also changes the value of𝐱𝐢\\mathbf\{x\_\{i\}\}to its inverse, which is what we do in actual causality\. WithΔ=\{𝑎𝑏​\(𝐱𝟐\)\}\\Delta=\\\{\{\\it ab\}\(\\mathbf\{x\_\{2\}\}\)\\\}, that is, changing in𝒯\\mathcal\{T\},¬𝑎𝑏​\(𝐱𝟐\)\\neg\{\\it ab\}\(\\mathbf\{x\_\{2\}\}\)into𝑎𝑏​\(𝐱𝟐\)\{\\it ab\}\(\\mathbf\{x\_\{2\}\}\), we obtain the new input value𝐱𝟐=1\\mathbf\{x\_\{2\}\}=1, and the obtainℬ​\(1,1,1,0;𝟏\)\\mathcal\{B\}\(1,\{\\color\[rgb\]\{1,0,0\}1\},1,0;\{\\color\[rgb\]\{1,0,0\}\\mathbf\{1\}\}\), whose output does not collide with the intended one at the very right of \([8](https://arxiv.org/html/2605.08688#S4.E8)\)\.Δ\\Deltais a diagnosis\.■\\blacksquare

Notice that because of these double implications, modelℳ\\mathcal\{M\}in \([7](https://arxiv.org/html/2605.08688#S4.E7)\) is not aweakmodel of failure anymore\. Using only left\-to\-right arrows does not produce the intended changes of input values\. If we want a weak model, we could drop the right\-to\-left arrows, modifying the definition of diagnosis, as follows:Δ⊆\{𝑎𝑏​\(𝐱𝐢\)\|𝐱𝐢∈ℱ\}\\Delta\\subseteq\\\{\{\\it ab\}\(\\mathbf\{x\_\{i\}\}\)~\|~\\mathbf\{x\_\{i\}\}\\in\\mathcal\{F\}\\\}is a diagnosis if, changing in𝒯\\mathcal\{T\}the¬𝑎𝑏​\(𝐱𝐢\)\\neg\{\\it ab\}\(\\mathbf\{x\_\{i\}\}\)into𝑎𝑏​\(𝐱𝐢\)\{\\it ab\}\(\\mathbf\{x\_\{i\}\}\)andthe associated inputs𝐱𝐢\\mathbf\{x\_\{i\}\}into their inverses, restores consistency\.

Notice that the method just presented does not need the internals of the classifier, and could be applied with a black\-box binary classifier𝒞​\(𝐱𝟏,𝐱𝟐,𝐱𝟑,𝐱𝟒;𝐎\)\\mathcal\{C\}\(\\mathbf\{x\_\{1\}\},\\mathbf\{x\_\{2\}\},\\mathbf\{x\_\{3\}\},\\mathbf\{x\_\{4\}\};\\mathbf\{O\}\)\.

## 5Exploiting Connections

In this section we show and example of how known techniques and results for CBD can be used to investigate applications of actual causality and resposibility\. This, in the context of Explainable Data Management, where, more specifically, we want to explain how a Boolean query𝒬\\mathcal\{Q\}, successfully answered by a databaseDD, becomes true\.

In this case, we want explanations in terms ofwhichDB tuples contribute to the positive answer, and byhow much\. The latter is answered by means of an attribution score, which, in our case, turns out to be causal responsibility \(for more on the subject and other attribution scores in XDM, see\[[9](https://arxiv.org/html/2605.08688#bib.bib9)\]\)\. For illustration purposes, we consider Boolean conjunctive queries, i\.e\. of the form𝒬:∃¯​\(P1​\(x¯1\)∧⋯∧Pn​\(x¯n\)\)\\mathcal\{Q\}\\\!:\\bar\{\\exists\}\(P\_\{1\}\(\\bar\{x\}\_\{1\}\)\\wedge\\cdots\\wedge P\_\{n\}\(\\bar\{x\}\_\{n\}\)\), which is fully existentially quantified\.

###### Example 9

Consider the databaseD=\{R\(c,b\),R\(a,d\),R\(b,a\),R\(e,f\),S\(a\),D=\\\{R\(c,b\),R\(a,d\),R\(b,a\),R\(e,f\),S\(a\),S\(b\),S\(c\),S\(d\)\}S\(b\),S\(c\),S\(d\)\\\}, whose elements are called tuples\. Every ground atom written in the language ofDD’s schema, can be seen as a propositional variable, which is true whenτ∈D\\tau\\in D, and false otherwise\.

Now, the query𝒬:∃x​∃y​\(S​\(x\)∧R​\(x,y\)∧S​\(y\)\)\\mathcal\{Q\}\\\!:\\exists x\\exists y\(S\(x\)\\land R\(x,y\)\\land S\(y\)\)becomes true inDD; and the join in it can be satisfied with different combinations of tuples inDD\. For example, by the tuplesS​\(c\),R​\(c,b\),S​\(b\)S\(c\),R\(c,b\),S\(b\)\. We want to identify the tuples that are actual causes for𝒬\\mathcal\{Q\}to be true\. For example, ifS​\(b\)S\(b\)is deleted fromDD, as an intervention, this particular instantiation of the join becomes false\.

In more general terms,𝒬\\mathcal\{Q\}is true inDD, and we want toinvalidate𝒬\\mathcal\{Q\}by intervening tuples; here, by deleting tuples \(adding tuples toDDwill not invalidate a conjunctive query\)\. By doing so, we can identify tuples as actual causes\. However, instead of tuple interventions in relation to the query at hand, we can reduce the problem to a CBD problem\.

Since we wantinvalidate the query, the query is transformed into its negation, which becomes adenial integrity constraintonDD, namely,κ:¬∃x​∃y​\(S​\(x\)∧R​\(x,y\)∧S​\(y\)\)\\kappa\\\!:\\ \\neg\\exists x\\exists y\(S\(x\)\\wedge R\(x,y\)\\wedge\\ S\(y\)\), which prohibits the satisfaction of the query join\. It holds that𝒬\\mathcal\{Q\}is satisfied byDDiffκ\\kappais violated byDD, which should be considered the faulty behavior under normal conditions\. Accordingly, we specify a weak model of failure:

D∪\{∀x∀y\(¬𝐴𝑏𝑆\(x\)\\displaystyle D\\ \\cup\\ \\\{\\forall x\\forall y\(\\neg\{\\it AbS\}\(x\)\\\!\\\!\\\!∧\\displaystyle\\wedge¬𝐴𝑏𝑅​\(x,y\)∧¬𝐴𝑏𝑆​\(y\)⟶\\displaystyle\\\!\\\!\\\!\\neg\{\\it AbR\}\(x,y\)\\wedge\\neg\{\\it AbS\}\(y\)\\ \\longrightarrow\(\(S\(x\)∧R\(x,y\)∧S\(y\)\)→𝑓𝑎𝑙𝑠𝑒\)\}\.\\displaystyle~~~~~~~~~~\(\(S\(x\)\\wedge R\(x,y\)\\wedge S\(y\)\)\\rightarrow\{\\it false\}\)\\\}\.
The model includes an abnormality predicate for each relational predicate, and an always false propositional atom𝑓𝑎𝑙𝑠𝑒\{\\it false\}\. This formula says that when the tuples are not abnormal, they do not participate in the violation of the ICκ\\kappa\. That is, under normality assumptions, the database does not make the query true\.

Here, the observation is𝒬\\mathcal\{Q\}itself, which, being true inDD, combined with \([9](https://arxiv.org/html/2605.08688#S5.Ex4)\) produces an inconsistent theory when the𝐴𝑏𝑆\{\\it AbS\}\- and𝐴𝑏𝑅\{\\it AbR\}\-atoms in \([9](https://arxiv.org/html/2605.08688#S5.Ex4)\) are all false\. According to CBD, for the combinations ofSS\- andRR\-atoms that make the join true, some of those abnormality atoms have to be true\. In particular, at least one of𝐴𝑏S​\(c\)\{\\it Ab\}\_\{S\}\(c\),𝐴𝑏R​\(c,b\)\{\\it Ab\}\_\{R\}\(c,b\),𝐴𝑏R​\(b\)\{\\it Ab\}\_\{R\}\(b\)has to be true\. The tuples whose associated abnormality atoms become true are the actual causes for the query\.

From the minimal diagnoses that contain a tuple, we can compute minimal contingency sets for it, and eventually, its responsibility\.■\\blacksquare

In\[[4](https://arxiv.org/html/2605.08688#bib.bib4)\], this kind of reduction from actual causality for QA in DBs to CBD turned out to be useful to obtain algorithmic and complexity results for responsibility in DBs\. This was achieved via algorithms based on computing diagnoses as hitting\-sets ofconflictsin CBD\[[24](https://arxiv.org/html/2605.08688#bib.bib24)\];222Aconflictin CBD is a set of negativeab\-literals whose conjunction is inconsistent with the CBD model plus the observation\.and also via results for minimum\-sizeDB repairsfor the inconsistency associated to the denial constraints\[[3](https://arxiv.org/html/2605.08688#bib.bib3),[21](https://arxiv.org/html/2605.08688#bib.bib21)\]; minimum\-size due to the need for minimum\-size contingency sets that underlie responsibility\.

## 6Conclusions

We have barely started to scratch the surface of the connections between consist\-ency\-based diagnosis and actual causality, and their applications to XAI and XDM\. The connections are interestingper se, and could be extended in different directions\. Going beyond the propositional setting would be interesting, and useful\. Related to this, in\[[6](https://arxiv.org/html/2605.08688#bib.bib6)\]\(see also\[[9](https://arxiv.org/html/2605.08688#bib.bib9)\]\), the responsibility attribution score was extended to the non\-binary case\. The extension is not trivial, and deserves more investigation\. Similar challenges should appear around a connection to CBD\.

Several computational techniques and results have been introduced and established in actual causality cum responsibility, on one side, and CBD on the other; following independent paths\. For example, it would be interesting to investigate the meaning and applicability of the notion ofkernel diagnosis\[[16](https://arxiv.org/html/2605.08688#bib.bib16)\]when applied to actual causality\. It would also be interesting to investigate its connections to thecoreof database repairs\[[11](https://arxiv.org/html/2605.08688#bib.bib11)\], and closer connections with sufficient \(or abductive\) explanations\[[16](https://arxiv.org/html/2605.08688#bib.bib16), sec\. 6\]\.

By applying actual causality in a CBD setting, we have been able to use the quantitative responsibility score to identify the most relevant \(elements\) of diagnoses\. It would be interesting to develop algorithms for computing early, or only, highly relevant diagnoses or elements thereof\. Such an idea was already proposed in\[[16](https://arxiv.org/html/2605.08688#bib.bib16), sec\. 8\], but without relation to responsibility\. Instead they propose using additional domain or probabilistic knowledge\. This could also be interesting in a setting where responsibility is applied\.333For responsibility under database integrity constraints, which goes along these lines, see\[[5](https://arxiv.org/html/2605.08688#bib.bib5),[8](https://arxiv.org/html/2605.08688#bib.bib8)\]\.

Acknowledgements:L\. Bertossi has been financially supported by the IMFD, Chile; and NSERC\-DG 2023\-04650, Canada\.

## References

- \[1\]Audemard, G\., Lagniez, J\.\-M\., Marquis, P\. and Szczepanski, N\. On the Computation of Example\-Based Abductive Explanations for Random Forests\. Proc\. IJCAI 2024, pp\. 3679\-3687\.
- \[2\]Arenas, M\., Barcelo, P\., Bertossi, L\. and Monet, M\. On the Complexity of SHAP\-Score\-Based Explanations: Tractability via Knowledge Compilation and Non\-Approximability Results\.J\. Mach\. Learn\. Res\., 2023, 24\(63\):1\-58\.
- \[3\]Bertossi, L\.Database Repairing and Consistent Query Answering\. Synthesis Lectures in Data Management\. Morgan & Claypool, 2011\.
- \[4\]Bertossi, L\. and Salimi, B\. From Causes for Database Queries to Repairs and Model\-Based Diagnosis and Back\.Theory of Computing Systems, 2017, 61\(1\):191\-232\.
- \[5\]Bertossi, L\. and Salimi, B\. Causes for Query Answers from Databases: Datalog Abduction, View\-Updates, and Integrity Constraints\.Int\. J\. Approximate Reasoning, 2017, 90:226\-252\.
- \[6\]Bertossi, L\., Li, J\., Schleich, M\., Suciu, D\. and Vagena, Z\. Causality\-Based Explanation of Classification Outcomes\. Proc\. 4th WS Data Management for End\-To\-End Machine Learning \(SIGMOD\-DEEM\), 2020, pp\. 6:1\-6:10\.
- \[7\]Bertossi, L\. Declarative Approaches to Counterfactual Explanations for Classification\.Theory and Practice of Logic Programming, 2023, 23\(3\):559–593\.
- \[8\]Bertossi, L\. From Database Repairs to Causality in Databases and Beyond\.TLDKS, Springer LNCS 14160, 2023, pp\. 119\-131\.
- \[9\]Bertossi, L\. Attribution\-Scores in Data Management and Explainable Machine Learning\. Invited tutorial paper in Proc\. ADBIS’23, Springer LNCS 13985, 2023, pp\. 16\-33\.
- \[10\]Bertossi, L\. and León, J\. E\. Efficient Computation of Shap Explanation Scores for Neural Network Classifiers via Knowledge Compilation\. Proc\. JELIA’23, Springer LNCS 14281, 2023, pp\. 49\-64\.
- \[11\]Bertossi, L\. and Pardal, N\. Sufficient Explanations in Databases and their Connections to Database Repairs\. arXiv paper 2511\.15623\.
- \[12\]Bienvenu, M\., Figueira, D\. and Lafourcade, P\. Shapley Revisited: Tractable Responsibility Measures for Query Answers\. Proc\. ACM on Management of Data, 2025, 3\(2\)112, pp\. 1–26\.
- \[13\]Biradar, G\., Izza, Y\., Lobo, E\., Viswanathan, V\. and Zick, Y\. Axiomatic Aggregations of Abductive Explanations\. In Proc\. AAAI 2024, 2024\.
- \[14\]Chockler, H\. and Halpern, J\. Responsibility and Blame: A Structural\-Model Approach\.J\. Artif\. Intell\. Res\., 2004, 22:93\-115\.
- \[15\]Darwiche, A\. Logic for Explainable AI\. Proc\. LICS 2023, pp\. 1\-11\.
- \[16\]de Kleer, J\., Mackworth, A\. and Reiter, R\. Characterizing Diagnoses and Systems\.Artif\. Intell\., 1992, 56\(2\-3\):197\-222\.
- \[17\]Halpern, J\. and Pearl, J\. Causes and Explanations: A Structural\-Model Approach\. Part I: Causes\.The British Journal for the Philosophy of Science, 2005, 56\(4\):843\-887\.
- \[18\]Halpern, J\.Actual Causality\. MIT Press, 2016\.
- \[19\]Huang, X\., Cooper, M\. C\. Morgado, A\., Planes, J\. and Marques\-Silva, J\. Feature Necessity and Relevancy in Machine Learning Explanations\.J\. Automated Reasoning, 2026, 70\(1\):4\.
- \[20\]Janzing, D\., Minorics, L\. and Blöbaum, P\. Feature Relevance Quantification in Explainable AI: A Causal Problem\. Proc\. 23rd International Conference on Artificial Intelligence and Statistics \(AISTATS\) 2020, PMLR: Vol\. 108\.
- \[21\]Lopatenko, A\. and Bertossi, L\. Complexity of Consistent Query Answering in Databases under Cardinality\-Based and Incremental Repair Semantics\. Proc\. ICDT, 2007, Springer LNCS 4353, pp\. 179\-193\. Extended version in arXiv paper 1605\.07159\.
- \[22\]Meliou, A\., Gatterbauer, W\., Moore, K\. F\. and Suciu, D\.The Complexity of Causality and Responsibility for Query Answers and Non\-Answers\.Proc\. VLDB 2010, pp\. 34\-41\.
- \[23\]Pearl, J\.Causality: Models, Reasoning and Inference\. Cambridge University Press, 2nd Ed\., 2009\.
- \[24\]Reiter, R\. A Theory of Diagnosis from First Principles\.Artificial Intelligence, 1987, 32\(1\):57\-95\.
- \[25\]Schölkopf, B\. Causality for Machine Learning\. InProbabilistic and Causal Inference: The Works of Judea Pearl, 2022, pp\. 765\-804\.
- \[26\]Struss, P\. Model\-Based Problem Solving\. InHandbook of Knowledge Representation, Chap\. 4, Elsevier, 2008, pp\. 395\-465\.