We present a new reduction of inconsistency-tolerant query answering to acceptance in ADFs. In particular, we consider knowledge bases (KBs) that use existential rules, and consider common inconsistency-tolerant semantics based on maximal consistent subsets. While reductions of inconsistency-tolerant reasoning to argumentation frameworks have been considered before, we aim to obtain a reduction that reflects the inference structure of the KB on a fine-grained level, so that they can be used to explain query answers on the level of individual inference steps. In particular, in our ADFs, every node corresponds to a fact derived in the chase, and acceptance conditions are used to relate facts using inference rules and integrity constraints. We show that our reduction satisfies rationality postulates, and observe that common semantics of ADFs fail to fully reproduce inconsistency-tolerant query answering with our reduction. We introduce a new semantics as refinement of the preferred semantics, which solves this problem, and analyze the computational complexity of this new semantics in the general and in our case.
One of the main advantages of symbolic AI is explainability.
However, while most symbolic AI systems are explainable
in theory, in practice, providing human understandable
explanations remains a challenge that recently received a lot
of attention [
While earlier works on explainability focus on providing
subsets of the data and/or rule sets as explanations [
0000-0002-5806-1012 (A. Keshavarzi Zafarghandi); 0000-0001-5999-2583 (P. Koopmann) © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). frameworks (AFs) to represent inconsistency-tolerant reasoning, where each argument has itself a complex structure consisting of a support (facts from the database) and conclusions (facts derivable from the support), but the relation between those two sets is not explained.
Motivated by this short-coming, we introduce a new
translation of inconsistent KBs into Abstract Dialectical
Frameworks (ADFs) [
We show that the translated ADFs satisfy desirable
rationality postulates for such a translation, when using the
well-established admissible and preferred semantics.
However, it turns out that the preferred semantics does not
capture the usual inconsistency-tolerant semantics of KBs [
Since meaningful query answers cannot be obtained from
inconsistent KBs under classical semantics based on first
order logics, recent research has explored various approaches
to address this challenge. 1. Inconsistency-Tolerant
Semantics: This approach focuses on developing semantics for
query answering that can handle inconsistencies in the KB.
Some works define repairs, which are subsets of the KB that
are consistent, and then use these repairs to determine the
answer to a query [
While query answering has long been a cornerstone of
database research (e.g., [
A number of works link argumentation and
nonmonotonic reasoning. The process of converting KBs into
AFs has been a well-studied area (e.g., [
However, abstraction also has limitations. While abstract
formalisms and their semantics aim to identify a
conflictfree set of arguments, these arguments might still not draw
rational conclusions when mapped back to the original
KB [
Building on their previous work ([
To leverage the advantages of abstract argumentation formalisms—namely, systematically dealing with inconsistencies and using the structure of the argumentation graph to enhance transparency—the first task of this work is to transform a KB to an abstract argumentation formalism. The second task is to investigate whether the induced argumentation formalism from the given KB satisfies rationality postulates.
While several works have instantiated KBs into abstract
argumentation frameworks (AFs) and show that the
resulting framework satisfies rationality postulates (e.g., [
While [
Since ADFs allow nodes to represent statements, each fact from a strict KB can be directly translated into an abstract node within the ADF. This simplified approach enables the construction of the associated ADF from a KB in polynomial time with respect to the size of a chase of a KB.
Furthermore, in our paper we show that the resulting ADF satisfies the rationality postulates under preferred semantics. Additionally, a new type of semantics for ADFs is introduced. This new semantics is shown to be equivalent to the chase procedure applied to a repair of the original KB.
We assume the reader is familiar with basics of first-order
logics. Given sets and , we use | as alternative
notation for ∩ .
3.1. Abstract Dialectical Frameworks
We summarize key concepts of ADFs [
Definition 1. An abstract dialectical framework (ADF) is a tuple = (, , ) where:
3. = { }∈ contains, for each ∈ , a propositional formula over
par () = { ∈ | (, ) ∈ }.
An ADF can be represented by a graph in which nodes indicate arguments/statements and links show the relations between them. Intuitively, the acceptance condition of each statement clarifies under which conditions the statement can be accepted.
An interpretation (for ) is a function : ↦→ {t, f , u} that maps statements to one of the three truth values true (t), false (f ), and undecided (u). is called two-valued if for every ∈ , () ∈ {t, f }. The trivial interpretation u satisfies u() = u for all ∈ . For brevity, we sometimes identify with the corresponding set of literals { | () = t} ∪ {¬ | () = f }.
For instance, = { → f , → t, → u} corresponds to {¬, }. Furthermore, we set t = {| () = t}. We lift interpretations to propositional formulas ( ) = over , where is obtained from by replacing every ∈ by ⊤ if () = t, by ⊥ if () = ⊥, and keeping it if () = u. Given a statement ∈ , is called acceptable w.r.t. if is irrefutable (a tautology). The semantics are defined via the characteristic operator Γ .
of . The charecteristic operator Γ is defined by Γ () = ′, where for each ∈ , ′() = t if is irrefutable, ′() = f if is unsatisfiable, and ′() = u, otherwise.
The information ordering < on truth values is the smallest ordering satisfying u < t and u < f . ≤ is the reflexive closure of <. We extend ≤ to interpretations by setting ≤ if () ≤ () for each ∈ .
A semantics for ADFs now assigns to each ADF a set of interpretations. Most types of semantics for ADFs are based on the concept of admissibility. An interpretation for a given ADF is called admissible if ≤ Γ (); it is preferred if is ≤ -maximal admissible; it is complete if = Γ (); it is the grounded interpretation of if is the least fixed point of Γ ; it is a (two-valued) model if is two-valued and Γ () = ; it is stable if is a twovalued model of and t = t, where is the grounded interpretation of the stb-reduct = (, , ), where = t, = ∩ ( × ), and [/⊥ : () = f ] for each ∈ .
The set of all interpretations for an ADF is denoted by (), where ∈ {adm, prf, com, grd, mod, stb} abbreviates the diferent semantics in the obvious manner. Definition 3. Let a semantics for ADFs, = (, , ) be an ADF, ∈ and and interpretation.
asks whether ∈ (). 2. The credulous acceptance problem, denoted by
Cred (, ), asks if for some ∈ (), () = t. 3. The skeptical acceptance problem, denoted by
Skept (, ), asks if for each ∈ (), () = t. 3.2. Existential Rules An atom is an atomic formula (⃗) for some predicate , which is ground if ⃗ contains only constants. An instance is a set of first-order ground atoms, which is called a database if it is finite. For convenience, we identify first-order interpretations with instances. An existential rule is a first-order formula of the form ∀⃗, ⃗(⃗, ⃗) → ∃⃗ (⃗, ⃗), and an integrity constraint is a formula of the form ∀⃗, ⃗(⃗, ⃗) → ⊥, where (⃗, ⃗) are possibly empty conjunctions of atoms. We call (⃗, ⃗) the body, and ∃⃗ (⃗, ⃗) the head of the rule, and treat those conjunctions as sets, i.e. the order of conjuncts is not relevant. Existential rules and integrity constraints are collectively called rules, and for convenience, we leave out the universal quantification when writing them. A program is a set of rules, and a knowledge base (KB) is a tuple = ⟨, ⟩ with a database and a program, which we identify with the first-order theory ∪ .
A conjunctive query (CQ) is a first-order formula of the form (⃗) = ∃⃗(⃗, ⃗), where (⃗, ⃗) is a conjunction of (A1) (A2) (A3) (A4) (A5) (A6) (A7) (A8)
DL Syntax
⊑ 1 ⊓ 2 ⊑ ⊓ ⊑ ⊥ ⊑ ∃. ⊑ ∀. ⊑ ∃.Self
⊑ ∘ ⊑
Corresponding Rule
() → () 1() ∧ 2() → ()
() ∧ () → ⊥ () → ∃.(, ) ∧ () () ∧ (, ) → ()
() → (, ) (, ) → (, ) (, ) ∧ (, ) → (, ) atoms over ⃗, ⃗ and the set of constants. An answer to this query is a vector ⃗ of constants s.t. |= (⃗).
Query entailment for KBs can be characterized using the chase, and in this paper, it is convenient to use the so-called Skolem chase for this. To define the Skolem chase, we first define the Skolemization of , which is obtained from by replacing every existentially quantified variable in an existential rule (⃗, ⃗) → ∃⃗ (⃗, ⃗) by the term (⃗, ⃗), where is a function symbol that is unique to that rule and the variable . The grounding ℎ of wrt contains all ground rules that can be obtained by replacing the variables in with terms obtained using the constants and function symbols in ∪ . Note that ∪ ℎ is essentially a possibly infinite set of propositional Horn formulas.
A ground existential rule can be applied on an instance if its body occurs in , and the result of this application is then obtained by adding its head to . The Skolem chase, denoted by chase(), is now the fixpoint of a fair application of the existential rules in ℎ on . Here, fair means that every applicable rule is eventually applied.
It is well known that is consistent if = chase() does not invalidate any integrity constraint in . In this case, for every CQ, the answers over are exactly the answers over chase().
In the context of this paper, we look at fragments of the
full language of existential rules. Many description logics
of the Horn-family can be translated into rules (see Table 1).
We focus on programs for which chase() is finite, which
is for instance the case if
• is datalog, i.e. it contains neither existentially
quantified variables nor function symbols, or
• is cycle-restricted (see [
Definition 4 (ABox repair). An ABox repair for a KB = ⟨, ⟩ is a ⊆ -maximal ′ ⊆ s.t. ⟨′, ⟩ ̸|= ⊥. We use Repairs(, ) = Repairs() to denote the set of all such repairs.
In this paper, we focus on the following semantics for inconsistency-tolerant query answering.
Definition 5. Given a KB = ⟨, ⟩ a query (⃗) and a vector ⃗ of constants the length of ⃗, 1 · · · 1 · · ·
|=AR (⃗), if for every repair ′ ∈ Repairs(), ⟨, ′⟩ |= (⃗).
|=brave (⃗), if for some repair ′ ∈ Repairs(), ⟨, ′⟩ |= (⃗). 4. Induced ADF from a given KB Our idea is to represent atoms in the chase directly as statements in the ADF, and use links to capture rule inferences as well as conflicts detected through integrity constraints. This way, understanding why a query is entailed under a certain semantics or not can be exhibited by navigating through the graph and analyzing the propagation of facts and conflicts.
We show that our translation satisfies common rationality postulates, but also that standard semantics for ADFs are not able to reproduce usual semantics for inconsistency-tolerant reasoning with our formalization. We thus introduce a new semantics for ADFs called min-′-max preferred semantics (Definition 8). In particular, we will be able to show that the extensions wrt that semantics correspond to chases of repairs.
We focus on queries of a single atom, as more complex queries can be reduced to them: for a given query (⃗) ← ∃⃗.(⃗, ⃗), we would simply add the rule (⃗, ⃗) → (⃗), where is a fresh predicate. Another assumption we make w.l.o.g. is that integrity constraints always contain exactly two atoms. Recall that ℎ refers to the grounding of . Definition 6 (Induced ADF). Let = ⟨, ⟩ be KB. Its induced ADF () = (, , ) is defined as follows: 1. = chase() 2. for each ∈ , contains the acceptance condition of defined as = 1 ∧ 3 if ∈ , and otherwise as = 1 ∧ 2 ∧ 3 , where,
1 = ⋀︁ {︀ ⋀︁ → | ∧ ⋀︁ → ∈ ℎ, =1 =1
∈ , ∈ }︀ 2 = ⋁︁ {︀ ⋀︁ | ⋀︁ → ∈ ℎ, ∈ }︀ =1 =1 3 = ⋀︁ {︀ ¬ | ∧ → ⊥ ∈ ℎ, ∈ }︀ 3. contains ⟨, ⟩ for every and s.t. occurs in Figure 1 shows a partial illustration of the induced ADF.
The intuition behind 3 of is as follows: if there is an integrity constraint ∧ → ⊥, and , ∈ chase(), then and cannot be both in the chase of a repair.
2 intuitively ensures that every accepted statement is justified through inferences in the chase, starting from the facts in a repair. If is a head of some rule, is in the chase of a repair ′ if all the premises (body) of at least one of the rules are in the chase of ′.
Finally, the intuition behind 1 is as follows: if occurs in the body of a rule and all atoms in the body are satisifed, then the head has to be satisfied as well. If the acceptance condition of makes it impossible for to be satisfied, e.g. because conflicts with another atom that we assigned to true, then cannot be accepted either, since otherwise a rule in would not be satisfied in the interpretation.
We demonstrate the soundness of our transformation.
To achieve this, we adopt a two-step approach. First, we
establish the rationality of the constructed ADF. We do this
by verifying that the induced ADF satisfies the well-known
rational postulates for argumentation formalisms [
Second, we investigate the correspondence between interpretations of our ADFs and KB repairs. We illustrate with examples why the current semantics of ADFs is insuficient for capturing exactly the set of repairs and their chases. We then define a new semantics based on a subclass of preferred interpretations, and show that this semantics does allow us to reproduce query entailment under standard inconsistency-tolerant semantics using credulous and skeptical acceptance.
Before going to the formal proofs, we illustrate the transformation process with some examples. We first look at the consistent case.
Example 1. Let = ⟨, ⟩ be KB such that = {()} and = {() → ()}. Then the chase of is {(), ()}. The set of statements in the induced ADF () is = {(), ()}. The acceptance conditions are () has two preferred interpretations: 1 = {(), ()} and 2 = {¬(), ¬()}, and only 2 is a stable model of ().
Intuitively, a repair of a KB is a maximal consistent set of facts from the database. Similarly, a preferred interpretation of an ADF contains the maximal information (w.r.t. ≤ ordering) about the acceptance of statements. In Example 1, while interpretation 1 accepts both and , 2 rejects both. The repair of is 1t|, and 1t is the chase of this repair. Thus, although preferred interpretations contain the maximum information about the acceptance of the statements, since all statements that support each other in a loop can be assigned to f together in a preferred interpretation, the set of preferred interpretations does not coincide with the set of repairs of the associated KB. Moreover, this example demonstrates a distinction between the set of stable interpretations of the induced ADF and the repairs of the given KB. Example 2 contains an integrity constraint. Example 2. Let = ⟨, ⟩ be KB such that = {(), ()} and = {() → (), () → (), () ∧ () → ⊥}. Then the set of statements in () is = {(), (), (), ()} and the acceptance conditions are
tency for admissible semantics.
Observe that 1t ̸⊆ 2t and 2t ̸⊆ 1t. Both 1t| and 2t| are repairs for , furthermore 1t and 2t coincide with the chases of the repairs of .
While in Example 2, the set of preferred interpretations
and the set of repairs coincide, we will later see that this is
not always the case. Before we further explore the
relationship between ADF semantics and the set of repairs for the
KB in Section 4.2, we show that the induced ADF satisfies
the rationality postulates defined in [
Postulate 1 (Closure). Given KB = ⟨, ⟩, () satisifes closure for semantics if for any -interpretation , it holds that t = chase(t).
Another crucial property of induced ADFs is consistency.
The literature [
Definition 7. Given KB = ⟨, ⟩, its induced ADF , we call an interpretation is consistent if for each ∧ → ⊥ ∈ ℎ s.t. () = t, we have () ̸= t.
Postulate 2 (Direct Consistency). Given KB = ⟨, ⟩ and its induced ADF (), () satisfies direct consistency for semantics if each -interpretation is consistent. Postulate 3 (Indirect Consistency). Given KB = ⟨, ⟩ and its induced ADF (). () satisfies indirect consistency for semantics if for each -interpretation , Cl() is consistent.
We show that the induced ADF defined in Definition 6 satisfy those rationality postulates under admissible semantics.
missible semantics.
Proof. Let = ⟨, ⟩. We show that for each admissible interpretation of (), chase(t) = t. t ⊆ chase(t) follows directly from the definition of the chase, so that we only need to show chase(t) ⊆ t. Let ⋀︀=1 → ∈ ℎ be such that ∈ t for each 1 ≤ ≤ . We need to show that then, ∈ t. It follows from 1 in the acceptance condition of each , and the fact that is admissible, that is if () = t for each , then (⋀︀̸= → ) ≡ ⊤ . Thus, since () = t for each 1 ≤ ≤ , we obtain () = t. Hence, Cl() = t for each admissible interpretation .
Proof. Toward a contradiction, assume () does not satisfy direct consistency for admissible semantics. Thus, there exists an admissible interpretation of (), and there exists ∧ → ⊥ ∈ ℎ s.t., , ∈ t. Since, by Definition 6, ¬ is in the acceptance condition of and is admissible, if () = t, we must have () = f . Thus, the assumption that , ∈ t cannot be true.
sistency for admissible semantics.
Proof. This follows from Theorem 1 and Theorem 2. 4.2. Minmax-preferred semantics for ADFs Since a preferred interpretation of an ADF is a ≤ -maximal admissible interpretation, the preferred semantics of ADFs can be a candidate for evaluating ABox repair semantics of the associated KB . In Example 2 (an inconsistent KB), each preferred interpretation of the induced ADF corresponds to a repair of the original KB, . However, in Example 1 (a consistent KB), only one of the preferred interpretations, which is not a stable model, is a repair. This demonstrates that stable models of the induced ADF do not have to correspond to repairs. Examples 1–2 indicate that, if t| should coincide with a repair of , t| needs to be subsetmaximal among preferred interpretations. This is however not suficient, as it is illustrated by Example 3.
Example 3. Let = ⟨, ⟩ be a KB such that = {(), ()} and contains the following rules: () ∧ () → ⊥ () ∧ () → () () ∧ () → () () → () () → ()
() : ¬() ∧ (() → ()) ∧ (() → ()) () : ¬() ∧ (() → ()) ∧ (() → ()) () : ((() ∧ ()) ∨ ()) ∧ () () : ((() ∧ ()) ∨ ()) ∧ ()
t|, and indeed contains a repair: = {(), ¬(), (), ()}
To reproduce inconsistency-tolerant semantics, our interpretations do not only need to capture the repairs, but also their entailments, as produced by the chase. Together, our examples illustrate what needs to be done to obtain a semantics that fully characterizes entailments of repairs. First, we need to maximize the set of statements that correspond to facts from the database. This aligns with the definition of repairs to be subset-maximal consistent subsets of the database. In addition, we have to minimize the set of derived statements, to reflect the minimality of the chase that contains only facts that can be deduced from the database.
In Definition 8, we define a new type of semantics for ADFs called min-′-max preferred semantics, which uses as parameter a set ′ ⊆ of statements to be maximized. While our definition is generic to any set ′, we will later instantiate ′ with , to address the first point made above. An interpretation is considered min-′-max preferred if it is maximal not only with respect to the ≤ ordering but also with respect to ⊆ concerning ′ ⊆ . That is, t|′ = t ∪ ′ has to be maximal among the preferred interpretations. Furthermore, t has to be minimal w.r.t. ⊆ relation among all chosen interpretation in the previous step.
Definition 8. Let = (, , ) be an ADF, and let ′ ⊆ . An interpretation is min-′-max preferred interpretation (for ), in symbols ∈ min-′-max-prf(), if ∈ prf() and 1. t|′ is maximal among all preferred interpretations of , i.e., if ∈ prf(), then t|′ ̸⊂ t|′ , 2. t is minimal among all ∈ prf() s.t. t|′ = t|′ , i.e., t ̸⊂ t for any such .
Note that the order of the conditions in Definition 6 is crucial. First, we select a preferred interpretation as a candidate. The first condition checks if t|′ is maximal among all t|′ , where ∈ prf(). Then, the second condition verifies if t is minimal among the interpretations chosen in the first step.
Returning to Example 3, we observe that for ′ = , is not min--max preferred, since () and () contradict the minimality criterion, but assigning those statements to f , we obtain a min--max preferred interpretation, which corresponds to the chase of a repair as required. Lemma 4. Let = (, , ) be an ADF, and let ′ ⊆ . 1. Every ADF has at least one min-′-max preferred interpretation w.r.t. ′.
Proof. Every ADF has at least one preferred interpretation. Among these preferred interpretations, there exists at least one interpretation such that t|′ is subset-maximal among all t|′ , where is a preferred interpretation. Furthermore, within this set of interpretations, there exists at least an interpretation such that t is minimal among all , where t = t and ∈ prf().
The second item is evident from the definition of the min-′-max-prf semantics, as presented in Definition 8. This definition states that the set of all min-′-max-prf for is a subset of the set of all preferred interpretations of .
The last two items are shown by our examples.
Returning to our induced ADFs, since every min-′-max preferred interpretation is admissible, we have the following result.
Corollary 5. Given KB = ⟨, ⟩ and its induced
min-′-max-prf semantics (for any ′). Our final aim is to show that our induced ADFs can be used for inconsistency-tolerant query answering. In particular, we want to show that atomic query entailment under AR and brave semantics corresponds to skeptical and credulous acceptance under min-′-max preferred semantics for the case ′ = , i.e. under min--max preferred semantics. For this, we need to show that min--max preferred interpretations do indeed capture the set of chases of ABox repairs.
We first show how admissible interpretations can be constructed from repairs.
Lemma 6. Given a KB = ⟨, ⟩, ′ ∈ Repairs(), and let be an interpretation of () s.t. for each ∈ , () = t if ∈ chase(′), and () = f otherwise.
Proof. We have to show that () = Γ ()() if () ∈ {t, f }. Let = 1 ∧ 2 ∧ 3 be the acceptance condition of in (), as introduced in Definition 6, where for convenience, we set 2 = ⊤ in case ∈ .
Assume that () = t. To show that is an admissible interpretation, we show that Γ ()() = t. For this, we need to show that ≡ ⊤ , in particular that ( 1 ) ≡ ( 2 ) ≡ ( 3 ) ≡ ⊤ . Toward a contradiction, assume that ( ) ≢ ⊤ . Since is two-valued, then ( ) ≡ ⊥ , which means that ( 1 ) ≡ ⊥ , ( 2 ) ≡ ⊥ , or ( 3 ) ≡ ⊥.
• First, we assume that ( 1 ) ≡ ⊥ . That is, there exists ∧ ⋀︀=1 → ∈ ℎ such that (⋀︀=1 → ) ≡ ⊥ , i.e., () = t for each , but () = f . However, if () = t, then by the definition of , ∈ chase(′). Since ∈ chase(′) for each , and ∈ chase(′), our rule in applies and ∈ chase(′). It follows that () = t by construction. This is a contradicts our assumption, so that ( 1 ) ≡ ⊥ cannot hold. Consequently, ( 1 ) ≢ ⊥ . • Next, assume that ( 2 ) ≡ ⊥ . Then, for each ⋀︀ ℎ, there must exist an , s.t., =1 → ∈ () = f . By the definition of interpretation , then ̸∈ chase(′). If for each ⋀︀ =1 → ∈ ℎ, there exists , s.t., ̸∈ chase(′), cannot be derived, and ̸∈ chase(′), so that () = f . This is a contradiction by the assumption that () = t. We obtain that ( 2 ) ≢ ⊥ . • Finally, assume that ( 3 ) ≡ ⊥ . That is, there ℎ s.t., (¬) = f , i.e., exists ∧ → ⊥ ∈ () = t. By the definition of interpretation , () = t implies that ∈ chase(′). This is a contradiction by the assumption that ′ is a repair because ∈ chase(′) and ∈ chase(′) would then imply that ′ is inconsistent. We obtain ( 3 ) ≢ ⊥ .
Thus, if () = t, then ( 1 ) ≡ ( 2 ) ≡ ( 3 ) ≡ ⊤ , which implies Γ ()()() = t.
Next we show that if () = f , then Γ ()()() = f . Assume () = f and Γ ()()() = t. This means that ( ) ≡ ⊤ , and in particular, ( 2 ) ≡ ⊤ , which could be due to some rule ⋀︀
=1 → ∈ ℎ s.t. () = t, or because ∈
First assume there is ⋀︀
=1 → ∈ ℎ s.t. () = t. By our construction, ∈ chase(′), which implies ∈ chase(′) by definition of the chase. This contradicts () = f , and thus ( 2 ) must be contradictory, and consequently also ( ) ≡ ⊥ .
Assume otherwise that ∈ . We show that this would imply that chase(′) ∪ {} is consistent, contrary to the assumption that ′ is a repair. We first show that chase(′) ∪ {} = chase(′ ∪ {}). Assume there is a rule ∧ 1 ∧ . . . ∧ → ∈ ℎ that is applicable on chase(′) ∪ {}, that is, 1, . . ., ∈ chase(′). From latter, it follows by construction that () = t for all 1 ≤ ≤ . Moreover, by construction of , 1 ∧ . . . ∧ → occurs as conjunct in 1 , and since ( 1 ) ≡ ⊤ , we must have () = t and ∈ chase(′). That means, the conclusion of every rule that is applicable on chase(′) ∪ {} is already in chase(′), so that indeed chase(′ ∪ {}) = chase(′) ∪ {}. It remains to show that ′ ∪ {} is consistent, for which we now only have to show that there is no ∧ → ⊥ ∈ ℎ s.t. ∈ chase(′). For any such integrity constraint, because ( 3 ) ≡ ⊤ and 3 contains ¬ as conjunct, () = f , and by construction of , ̸∈ chase(′). We obtain that ′ ∪ {} is consistent, contrary to the initial assumption that ′ is a repair. Correspondingly, the assumption that () = f and Γ ()() = t cannot be true.
We obtain that = Γ (), and thus that it is an admissible interpretation of .
Using Lemma 6, we first show that, if we restrict our attention to those statements that correspond to database facts, then indeed do min--max preferred interpretation capture the set of repairs. That is, the maximizing part of our semantics works as intended.
-max preferred interpretation of () s.t. t| = ′, and for every min--max preferred interpretation of (), there exists ′ ∈ Repairs() s.t. ′ = t|.
Proof. (⇒) Assume that ′ ∈ Repairs(). We show that () has a min--max preferred interpretation s.t., ′ = t|. We construct based on ′ as in the proof for Lemma 6. The constructed interpretation is an admissible interpretation of (). Furthermore, since each ∈ is either assigned to t or f , is a preferred and two-valued model of ().
It remains to show that is a min--max preferred interpretation of (). Toward a contradiction, assume that is not a min--max preferred interpretation of (). That is, either 1. t| is not maximal among all preferred interpretations of (), which means there exists ∈ prf(()) s.t., t| ⊂ t|; 2. or, there exists ∈ prf s.t., t| = t|, but t ⊂ t.
We first show that Item 1 cannot occur. Toward a contradiction, we assume that there exists ∈ prf() s.t., t| ⊂ t|. Set ′′ = t|. By construction, ′′ ⊆ and ′ ⊂ ′′. We can furthermore show that ′′ is consistent: because is preferred, by Theorem 1 we can apply Postulate 1 (closure), which by induction implies chase(′′) ⊆ t. Moreover, must satisfy Postulate 2 (consistency), chase(′′) does not invalidate any integrity constraints. This means that ′′ is consistent, so that ′ cannot be maximal and consistent, and thus not a repair.
Next, we show that Item 2 cannot occur. Assume that there exist a preferred interpretation s.t., t| = t|, but t ⊂ t. If t ⊂ t, then there exists ̸∈ t, and ∈ t. By construction, t = chase(). Furthermore, chase(′) = chase(t|) = chase(t|), because t| = t|, by our assumption. We obtain that ∈ chase(t|) but ̸∈ t, so that t ⊂ chase(t|). This means there must be rules in that are applicable on t but not applied, which contradicts Postulate 1, which by Theorem 1 means that cannot be a preferred extension, contrary to our initial assumption that ∈ prf().
(⇐) Assume that is a min--max preferred interpretation. Let ′ = t|. We show that ′ ∈ Repairs(), for which we need to show that ′ is consistent and a maximal subset of with that property.
First, we show that ′ is consistent. If ′ were inconsistent, then there would be an integrity constraint ∧ → ⊥ ∈ ℎ s.t. , ∈ chase(′). By repeated application of Postulate 1 (closure), we obtain that chase(′) = chase(t|) ⊆ t, which would imply that , ∈ t, contradicting Postulate 2 (consistency).
Next we have to show that ′ is maximal. Toward a contradiction assume that ′ is not maximal. Thus, there exits ′′ s.t., ′ ⊂ ′′ and ′′ is consistent.
In the same way as in the first part of this proof, we can construct a min--max preferred interpretation interpretation s.t. | = ′′. But then, we have found an interpretation ∈ prf(()) s.t. t| ⊂ t|, contradicting that is min--max preferred interpretation.
To be able to answer queries, which rely on derived facts, we need to also make sure that the chase is correctly relfected in our interpretations. Intuitively, we have to show that also the minimizing part of our interpretations works as intended.
-max preferred interpretation of () s.t. chase(′) = t, and for every min--max preferred interpretation , there exists ′ ∈ Repairs() s.t. chase(′) = t. Proof. The first direction follows directly from constructions we already used: the interpretation constructed in Lemma 6 based on any repair ′ satisfies chase(′) = t, and is shown to be min--max preferred interpretation.
For the other direction, let be a min--max preferred interpretation of (). By Lemma 7 there exists ′ ∈ Repairs() s.t. ′ = t|. Applying Postulate 1 (closure), we obtain chase(′) ⊆ t. By the previous direction, there exists a min--max preferred interpretation s.t., chase(′) = t. We obtain t ⊆ t, which by the minimality condition of the Definition 8 (Item 2), implies t = t. Hence, chase(′) = t.
Proof. This follows from the fact a consistent KB has exactly one repair, so that every min--max preferred semantics would have to capture exactly its chase. inconsistent.
Note that the converse of Corollary 9 does not hold: consider the KB = ⟨, ⟩ s.t., = {(), ()} and = {() →
⊥}. has one repair, the induced ADF exactly one min--max preferred interpretation, but is ADF of .
Theorem 10. Given a KB = ⟨, ⟩ a query (⃗) and a vector ⃗ of constants the length of ⃗. Let () be the induced
Skeptmin--max-prf((⃗), ()) is satisfied.
Credmin--max-prf((⃗), ()) is satisfied. satisfied. is satisfied.
Proof. By Theorem 8, for every ′ ∈ Repairs(), there exists a min--max preferred interpretation of () s.t. chase(′) = t, (and vice versa). Therefore, ⃗ is an answer of (⃗) under AR semantics, i.e., for every repair
′ ∈ Repairs(), ⟨, ′⟩ |= (⃗), if for each min- max preferred interpretation (of ()), ((⃗)) = t, since chase(′) = t, i.e., if Skeptmin--max-prf((⃗), ())
Similarly, ⃗ is considered an answer of (⃗) under brave semantics if for some repair ′ ∈ Repairs(), ⟨, ′⟩ |= (⃗), if and only if there exists an min--max preferred interpretation (of ()), such that ((⃗)) = t, since chase(′) = t, i.e., if Credmin--max-prf((⃗), t, ()) is
We first analyze the complexity of our new semantics for
the standard reasoning tasks of ADFs [
We make use of standard complexity classes of the
polynomial hierarchy [
Proof. Consider an arbitrary instance of the problem, that is, a given ADF = (, , ), a three-valued interpreta. We show membership in Σ3P for the complementary problem of not being a min-′-max pre
The algorithm guesses an interpretation , checks ∈
prf() (in Π2P [
Cred Σ2P-c Σ2P-c in ΣP
4 in NP
Skept trivial Π3P-c in ΠP
4 in coNP coNP-c Π2P-c Π3P-c in P Complexity under min-′-max preferred semantics of ADFs and of the induced ADF from a KB.
If any of the above items is successful, then ̸∈ min-′-max-prf(). Thus, the complementary problem Vermin-′-max-prf(, ) is in Σ3P. From this it follows that the verification problem is in Π3P for ADFs.
Proof. Let
= (, , ) be an arbitrary ADF, ∈ . To check if there exists a min-′-max preferred interpretation satisfying () = t, guess an interpretation with () = t, and then verify whether ∈ min-′-max-prf(). According to Theorem 11, verifying whether ∈ min-′-max-prf() is in Π3P. Thus, the comP bined guessing and checking process results in NPΠ3 = Σ4P.
Theorem 13. It holds that Skeptmin-′-max-prf is in Π4P for Proof. Given an ADF = (, , ), and a statement , answering Skeptmin-′-max-prf(, ) involves considering the complementary problem. In this case, we determine whether there exists a min-′-max preferred interpretation in which is not assigned to t. As per Theorem 11, the task of checking if is a min-′-max preferred interpretation of is in Π3P. Thus, Skeptmin-′-max-prf(, ) is in Π4 . P 5.2. Complexity of min--max preferred semantics on the induced ADFs The hardness results in the previous subsection all depend on the fact that already the admissibility-problem is coNPcomplete for ADFs. The ADFs we define in Definition 6 have a specific syntactic form that allows us to show admissibility in polynomial time.
Proof. To decide whether is admissible, we have to determine whether ≤ Γ (). We show that Γ () can be computed in polynomial time, which shows that this test is possible in polynomial time as well.
To compute Γ (), we need to determine, for each ∈ , whether ( ) is irrefutable, unsatisfiable, or contingent (Definition 2). Fix some such . We describe a deterministic procedure to compute Γ ()(). Roughly, we try to find a disjunction 2 which is irrefutable or contigent together with 1 ∧
2. We describe the procedure for each disjunct in the following. Each such disjunct is of the form ⋀︀ =1 and corresponds to a rule ⋀︀ =1 → ∈ ℎ.
To check satisfiability, we attempt to extend to a satisfying interpretation . If for some ∈ {1, . . . , }, () = f , we know that this disjunct cannot be satisfied in any extension of . Otherwise, we build a partial valuation 0 based on by setting 0() = t for every 1 ≤ ≤ , 0(′) = for every other atom ′ s.t. (′) ̸= u, and (′) = u for the remaining atoms. Then we iteratively go through the rules in ℎ that are relevant for the acceptance condition. In particular, we try to generate a sequence of partial valuations 0, . . ., as follows, where ≥ 0: 1. If 1 contains an implication 1 ∧. . .∧ → s.t. () = t for 1 ≤ ≤ and () = u, continue with +1 which extends by +1() = t. 2. If 3 contains a conjunct ¬ with () = t, we know that the current disjunct cannot be satisfied. 3. If 1 contains an implication 1 ∧ . . . ∧ → s.t. () = t for 1 ≤ ≤ and () = f , we know that the current disjunct cannot be satisfied. If for none of the disjuncts, we are successful, we know that cannot be satisfied by any valuation, and we can set Γ ()() = f . If we manage to find a partial valuation on which no more steps can be applied, we found a partial way of satisfying the acceptance condition, which means we know that is satisfiable, but not yet whether it is also irrefutable. For this, we just need to check whether there is some atom ′ s.t. (′) ̸= (′). If there is not, our process confirmed that all conjuncts of are already satisfied by , and we can set Γ ()() = t. If there is, we can find a valuation ′ that makes 1 ∧ 3 with the current disjunct false by setting ′() = f and ′(′) = (′) for all other atoms. If we cannot find a disjunct that justifies ′() = t, but showed satisfiability, we consequently can set Γ ()() = u.
But indeed, we know that more complexities go down:
P, Credmin--max-prf in NP and Skeptmin--max-prf in coNP. Proof. Consider an arbitrary instance of the problem, that is, a KB = ⟨, ⟩, the induced ADF (), and a threevalued interpretation (for ). By Lemma 8, if is a min-max preferred interpretation, then there exists ′ ∈ Repairs() s.t. chase(′) = t. Instead of checking if is a min--max preferred interpretation, we check if there is a repair ′ s.t. chase(′) = t. In this case, by Lemma 7, ′ = t| is a repair. Thus, first we check if t| is a repair. If it is, we check if chase(t|) = t. Both steps can be done in polynomial time. Therefore, Vermin--max-prf is in P.
For Credmin--max-prf, to check if there exists min-max preferred interpretation satisfying () = t, guess an interpretation with () = t and verify if ∈ min--max-prf(). Verification is in P. Therefore, Credmin--max-prf is in NP. For Skeptmin--max-prf we consider the complementary problem, i.e., we check if there is a ∈ min--max-prf(), s.t. () ̸= t.
We can use Theorem 15 directly to (re-)prove upper bounds for various settings of inconsistency-tolerant reasoning. As is common, we look at the decision problem corresponding to query answering, which is the query entailment problem which checks whether for a given instantiated query (⃗), |= (⃗). Recall that for data complexity, we assume the size of the program is fixed, while for combined complexity we assume both database and program to be given by the input.
• data complexity for datalog programs and acyclic
• combined complexity for ℰ ℒ+.
Proof. The first results rely only on the size of chase(), since the size of the induced ADF is polynomial in it. For Horn-ℛℐ, we observe by inspection of the rules in Table 1 that for a fixed acyclic program, each Skolem term contains exactly one variable, and consequently, each Skolem term in chase() contains exactly one constant, and its nesting depth is determined only by . Consequently, the number of terms in chase(), as well as of atoms, is also polynomial in the size of .
It remains the case of ℰ ℒ+, and here we have to be a bit more clever, since the chase can in general be exponential in size. Instead of building the ADF from the chase, we construct a representative chase of polynomial size that we use as basis for the ADF. For this, we convert into a program ′ by replacing all rules of the form (A3) by () → (, ) ∧ ( ), where is a fresh constant introduced for . chase(, ′) can now be computed in polynomial time by simple forwardchaining. One can also show that for every subset ′ ⊆ , there is an homomorphism from chase(, ) into chase(, ′) that maps every element to an element satisfying the same unary predicates. Using this, one can show that query answers can directly be determined based on the ADF induced from chase(, ′).
We proposed a method for using ADFs to answer queries over inconsistent KBs. ADFs are useful for this task because they ofer an abstract way to represent statements and arguments. To construct our framework, we consider each atom in the chase of a KB as an abstract node or statement. This eliminates the need to explicitly build statements within the ADF. We showed that the induced ADFs satisfy rationality postulates, and introduced a new semantics for ADFs that is needed to reproduce inconsistency-tolerant semantics for KBs. Finally, we gave some complexity upper bounds for this new semantics, which in the general case are higher than for preferred semantics, but substantially lower for the ADFs obtained with our construction.
In the future, we want to improve the complexity bounds
and provide matching lower bounds for the general case
of our new semantics. Furthermore, we want to
investigate how our ADFs can be used to provide explanations of
query answers for inconsistency-tolerant KBs to end-users.
An idea could be to extend the graphical, interactive
proofexploration tool Evonne [
This publication has been supported by the Netherlands Organisation for Scientific Research (NWO) through the Hybrid Intelligence Gravitation Programme with project number 024.004.022