An argumentative approach for handling inconsistency in prioritized Datalog ± ontologies

Abstract

Prioritized ${Datalog}^{\pm}$ is a well-studied formalism for modelling ontological knowledge and data, and has a success story in many applications in the (Semantic) Web and in other domains. Since the information content on the Web is both inherently context-dependent and frequently updated, the occurrence of a logical inconsistency is often inevitable. This phenomenon has led the research community to develop various types of inconsistency-tolerant semantics over the last few decades. Although the study of query answering under inconsistency-tolerant semantics is well-understood, the problem of explaining query answering under such semantics took considerably less attention, especially in the scenario where the facts are prioritized.

In this paper, we aim to fill this gap. More specifically, we use Dung’s abstract argumentation framework to address the problem of explaining inconsistency-tolerant query answering in ${Datalog}^{\pm}$ KB where facts are prioritized, or preordered. We clarify the relationship between preferred repair semantics and various notions of extensions for argumentation frameworks. The strength of such argumentation-based approach is the explainability; users can more easily understand why different points of views are conflicting and why the query answer is entailed (or not) under different semantics. To this end we introduce the formal notion of a dialogical explanation, and show how it can be used to both explain showing why query results hold and not hold according to the known semantics in inconsistent ${Datalog}^{\pm}$ knowledge bases.

Keywords

Argumentation inconsistency preferences prioritized knowledge bases explanation

1. Introduction

Formal ontologies have been remarkably successful in their wide-array of applications to various domains, including biomedics, cultural heritage, and the semantic web [8,28,29,38]. In particular, Datalog and Description Logics (DLs) (or the more closely related Web Ontology Language (OWL)) have been popular formal ontology languages due to their fine-balance between expressiveness and decidability [2,18,37]. Further, their lighter-weighted fragments such as guarded ${Datalog}^{\pm}$ , DL-Lite $EL$ family, respectively, have largely been a major focus of both applied and theoretical research due to their desirable computational properties [9,17,18].

Oftentimes in real-world applications, data collected from different resources give rise to conflicting information. In order to provide useful answers to user queries in such situations, research has been carried out on inconsistency-tolerant semantics in which one looks at maximal consistent subsets (also called repairs) [14,16,30,31]. When we have the information about the reliability of different data resources, we can exploit such information by giving higher priority to more reliable resources of data [40]. This can be done by using a preference relation over data resources representing their reliability. Operationalising this idea, various repair semantics with priorities (also called preferred repairs) have been proposed [11,14,31,33,39].

The explanation techniques for query answering in knowledge bases (KBs) under repair semantics, have received much less attention. Some existing approaches address explanations for reasoning tasks such as query entailment under various inconsistency-tolerant semantics in the presence of existential rules [32] or DL-Lite [16].1

¹
It should be noted that these works are in fact quite related i.e., the minimal explanation in Lukasiewicz’s work [32] can be seen as the cause defined in [16].

The main idea of these approaches is to define a set of assertions as an explanation that will lead to an answer which holds under the inconsistency-tolerant semantics. These include brave, ABox Repair (AR) and Intersection ABox Repair (IAR) semantics for the DL-Lite family of languages and

Datalog \pm

[16,32]. The main focus of these works has been on the computational aspect, however, the explanations aspect regarding the conflicting information (e.g., explaining why some answers are (not) accepted under repair semantics) are rather left limited. It is limited in the sense that conflicting information is harder to trace and pinpoint when one uses only the formal language. In our work, we use Dung’s abstract argumentation framework (AF) [23] which comes with a graph-based component, which is convenient when it comes to illustrate the critical structure that causes the conflict along with all the structural dependencies behind it.

AF has been a focus of study for a large amount of works in the literature of representation and reasoning with inconsistent KBs (see e.g., [4–7,13,21,22,27,41,42] and [3] for an overview). In some recent works [4,21,22,27,41], authors proposed various argumentation frameworks to provide a useful platform for representing and reasoning with maximally consistent subsets of prioritized KBs in propositional logic. In first order fragments, such as inconsistent ontological KBs, argumentation has also been a focus of several works [13,25,42]. A common feature of these works is that, they first show that their formal machinery outputs a set of extensions which is equivalent to the set of repairs of the KB, and then they study the computational properties of the repair semantics. Explanations aspect concerning the user perspective (i.e., explaining why the query is entailed or not in the inconsistent KB under some repairs), however, mostly stayed limited. As a result of that, the explanation techniques to allow users understanding querying process better is one of the recent challenges in KR research.2

Now, there is a new highly relevant annual workshop (The Third Workshop on Explainable Logic-Based Knowledge Representation) aiming this, and the related questions in general: https://sites.google.com/view/xlokr2022.

Some recent works in the argumentation-based line studied explanation for query answering under inconsistency-tolerant semantics [5–7]. The argumentation setting, here, provides with a dialectical characterization3

The actual term they use is dialectical, however for the alignment purposes of the terminology within our work, later in the paper we use the term dialogical.

of the brave and IAR semantics. However, they do not consider prioritised facts.

To the best of our knowledge, the problem of explaining inconsistency-tolerant query answering in prioritized ${Datalog}^{\pm}$ KBs has not been yet investigated through the lens of abstract argumentation framework. In this paper, we aim to close this gap. Namely, we employ Dung’s abstract argumentation theory for building a graphical representation to supply the user with an explanation that is rich enough in both (1) representing the supporting arguments of the query and (2) pinpointing the conflicting pieces of information that are relevant for the supporting arguments and the query in a graph structure. Hence, the main desirable feature of our work lies in this two-level explanation. In the first level, one can zoom in the argument to explain why it is logically derived from the KB under the particular semantics. We note that this notion coincides with the notion of cause defined in [13] and the minimal explanation defined in [32]. And the second level provides with a set of argumentation trees in which each can be seen as a dialogue between the user and the machine. We remark that this is an important aspect of developing explainable artificial intelligence (XAI) systems in which reasoners should display understandable explanations to users. We hope that our work will prove beneficial in achieving this long quest.

The main contributions of our paper are as follows:

We propose a new prioritized argumentation framework to address the problem of explaining query answers in inconsistent ${Datalog}^{\pm}$ KBs where priorities of facts are total preordered.

We formalise the relation between preferred repairs of the prioritized KB and extensions of the proposed argumentation framework.

We prove that the proposed AF satisfies rationality postulates from [1,19]. These are consistency, closure of extension, closure under sub-arguments, strong consistency, exhaustiveness and free precedence.

We exploit the equivalence between the preferred repairs of the prioritized KBs and the extensions of the proposed AF to provide dialogical explanations for the query answer under different semantics (see Section 5 for details).

This paper is structured as follows: Section 2 provides an overview of related works. Section 3 reviews abstract argumentation (in Section 3.1), ${Datalog}^{\pm}$ (in Section 3.2) and some elementary concepts such as the concepts of conflicts, repairs. Section 3.3 also presents a prioritized ${Datalog}^{\pm}$ KB in which the priority over facts is total, and preferred repair semantics used as the basis of inconsistency-tolerant query answering. In Section 4, we introduce a prioritized argumentation framework corresponding to the prioritized ${Datalog}^{\pm}$ KB where the priorities of facts are total preorder. We then clarify in Section 4.2 the relation between preferred repairs of given prioritized ${Datalog}^{\pm}$ KB and extensions of the proposed argumentation framework. We prove that such argumentation setting satisfies rationality postulates of [1,19] in Section 4.3. In Section 5, we focus on the use of argumentation framework for explanation techniques. Section 2 discusses related works, and Section 6 concludes the paper.

2. Related work

As mentioned in the introduction, there are only few works given in [5–7,13,15,16,32] to address the problem of explaining query answers in ontological KBs. For ${Datalog}^{\pm}$ KBs, in [32], Lukasiewicz et al. considered the explanation techniques by defining explanations under the AR, IAR and ICR4

⁴
ICR stands for intersection of closed repairs.

semantics in a different formalism based on existential rules. In that work, minimal explanations are defined as minimal consistent subsets from a set of facts that deduce the query. Authors carry out an in-depth computational complexity analysis, including the data-, the combined-, bounded arity-combined- and fixed-program-combined complexity. The other works consider a different formalism presented by

{DL - Lite}_{R}

[15,16]. In these works, Bienvenu et al. defined explanations for positive and negative answers under the brave, AR, and IAR semantics, and analyzed the data complexity of the related problems. We note that the concept of cause in this work is equivalent to the notion of minimal explanation in [32]. However, these works mainly focus on computational aspects of finding explanations and do not cover the representational aspect regarding users in which our work is built upon.

Argumentation-based approaches are also commonly used for representation and reasoning with inconsistent KBs. Works such as [13,25] and [42] make use of formal argumentation for inconsistency-tolerant reasoning in ontological KBs. In these works, they focus on the relation between the set of extensions and the set of repairs with respect to KBs. These works’ main focus, however, is on the computational properties of the repair semantics but not on the problem of explaining query answers.

On the propositional logic side, Arieli et al. [4] proposed a prioritized sequent-based argumentation framework in which arguments are characterized by the proof-theoretic notion of a sequent, and attack relations are represented by elimination rules. Authors show that extensions of such argumentation setting correspond to the most preferred maximal consistent subsets of propositional KB. In [22], Marcello et al. developed argumentative characterisations of preferred sub-theories using both the standard approaches and the dialogical approaches more suited for the real-world resource-bounded agents (i.e., human). The idea of this work is to apply preferred sub-theories to compute the most preferred maximal consistent subsets in a given propositional KB, and show a link between preferred sub-theories based and the stable semantics of both approaches. In contrast with the propositional language, our work studies a fragment of first-order logic, namely ${Datalog}^{\pm}$ . Moreover, our argumentation framework considers a different construction of argument and attacks (as we shall call it prioritized argumentation framework introduced in subsequent sections).

Another closely related work is Young et al. [41] which introduces prioritised default logic (PDL) in the form of an argumentation framework ${ASPIC}^{+}$ (also called structured argumentation). This work is inspired from the study of Modgil [35]. In particular, ${ASPIC}^{+}$ has been upgraded from abstract argumentation, and arguments are constructed from premises, as well as deductive and defeasible rules of inference. The conclusions of arguments can contradict each other and hence arguments can attack each other. However, ${ASPIC}^{+}$ system consider the priorities among rules (partial order) while our argumentation setting considers priorities over facts in KBs, as we will define in next sections.

Perhaps the closest related works are [5,6] and [7] by Ariqua et al. who study inconsistency-tolerant semantics based explanation. They study a relation between acceptable semantics (stable, preferred, grounded semantic) of argumentation systems and inconsistency-tolerant semantics (ICR, IAR, CQA) of ${Datalog}^{\pm}$ KBs [6]. In the argumentation system, the explanation for ICR-answer is computed by a hitting set algorithm and the query answer is based either on the sets of supporting arguments presenting in each extension (corresponding to the repair) or on the set of attacking arguments. In [5,7], the argumentation setting provides a dialogical characterization of the Brave and IAR semantics. This was done by the argumentation dialogue system with different participant profiles. Their motivation is similar to our work, however, we consider ${Datalog}^{\pm}$ KBs with the case prioritized facts.

3. Preliminaries

3.1. Abstract argumentation

We shall briefly recall the notion of abstract argumentation (AF) and related definitions, which are originally introduced by Dung [23].

Definition 1 (Abstract Argumentation).

An abstract argumentation framework is a pair $A = (Arg, Att)$ where $Arg$ is the set of arguments, and $Att \subseteq Arg \times Arg$ is the attacking relation i.e., $(A, B) \in Att$ means A attacks B.

The argumentation framework is based on acceptability semantics which defines the set of accepted arguments, also called extensions. These extensions include admissible, complete, stable, preferred and grounded semantics which are defined as follows.

Definition 2 (Extensions).

Let $A = (Arg, Att)$ be an argumentation framework, $M \subseteq Arg$ be a set of arguments and $A, A^{'} \in Arg$ . Then,

$M$ attacks an argument A if there exists an $A^{'} \in M$ s.t. $(A^{'}, A) \in Att$ .

$M$ defends an argument A if $M$ attacks every argument attacking A.

$M$ is conflict-free if there are no arguments $A, A^{'} \in M$ s.t. $(A, A^{'}) \in Att$ .

$M$ is an admissible extension if $M$ is conflict-free and defends each argument in it.

$M$ is a complete extension (cmp) if $M$ is an admissible extension containing all arguments that it defends.

$M$ is a preferred extension (prf) if $M$ is a maximal (w.r.t. set inclusion) admissible extension.

$M$ is a stable extension (stb) if $M$ is a conflict-free and attacks every argument which is not in it.

$M$ is a grounded extension (grd) if $M$ is a minimal (w.r.t. set inclusion) complete extension.

Example 1.
Let us consider an AF $A = (Arg, Att)$ where $Arg = {a, b, c, d, e}$ and $Att = {(e, e), (d, e), (d, c), (c, d), (c, b), (a, b)}$ , illustrated in Fig. 1. We can make the following observations: The admissible extensions are ${a}, {c}, {d}, {a, d}, {a, c}$ and ∅. The complete extensions are ${a}, {a, c}$ and ${a, d}$ . The preferred extensions are ${a, c}$ and ${a, d}$ . The stable extension is ${a, d}$ . The grounded extension is ${a}$ .

Fig. 1.
Argumentation framework for Example 1.

In order to evaluate the arguments, two types of acceptance are introduced in terms of their extensions: the sceptical and credulous acceptance. Sceptical acceptance requires that an argument is accepted in all extensions, while credulous acceptance requires that an argument is accepted in at least one extension. This is formalized in the following definitions:
Definition 3 (Acceptance and rejection).

Given an AF $A = (Arg, Att)$ , let $A \in Arg$ and $S \in {stb, prf, cmp, grd}$ . Then, the justification states are defined as follows:

A is sceptically accepted w.r.t. a semantic S iff it is in all extensions under S.

A is credulously accepted w.r.t. a semantic S iff it is in at least one extension under S.

A is rejected iff it is not in any extension under S.

Intuitively, when an argument (or a set of arguments) is sceptically accepted, it is the most trusted justification, even in the most sceptical scenarios. The credulously acceptance is a weaker form of acceptance since it is possibly not accepted in all extensions.

3.2. ${Datalog}^{\pm}$

In this subsection, we recall some of the basics of ${Datalog}^{\pm}$ [17] and the existential rules. ${Datalog}^{\pm}$ allows for the presence of existential variables in the rule head and consists of formulas built with the usual quantifiers $(\exists, \forall)$ and only two connectors: implication $(\to)$ and conjunction $(\land)$ .

We assume a set C of constants, a set P of predicates, a set V of variables and a set T of terms. A term t over C is either a constant or a variable, or null. An atomic formula (or atom) has the form $p (t_{1}, \dots, t_{n})$ , where $p \in P$ is an n-ary predicate, and $t_{1}, \dots, t_{n} \in T$ are terms. A ground atom is an atom with no variables. A conjunction of atoms is called a conjunct. A conjunction of ground atoms is called a ground conjunct. A variable in a formula is free if it is not in the scope of any quantifier. A formula is closed if it has no free variables.

In the existential rules framework, a fact is the existential closure of a conjunction of atoms [10]. For example, $\exists x (p_{1} (x) \land p_{2} (x, c))$ is a fact. For a given fact f, we exclude duplicate atoms in f, which allows us to see a fact as a set of atoms. Given a fact f, we denote by $term (f)$ (resp. $var (f)$ ) the set of terms (resp. variables) that occurs in f. A substitution s of V by T is a mapping from V to T (i.e., $s : V \to T$ ). Given a fact f, $s (f)$ denotes the fact obtained from f by replacing each occurrence of $v \in V \cap var (f)$ by $s (v)$ . A homomorphism from a set of atoms F to a set of atoms $F^{'}$ is a substitution of $var (F)$ by $term (F^{'})$ s.t. $s (F) \subseteq F^{'}$ (where $s (F)$ is obtained from F by substituting each variable according to s). A conjunctive query (CQ) has the form $Q : = ϕ (x_{1}, \dots, x_{n}) \leftarrow B$ , where B (the body of Q) is a fact, $x_{1}, \dots, x_{n}$ are in B, and ϕ is n-ary predicate. An answer to Q in f, denoted $Q (f)$ , is a tuple of constants $(c_{1}, \dots, c_{n})$ s.t. there exists a homomorphism s from B to f, that is, $(s (x_{1}), \dots, s (x_{n})) = (c_{1}, \dots, c_{n})$ . If $n = 0$ , then Q is a Boolean conjunctive query (BCQ).

For simplicity, we shall sometimes abuse the notation and write a single letter x for a vector of variables whenever it is clear from the context e.g., $\forall x$ where $x = x_{1}, \dots, x_{n}$ . Further, we shall treat them as sets and use set operators (e.g., $\cup, \cap$ ) whenever the resulting set is obvious. An existential rule is a rule of the form $\forall x \forall y (B \to \exists z H)$ where $B, H$ are conjunctions of closed atoms, $var (B) = x \cup y$ and $var (H) = x \cup z$ where H is the head of the existential rule (and B as before stands for body), and variables z are the existential variables of the existential rule. A negative constraint (or simply called a constraint) is a rule of the form $\forall x C (x) \to ⊥$ where C is a conjunction of atoms.

A knowledge base (KB) $K = (F, R, C)$ is a tuple of sets of facts, rules and negative constraints, respectively. Reasoning in a KB is performed by a saturation mechanism, i.e., applying all possible rules in $R$ over $F$ until it reaches a fixed point. To express saturation, we need to define rule applicability which we give next.

A rule $r : = B \to H$ applies to a fact f if there exists a homomorphism s from B to f. The application of r to f with respect to s produces a fact $β (f, r, s) : = f \cup s (rep (H))$ , where $rep (H)$ is obtained by replacing existential variables with fresh variables. $β (f, r, s)$ is called a derivation from f. Given a fact f and a set of rules $R$ , a fact $f^{'}$ is an $R$ -derivation of f if there is a finite derivation sequence $(f_{0} = f, \dots, f_{k} = f^{'})$ s.t. $\forall j, 0 ⩽ j < k$ , a rule $r \in R$ that is applicable to $f_{j}$ and $f_{j + 1}$ is a derivation from $f_{j}$ . We denote by $C l_{R} (F)$ the closure of $F$ with respect to $R$ . The application of a rule to a set of facts is called a chase.

Next, we define query answering with respect to $K$ . Given a query Q, the set of models of $F$ given $R$ , denoted by $mods (F, R)$ , is the set of all facts $F^{'} \subseteq F$ and every $r \in R$ is satisfied in $F^{'}$ . The set of answers to a conjunctive query Q on $F^{'}$ given $R$ , denoted as $a n s (Q, F^{'}, R)$ , is the set of tuples t s.t. $t \in Q (F^{'})$ for all $F^{'} \in mods (F, R)$ . The answer to BCQ Q over $F$ given $R$ is positive, denoted as $F \cup R ⊧ Q$ iff $F^{'} ⊧ Q$ for all $F^{'} \in mods (F, R)$ . In this paper, we use the Skolem chase mechanisms to prevent infinite redundancies (see [34]). $C l_{R} (F)$ is finite. A (BCQ) Q on $K$ can be answered by calculating the chase and checking whether the query is entailed by the models of $F, R$ . In this case, we write $C l_{R} (F) ⊧ Q$ .

3.3. Prioritized ${Datalog}^{\pm}$ knowledge base

In this section, we shall introduce the first major component of our framework; namely, the notion of prioritized ${Datalog}^{\pm}$ KBs and preferred repairs.

In many applications, there are often multiple sources of information, each providing partially overlapping and partially different part of the knowledge, and each having potentially a different level of reliability. In order to distinguish this varying degree of reliability, one can employ a preference relation with the basic intuition that the higher the reliability of the information source, the more prioritised (or more preferable) it is in the ranking. Following this intuition, we introduce the notion of prioritized ${Datalog}^{\pm}$ KBs in which facts of $F$ have priorities.

Definition 4 (Prioritized ${D ATALOG}^{\pm}$ knowledge bases).

The KB $K = (F, R, C)$ is a prioritized ${Datalog}^{\pm}$ KB iff the fact base $F$ ,

is partitioned into h pairwise-disjoint sets such that $F = F_{1} ⊍ F_{2} ⊍ \dots ⊍ F_{h}$

the facts in $F_{i}$ have a higher priority than the ones in $F_{j}$ (denoted as $F_{i} ≻ F_{j}$ ) whenever $i < j$ .

Note that the facts of $F_{1}$ are considered the most reliable ones while the facts of $F_{h}$ are the least reliable ones. We shall extend the relation ≻ between set of facts to priority relation over facts by considering each $F_{i} \subseteq F$ as a equivalence class over the priority of facts. Hence, we will need the total preorder version ⪰ defined over facts. We denote a totally preordered fact bases of $K$ by $(F, ⪰)$ . If all the facts in a knowledge base have the same priority, then we shall call it a flat knowledge base.

Example 2.
Let $K_{d c} = (F, R, C)$ be a ${Datalog}^{\pm}$ KB describing dances and props used in some dances. The KB considers unary predicates (classes) $Dances, Mdances$ , $Tdances, DancesWP, DancesWOP, Props$ standing for “dances”, “modern dances”, “traditional dances”, “dances with props”, “dances without props” and “the props that are used in some dances”, respectively. A binary predicate (relationship) $HasProps$ expresses “the props used in some dances can be hat, flowers” ( $f l$ for short) and “handkerchiefs” ( $h k$ for short). Consider the following knowledge base rules and negative constraints. $\begin{array}{l} R = & {R_{1} : Mdances (x) \to DancesWOP (x), \\ R_{2} : Tdances (x) \to DancesWP (x), \\ R_{3} : HasProps (x, y) \to DancesWP (x)} \\ C = & {C : DancesWP (x) \land DancesWOP (x) \to ⊥} \end{array}$ along with the set of facts $F$ obtained from different sources $F = {F_{1}, F_{2}, F_{3}, F_{4}}$ where $d_{1}, d_{2}, d_{3}$ represent particular instances of dances: $\begin{array}{l} F_{1} = {DancesWOP (d_{3}), Tdances (d_{1})} \\ F_{2} = {DancesWP (d_{3}), HasProps (d_{1}, f l)} \\ F_{3} = {Mdances (d_{1})} \\ F_{4} = {Mdances (d_{2}), HasProps (d_{2}, h k)} \end{array}$

The first axiom states that modern dances do not use props. The second one states that traditional dances use props. $R_{3}$ specifies that anything having props must be a dance with props. C expresses the fact that the list of modern dances and the list of traditional dances are disjoint. In the fact base, $F_{1}$ consists of the most reliable assertions (or facts) while $F_{4}$ includes the least reliable ones.

Since data is assumed to be the source of inconsistency, violation of constraints might be the case when applying the rules to the set of facts. In what follows, we recall the formal definition of inconsistency in ${Datalog}^{\pm}$ KBs; then we introduce the subset-repairing technique which is inspired by a work from the database community and DLs [30]. The basic idea of the subset-repairing technique is to compute maximal consistent subsets of $F$ , called repairs, and use them to perform querying in flat KBs.
Definition 5 (Inconsistency).

Given a knowledge base $K = (F, R, C)$ , a set of facts $F$ is inconsistent with respect to a set of rules $R$ and negative constraints $C$ (or $R$ -inconsistent for short) iff there exists a constraint $C \in C$ such that $C l_{R} (F) ⊧ body (C)$ . Accordingly, $F$ is said to be $R$ -consistent if it is not inconsistent. Moreover, $K$ is said to be inconsistent iff there exists a set of facts $F^{'} \subseteq F$ s.t. $F^{'}$ is $R$ -inconsistent.

Next, we give the formal definition for the notion of repair.

Definition 6 (Repair).

Let $K = (F, R, C)$ be a flat ${Datalog}^{\pm}$ KB. A repair $B$ of $K$ is an inclusion-maximal subset of $F$ such that $C l_{R} (B)$ is $R$ -consistent. We denote the set of all repairs w.r.t. $F$ by $REPS (K)$ .

In prioritized ${Datalog}^{\pm}$ KBs, the notion of repair can be generalised to the case where all the facts of $F$ have been partitioned into priority levels. In particular, we adopt variants of the repairs, called preferred repairs, which is inspired by the work in Description Logic KB [14]. Accordingly, we consider two ways of defining preference relations over repairs [14,20,24]. A first possibility is to compare the most preferred facts between the repairs. In order to order the preference of facts, we use a ranking function. A second one is a lexicographic cardinality based comparison over repairs.

Definition 7 (Ranking function).

Let $K = (F, R, C)$ be a prioritized ${Datalog}^{\pm}$ KB with a totally preordered fact bases $(F, ⪰)$ . A ranking function for fact base $F$ is Ω: $F \to N^{+}$ , i.e., for a fact $α \in F$ , $Ω (α) = i$ iff $α \in F_{i}, \forall i \in (1, \dots, h)$ . Let M be a subset of $F$ , we denote $Ω (M) = {Ω (α) ∣ α \in F}$ .

Now we define two preference relations for preferred repairs.

Definition 8 (Preference relation).

Given a prioritized ${Datalog}^{\pm}$ KB $K = (F, R, C)$ with $F = (F_{1} ⊍ F_{2} ⊍ \dots ⊍ F_{h})$ . Let $B_{1}, B_{2}$ be two repairs in $REPS (K)$ , $B_{1}$ is preferred to $B_{2}$ , denoted by $B_{1} ⪰_{⋆} B_{2}$ where $⋆ \in {\min, lex}$ , which is defined in two different ways:

$B_{1} ⪰_{\min} B_{2}$ iff $\min (Ω (B_{1} ∖ B_{2})) ⩽ \min (Ω (B_{2} ∖ B_{1}))$ , where $\min (Ω (B_{1}))$ denotes the most preferred element in $B_{1}$ .

$B_{1} ⪰_{lex} B_{2}$ , iff $| B_{1} \cap F_{i} | = | B_{2} \cap F_{i} |$ for every $1 ⩽ i ⩽ h$ , or there is some $1 ⩽ i ⩽ h$ such that $| B_{1} \cap F_{i} | > | B_{2} \cap F_{i} |$ and for all $1 ⩽ j < i, | B_{1} \cap F_{j} | = | B_{2} \cap F_{j} |$ .

Remark 1.
The relation $⪰_{⋆}$ is pre-order, that is: reflexive ( $B_{1} ⪰_{⋆} B_{1}$ ), transitive (if $B_{1} ⪰_{⋆} B_{2}$ and $B_{2} ⪰_{⋆} B_{3}$ then $B_{1} ⪰_{⋆} B_{3}$ ). A strict pre-order $≻_{⋆}$ is an irreflexive ( $B_{1} ⪰_{⋆} B_{1}$ does not hold) and transitive binary relation. $B_{1} ≻_{⋆} B_{2}$ means that $B_{1}$ is strictly preferred to $B_{2}$ . A strict pre-order is generally defined from $⪰_{⋆}$ as $B_{1} ≻_{⋆} B_{2}$ iff $B_{1} ⪰_{⋆} B_{2}$ and $B_{2} ⋡_{⋆} B_{1}$ . $B_{1}$ is equal to $B_{2}$ , denoted by $B_{1} =_{⋆} B_{1}$ , iff $B_{1} ⪰_{⋆} B_{2}$ and $B_{2} ⪰_{⋆} B_{1}$ .

We introduce definitions of a preferred repair and a set of $≻_{⋆}$ -most preferred repairs in prioritized ${Datalog}^{\pm}$ KBs.
Definition 9 (Preferred repair).

Let $K = (F, R, C)$ be a prioritized ${Datalog}^{\pm}$ KB with $(F, ⪰)$ and $⪰_{⋆}$ be a preorder over subsets of $F$ where $⋆ \in {\min, lex}$ .

A preferred repair of $K$ is an $R$ -consistent subset of $F$ that is minimal w.r.t. $⪰_{⋆}$ .

A set of $≻_{⋆}$ -most preferred repairs w.r.t. $(F, ⪰)$ , denoted by $REPS (K, ≻_{⋆})$ , is defined as: $\begin{array}{l} REPS (K, ≻_{⋆}) = {B \in REPS (K) ∣ there is no B^{'} \in REPS (K) such that B^{'} ≻_{⋆} B} . \end{array}$

We next introduce notions of consistent entailment under preferred repair semantics. ${AR}_{⪰}$ semantics require that a query is entailed from all preferred repairs. ${BAR}_{⪰}$ semantics require a query that is entailed by some preferred repairs. In our context, the accepted query has either a yes-answer (entailed) or a no-answer (not entailed). We note that the ${AR}_{⪰}$ semantic (resp. the ${BAR}_{⪰}$ semantic) extends the definition of the AR semantics (resp. the brave semantics) proposed in [14,30] when $(F, ⪰)$ is a total preordered fact base.

Definition 10.
( ${AR}_{⪰}$ and ${BAR}_{⪰}$ semantics) Let $K = (F, R, C)$ be a prioritized ${Datalog}^{\pm}$ KB with $(F, ⪰)$ and Q be a query. Then:
Q is entailed by $K$ under ${AR}_{⪰}$ semantics, written $K ⊧_{A R_{⪰}} Q$ iff for every preferred repair

$B \in REPS (K, ≻_{⋆})$ , $C l_{R} (B) ⊧ Q$ .

Q is entailed by $K$ under ${BAR}_{⪰}$ semantics, written $K ⊧_{B A R_{⪰}} Q$ iff for some preferred repairs

$B \in REPS (K, ≻_{⋆})$ , $C l_{R} (B) ⊧ Q$

Example 3.
Let us consider the KB $K_{d c}$ in Example 2 with $F = {F_{1}, F_{2}, F_{3}, F_{4}}$ . In this example, $F_{1}$ consists of the most reliable assertions while $F_{4}$ includes the least reliable ones. $\begin{array}{l} F_{1} = {DancesWOP (d_{3}), Tdances (d_{1})} \\ F_{2} = {DancesWP (d_{3}), Mdances (d_{1})} \\ F_{3} = {HasProps (d_{1}, f l)} \\ F_{4} = {Mdances (d_{2}), HasProps (d_{2}, h k)} \end{array}$ The set of repairs of $K_{d c}$ is $REPS (K_{d c}) = {B_{1}, B_{2}, B_{3}, B_{4}, B_{5}, B_{6}, B_{7}, B_{8}}$ where: $\begin{array}{l} B_{1} = {DancesWOP (d_{3}), Mdances (d_{1}), Mdances (d_{2})}, \\ B_{2} = {DancesWOP (d_{3}), Mdances (d_{1}), HasProps (d_{2}, h k)}, \\ B_{3} = {DancesWOP (d_{3}), Tdances (d_{1}), HasProps (d_{1}, f l), Mdances (d_{2})}, \\ B_{4} = {DancesWOP (d_{3}), Tdances (d_{1}), HasProps (d_{1}, f l), HasProps (d_{2}, h k)}, \\ B_{5} = {DancesWP (d_{3}), Mdances (d_{1}), Mdances (d_{2})}, \\ B_{6} = {DancesWP (d_{3}), Mdances (d_{1}), HasProps (d_{2}, h k)}, \\ B_{7} = {DancesWP (d_{3}), Tdances (d_{1}), HasProps (d_{1}, f l), HasProps (d_{2}, h k)}, \\ B_{8} = {DancesWP (d_{3}), Tdances (d_{1}), HasProps (d_{1}, f l), Mdances (d_{2})} \end{array}$

In the KB, rules $R_{1}, R_{2}, R_{3}$ are applied to calculate $C l_{R} (B_{4})$ , $C l_{R} (B_{3})$ . We have: $\begin{array}{l} C l_{R} (B_{3}) = & {DancesWOP (d_{3}), Tdances (d_{1}), HasProps (d_{1}, f l), Mdances (d_{2}), \\ DancesWP (d_{1}), DancesWOP (d_{2})} \\ C l_{R} (B_{4}) = & {DancesWOP (d_{3}), Tdances (d_{1}), HasProps (d_{1}, f l), HasProps (d_{2}, h k), \\ DancesWP (d_{1}), DancesWP (d_{2})} \end{array}$
For the relation $⪰_{\min}$ , we have $B_{1} ≻_{\min} B_{5}$ , since $\min (Ω (B_{1} ∖ B_{5})) = \min (Ω (DancesWOP (d_{3}))) = 1$ and $\min (Ω (B_{5} ∖ B_{1})) = \min (Ω (DancesWP (d_{3}))) = 2$ , $\min (Ω (B_{1} ∖ B_{5})) < \min (Ω (B_{5} ∖ B_{1}))$ . We conclude that $B_{3} =_{\min} B_{4} >_{\min} B_{7} =_{\min} B_{8} =_{\min} B_{1} =_{\min} B_{2} >_{\min} B_{5} =_{\min} B_{6}$ . Then $REPS (K_{d c}, >_{\min}) = {B_{3}, B_{4}}$ .

Consider a query $Q (d_{1}) = DancesWP (d_{1})$ asking whether $d_{1}$ is a dance with props (this is a Boolean query that has a yes-(no)answer). Since $Q (d_{1}) = DancesWP (d_{1})$ is accepted in all preferred repairs, $K_{d c} ⊧_{A R_{⪰}} Q (d_{1})$ .

Consider a query $Q (d_{2}) = DancesWOP (d_{2})$ asking where a person $d_{2}$ dances without props. It holds that $K_{d c} ⊧_{B A R_{⪰}} Q (d_{2})$ (since $C l_{R} (B_{4}) ⊭ Q (d_{2})$ and $C l_{R} (B_{3}) ⊧ Q (d_{2})$ ), whereas it is not an answer under ${AR}_{⪰}$ semantics. In other words, the answer is accepted only in some preferred repairs.

For the relation $⪰_{lex}$ , we have $B_{1} ≻_{lex} B_{5}$ since $i = 1$ such that $∣ B_{1} \cap F_{1} ∣ > ∣ B_{5} \cap F_{1} ∣$ . Hence, $B_{3} =_{lex} B_{4} ≻_{lex} B_{7} =_{lex} B_{8} ≻_{lex} B_{1} =_{lex} B_{2} ≻_{lex} B_{5} =_{lex} B_{6}$ , then $REPS (K_{d c}, ≻_{lex}) = {B_{3}, B_{4}}$ . We have $K_{d c} ⊧_{B A R_{⪰}} Q (d_{2})$ and $K_{d c} ⊧_{A R_{⪰}} Q (d_{1})$ .

4. A prioritized argumentation framework for prioritized ${Datalog}^{\pm}$ KB

In this section, we focus on the use of Dung’s argumentation framework to address the problem of explaining query answers under preferred repair semantics in prioritized ${Datalog}^{\pm}$ KBs. The main idea is that we translate prioritized KBs into argumentation frameworks. This correspondence enables us to understand explanations based on a form of the arguments and to compute preferred repairs based on the extensions of the argumentation framework.

4.1. Prioritized argumentation framework

In this section, we introduce a prioritized argumentation framework (PAF) as an instantiation5

⁵
This means that we inherit attack and defeat relations over arguments as it was defined in Dung’s framework.

of the abstract AF to address the problem of explaining query for KB with totally preordered fact bases

(F, ⪰)

. In the PAF setting, we consider the notions of argument and undercut attack which was introduced in [6], and extend the latter to the so-called defeat attack for the case of prioritized KBs. In particular, we lift the relation

⪰_{⋆}

over repairs of

K

to the preference relations between the arguments. Then, we introduce the defeat attack as a variant of undercut attack, where the priority of the attacking argument is preferred to the attacked one.

In [6], an argument consists of a set of facts called a support, and a conclusion entailed from the support. Following this idea, we will define the concept of argument in the context of PAF.

Definition 11 (PAF Argument).

Let $K = (F, R, C)$ be a prioritized ${Datalog}^{\pm}$ with $(F, ⪰)$ . A (PAF) argument A is a tuple $(Ψ, α)$ with Ψ a non-empty $R$ -consistent subset of $F$ and α a set of facts such that:

$Ψ \subseteq F$ and $C l_{R} (Ψ)$ is $R$ -consistent ((consistency)

$α \subseteq C l_{R} (Ψ)$ (entailment)

$∄ Ψ^{'} \subset Ψ$ s.t. $α \subseteq C l_{R} (Ψ^{'}))$ (minimality)

The support Ψ of a PAF argument A is denoted by

Sup (A)

and the conclusion α by

Con (A)

For simplification purposes, in the rest of the article, we shall simply call a “PAF argument” as “argument”. Next, we introduce some notation for the concepts we will use throughout the paper.

Given a prioritized ${Datalog}^{\pm}$ KB $K = (F, R, C)$ and a set of facts $F^{'} \subseteq F$ ,

The set of all arguments generated from $K$ is denoted as ${Arg}_{K}$ .

The set of arguments that is constructed from $F^{'}$ (i.e., ${A \in {Arg}_{K} ∣ Sup (A) \subseteq F^{'}}$ ) is denoted as $ARGS (F^{'})$ .

Given a set of arguments $S \subseteq {Arg}_{K}$ , the set of conclusions of arguments in $S$ (i.e., $⋃_{A \in S} Con (A)$ ) is denoted by $CONS (S)$ .

Given a set of arguments $S \subseteq {Arg}_{K}$ , the set of supports of arguments in $S$ (i.e., $⋃_{A \in S} Sup (A)$ ) is denoted by $BASE (S)$ .

An argument B is a subargument of argument A iff $Sup (B) \subseteq Sup (A)$ . We denote the set of subarguments of A as $SUBS (A)$ .

We next show how we construct arguments from the prioritized ${Datalog}^{\pm}$ KB. In Algorithm 1 below, we find all consistent subsets of $F$ (line 2), which is done by the function AllConsistentSubset. Next, all possible arguments are generated: $R$ -consistent subsets of $F$ are used as the supports and the conclusions are deduced from them (This can be done by using the function Chase [26]) (line 3–6).

Algorithm 1:

GenerateArguments

Example 4.

Consider again the KB $K_{d c} = (F, R, C)$ from Example 3. By using Algorithm 1, we can obtain a set of arguments. $\begin{array}{l} A_{1} = ({DancesWOP (d_{3})}, {DancesWOP (d_{3}))}, \\ A_{2} = ({DancesWP (d_{3})}, {DancesWP (d_{3}))}, \\ A_{3} = ({Tdances (d_{1})}, {Tdances (d_{1}))}, \\ A_{4} = ({Tdances (d_{1})}, {DancesWP (d_{1}))}, \\ A_{5} = ({HasProps (d_{1}, f l)}, {HasProps (d_{1}, f l))}, \\ A_{6} = ({HasProps (d_{1}, f l)}, {DancesWP (d_{1}))}, \\ A_{7} = ({Mdances (d_{1})}, {Mdances (d_{1}))}, \\ A_{8} = ({Mdances (d_{1})}, {DancesWOP (d_{1}))}, \\ A_{9} = ({Mdances (d_{2})}, {Mdances (d_{2}))}, \\ A_{10} = ({Mdances (d_{2})}, {DancesWOP (d_{2})}), \\ A_{11} = ({HasProps (d_{2}, h k)}, {HasProps (d_{2}, h k)}), \\ A_{12} = ({HasProps (d_{2}, h k)}, {DancesWP (d_{2})}) . \end{array}$

We next define an undercut attack to express conflicting information.

Definition 12 (Undercut attack).

Let $A, B$ be two arguments. A undercut attacks (or undercuts) B iff $\exists β \in Sup (B)$ s.t. $C l_{R} ({Con (A), β})$ is $R$ -inconsistent.

Informally, A undercut attacks B if there is an element of the support of B which is $R$ -inconsistent with the conclusion of A. We note that this attack is not symmetric [6].

Now we introduce the notion of defeat attack, which is a variant of the undercut relation for the prioritized KB. Since the facts of $F$ are prioritized, there exists a preference relation between arguments. In the PAF setting, we lift the relation $⪰_{⋆}$ over preferred repairs of $K$ to a preference relation on sets of arguments. In what follows, we shall write $A ⪰_{⋆} B$ to indicate that A is at least as preferred as B, for all $A, B \in {Arg}_{K}$ where $⋆ \in {\min, lex}$ . Example 5 illustrates two instances for $⪰_{⋆}$ .

Remark 2.
Realize that the relation $⪰_{⋆}$ is reflexive and transitive. The strict total preorder counterpart is denoted as $≻_{⋆}$ as usual. Both the relation and its strict version are right-monotonic i.e., if $A ⪰_{⋆} B$ (resp. $A ≻_{⋆} B$ ) and $Sup (C) \subseteq Sup (B)$ then $A ⪰_{⋆} C$ (resp. $A ≻_{⋆} C$ ).
Example 5 (Example 4 continued).

We apply two instances of $⪰_{⋆}$ to the arguments.

In case of $⪰_{\min}$ , it holds that $A_{3} ≻_{\min} A_{7}$ since $\min (Ω (A_{3} ∖ A_{7})) = 1 ≻ \min (Ω (A_{7} ∖ A_{3})) = 2$ .

In case of $⪰_{lex}$ , since $| Sup (A_{3}) \cup F_{1} | = 1 > | Sup (A_{7}) \cup F_{1} | = 0$ , we have $A_{3} ≻_{lex} A_{7}$ .

From now on, we shall use ≻ instead of $≻_{⋆}$ throughout the paper. Next, we give the formal definition of defeat attack.

Definition 13 (Defeat attack).

Let $A, B$ be two arguments and ≻ be a preference relation on ${Arg}_{K}$ . A defeats B iff A undercuts B and $A ≻ B$ .

Intuitively, the defeat attack succeeds if and only if the priority argument of higher level attacks the one of the lower level. We illustrate it over an example.

Example 6 (Example 5 continued).

Consider two arguments: $\begin{array}{l} A_{7} = ({Mdances (d_{1})}, {Mdances (d_{1})}), \\ A_{3} = ({Tdances (d_{1})}, {Tdances (d_{1})}), \end{array}$

We have $A_{3}$ defeats $A_{7}$ since there is $Tdances (d_{1}) \in Sup (A_{3})$ s.t. $C l_{R} ({Con (A_{7}), Tdances (d_{1})})$ is $R$ -inconsistent and $A_{3} ≻_{\min} A_{7}$ .

Next, we introduce the notion of prioritized argumentation framework.

Definition 14 (Prioritized argumentation).

Let $K = (F, R, C)$ be a prioritized ${Datalog}^{\pm}$ KB with $(F, ⪰)$ . A prioritized argumentation framework for $K$ is a triple $A^{≻} = ({Arg}_{K}, {Def}_{≻})$ , where

${Arg}_{K}$ is a set of (PAF) arguments,

${Def}_{≻} \subseteq {Arg}_{K} \times {Arg}_{K}$ where ${Def}_{≻}$ is a set of defeat attacks of $A^{≻}$ . We write $A \to B \in {Def}_{≻}$ , i.e. A defeats B.

In the PAF setting, we can apply Dung’s acceptability semantics for evaluating the arguments. We shall denote a set of extensions of $A^{≻}$ by $EXTS (A^{≻})$ .

Example 7.
Reconsider the prioritized KB $K_{d c} = (F, R, C)$ mentioned in Example 3 with the Arguments given in Example 4.

As a result, we have the set of stable extensions $EXTS (A^{≻}) = {M_{1}, M_{2}}$ where $M_{1} = {A_{1}, A_{3}, A_{4}, A_{5}, A_{6}, A_{9}, A_{10}}$ ,

$M_{2} = {A_{1}, A_{3}, A_{4}, A_{5}, A_{6}, A_{11}, A_{12}}$ . The sets of conclusions of the extensions are as follows. $\begin{array}{l} CONS (M_{1}) = & {DancesWOP (d_{3}), Tdances (d_{1}), HasProps (d_{1}, f l), DancesWP (d_{1}), \\ Mdances (d_{2}), DancesWOP (d_{2})} \\ CONS (M_{2}) = & {DancesWOP (d_{3}), Tdances (d_{1}), HasProps (d_{1}, f l), DancesWP (d_{1}), \\ HasProps (d_{2}, h k), DancesWP (d_{2})} . \end{array}$

Next, we present our Algorithm 2 (GenerateArgumentGraph) that produces an argument graph $A G$ which is a crucial part of this work. In an $A G$ , nodes are arguments and edges represent defeat attacks between the arguments. As the first step, a set of vertices is created by adding a set of arguments to Arg (line 1). Next, the algorithm generates a set FreeArg where the arguments are built from the set of conflict-free facts (line 2–4). Since we know that there are no attacks from any subset of FreeArg to any argument of FreeArg, we only compute defeat attacks from the arguments of FreeArg to arguments of $Arg ∖ FreeArg$ and add them to graph as edges (line 5–10).

Algorithm 2:
GenerateArgumentGraph

The following theorem shows the soundness of Algorithm 2; that is, the algorithm computes all the defeat attacks correctly and for each defeat attack there is an edge in the generated graph AG representing that attack. The proof is rather straight forward.
Theorem 1 (Soundness of Algorithm 2).

Let $K = (F, R, C)$ be a prioritized ${Datalog}^{\pm}$ KB and AG = (Arg, Def) be the generated AG by Algorithm 2 . We have that:

An argument A defeats an argument B iff $Sup (A) ⪰_{⋆} Sup (B)$ and $Con (A) = Γ ∖ Sup (B)$ for some sets of conflicting facts in $F$ s.t. $Γ \cup Sup (B) \neq \emptyset$ and $∄ Γ^{'}$ of $F$ satisfying $Γ^{'} \cup Sup (B) \subset Γ \cup Sup (B)$ .

For all defeat attacks, $\exists e \in Def$ s.t. $e = (A, B)$ , where the defeat attack between A and B is represented by the edge of AG.

Proof.
First, we show that for each iteration of the for loop at line 7, computing defeat attacks is based on computing minimal inconsistent sets in $K$ . Then we show that for any defeat attack based on computing sets of conflicting facts in $K$ , there exists an edge representing it in the generated AG.

Given a prioritized KB $K = (F, R, C)$ and two arguments A and B. For any $Γ \in SetofConflicts$ until the last set k in which all minimal inconsistent sets have been applied at least once in $SetofConflicts$ , defeat attacks are computed, i.e., if $Sup (A) ⪰_{⋆} Sup (B)$ and $Γ \cap Sup (B) \neq \emptyset$ and $Con (A) = Γ ∖ Sup (B)$ then A defeats B. If a defeat attack $e = (A, B) \notin Def$ then it is added in $A G$ , otherwise it already exits. Thus, all defeat attacks are represented with the edges of the generated AG. □
4.2. Acceptability in the prioritized argumentation framework

In the previous section, we have shown a translation from prioritized KBs to PAF. In this section, we first define the acceptability semantics in PAF, and then show (in Theorem 2) that preferred repairs of prioritized KBs correspond to the extensions of PAFs which is also one of the main results of this article.

Inspired from the study [6], we define the prioritized versions of the acceptances for a query Q in prioritized ${Datalog}^{\pm}$ KB.

Definition 15 (Acceptability).

Let $K = (F, R, C)$ be a prioritized ${Datalog}^{\pm}$ KB with $(F, ⪰)$ , $A^{≻} = ({Arg}_{K}, {Def}_{≻})$ be the corresponding argumentation framework, Q be a query and S denote either the stable semantics or the preferred semantics i.e., $S \in {stb, prf}$ . Then,

Q is sceptically accepted under semantics S (written $K ⊧_{s c, S}^{≻} Q$ ) iff for all $M \in EXTS (A^{≻})$ , $CONS (M) ⊧ Q$ .

Q is credulously accepted under semantics S (written $K ⊧_{c r, S}^{≻} Q$ ) iff for some $M \in EXTS (A^{≻})$ , $M \in EXTS (A^{≻}), CONS (M) ⊧ Q$ .

Finally, we can present the main result of this section.

Theorem 2.
Given a prioritized ${Datalog}^{\pm}$ KB $K$ , and the corresponding PAF $A^{≻}$ , a query Q, and S being either the stable or the preferred semantics (i.e., $S \in {stb, prf}$ ),
$K \underset{A R_{⪰}}{⊧} Q$ iff $K ⊧_{s c, stb}^{≻} Q$ iff $K ⊧_{s c, prf}^{≻} Q$ .

$K \underset{B A R_{⪰}}{⊧} Q$ iff $K ⊧_{c r, stb}^{≻} Q$ iff $K ⊧_{c r, prf}^{≻} Q$ .

The theorem follows from the three lemmas below. Lemmas 4 and 5 show that the equivalence between the set of repairs and the set of preferred (resp. stable) extension, and in turn implies the equivalence results for query answering in KB.

First, we show that a repair of a KB has a higher priority than any consistent subsets of facts of the KB.
Lemma 3.
Given a prioritized ${Datalog}^{\pm}$ KB $K = (F, R, C)$ , if $B \in REPS (K, ≻)$ and $F^{'} \subseteq F$ is a consistent set of facts, then $F^{'} ⊁ B$ .
Proof.
By assumption $F^{'}$ is consistent. Then, there exists a $F^{″} \in REPS (K)$ s.t. $F^{'} \subseteq F^{″}$ . By the monotonic property of ≻, $F^{″} ≻ F^{'}$ . As $B \in REPS (K, ≻)$ , so $F^{″} ≮ B$ and by the transitivity property of ≻, we infer that $F^{'} ≮ B$ . □

We present the next result which shows that every repair for the KB with a total preorder between them, is a stable extension of the constructed argumentation framework (with respect to the same order).
Lemma 4.
Let $K = (F, R, C)$ be a prioritized ${Datalog}^{\pm}$ KB and $A^{≻} = ({Arg}_{K}, {Def}_{≻})$ be the corresponding argumentation framework. If $B \in REPS (K, ≻)$ then $ARGS (B)$ is a stable extension of $A^{≻}$ .
Proof.
Suppose that $B \in REPS (K, ≻)$ and $M = ARGS (B)$ . Let us show that $M$ is a stable extension of $({Arg}_{K}, {Def}_{≻})$ .

We first prove that $M$ is conflict-free. Assume for a contradiction that $C, D \in M$ s.t $C \to D \in {Def}_{≻}$ . From the definition of undercut attack, there exists $β \in Sup (D)$ such that $C l_{R} ({Con (C), β})$ is $R$ -inconsistent. Thus, $C l_{R} (Sup (C) \cup {β})$ is $R$ -inconsistent. But then $B$ is not inconsistent which is a contradiction, hence $M$ must be conflict-free.

Next we prove that $M$ defeats each argument not belonging to it. Let $C = (Θ, α) \in {Arg}_{K} ∖ M$ and $α \in Θ ∖ B$ . Considering $D = (B, \land B)$ , we have $α \notin B$ , and $B$ is a maximal consistent subset (i.e., a repair) of $F$ . Then, $C l_{R} ({Con (C), α})$ is $R$ -inconsistent, and D undercuts C. Suppose that Θ is consistent. Since $B \in REPS (K, ≻)$ , $Θ ⊁ B$ (by Lemma 3). By Definition 13, D defeats C, i.e., $D \to C \in {Def}_{≻}$ . Consequently, $M$ is a stable extension. □

Lemma 5 below shows that every preferred extension of the constructed argumentation framework is a repair for the prioritized KB.
Lemma 5.
Let $K = (F, R, C)$ be a prioritized ${Datalog}^{\pm}$ KB and $A^{≻} = ({Arg}_{K}, {Def}_{≻})$ be the corresponding argumentation framework. If $M \in EXTS (A^{≻})$ and also a preferred extension, then there is some $B \in REPS (K, ≻)$ such that $M = ARGS (B)$ .
Proof.
Suppose that $M \in EXTS (A^{≻})$ . We will first prove that there exists a repair $B$ such that $M = ARGS (B)$ . Let us start by assuming that $P = BASE (M)$ , and show that $P$ is consistent. Suppose for the sake of contradiction that $P$ is inconsistent. Let ${α_{1}, \dots, α_{n}} = P^{'} \subseteq P$ be an inconsistent set and every proper subset of it is consistent. Let $C \in M$ be an argument such that $α_{n} \in Sup (C)$ and $C^{'} = (P^{'} ∖ {α_{n}}, α_{1} \land \dots \land α_{n - 1})$ . It follows that $C l_{R} ({Con (C^{'}), α_{n}})$ is $R$ -inconsistent, then $C^{'}$ defeats C. Since $M$ is conflict free, then $C^{'} \notin M$ , and since $M$ is an admissible set, there is $D \in M$ such that $D \to C^{'} \in {Def}_{A}$ . Because D defeats $C^{'}$ , there exists $i \in {1, \dots, n - 1}$ such that $C l_{R} ({Con (D), α_{i}})$ is $R$ -inconsistent and $D ≻ C^{'}$ . Since $α_{i} \in BASE (M)$ , there exists $E \in M$ s.t. $α_{i} \in Sup (E)$ , which implies D defeats E. Clearly, C is attacked by $C^{'}$ but cannot be defended, which is in contradiction with the fact that $M$ is admissible. Therefore it must be the case that $P$ is consistent.

Next, we will show that $M = ARGS (BASE (M))$ . Clearly $M \subseteq ARGS (P)$ . From Lemma 4 and the first part of the current proof, we already know that $ARGS (P)$ is a stable and preferred extension, thus $M ⊊ ARGS (P)$ is not possible.

Next, we show that $B$ is maximal consistent i.e., there is no $B^{'} \in REPS (K, ≻)$ such that $B^{'} ≻ B$ . Assume the contrary. Since $M$ is a preferred extension, $ARGS (B) ∖ ARGS (B^{'}) \neq \emptyset$ , and there exists $Φ \subseteq {B ∖ B}^{'}$ such that $D = (Φ, \land Φ) \in ARGS (B)$ . By Lemma 4, $ARGS (B^{'})$ is a stable extension of $A^{≻}$ , which implies that there exists $Θ \subseteq B^{'}$ such that $C = (Θ, \land Θ) \in ARGS (B^{'})$ and C defeats D. Thus, there must exist an $E = (Γ, \land Γ) \in M$ (since $M$ is preferred) which defeats C. Hence $B^{'} ⊁ Γ$ . Moreover, $Γ \subseteq B$ , the $B ≻ Γ$ (by the monotonicity). By transitivity, $B^{'} ≻ Γ$ which is contradictory. Consequently, $B \in REPS (K, ≻)$ . □

Next, Lemma 6 show that an PAF possess a “coherent” property, i.e., the PAF is said to be coherent if its preferred and stable extensions coincide [36].
Lemma 6 (Modgil et.al [36]).

Let $A^{≻} = ({Arg}_{K}, {Def}_{≻})$ be a prioritized argumentation framework over a prioritized KB. If $| EXTS (A^{≻}) | = | REPS (K, ≻) |$ , then $A^{≻}$ is coherent.

Proof.
The proof follows directly from Lemma 4 and Lemma 5. The lemmas are needed to prove Lemma 6. □

Now, we are finally ready to prove Theorem 2.
Proof.
By Lemmas 4 and 5, there exists a link between the set of repair on $K$ and the set of extensions on $A^{≻}$ . Obviously, for every query Q and repair $B \in REPS (K, ≻)$ , it is the case that $C l_{R} (B) ⊧ Q$ iff $CONS (ARGS (B)) ⊧ Q$ . The theorem is now proven as follows:
$K \underset{B A R_{⪰}}{⊧} Q$ iff for some $B \in REPS (K, ≻), C l_{R} (B) ⊧ Q$ iff for some $M \in EXTS (A^{≻})$ , $CONS (M) ⊧ Q$ iff Q is credulously accepted.

$K \underset{A R_{⪰}}{⊧} Q$ iff for every $B \in REPS (K, ≻)$ , $C l_{R} (B) ⊧ Q$ iff for every $M_{i} \in EXTS (A^{≻})$ , $CONS (M_{i}) ⊧ Q$ iff Q is sceptically accepted.
This concludes Theorem 2 □

The following example illustrates the idea of this theorem. Example 8.
Reconsider the prioritized KB $K_{d c} = (F, R, C)$ mentioned in Example 3 with the arguments given in Example 4.

Consider the query $Q (d_{1}) = DancesWP (d_{1})$ asking whether $d_{1}$ is a dance with props. In the PAF, we find that $Q (d_{1})$ is sceptically accepted under stable semantics, i.e., $K_{d c} ⊧_{s c, stb}^{≻} Q (d_{1})$ since $d_{1}$ is in all extensions and it is the most trusted answer no matter which extension is considered. By Theorem 2, $Q (d_{1})$ holds under the ${AR}_{⪰}$ semantics if and only if it is sceptically accepted with respect to the stable semantic. Thus, $Q (d_{1})$ is entailed by KB under the ${AR}_{⪰}$ semantics.

Similarly, consider the query $Q (d_{2}) = DancesWOP (d_{2})$ asking whether $d_{2}$ is a dance without props. We find that $Q (d_{2})$ is credulously accepted under stable semantics, i.e., $K_{d c} ⊧_{c r, stb}^{≻} Q (d_{2})$ since $d_{2}$ is not in all extensions and it is the less trustworthy answer. By Theorem 2, it can be seen that $Q (d_{2})$ is entailed under the ${BAR}_{⪰}$ semantics if and only if it is credulously accepted with respect to stable semantics. Therefore, $Q (d_{2})$ is an answer under the ${BAR}_{⪰}$ semantics.

This example illustrates that the semantics of acceptance of an argument according to our PAF and the semantics of query entailment coincide, as it was shown in Theorem 2.

4.3. Rationality postulates

In this section, we demonstrate that the proposed argumentation framework has some desirable properties, namely a set of rationality postulates from [1,19] which is one of the main results we present in the paper. These are consistency, closure of extension, closure under sub-arguments, strong consistency, exhaustiveness and free precedence given in the definition below.

Definition 16 (Rationality Postulates).

Let $A^{≻} = ({Arg}_{K}, {Def}_{≻})$ be a prioritized argumentation framework corresponding to a prioritized ${Datalog}^{\pm}$ KB $K$ with $(F, ⪰)$ . For every extension $M \in EXTS (A^{≻})$ and every argument $A \in A^{≻}$ ,

$A^{≻}$ satisfies closure of extensions if the set $CONS (M)$ of conclusions of arguments in $M$ is closed under $C l_{R}$ .

$A^{≻}$ satisfies closure under Sub-argument if $A \in M$ then $Sub (A) \in M$ (recall that $Sub (A)$ stands for sub-argument set of A).

$A^{≻}$ satisfies weak closure under Sub-argument if $A \in M$ , B is a subargument of argument A and $B ⩽_{p r} A$ then $B \in M$ .

$A^{≻}$ satisfies consistency if the set $CONS (M)$ of conclusions of arguments in $M$ is consistent.

$A^{≻}$ satisfies exhaustiveness if $Sup (A) \cup {Con (A)} \subseteq CONS (M)$ then $A \in M$ .

$A^{≻}$ satisfies weak exhaustiveness if $Sup (A) \subseteq ⋃_{B \in M} Sup (B)$ then $A \in M$ .

$A^{≻}$ satisfies free precedence if $ARGS (Free (K)) \subseteq M$ where $Free (K) = F ∖ {M C \subseteq F ∣ M C is a minimal conflict}$ .

Now, we show one of the main contribution of this paper.

Theorem 7.
The PAF $A^{≻}$ satisfies rationality postulates.
Proof.
Obviously, ${R 2}^{}$ implies to R2 and ${R 4}^{}$ implies to R4. We prove each of the remaining postulates.

Closure of extensions: We prove that for every $M \in EXTS (A^{≻})$ , $CONS (M) = C l_{R} (CONS (M))$ . By the definition of $C l_{R}$ , $CONS (M) \subseteq C l_{R} (CONS (M))$ . Now we show the direction $C l_{R} (CONS (M)) \subseteq CONS (M)$ . Let $α \in C l_{R} (CONS (M))$ . Since $M$ is a preferred, stable extension, by Lemmas 4 and 5 there exists a set of formulas $B$ such that $M = ARGS (B)$ . Thus $M = ARGS (BASE (M))$ . Since the supports of the arguments of $M$ consist of the formulas in $B$ , $α \in C l_{R} (B)$ . Hence, $\exists A \in M$ such that $Con (A) = α$ .

Weak closure under sub-argument: Let $A \in M$ and B be a sub-argument of A such that $B \in M$ and $B ≺ A$ . Assume the contrary that $B \notin M$ . Since $M$ is a stable extension, there exists $C \in M$ such that C defeats B which means $\exists β \in Sup (B)$ such that $C l_{R} ({Con (C), β})$ is $R$ -inconsistent and $B ⊀ C$ . Moreover, as B is a sub-argument of A which means $Sup (B) \subseteq Sup (A)$ , it follows that $β \in Sup (A)$ . Thus C also undercut attacks A. And since $B ⊀ C$ and $B ≺ A$ , it is the case that $A ⊀ C$ . By the definition of defeat, C defeats A. Clearly, this shows that $M$ is conflicting which is a contradiction.

Consistency: We prove that for $M \in EXTS (A^{≻})$ , $CONS (M)$ is consistent. Let $M$ be a stable or preferred extension of $A^{≻}$ . By Lemma 5, there is a repair $B \in REPS (K, ≻)$ such that $M = ARGS (B)$ . Since $CONS (M) = C l_{R} (B)$ and $B$ is a repair, then $C l_{R} (B)$ is consistent. Thus $CONS (M)$ is consistent.

Exhaustiveness: Suppose the contrary that there exists an argument $A \in {Arg}_{K}$ such that $Sup (A) \cup {Con (A)} \subseteq CONS (M)$ and $A \notin M$ . Since $M$ is a stable extension, there exists an argument $B \in M$ such that B defeats A. This means that there exists $α \in Sup (A)$ such that $C l_{R} ({α, Con (B)})$ is $R$ -inconsistent. We also know that $Sup (A) \subseteq CONS (M)$ and $Con (B) \in CONS (M)$ . This means that $CONS (M)$ is inconsistent which contradicts with the consistency postulate.

Free precedence: We first observe that $Free (K)$ is consistent with each consistent set of facts $F^{'} \subseteq F$ . Suppose that an argument $A \in A^{≻}$ such that $Sup (A) \subseteq Free (K)$ . We show that A is not attacked. Assume the contrary that there exists $B \in A^{≻}$ in which B defeats A. By the definition of defeat, there exists $α \in Sup (A)$ such that $C l_{R} ({Con (B), α})$ is $R$ -inconsistent. Then, $C l_{R} (Sup (B) \cup Free (K))$ is inconsistent. Since $Sup (B)$ is consistent, $Free (K)$ is inconsistent, which is in contradiction with our initial assumption. Thus A is unattacked and it is a member of every extension. □

5. Argument-based explanations

In the previous section, we have clarified the use of the sceptical (resp. credulous) semantics of our prioritized argumentation framework to determine answers of a query under ${AR}_{⪰}$ semantics (resp. ${BAR}_{⪰}$ semantics) in a prioritized knowledge base. Such a use allows us to introduce explanation techniques for query answering by using the power of abstract argumentation which is the main motivation of this work. More specifically, given an inconsistent prioritized KB $K$ , a corresponding PAF $A^{≻}$ and a Boolean query Q, how can we better help the user to understand the classification of a query answer, such as why is Q an answer no matter which repair is considered (i.e., ${AR}_{⪰}$ )? Or why is it not? (Which means why does the answer hold with respect to at least one repair?

In PAF, we can interpret the above questions as: Is Q supported by an argument that can be deemed (dialogically) acceptable under sceptical semantics or credulous semantics? In general, explanations based on the argumentation can be viewed as a debate between two fictitious agents (i.e., the proponent and the opponent) arguing why arguments in an extension should be (or should not be) accepted. The general idea is as follows:

We first present the notion of supporting argument of a query, which was proposed in [6] (presented in Section 5.2).

We then construct dialogical explanations for that query, which are based on the notions of argumentation trees and argumentation structure introduced in [12] (presented in Section 5.2).

Finally, we show the usability of argumentation structure with respect to explanations of ${AR}_{⪰}$ and ${BAR}_{⪰}$ entailment (presented in Section 5.3).

Before representing the formal theory, we introduce the general idea with a motivating example.

5.1. Motivating example

In what follows we present a motivating example, which illustrates the motivation of using the argumentation framework to explain the ${AR}_{⪰}$ and ${BAR}_{⪰}$ semantics.

Example 9.
Given a prioritized KB $K_{d c} = (F, R, C)$ mentioned in Example 3 and a query $Q = \forall x DancesWOP (x)$ that stands for “Get all the dances that do not use props”. The system returns that ${d_{3}, d_{1}}$ is a set of ${AR}_{⪰}$ -answers and $d_{2}$ is a ${BAR}_{⪰}$ -answers. The user expects that the query $Q (d_{2}) = DancesWOP (d_{2})$ is a ${AR}_{⪰}$ -answer, which means “arguments supporting $d_{2}$ are accepted under the sceptical semantics”. Now, the user wants to understand why $Q (d_{2})$ is not an ${AR}_{⪰}$ -answer. There is a dialogical process to explain this as follows:

User: Why not $Q (d_{2}) = DancesWOP (d_{2})$ given $A_{10}$ ?

Reasoner: Because $DancesWP (d_{2})$

the following constraint is violated:

$\forall x DancesWP (x) \land DancesWOP (x) \to ⊥$ ,

and $Mdances (d_{2})$ is not preferred to $HasProps (d_{2}, h k)$

User: I got it!

Above is the dialogical process that shows $Q (d_{2}) = DancesWOP (d_{2})$ is in conflict with $DancesWP (d_{2})$ .

At the beginning, the user asks why $DancesWOP (d_{2})$ is not an answer for the query $Q (d_{2})$ given $A_{10}$ ? Realize at this point that $A_{10} = ({Mdances (d_{2})}, {DancesWOP (d_{2})})$ is an argumentation where $Q (d_{2}) = DancesWOP (d_{2})$ is a conclusion of $A_{10}$ , however $A_{10}$ is not in all extensions.

In particular, $A_{10} = ({Mdances (d_{2})}, {DancesWOP (d_{2})})$ is defeated by the counter-arguments $A_{12} = ({HasProps (d_{2}, h k)}, {DancesWP (d_{2})})$ and $A_{11} = ({HasProps (d_{2}, h k)}, {HasProps (d_{2}, h k)})$ ,

$A_{12} ⪰ A_{10}$ and $A_{11} ⪰ A_{10}$ , and $DancesWP (d_{2})$ is a conclusion of $A_{12}$ . This means $Q (d_{2}) = DancesWOP (d_{2})$ is not entailed in all extensions, i.e., $K_{d c} ⊭_{A R_{⪰}} Q (d_{2})$ . At this very step, although not happened in the dialogue, the user could further ask “Why $DancesWP (d_{2})$ ?” and the reasoner could reply “Because $HasProps (d_{2}, h k)$ ” which implies $DancesWP (d_{2})$ . The main strength of our approach is that we provide the user with the information regarding such potential scenarios, in the form of a dialogical explanation which is illustrated below for this particular example.

where C: $\forall x DancesWP (x) \land DancesWOP (x) \to ⊥$

The above example shows the need for explanation facilities to help the user to understand why a query holds and fails. We next discuss the generation process of dialogical explanations through argumentation trees for inconsistency of a prioritized KG.
5.2. Argumentation trees

In order to construct dialogical explanations, we introduce the notion of an argumentation tree proposed in [12], which is a formal representation of the dialogue within the PAF. Before continuing, let us first review the notion called causes (for a query) introduced in [16].

Definition 17 (Bienvenu et.al [16]).

A cause for a Boolean query Q in a KB $K$ is an inclusion minimal consistent subset $C \subseteq F$ s.t. $C l_{R} (C) ⊧ Q$ .

It turns out that the notion of causes coincides with the definition of arguments. Inspired by earlier argumentation frameworks [6], we recall the notion of supporting argument of a query. Informally, an argument supports a query if and only if the query is entailed by the conclusion of the argument. The notion is necessary to select the arguments for or against the query.

Definition 18 (Arioua et.al. [6]).

Let $A^{≻} = ({Arg}_{K}, {Def}_{≻})$ be a PAF and Q be a query. An argument $A \in {Arg}_{K}$ supports the query Q iff $Con (A) ⊧ Q$ . A is called a supporting argument of Q. The set of supporting arguments of Q will be denoted as $Supporter (Q)$ .

Corollary 1 clarifies the relation between causes and supporting arguments of the query, which follows directly from Definition 18.

Corollary 1.
Let $K = (F, R, C)$ be a prioritized ${Datalog}^{\pm}$ KB with $(F, ⪰)$ s.t. $Ψ \subseteq F$ and Q be a Boolean query and $A^{≻} = ({Arg}_{K}, {Def}_{≻})$ be a PAF. Then, $A = (Ψ, α)$ is a supporting argument s.t. ${α} ⊧ Q$ iff Ψ is a cause for Q in $K$ .

Observe that the relation between the repair semantics and the causes has been shown in [16]. The causes also correspond to the supporting arguments of the query (by Corollary 1). It is easily seen that these relations are crucial to establish the results mentioned in Proposition 1 related to the definitions in this section. The following proposition clarifies the relation between the preferred repairs and the supporting arguments of the query.
Proposition 1.
Let $K = (F, R, C)$ be a prioritized ${Datalog}^{\pm}$ KB with $(F, ⪰)$ , $A^{≻} = ({Arg}_{K}, {Def}_{≻})$ be the corresponding argumentation framework, and Q be a query. The following holds:

1. $K ⊧_{B A R_{⪰}} Q$ iff $\exists A \in {Arg}_{K}$ such that $A \in Supporter (Q)$ and $\exists M \in EXTS (A^{≻})$ with $A \in M$ .

2. $K ⊧_{A R_{⪰}} Q$ iff there is a set of supporting arguments $Supporter (Q) = {A_{1}, \dots, A_{n}}$ and every extension $M \in EXTS (A^{≻})$ contains $A_{i}$ .

In our work, we use argumentation as a formal framework to explain query answers under $A R_{⪰}$ and $B A R_{⪰}$ semantics. That way, we can explain query answer (and no-answers) by using arguments and counter-arguments by graphically representing different points of view, and why they are conflicting or not. To that end, we introduce argumentation tree where each node is an argument, the root node is a supporting argument, and every child node defeats its parent. Intuitively, it can be seen as a dialogical explanation in the form of a tree of dispute gathering arguments and counter-arguments for and against the query (see for instance Fig. 9).
Definition 19 (Argumentation tree).

An argumentation tree $T (A_{0})$ is a tree for a given query Q w.r.t. $K = (F, R, C)$ , whose nodes are arguments in which:

The root node $A_{0}$ is either a supporting or a counter argument for Q

For every node $A_{k} = (Ψ_{k}, α_{k})$ whose ancestor nodes are $A_{0} = (Ψ_{0}, α_{0}), \dots, A_{n} = (Ψ_{n}, α_{n})$ (hence, $k > n$ ), there exists $β \in Ψ_{k}$ s.t. $β \notin Ψ_{i}$ for $i = 0, \dots, n$ .

Each child node defeats its parent node.

Note that the second condition of the definition guarantees that each counter-argument contains an additional information compared to its ancestry, thereby preventing cycles. Note also that for a given query Q, there can be multiple but finitely many argumentation tree since there are potentially many but finite supporting argument to be chosen as the root node. Moreover, the length of each such tree is finite which follows from the cycle-freeness guaranteed by the second condition of Definition 19. We state this important fact as a proposition below.

Proposition 2 (Finiteness).

Given a prioritized KB $K$ and a query Q, there is a finite number of argumentation trees for Q and each of them is finite.

Following the previous result, it is of interest to know the complexity of deciding whether a supporting argument is defeated or not. The following results answer this.

Proposition 3.
Given an argumentation tree $T (A_{0})$ , $A_{0}$ is an accepted argument iff there is no path of length n from $A_{0}$ to a terminal node where n is an odd number.
Proof Sketch.
Instead of giving the full-fledged proof, we give the crucial observation that proof follows from. Observe that if there is a path from a $A_{0}$ to a terminal node of odd length, then it means that there is an undefeated attacker which attacks either $A_{0}$ or a defender argument of $A_{0}$ . Otherwise $A_{0}$ is undefeated which means it is accepted. □

Argumentation trees are very useful in the sense that it contains all the relevant information about the position of the arguments. As a result of that, once they are provided the computational complexity of deciding whether the root node is an accepted argument is very favorable as we mention it in the following corollary (which follows from the proposition above).
Corollary 2.
Deciding whether $A_{0}$ is accepted, given argumentation tree $T (A_{0})$ is of time linear in the size of the tree. (Specifically, it is at most $| T (A_{0}) |$ ).

In order to ground these intuitions, we give an example.
Example 10 (Continued Example 9).

An argumentation tree for $Q (d_{2}) = DancesWOP (d_{2})$ is given as follows: The roots of the tree is the supporting argument $A_{10}$ (i.e., $Con (A_{10}) ⊧ Q (d_{2})$ ). $A_{10}$ is defeated by $A_{11}$ and $A_{12}$ (since these nodes have no children).

In what follows, given an argumentation tree for $A_{0}$ of Q, nodes is labeled as either + for undefeated or − for defeated. In the tree, all leaves $A_{n}$ will be labeled by $(+, A_{n})$ since they have no defeaters, every internal node $A_{n - 1}$ is labeled by $(-, A_{n - 1})$ if and only if it has at least one $(+, A_{n})$ as a child, otherwise it will be labeled as $(+, A_{n - 1})$ . If the supporting argument $A_{0}$ of Q is marked as $(+, A_{0})$ , we shall regard it as an acceptance, otherwise it is a nonacceptance.

Now, with the notion of labelling, we can determine whether the argumentation tree is successful or not.

Definition 20.
Let $T (A_{0})$ be an argumentation tree for a given Q. T is successful with respect to Q iff the supporting argument $A_{0}$ of Q is accepted (under respective semantics) otherwise T is unsuccessful.

The dialogical process can be seen as a two-person (argumentation) game between a proponent and an opponent. The proponent and the opponent are engaged in an argumentation dialogue of a sequence of moves. The dialogue starts by the proponent with a supporting argument for Q. Then, the opponent presents an argument (or a set of arguments) that defeats the supporting argument of the proponent. Next, the proponent tries to avoid this attack and reinstate the query by using another argument which is not attacked by the opponent. The opponent tries to extend the previous set of attackers so that it defeats all the supporting arguments advanced so far. When the opponent fails to extend the set, it retraces back and chooses another set of attackers and continues the dialogue from thereafter. By doing so, the opponent is trying to construct a set of arguments that defeats all the supporting of the query Q.

The following example shows how the dialogical process for Example 9 is constructed from the argumentation tree.
Example 11 (Continued Example 10).

For $Q (d_{2}) = DancesWOP (d_{2})$ , the argumentation tree can be seen as a dialogical explanation for the non-acceptance of the supporting argument $A_{10}$ ; that is, the argumentation tree for $Q (d_{2})$ is unsuccessful.

The dialogical process is built as follows: At the beginning, an explanation request is made by the proponent (the human user) asking “Why the query $Q (d_{2})$ is not entailed under skeptical semantics while there is an argument $A_{10}$ asserts the entailment of $Q (d_{2})$ ?”. The opponent (the non-human reasoner) responds with an explanation showing that the argument $A_{10}$ (that supports $Q (d_{2})$ ) is defeated by $A_{11}$ and $A_{12}$ . Since there is no argument attacking $A_{11}$ and $A_{12}$ , the dialogue ends with the conclusion that $A_{10}$ is not accepted.

As aforementioned, given a prioritized KB $K$ , a query can have more than one argumentation tree with different status (successful or unsuccessful). In order to collect the information from these argumentation trees (for and against the query), we define argumentation structures.

Definition 21 (Argumentation structure).

An argumentation structure for a query Q is a pair of sets $(P, O)$ where $P$ is the set of argumentation trees for Q and $O$ is the set of argumentation trees against Q.

Example 12 (Continued Example 11).

Consider the query $Q (d_{2})$ with the set of supporting arguments $Supporter (Q (d_{2})) = {A_{10}}$ . Then, the set of all counter-arguments is ${A_{11}, A_{12}}$ . Now we build an argumentation structure $(P, O)$ for $Q (d_{2})$ given below.

We obtained some of the argument trees of the argument structure for $Q (d_{2})$ and its contraries. In particular, the argumentation trees in $P$ indicate that the supporting argument $A_{10}$ for $Q (d_{2})$ is defeated by its contraries $A_{11}$ and $A_{12}$ . This means that there exists an extension in which $A_{10}$ is not accepted. The argumentation trees in $O$ also show that the contraries of $Q (d_{2})$ are defeated by the argument $A_{10}$ . Then, all the roots are defeated in the structure $(P, O)$ , which means that the supporting argument $A_{10}$ could not be accepted in all extensions.

5.3. Argument-based explanations for query answers

In this section, we explain $A R_{⪰}$ and $B A R_{⪰}$ entailment for a given query through argument-based explanations which formally define next.

Next, we clarify the relation between argument-based explanations and the $A R_{⪰}$ and $B A R_{⪰}$ entailment. Definition 22 makes use of Proposition 1. Note that if the knowledge base is consistent then all argumentation trees in $P$ have exactly one node and $O$ is an empty set.

Definition 22 (Argument-based explanation).

Let $K$ be a prioritized $Datalog \pm$ KB and Q be a query. An argument-based explanation $Exp (Q)$ for Q is the tuple $(Supporter (Q), (P, O))$ where $Supporter (Q)$ is a set of supporting arguments for Q and $(P, O)$ is an argumentation structure for Q. Then, Exp(Q) is an explanation for

if $\exists T (A) \in P$ which is successful and $\forall T^{'} (B_{j}) \in O$ are unsuccessful or $O = \emptyset$ . (I.e., $K \underset{B A R_{⪰}}{⊧} Q$ ).

if $\exists Supporter (Q) \neq \emptyset$ and $\forall A \in Supporter (Q)$ , $T (A)$ is successful, and $\forall T^{'} (B) \in O$ , $T^{'} (B)$ is unsuccessful or $O = \emptyset$ , where B is a counter-argument for A. (I.e., $K \underset{A R_{⪰}}{⊧} Q$ ).

if it is an explanation for $B A R_{⪰}$ answer and not $A R_{⪰}$ answer. (I.e., $K \underset{A R_{⪰}}{⊭} Q$ ).

Realize that given a Q and $K$ , $Exp (Q)$ is always unique, since it considers all the argumentation trees. Explanations for $B A R_{⪰}$ -answers possesses a supporting argument holding in some extensions. This means the query is supported by an argument in some extensions such that the argument is defended. In general, the credulous view amounts to allowing for different argumentation trees for/ against the query to be both successful at the same time. Moreover, we explain why an answer returned as a $B A R_{⪰}$ -answer does not hold under some extensions.

Regarding explanations for an $A R_{⪰}$ -answer, the answer may be supported by different arguments in different extensions. Therefore, we next define a set of supporting arguments of an explanation that covers all extensions. According to Definition 22, explanations for $A R_{⪰}$ semantics indicate that a query is entailed under $A R_{⪰}$ semantics if the query is accepted under sceptical semantics if it is supported by a set of arguments that are defended.

Next, explanations for $K \underset{A R_{⪰}}{⊭} Q$ show that the supporting argument of Q is defeated by a set of arguments and vice versa. We note that explanations for negative $A R_{⪰}$ -answers should be accompanied with the explanations for being a $B A R_{⪰}$ -answer, because otherwise they may be difficult to understand, which is shown in Example 13.

Example 13 (Continued Example 9).

Consider $Q (d_{2}) = DancesWOP (d_{2})$ .

We explain $K ⊭_{A R_{⪰}} Q (d_{2})$ . An argument-based explanation for $Q (d_{2})$ includes a set of supporting arguments for $Q (d_{2}) Supporter (Q (d_{2})) = {A_{10}}$ and an argumentation structure $(P, O)$ . We construct the argumentation structure for $Q (d_{2})$ given Fig. 2(a). In this structure, we obtain three argument trees for the argument structure for $Q (d_{2})$ and its contraries. In particular, the argumentation trees in $P$ indicate that the supporting argument $A_{10}$ for $Q (d_{2})$ is defeated by its contraries $A_{11}$ and $A_{12}$ . This means that there exists an extension in which $A_{10}$ is not accepted. The argumentation trees in $O$ also show that the contraries of $Q (d_{2})$ are defeated by the argument $A_{10}$ . Then, the structure $(P, O)$ shows the supporting argument $A_{10}$ could be not accepted in all extensions, i.e., $K ⊭_{A R_{⪰}} Q (d_{2})$ .

We consider an explanation for $B A R_{⪰}$ -answer of the query $Q (d_{2})$ , in which the argumentation structure for $Q (d_{2})$ is given Fig. 2(b). In this structure, the argumentation trees in $P$ and $O$ indicate that the supporting argument $A_{10}$ for $Q (d_{2})$ is undefeated. This means that there exists an extension $M_{2}$ where $A_{10}$ is accepted. Moreover, Example 11 shows the explanation for $K ⊭_{A R_{⪰}} Q (d_{2})$ . Then $A_{10}$ could be accepted in only some extensions. Thus, $K ⊧_{B A R_{⪰}} Q (d_{2})$ and $K ⊭_{A R_{⪰}} Q (d_{2})$ .

Fig. 2.

Augmentation structures for $Q (d_{2})$ : (a) negative $A R_{⪰}$ -answer and (b) $B A R_{⪰}$ -answer.

Regarding explanations for ${AR}_{⪰}$ -answers, argumentation trees in $P$ are successful and argumentation trees in $O$ are unsuccessful. The explanation for ${AR}_{⪰}$ -answers is illustrated in Example 14.

Example 14 (Continued Example 9).

Consider $Q (d_{1}) = DancesWP (d_{1})$ . An argument-based explanation for $Q (d_{1})$ consists of $Supporter (Q (d_{1})) = {A_{4}, A_{6}}$ and an argumentation structure for $Q (d_{1})$ . We construct the argumentation structure for $Q (d_{1})$ given below. In this structure, the argumentation trees in $P$ show how the set of supporting arguments ${A_{4}, A_{6}}$ is undefeated by their contraries ${A_{7}, A_{8}}$ . The argumentation trees in $O$ indicate that the contraries of the supporting argument are defeated. Then, ${A_{4}, A_{6}}$ is accepted in all extensions. Thus, we can explain why $K ⊧_{A R_{⪰}} Q (d_{1})$ .

Next, we present Algorithm 3 to generate an argumentation tree for a specific argument. The function GenerateTree in Algorithm 3 takes an argument A and an argumentation graph $A G$ as an input and outputs an argumentation tree. First, the algorithm computes the set of attackers (for-loop from Line 2 to Line 5). Then, for each attacker the algorithm computes its attackers (for-loop from Line 6 to Line 9). Finally, the function returns the argumentation tree called ArgTree.

Algorithm 3:

GenerateTree

We now propose the main algorithm ExplainQuery (Algorithm 4) that determines the explanations and the semantics ( ${AR}_{⪰}$ , ${BAR}_{⪰}$ ) under which a Boolean query holds. As a first step, ExplainQuery computes the set of supporters for Q (lines 5–7). The next step is to build argumentation trees for each supporting argument of Q and its contrary (lines 8–14). Then, the algorithm computes the set of extensions (Line 4) and uses the extensions to identify the semantics (among ${AR}_{⪰}$ , ${BAR}_{⪰}$ ) under which Q holds (Line 15). Moreover, the algorithm generate argumentation trees for supporting arguments and their contrary in an argument structure $(P, O)$ (lines 10–14). Then the supporters and the argument structure $(P, O)$ for Q are used to identify the argument-based explanations (Line 16).

Algorithm 4:

ExplainQuery

The correctness of Algorithm 4 is given by Theorem 8.

Theorem 8 (Soundness of Algorithm 4).

Let $K = (F, R, C)$ be a prioritized ${Datalog}^{\pm}$ KB and Q be a Boolean query. Then ExplainQuery correctly computes a set of explanations to Q and semantics (among $A R_{⪰}$ , $B A R_{⪰}$ ) under which Q holds.

Proof.
Given a prioritized KB $K = (F, R, C)$ , a Boolean query Q and the generated argumentation graph (AG) (by Algorithm 2). For the for-loop on Line 5, for any argument $A \in Args$ until the last argument m (where all argument have been applied at least once in $Arg$ ), Line 6 checks whether $Con (A) ⊧ Q$ . If it is, the algorithm will return the set of supporter for Q at the end of the for-loop at Line 5 if the set of supporters is not empty. Next, prior to the first for-loop on Line 10, for any supporting argument $A \in Supporter (Q)$ until the last supporting argument n (where all argument have been applied at least once in $Supporter (Q)$ ), the algorithm computes dialogical explanations as argumentation trees for A (Line 11) and the set of attacker for A (Line 12). At the inner for-loop loop on Line 13, for any $B \in Attacker$ until the last argument n in which all arguments have been applied at least once in $Attacker$ , Line 14 calculates the set of argumentation tree A’s contrary. Thus, at the end of the for-loop at Line 10, the algorithm returns: (1) semantics (i.e., $A R_{⪰}$ , $B A R_{⪰}$ ) under which Q holds if the set of supporting arguments is not empty; (2) all argument-based explanations for Q if the set of argumentation trees is not empty. The algorithm returns ∅, otherwise. □
6. Conclusion

In this paper, we have investigated the use of argumentation to handle inconsistency in ${Datalog}^{\pm}$ KBs where facts are ordered representing their reliability, with the aim to improve the explanation techniques under preferred semantics. We then showed that the semantics of our framework (PAF) corresponds to the preferred repair semantics of the prioritized ${Datalog}^{\pm}$ KB. In particular, we exploit the equivalence relation between the preferred repairs and the extensions to provide explanations for the query answers under $A R_{⪰}$ and $B A R_{⪰}$ semantics. Based on these explanations, the user provided with a broader explanation regarding the querying process in terms of conflicting information. To the best of our knowledge, this is the first work which studies explanations for query answering in ${Datalog}^{\pm}$ KB through the lens of argumentation framework. We very much hope that our work helps paving the way for the application of certain algorithms to computer-preferred repairs in prioritized ${Datalog}^{\pm}$ KBs. The main particular advantage of our approach over existing works is that, it does not only provides the user with the supporting arguments for a query, but also a set of dispute trees rooted in for- and against- arguments for the query. That way, user is not informed only for the accepted answers to the query but also other potentially relevant arguments.

A natural future avenue of research is to analyze the computational complexity of computing the argument-based explanations both empirically and theoretically, pinpointing easy and hard cases. Moreover, we plan to extend our work to the case of dynamic knowledge bases, i.e., prioritized information can be updated and the new information may contradict to existing knowledge. One advantage of dynamic knowledge bases over static ones is that, they can represent the relevant knowledge that is tailored towards the dependent context and the temporality which can be carried out by knowledge updates that are common in real-world applications.

Footnotes

Acknowledgements

This work was supported by grants from Khon Kaen University via ASEAN and GMS Countries’s Personnel Programs 2016–2019 and an Interdisciplinary Grant (CSKKU2559) from the Department of Computer Science, Khon Kaen University. Erman Acar is generously funded by the Hybrid Intelligence Project which is financed by the Dutch Ministry of Education, Culture and Science with project number 024.004.022

References

Amgoud, Postulates for logic-based argumentation systems, International Journal of Approximate Reasoning 55(9) (2014), 2028–2048, Weighted Logics for Artificial Intelligence. doi:10.1016/j.ijar.2013.10.004.

Antoniou and

F.V.

Harmelen, Web ontology language: OWL, in: Handbook on Ontologies, 2004.

Arieli,

Borg and

Heyninck, A review of the relations between logical argumentation and reasoning with maximal consistency, Annals of Mathematics and Artificial Intelligence 87(3) (2019), 187–226. doi:10.1007/s10472-019-09629-7.

Arieli,

Borg and

Straundefineder, Prioritized sequent-based argumentation, in: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 2018, pp. 1105–1113.

Arioua and

Croitoru, Dialectical characterization of consistent query explanation with existential rules, in: FLAIRS Conference, 2016.

Arioua,

Croitoru and

Vesic, Logic-based argumentation with existential rules, International Journal of Approximate Reasoning 90 (2017), 76–106, https://www-sciencedirect-com-443.web.bisu.edu.cn/science/article/pii/S0888613X17304383 . doi:10.1016/j.ijar.2017.07.004.

Arioua,

Tamani and

Croitoru, Query answering explanation in inconsistent datalog knowledge bases, in: Database and Expert Systems Applications,

Chen,

Hameurlain,

Toumani,

Wagner and

Decker, eds, Springer International Publishing, Cham, 2015, pp. 203–219. ISBN 978-3-319-22849-5. doi:10.1007/978-3-319-22849-5_15.

Asfand-E-Yar and

Ali, Semantic integration of heterogeneous databases of same domain using ontology, IEEE Access 8 (2020), 77903–77919. doi:10.1109/ACCESS.2020.2988685.

Baader,

Brandt and

Lutz, Pushing the EL envelope, in: Proceedings of the 19th International Joint Conference on Artificial Intelligence, IJCAI’05, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2005, pp. 364–369.

10.

J.-F.

Baget,

Leclère,

M.-L.

Mugnier and

Salvat, On rules with existential variables: Walking the decidability line, Artificial Intelligence 175(9) (2011), 1620–1654, https://www-sciencedirect-com-443.web.bisu.edu.cn/science/article/pii/S0004370211000397 . doi:10.1016/j.artint.2011.03.002.

11.

Belabbes,

Benferhat and

Chomicki, Elect: An inconsistency handling approach for partially preordered lightweight ontologies, in: Logic Programming and Nonmonotonic Reasoning,

Balduccini,

Lierler and

Woltran, eds, Springer International Publishing, Cham, 2019, pp. 210–223. ISBN 978-3-030-20528-7. doi:10.1007/978-3-030-20528-7_16.

12.

Besnard and

Hunter, A logic-based theory of deductive arguments. This is an extended version of a paper entitled “Towards a logic-based theory of argumentation”, in: Proceedings of the National Conference on Artificial Intelligence (AAAI’2000), Austin, TX, Artificial Intelligence, Vol. 128, MIT Press, Cambridge, MA, 2001, pp. 203–235. doi:10.1016/S0004-3702(01)00071-6.

13.

Bienvenu and

Bourgaux, Querying and Repairing Inconsistent Prioritized Knowledge Bases: Complexity Analysis and Links with Abstract Argumentation, 2020, CoRR, arXiv:2003.05746.

14.

Bienvenu,

Bourgaux and

Goasdoué, Querying Inconsistent Description Logic Knowledge Bases under Preferred Repair Semantics, 2014.

15.

Bienvenu,

Bourgaux and

Goasdoue, Explaining inconsistency-tolerant query answering over description logic knowledge bases, in: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI16, AAAI Press, 2016, pp. 900–906.

16.

Bienvenu,

Bourgaux and

Goasdoue, Computing and explaining query answers over inconsistent DL-lite knowledge bases, J. Artif. Int. Res. 64(1) (2019), 563–644. doi:10.1613/jair.1.11395.

17.

Cali,

Gottlob,

Lukasiewicz and

Pieris, Datalog+/−: A family of languages for ontology querying, in: Datalog Reloaded – 1st International Workshop, Datalog 2010, Revised Selected Papers,

de Moor,

Gottlob,

Furche and

A.J.

Sellers, eds, Lecture Notes in Computer Science, Oxford, UK, March 16–19, 2010, Vol. 6702, Springer, Oxford, UK, 2011, pp. 351–368. ISBN 978-3-642-24205-2. doi:10.1007/978-3-642-24206-9_20.

18.

Calvanese,

De Giacomo,

Lembo,

Lenzerini and

Rosati, Tractable reasoning and efficient query answering in description logics: The DL-lite family, Journal of Automated Reasoning 39(3) (2007), 385–429. doi:10.1007/s10817-007-9078-x.

19.

Caminada and

Amgoud, On the evaluation of argumentation formalisms, Artificial Intelligence 171(5) (2007), 286–310. doi:10.1016/j.artint.2007.02.003.

20.

Cayrol,

Dubois and

Touazi, On the semantics of partially ordered bases, in: Proceedings of the 8th International Symposium on Foundations of Information and Knowledge Systems – Volume 8367, FoIKS 2014, Springer-Verlag, Berlin, Heidelberg, 2014, pp. 136–153. ISBN 9783319049380.

21.

Cyras and

Toni, ABA+: Assumption-based argumentation with preferences, in: Proceedings of the Fifteenth International Conference on Principles of Knowledge Representation and Reasoning, KR’16, AAAI Press, 2016, pp. 553–556.

22.

D’Agostino and

Modgil, A study of argumentative characterisations of preferred subtheories, in: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18, International Joint Conferences on Artificial Intelligence Organization, 2018, pp. 1788–1794.

23.

P.M.

Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artif. Intell. 77(2) (1995), 321–357. doi:10.1016/0004-3702(94)00041-X.

24.

Eiter and

Gottlob, The complexity of logic-based abduction, J. ACM 42(1) (1995), 3–42. doi:10.1145/200836.200838.

25.

Gomez,

Chesñevar and

Simari, Reasoning with inconsistent ontologies through argumentation, Applied Artificial Intelligence 24 (2010), 102–148. doi:10.1080/08839510903448692.

26.

Hecham,

Bisquert and

Croitoru, On the chase for all provenance paths with existential rules, in: RuleML+RR, 2017.

27.

Heyninck and

Straundefineder, A fully rational argumentation system for preordered defeasible rules, in: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS’19, International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 2019, pp. 1704–1712. ISBN 9781450363099.

28.

Lee,

Cornet,

Lau and

de Keizer, A survey of SNOMED CT implementations, Journal of Biomedical Informatics 46(1) (2013), 87–96. doi:10.1016/j.jbi.2012.09.006.

29.

Lehmann,

Isele,

Jakob,

Jentzsch,

Kontokostas,

Mendes,

Hellmann,

Morsey,

Van Kleef,

Auer and

Bizer, DBpedia – A Large-scale, Multilingual Knowledge Base Extracted from Wikipedia, Semantic Web Journal 6 (2014). doi:10.3233/SW-140134.

30.

Lembo,

Lenzerini,

Rosati,

Ruzzi and

D.F.

Savo, Inconsistency-tolerant semantics for description logics, in: Web Reasoning and Rule Systems,

Hitzler and

Lukasiewicz, eds, Springer, Berlin Heidelberg, 2010, pp. 103–117. ISBN 978-3-642-15918-3. doi:10.1007/978-3-642-15918-3_9.

31.

Lukasiewicz,

Malizia and

Molinaro, Complexity of approximate query answering under inconsistency in Datalog+/, in: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18, International Joint Conferences on Artificial Intelligence Organization, 2018, pp. 1921–1927. doi:10.24963/ijcai.2018/265.

32.

Lukasiewicz,

Malizia and

Molinaro, Explanations for inconsistency-tolerant query answering under existential rules, in: Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI-20),

Conitzer and

Sha, eds, 2020.

33.

Lukasiewicz,

Malizia and

Vaicenavičius, Complexity of inconsistency-tolerant query answering in Datalog+/- under cardinality-based repairs, in: Proceedings of the AAAI Conference on Artificial Intelligence 33(01), 2019, pp. 2962–2969. doi:10.1609/aaai.v33i01.33012962.

34.

Marnette, Generalized schema-mappings: From termination to tractability, in: Proceedings of the Twenty-Eighth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS’09, Association for Computing Machinery, New York, NY, USA, 2009, pp. 13–22. ISBN 9781605585536. doi:10.1145/1559795.1559799.

35.

Modgil, Reasoning about preferences in argumentation frameworks, Artificial Intelligence 173(9) (2009), 901–934, https://www-sciencedirect-com-443.web.bisu.edu.cn/science/article/pii/S0004370209000162 . doi:10.1016/j.artint.2009.02.001.

36.

Modgil and

Caminada, Proof theories and algorithms for abstract argumentation frameworks, in: Argumentation in Artificial Intelligence,

Simari and

Rahwan, eds, Springer US, Boston, MA, 2009, pp. 105–129. doi:10.1007/978-0-387-98197-0_6.

37.

Poggi,

Lembo,

Calvanese,

De Giacomo,

Lenzerini and

Rosati, Linking data to ontologies, in: Journal on Data Semantics X,

Spaccapietra, ed., Springer, Berlin Heidelberg, 2008, pp. 133–173. ISBN 978-3-540-77688-8. doi:10.1007/978-3-540-77688-8_5.

38.

Stevens,

Egaña,

Wolstencroft,

Sattler,

Drummond,

Horridge and

Rector, Using OWL to model biological knowledge, International Journal of Man-Machine Studies 65 (2007), 583–594.

39.

Telli,

Benferhat,

Bourahla,

Bouraoui and

Tabia, Polynomial algorithms for computing a single preferred assertional-based repair, KI, Kunstliche Intelligenz 31 (2016), 15–30. doi:10.1007/s13218-016-0466-4.

40.

W.T.

Tsai,

Wei,

Chen,

R.A.

Paul,

J.-Y.

Chung and

Zhang, Data provenance in SOA: Security, reliability, and integrity, Service Oriented Computing and Applications 1 (2007), 223–247. doi:10.1007/s11761-007-0018-8.

41.

A.P.

Young,

Modgil and

Rodrigues, Prioritised Default Logic as Argumentation with Partial Order Default Priorities, 2016, arXiv:1609.05224.

42.

Yun,

Vesic and

Croitoru, Sets of attacking arguments for inconsistent datalog knowledge bases, in: COMMA 2020 – 8th International Conference on Computational Models of Argument, Frontiers in Artificial Intelligence and Applications, Vol. 326, Perugia / Virtual, Italy, 2020, pp. 419–430, https://hal.archives-ouvertes.fr/hal-03002140 . doi:10.3233/FAIA200526.

User: Why not $Q (d_{2}) = DancesWOP (d_{2})$ given $A_{10}$ ?
	Reasoner: Because $DancesWP (d_{2})$
	the following constraint is violated:
	$\forall x DancesWP (x) \land DancesWOP (x) \to ⊥$ ,
	and $Mdances (d_{2})$ is not preferred to $HasProps (d_{2}, h k)$
User: I got it!

An argumentative approach for handling inconsistency in prioritized Datalog ± ontologies

Abstract

Keywords

1. Introduction

1 It should be noted that these works are in fact quite related i.e., the minimal explanation in Lukasiewicz’s work [32] can be seen as the cause defined in [16].

4 ICR stands for intersection of closed repairs.

3.1. Abstract argumentation

Definition 1 (Abstract Argumentation).

Definition 2 (Extensions).

3.2. Datalog ±

3.3. Prioritized Datalog ± knowledge base

Definition 4 (Prioritized D ATALOG ± knowledge bases).

Definition 6 (Repair).

Definition 7 (Ranking function).

Definition 8 (Preference relation).

4.1. Prioritized argumentation framework

5 This means that we inherit attack and defeat relations over arguments as it was defined in Dung’s framework.

Definition 13 (Defeat attack).

Example 6 (Example 5 continued).

Definition 14 (Prioritized argumentation).

Definition 15 (Acceptability).

Definition 16 (Rationality Postulates).

5.1. Motivating example

Definition 17 (Bienvenu et.al [16]).

Definition 18 (Arioua et.al. [6]).

Proposition 2 (Finiteness).

Definition 21 (Argumentation structure).

Example 12 (Continued Example 11).

5.3. Argument-based explanations for query answers

Definition 22 (Argument-based explanation).

Example 13 (Continued Example 9).

Footnotes

Acknowledgements

References

¹
It should be noted that these works are in fact quite related i.e., the minimal explanation in Lukasiewicz’s work [32] can be seen as the cause defined in [16].

⁴
ICR stands for intersection of closed repairs.

3.2. ${Datalog}^{\pm}$

3.3. Prioritized ${Datalog}^{\pm}$ knowledge base

Definition 4 (Prioritized ${D ATALOG}^{\pm}$ knowledge bases).

⁵
This means that we inherit attack and defeat relations over arguments as it was defined in Dung’s framework.