=Paper=
{{Paper
|id=Vol-1517/JOWO-15_ontolp_paper_10
|storemode=property
|title=On the Influence of Incoherence in Inconsistency-tolerant Semantics for Datalog±
|pdfUrl=https://ceur-ws.org/Vol-1517/JOWO-15_ontolp_paper_10.pdf
|volume=Vol-1517
|dblpUrl=https://dblp.org/rec/conf/ijcai/DeagustiniMFS15
}}
==On the Influence of Incoherence in Inconsistency-tolerant Semantics for Datalog±==
https://ceur-ws.org/Vol-1517/JOWO-15_ontolp_paper_10.pdf
On the Influence of Incoherence in Inconsistency-tolerant Semantics for Datalog±
C. A. Deagustini and M. V. Martinez and M. A. Falappa and G. R. Simari
AI R&D Lab., Dep. of Computer Science and Engineering,
Universidad Nacional del Sur, Bahı́a Blanca, Argentina
Consejo Nacional de Investigaciones Cientı́ficas y Técnicas (CONICET),
Avenida Rivadavia 1917, Ciudad Autónoma de Buenos Aires, Argentina
Abstract Although to consider the constraints as always satisfiable
is a reasonable assumption to make, specially in the case of
The concept of incoherence naturally arises in onto-
a single ontology, in this work we will focus on a more gen-
logical settings, specially when integrating knowledge.
In this work we study a notion of incoherence for eral setting and consider that both data and constraints can
Datalog ± ontologies based on the definition of satis- change through time and become conflicting. In this more
fiability of a set of existential rules regarding the set general scenario, as knowledge evolves (and so the ontology
of integrity constraints in a Datalog ± ontology. We that represents it) not only data related issues can appear,
show how classical inconsistency-tolerant semantics for but also constraint related ones. The problem of conflicts
query answering behaves when dealing with atoms that among constraints is known in the Description Logics com-
are relevant to unsatisfiable sets of existential rules, munity as incoherence (Flouris et al. 2006; Qi and Hunter
which may hamper the quality of answers—even under 2007). As they were not developed to consider this kind of
inconsistency-tolerant semantics, which is expected as issue, several of the well-known inconsistency-tolerant se-
they were not designed to confront such issues. Finally,
mantics for query answering fail at computing good qual-
we propose a notion of incoherency-tolerant semantics
for query answering in Datalog ± , and present a particu- ity answers in the presence of incoherence. In this paper
lar one based on the transformation of classic Datalog ± we focus on a particular family of of ontological languages,
ontologies into defeasible Datalog ± ones, which use ar- namely Datalog ± (Calı̀, Gottlob, and Lukasiewicz 2012a).
gumentation as its reasoning machinery. We show how incoherence can arise in Datalog ± ontologies,
and how the reasoning technique based on the use of defea-
sible elements in Datalog ± and an argumentative semantics
Introduction and Motivation introduced by Martinez et al. (2014) can tolerate such issues,
The problem of inconsistency in ontologies has been widely thus resulting in a reasoning machinery suitable of dealing
acknowledged in both the Semantic Web and Database The- with both incoherent and inconsistent knowledge.
ory communities, and several methods have been developed This work integrates three different building blocks: first,
to deal with it, e.g., (Arenas, Bertossi, and Chomicki 1999; we introduce the notion of incoherence for Datalog ± ontolo-
Lembo et al. 2010; Lukasiewicz, Martinez, and Simari 2012; gies, relating it to the problem of satisfiability of concepts
Black, Hunter, and Pan 2009; Bienvenu 2012; Martinez et al. for Description Logics; second, we show how such notion
2014). The most widely accepted semantics for querying in- affects most of well-known inconsistency-tolerant semantics
consistent databases is that of consistent answers (Arenas, which, since they were not designed to confront such issues,
Bertossi, and Chomicki 1999) (or AR semantics in (Lembo can go up to the point of not returning any useful answer;
et al. 2010) for ontological languages), which yields the set finally, we propose a definition for incoherency-tolerant se-
of atoms that can be derived despite all possible ways of mantics, introducing an alternative semantics based on an
repairing the inconsistency. In this semantics often an as- argumentative reasoning process over the transformation
sumption is made that the set of ontological knowledge Σ of Datalog ± ontologies to their correspondent defeasible
expresses the semantics of the data and as such there is no Datalog ± ontologies. We show how this semantics behaves
internal conflict on the set of constraints, which is not sub- in a satisfactory way in the presence of incoherence, as
ject to changes over time. This means first, that the set of the process can return as answers atoms that trigger inco-
constraints is always satisfiable, in the sense that their ap- herency, which we show that cannot be done by classical
plication do not inevitably yield a consistency problem; sec- inconsistency-tolerant semantics.
ond, as a result of the previous observation, it must be the
case that the conflicts come from the data contained in the Preliminaries
database instance and that is the part of the ontology that
First, we briefly recall some basics on Datalog ± (Calı̀, Got-
must be modified in order to restore consistency.
tlob, and Lukasiewicz 2012a). We assume (i) an infinite uni-
Copyright c 2015, for this paper by its authors. Copying permitted verse of (data) constants ∆ (which constitute the “normal”
for private and academic purposes. domain of a database), (ii) an infinite set of (labeled) nulls
∆N (used as “fresh” Skolem terms, which are placeholders form ∀XΦ(X) → ⊥, where the body X is a conjunction of
for unknown values, and can thus be seen as variables), and atoms (without nulls) and the head is the truth constant false,
(iii) an infinite set of variables V (used in queries, dependen- denoted ⊥. Intuitively, the head of these constraints have to
cies, and constraints). Different constants represent different evaluate to false in D under a set of TGDs ΣT . That is, an
values (unique name assumption), while different nulls may NC τ is satisfied by a database D under a set of TGDs ΣT
represent the same value. We assume a lexicographic order iff there not exists a homomorphism h that maps the atoms
on ∆∪∆N , with every symbol in ∆N following all symbols of Φ(X) to D, where D is such that every TGD in ΣT is sat-
in ∆. We denote by X sequences of variables X1 , . . . , Xk isfied. As we will see through the paper, negative constraints
with k ≥ 0. We assume a relational schema R, which is a fi- are important to identify inconsistencies in a Datalog ± on-
nite set of predicate symbols (or simply predicates). A term t tology, as their violation is one of the main inconsistency
is a constant, null, or variable. An atomic formula (or atom) sources. In this work we restrict our attention to binary neg-
a has the form P (t1 , ..., tn ), where P is an n-ary predicate, ative constraints (or denial constraints), which are NCs such
and t1 , ..., tn are terms. A database (instance) D for a re- that their body is the conjunction of exactly two atoms, e.g.,
lational schema R is a (possibly infinite) set of atoms with p(X, Y ) ∧ q(X, Z) → ⊥. As we will show later, this class
predicates from R and arguments from ∆. of constraints suffices for the formalization of the concept of
Given a relational schema R, a tuple-gener- conflicting atoms.
ating dependency (TGD) σ is a first-order formula
∀X∀Y Φ(X, Y) → ∃Z Ψ(X, Z), where Φ(X, Y) and Equality-generating dependencies (EGDs) are first-order
Ψ(X, Z) are conjunctions of atoms over R (without formulas of the form ∀XΦ(X) → Xi = Xj , where Φ(X) is
nulls), called the body and the head of σ, respectively. a conjunction of atoms, and Xi and Xj are variables from X.
Satisfaction of TGDs are defined via homomorphisms, An EGD σ is satisfied in a database D for R iff, whenever
which are mappings µ : ∆ ∪ ∆N ∪ V → ∆ ∪ ∆N ∪ V there exists a homomorphism h such that h(Φ(X)) ⊆ D, it
such that (i) c ∈ ∆ implies µ(c) = c, (ii) c ∈ ∆N holds that h(Xi ) = h(Xj ). In this work we will focus on
implies µ(c) ∈ ∆ ∪ ∆N , and (iii) µ is naturally extended to a particular class of EGDs, called separable (Calı̀, Gottlob,
atoms, sets of atoms, and conjunctions of atoms. Consider a and Lukasiewicz 2012a); intuitively, separability of EGDs
database D for a relational schema R, and a TGD σ on R of w.r.t. a set of TGDs states that, if an EGD is violated, then
the form Υ(X, Y) → ∃Z Ψ(X, Z). Then, σ is applicable atoms contained in D are the reason of the violation (and not
to D if there exists a homomorphism h that maps the atoms the application of TGDs); i.e., if an EGD in ΣE is violated
of Υ(X, Y) to atoms of D. Let σ be applicable to D, and when we apply the TGDs in ΣT for a database D, then the
h0 be a homomorphism that extends h as follows: for each EGD is also violated in D. Separability is an standard as-
Xi ∈ X, h0 (Xi ) = h(Xi ); for each Zj ∈ Z, h0 (Zj ) = zj , sumption in Datalog ± ontology, as one of the most impor-
where zj is a “fresh” null, i.e., zj ∈ ∆N , zj does not tant features of this family of languages is the focus on de-
occur in D, and zj lexicographically follows all other nulls cidable (Calı̀, Lembo, and Rosati 2003) (actually tractable)
already introduced. The application of σ on D adds to D fragments of Datalog ± . EGDs play also an important role
the atom h0 (Ψ(X, Z)) if it is not already in D. After the in the matter of conflicts in Datalog ± ontologies. Note that
application we say that σ is satisfied by D. The Chase for a the restriction of using only separable EGDs makes that cer-
database D and a set of TGDs ΣT , denoted chase(D, ΣT ), tain cases of conflicts are not considered in our proposal; the
is the exhaustive application of the TGDs (Calı̀, Gottlob, treatment of such cases, though interesting from a technical
and Lukasiewicz 2012b) in a breadth-first (level-saturating) point of view, are outside the scope of this work since we
fashion, which leads to a (possibly infinite) chase for D focus on tractable fragments of Datalog ± as the ones men-
and Σ. Since TGDs can be reduced to TGDs with only tioned above. Moreover, as for the case with NCs, we restrict
single atoms in their heads, in the sequel, every TGD has EGDs to binary ones; that is, those which body ∀XΦ(X) is
without loss of generalization a single atom in its head. such that Φ(X) is the conjunction of exactly two atoms, e.g.,
A conjunctive query (CQ) over R has the form p(X, Y ) ∧ q(X, Z) → Y = Z.
Q(X) = ∃Y Φ(X, Y), where Φ(X, Y) is a conjunction of
atoms (possibly equalities, but not inequalities) with the We usually omit the universal quantifiers in TGDs, NCs
variables X and Y, and possibly constants, but without and EGDs, and we implicitly assume that all sets of depen-
nulls. In this work we restrict our attention to atomic queries. dencies and/or constraints are finite.
A Boolean CQ (BCQ) over R is a CQ of the form Q(),
often written as the set of all its atoms, without quanti-
fiers. The set of answers for a CQ Q to D and Σ, denoted
ans(Q, D, Σ), is the set of all tuples a such that a ∈ Q(B) Datalog ± Ontologies. A Datalog ± ontology KB = (D, Σ),
for all B ∈ mods(D, Σ). The answer for a BCQ Q to D and where Σ = ΣT ∪ΣE ∪ΣNC , consists of a database D, a set of
Σ is Yes, denoted D ∪ Σ |= Q, iff ans(Q, D, Σ) 6= ∅. It is im- TGDs ΣT , a set of separable EGDs ΣE , and a set of negative
portant to remark that BCQs Q over D and ΣT can be evalu- constraints ΣNC . Example 1 illustrates a simple Datalog ±
ated on the chase for D and ΣT , i.e., D ∪ ΣT |= Q is equiva- ontology.
lent to chase(D, ΣT ) |= Q (Calı̀, Gottlob, and Lukasiewicz
2012b).
Negative constraints (NCs) are first-order formulas of the
Example 1 Consider the following KB. Qi and Hunter 2007). Incoherence can be particularly im-
portant when combining multiple ontologies since the con-
D: {a1 : can sing(simone)
straints imposed by each one of them over the data could
a 2 : rock singer (axl ),
a3 : sing loud (ronnie),
(possibly) represent conflicting modellings of the applica-
a4 : has fans(ronnie),
tion at hand. Clearly, the notions of incoherence and in-
a5 : manage(band 1 , richard )}
consistency are highly related; in fact, Flouris et al. (2006)
establish a relation between incoherence and inconsistency,
ΣNC :
{τ1 : sore throat(X) ∧ can sing(X) → ⊥,
considering the former as a particular form of the latter.
τ2 : unknown(X) ∧ famous(X) → ⊥} Our proposed notion of incoherence states that given a
set of incoherent constraints Σ it is not possible to find
Σ : {ν : manage(X, Y ) ∧ manage(X, Z) → Y = Z}
a set of atoms D such that KB = (D, Σ) is a consis-
1
E
tent ontology and at the same time all TGDs in ΣT ⊆ Σ
Σ T : {σ 1 : rock singer (X) → sing loud (X),
are applicable in D. This means that a Datalog ± ontol-
σ2 : sing loud (X) → sore throat(X),
ogy KB can be consistent even if the set of constraints
σ : has fans(X) → famous(X),
3
is incoherent, as long as the database instance does not
σ4 : rock singer (X) → can sing(X)}
make those dependencies applicable. On the other hand, a
Datalog ± ontology KB can be inconsistent even when the
Following the classical notion of consistency, we say that set of constraints is coherent. Consider, as an example, the
a consistent Datalog ± ontology has a non-empty set of mod- following KB = ({tall(peter), small(peter)}, {tall(X) ∧
els. small(X) → ⊥}), where the (empty) set of dependencies is
trivially coherent; the ontology is, nevertheless, inconsistent.
Consistency. A Datalog ± ontology KB = (D, Σ) is consis-
In the last decades, several approaches to handling in-
tent iff mods(D, Σ) 6= ∅. We say that KB is inconsistent
consistency were developed in Artificial Intelligence and
otherwise.
Database Theory (e.g., (Konieczny and Pérez 2002; Del-
grande and Jin 2012; Arenas, Bertossi, and Chomicki
Incoherence in Datalog ± 1999)). Some of the best known approaches deal with incon-
The problem of obtaining consistent knowledge from an in- sistency by removing from the theory atoms, or a combina-
consistent knowledge base is natural in many computer sci- tion of atoms and constraints or rules. A different approach
ence fields. As knowledge evolves, contradictions are likely is to simultaneously consider all possible ways of repairing
to appear, and these inconsistencies have to be handled in a the ontology by deleting or adding atoms, as in most ap-
way such that they do not affect the quality of the informa- proaches to Consistent Query Answering (Arenas, Bertossi,
tion obtained from the knowledge base. and Chomicki 1999) (CQA for short). However, these data-
In the setting of Consistent Query Answering (CQA), driven approaches might not be adequate for an incoherent
database repairing, and inconsistency-tolerant query an- theory and may produce meaningless results. As we stated
swering in ontological languages (Arenas, Bertossi, and before, an incoherent set Σ renders inconsistent any ontol-
Chomicki 1999; Lembo et al. 2010; Lukasiewicz, Martinez, ogy whose database instance is such that the TGDs are ap-
and Simari 2012), often the assumption is made that the set plicable; in particular cases this may lead to the removal of
of constraints Σ expresses the semantics of the data in the every single atom in a database instance in an attempt to re-
component D, and as such there is no internal conflict on store consistency, resulting in an ontology without any valu-
the set of constraints and these constraints are not subject able information, when it could be the case that it is the set
to changes over time. We argue that it is also important to of constraints that is ill defined.
identify and separate the sources of conflicts in Datalog ± Before formalizing the notion of incoherence that we use
ontologies. In the previous section we defined inconsistency in our Datalog ± setting we need to identify the set of atoms
of a Datalog ± ontology based on the lack of models. From relevant to a given set of TGDs. Intuitively, we say that a set
an operational point of view, conflicts appear in a Datalog ± of atoms A is relevant to a set T of TGDs if the atoms in the
ontology whenever a NC or an EGD is violated, that is, set A are such that the application of T over A generates the
whenever the body of one such constraint can be mapped atoms that are needed to apply all dependencies in T , i.e.,
to either atoms in D or atoms that can be obtained from D A triggers the application of every TGD in T . Formally, the
by the application of the TGDs in ΣT ⊆ Σ. Besides these definition of atom relevancy is as follows:
conflicts, we will also focus on the relationship between the
Definition 1 (Relevant Set of Atoms for a Set of TGDs)
set of TGDs and the set of NCs and EGDs, as it could hap-
Let R be a relational schema, T be a set of TGDs, and A a
pen that (a subset of) the TGDs in ΣT cannot be applied
(possibly existentially closed) non-empty set of atoms, both
without always leading to the violation of the NCs or EGDs.
over R. We say that A is relevant to T iff for all σ ∈ T
Note that in this case clearly the data in the database instance
of the form ∀X∀YΦ(X, Y) → ∃ZΨ(X, Z) it holds that
is not the problem, as any database in which these TGDs
chase(A, T ) |= ∃X∃YΦ(X, Y).
are applicable will inevitable produce an inconsistent ontol-
ogy. This issue is related to that of unsatisfiability problem When it is clear from the context, if a singleton set A =
of a concept in an ontology and it is known in the Descrip- {a} is relevant to T ⊆ ΣT we just say that atom a is relevant
tion Logics community as incoherence (Flouris et al. 2006; to T . The following example illustrates atom relevancy.
Example 2 (Relevant Set of Atoms) Consider the follow- risky job(P ),
ing constraints: σ2 : in therapy(P ) → unstable(P )}
ΣT = {σ1 : supervises(X, Y ) → supervisor(X),
The set Σ1T is a satisfiable set of TGDs, and even though the
σ2 : supervisor(X) ∧ take decisions(X) →
simultaneous application of σ1 and σ2 may violate some
leads department(X, D),
formula in Σ1NC ∪ Σ1E , that does not hold for every relevant
σ3 : employee(X) → works in(X, D)}
set of atoms. Consider as an example the relevant set D1 =
First, let us consider the set A1 = {dangerous work(police), works in(police, marty),
{supervises(walter, jesse), take decisions(walter), in therapy(rust)}; D1 is a relevant set for Σ1T , however,
employee(jesse)}. This set is a relevant set of atoms as we have that mods(D1 , Σ1T ∪ Σ1NC ∪ Σ1E ) 6= ∅ then Σ1T is
to the set of constraints ΣT = {σ1 , σ2 , σ3 }, since σ1 satisfiable.
and σ3 are directly applicable to A1 and σ2 becomes On the other hand, as an example of unsatisfiability con-
applicable when we apply σ1 (i.e., the chase entails sider the following constraints:
the atom supervisor(walter), which together with
take decisions(walter) triggers σ2 ). Σ2NC = {τ1 : sore throat(X) ∧ can sing(X) → ⊥}
However, the set A2 = {supervises(walter, jesse),
take decisions(gus)} is not relevant to ΣT . Note that even Σ2T = {σ1 : rock singer (X) → sing loud (X),
though σ1 is applicable to A2 , the TGDs σ2 and σ3 are σ2 : sing loud (X) → sore throat(X),
never applied in chase(A2 , ΣT ), since the atoms in their σ3 : rock singer (X) → can sing(X)}
bodies are never generated in chase(A2 , ΣT ). For instance, The set Σ2T is an unsatisfiable set of dependencies, as the
consider the TGD σ2 ∈ ΣT . In the chase of ΣT over D application of TGDs {σ1 , σ2 , σ3 } on any relevant set of
we create the atom supervisor(walter), but nevertheless atoms will cause the violation of τ1 . For instance, consider
we still cannot trigger σ2 since we do not have and cannot the relevant atom rock singer (axl): we have that the ap-
generate the atom take decisions(walter), and the atom plication of Σ2T over {rock singer (axl)} causes the vio-
take decisions(gus) that is already in A2 does not match lation of τ1 when considered together with Σ2T , therefore
the constant value. mods({rock singer (axl)}, Σ2T ∪ Σ2NC ∪ Σ2E ) = ∅. Note that
We now present the notion of coherence for Datalog ± , any set of relevant atoms will cause the violation of τ1 .
which adapts the one introduced by Flouris et al. for We are now ready to formally define coherence for a
DLs (Flouris et al. 2006). Our conception of (in)coherence Datalog ± ontology. Intuitively, an ontology is coherent if
is based on the notion of satisfiability of a set of TGDs w.r.t. there is no subset of their TGDs that is unsatisfiable w.r.t.
a set of constraints. Intuitively, a set of dependencies is sat- the constraints in the ontology.
isfiable when there is a relevant set of atoms that triggers the
application of all dependencies in the set and does not pro- Definition 3 (Coherence) Let KB = (D, Σ) be a Datalog ±
duce the violation of any constraint in ΣNC ∪ ΣE , i.e., the ontology defined over a relational schema R, and Σ = ΣT ∪
TGDs can be satisfied along with the NCs and EGDs in KB. ΣE ∪ ΣNC , where ΣT is a set of TGDs, ΣE a set of separable
EGDs and ΣNC a set of negative constraints. KB is coherent
Definition 2 (Satisfiability of a set of TGDs w.r.t. a set of
iff ΣT is satisfiable w.r.t. ΣNC ∪ ΣE . Also, KB is said to be
constraints) Let R be a relational schema, T ⊆ ΣT be a set
incoherent iff it is not coherent.
of TGDs, and N ⊆ ΣNC ∪ ΣE , both over R. The set T is
satisfiable w.r.t. N iff there is a set A of (possibly existen- Example 4 (Coherence) Consider the sets of dependencies
tially closed) atoms over R such that A is relevant to T and and constraints defined in Example 3 and an arbitrary
mods(A, T ∪ N ) 6= ∅. We say that T is unsatisfiable w.r.t. database instance D. Clearly, the Datalog ± ontology
N iff T is not satisfiable w.r.t. N . Furthermore, ΣT is satis- KB1 = (D, Σ1T ∪ Σ1NC ∪ Σ1E ) is coherent, while KB2 =
fiable w.r.t. ΣNC ∪ ΣE iff there is no T ⊆ ΣT such that T is (D, Σ2T ∪ Σ2NC ∪ Σ2E ) is incoherent.
unsatisfiable w.r.t. some N with N ⊆ ΣNC ∪ ΣE .
Finally, we look deeper into the relation between incoher-
In the rest of the paper sometimes we write that a set of ence and inconsistency. Looking into Definitions 2 and 3 we
TGDs is (un)satisfiable omitting the set of constraints, we can infer that an incoherent KB will induce an inconsistent
do this in the context of a particular ontology where we have KB when the database instance contains any set of atoms
a fixed set of constraints ΣNC ∪ ΣE . Also, through the paper that is relevant to the unsatisfiable sets of TGDs. This result
we denote by U(KB) the set of minimal unsatiasfiable sets is captured in the following proposition.
of TGDs in ΣT for KB (i.e., unsatisfiable set of TGDs such
that every proper subset of it is satisfiable). The following Proposition 1 Let KB = (D, Σ) be a Datalog ± ontology
example illustrates the concept of satisfiability of a set of where Σ = ΣT ∪ ΣE ∪ ΣNC . If KB is incoherent and there
TGDs in a Datalog ± ontology exists A ⊆ D such that A is relevant to some unsatisfiable
set U ∈ U(KB) then KB = (D, Σ) is inconsistent.
Example 3 (Unsatisfiable sets of dependencies) Consider the
following sets of constraints. Example 5 (Relating Incoherence and Inconsistency) As an
instance of the relationship expressed in Proposition 1,
Σ1NC = {τ : risky job(P ) ∧ unstable(P ) → ⊥} consider once again the ontology presented in Example
Σ1T = {σ1 : dangerous work (W ) ∧ works in(W, P ) → 1. As hinted previously in Example 3, there we have the
set A ⊂ D = {rock singer (axl)} and the unsatisfiable to set of atoms straightforwardly, i.e., for a set of atoms A
set of TGDs U ⊂ ΣT = {σ1 : rock singer (X) → it holds that KB |=AR A iff for every a ∈ A it holds that
sing loud (X), σ2 : sing loud (X) → sore throat(X), σ4 : KB |=AR a, and KB 2AR A otherwise.
rock singer (X) → can sing(X)}. Since A is relevant to CAR Semantics. As noted by Lembo et al. (2010), the AR
U the conditions in Proposition 1 are fulfilled, and indeed semantics is not independent from the form of the knowl-
the ontology KB = (D, Σ) from Example 1 is inconsistent edge base; it is easy to show that given two inconsistent
since τ1 ∈ ΣT is violated. knowledge bases that are logically equivalent, contrary to
what one would expect, their respective repairs do not coin-
Incoherence influence on classic cide. To address this, another definition of repairs was also
inconsistency-tolerant semantics proposed by Lembo et al. (2010) that includes knowledge
We have established the relation between incoherence and that comes from the closure of the database instance with
inconsistency. As explained, classic inconsistency-tolerant respect to the set of TGDs. Since the closure of an incon-
techniques do not account for coherence issues since they sistent ontology yields the whole language, they define the
assume that such kind of problems will not appear. Never- consistent closure of an ontology KB = (D, ΣT ∪ΣE ∪ΣNC )
theless, if we consider that both components in the ontol- as the set CCL(KB) = {α | α ∈ H(LR ) s.t. ∃S ⊆
ogy evolve (perhaps being collaboratively maintained by a D and mods(S, ΣT ∪ ΣE ∪ ΣNC ) 6= ∅ and (S, ΣT ) |= α}. A
pool of users) then certainly incoherence is prone to arise. Closed ABox repair of a Datalog ± ontology KB is a consis-
In the following we show that it may be important for tent subset D0 of CCL(KB) such that it maximally preserves
inconsistency-tolerant techniques to consider incoherence in the database instance (Lembo et al. 2010). It is said that an
ontologies as well, since if not treated appropriately an in- atom a is CAR-consistently entailed from a Datalog ± on-
coherent set of TGDs may lead to the trivial solution of re- tology KB, denoted by KB |=CAR a iff a is classically en-
moving every single relevant atom in D (which in the worst tailed from every ontology built from each possible closed
case could be the entire database instance). This may be ad- ABox repair. We extend entailment to set of atoms straight-
equate for some particular domains, but does not seem to be forwardly, i.e., for a set of atoms A it holds that KB |=CAR A
a desirable outcome in the general case. iff for every a ∈ A it holds that KB |=CAR a, and KB 2CAR
Although classical query answering in Datalog ± is not A otherwise.
tolerant to inconsistency issues, a variety of inconsistency- Incoherence has great influence when calculating repairs,
tolerant semantics have been developed in the last decade as can be seen in the following result: independently of the
for ontological languages, including lightweight Descrip- semantics (i.e., AR or CAR) no atom that is relevant to an
tion Logics (DLs), such as EL and DL-Lite (Lembo et al. unsatisfiable set of TGDs belongs to a repair of an incoher-
2010; Bienvenu and Rosati 2013), and several fragments ent KB.
of Datalog ± (Lukasiewicz, Martinez, and Simari 2012). In
this section we analyze how incoherence influence in several Lemma 1 Let KB = (D, Σ) be an incoherent Datalog ±
inconsistency-tolerant semantics for ontological languages: ontology where Σ = ΣT ∪ ΣE ∪ ΣNC and R(KB) be the
AR semantics (Lembo et al. 2010), CAR semantics (Lembo set of (A-Box or Closed A-Box) repairs of KB. If A ⊆ D is
et al. 2010), adn provide some insights for sound approxi- relevant to some unsatisfiable set U ∈ U(KB) then A * R
mations of AR and of CAR. We present the basic concepts for every R ∈ R(KB).
needed to understand the different semantics for query an- The proof of Lemma 1 follows from Proposition 1, since
swering on Datalog ± ontologies and then show how entail- any set of atoms relevant to an unsatisfiable set of TGDs will
ment under such semantics behaves in the presence of in- be conflictive with ΣNC ∪ ΣE , thus not qualifying to be part
coherence. The notion of repair in relational databases is a of a proper repair.
model of the set of integrity constraints that is maximally
Example 6 Consider the atom rock singer (axl) from the
close, i.e., “as close as possible” to the original database.
Depending on how repairs are obtained we can have ontology presented in Example 1. As we have explained in
different semantics. In the following we recall AR- Example 5, such atom is relevant to U ⊂ ΣT = {σ1 :
semantics (Lembo et al. 2010), one of the most widely ac- rock singer (X) → sing loud (X), σ2 : sing loud (X) →
cepted inconsistency-tolerant semantics, along with an alter- sore throat(X), σ4 : rock singer (X) → can sing(X)}.
native to AR called CAR-semantics. It is easy to show that as a result of this the atom does
not belong to any A-Box or Closed A-Box repair. Con-
AR Semantics. The AR semantics corresponds to the no- sider the case of A-Box repairs. We have that they are max-
tion of consistent answers in relational databases (Arenas, imally consistent subsets of the component D. We have
Bertossi, and Chomicki 1999). Intuitively, an atom a is said that mods(rock singer (axl), Σ) = ∅, as the NC τ1 :
to be AR-consistently entailed from a Datalog ± ontology sore throat(X) ∧ can sing(X) → ⊥ is violated. More-
KB, denoted KB |=AR a iff a is classically entailed from over, clearly this violation happens for every set A ⊆ D
every ontology that can be built from every possible A-box such that rock singer (axl) ∈ A, and thus we have that
repair (a maximally consistent subset of the D component mods(A, Σ) = ∅, i.e., rock singer (axl) cannot be part of
that after its application to ΣT respects every constraint in any A-Box repair for the KB.
ΣE ∪ ΣNC ). We denote by KB 2AR a the fact that a cannot In an analogous way we can show that for any
be AR-consistently inferred from KB. We extend entailment D0 ⊆ D such that mods(D0 , Σ) 6= ∅ it holds that
(D0 , ΣT ) 6|= rock singer (axl), and thus it holds that incoherence (or incoherency-tolerant) iff there exists A ⊆ D
rock singer (axl) ∈/ CCL(KB). Then, since Closed A-Box and U ∈ U(KB) such that A is relevant to U and it holds
repairs are subsets of CCL(KB) it cannot happen that that KB |=S A.
rock singer (axl) belongs to any of these repairs. Intuitively, a query answering semantics is tolerant to in-
Then, from Lemma 1 follows that every atom that is coherence if it can entail atoms that trigger incoherent sets
relevant to an unsatisfiable set of TGDs cannot be AR- of TGDs as answers. Clearly, from Proposition 2 it follows
consistently (resp, CAR-consistently) entailed. that inconsistency-tolerant semantics based on repairs are
Proposition 2 Let KB = (D, Σ) be an incoherent not tolerant to incoherence.
Datalog ± ontology where Σ = ΣT ∪ ΣE ∪ ΣNC . If A ⊆ D is Observation 1 AR and CAR semantics are not
relevant to some unsatisfiable set U ⊆ ΣT then KB 2AR A incoherency-tolerant semantics.
and KB 2CAR A.
The proof follows from Lemma 1: since a relevant set of
An Incoherency-tolerant Semantics via
atoms does not belong to any repair then it cannot be part of Argumentative Inference
the answers of the AR and CAR semantics. As a corollary, We begin by recalling Defeasible Datalog ± (for the inter-
in the limit case that every atom in the database instance ested reader, a more complete presentation of the framework
is relevant to some unsatisfiable subset of the TGDs in the can be found in (Martinez et al. 2014)), and then we move
ontology then the set of AR-answers (resp, CAR-answers) on to show the behaviour of this semantics in the presence
is empty. of incoherence.
Defeasible Datalog ± (Martinez et al. 2014) is a varia-
Corollary 1 Let KB = (D, Σ) be an incoherent Datalog ± tion of Datalog ± that enables argumentative reasoning in
ontology where Σ = ΣT ∪ ΣE ∪ ΣNC , and let AAR Datalog ± by means of transforming the information en-
and ACAR be the set of atoms AR-consistently and CAR- coded in a KB to represent statements whose acceptance can
consistenly entailed from KB, respectively. If for every a ∈ be challenged. To do this, a Datalog ± ontology is extended
D there exists A ⊆ D such that a ∈ A and A is a minimal with a set of em defeasible atoms and defeasible TGDs; thus,
set of TGDs relevant to some U ∈ U(KB) then AAR = ∅ a Defeasible Datalog ± ontology contains both (classical)
and ACAR = ∅. strict knowledge and defeasible knowldge. The set of defea-
Since they follow from Proposition 1, both Proposition 2 sible TGDs allows to express weaker connections between
and Corollary 1 can be straightforwardly extended to other pieces of information than in a classical TGDs. Defeasible
repair based inconsistency-tolerant semantics such as ICAR TGDs are rules of the form Υ(X, Y) – ∃Z Ψ(X, Z), where
and ICR (Lembo et al. 2010). Υ(X, Y) and Ψ(X, Z) are conjunctions of atoms. As in
Example 7 Consider once again KB in Example 1, and DeLP’s defeasible rules (Garcı́a and Simari 2004), defeasi-
the atom a2 : rock singer(axl) in D. Such atom is ble TGDs are used to represent weaker connections between
relevant to the unsatisfiable set U ⊂ ΣT = {σ1 : the body and the head of a rule. Defeasible TGDs are writ-
rock singer (X) → sing loud (X), σ2 : sing loud (X) → ten using the symbol “ – ”, while the classical (right) arrow
sore throat(X), σ4 : rock singer (X) → can sing(X)}, “→” is reserved to strict TGDs and NCs.
and indeed it holds that KB 2AR rock singer(axl) and Defeasible Datalog ± Ontologies. A defeasible Datalog ±
KB 2CAR rock singer(axl). As explained in Example 6, ontology KB consists of a finite set F of ground atoms,
this is because rock singer(axl) cannot belong to any re- called facts, a finite set D of defeasible atoms, a finite set
pair since its consistent application to Σ is not feasible, i.e., of TGDs ΣT , a finite set of defeasible TGDs ΣD , and a fi-
mods((rock singer(axl), Σ)) = ∅. nite set of binary constraints ΣE ∪ ΣNC .
The following example shows a defeasible Datalog ± on-
Incoherency-tolerant semantics tology that encodes the knowledge from Example 1 chang-
We have shown how incoherence affects classic ing some of the facts and TGDs to defeasible ones.
inconsistency-tolerant semantics up to the point of not Example 8 The information from the ontology
returning any meaningful answer (since they were not presented in Example 1 can be better repre-
develop to consider such kind of issues). In this section we sented by the following defeasible Datalog ± on-
propose the notion of tolerance to incoherence for query tology KB = (F, D, Σ0T , ΣD ,ΣNC ), where F =
answering semantics. Such semantics will allow to be able {can sing(simone), rock singer (axl ), sing loud (ronnie),
to obtain useful answers from incoherent ontologies. We has fans(ronnie)} and D = {manage(band1 , richard )}.
continue this section by showing an alternative semantics Note that we have changed the fact stating that richard
for Datalog ± based on the use of argumentative inference manages band1 to a defeasible one, since reports indicates
that is tolerant to incoherence. For the elements of argu- that the members of band1 are looking for a new manager.
mentation we refer the reader to (Besnard and Hunter 2008; The sets of TGDs, and defeasible TGDs are now given
Rahwan and Simari 2009). by the following sets; note that we have changed some
Definition 4 (Incoherence-tolerant semantics) Let KB = of the TGDs into defeasible TGDs to make clear that the
(D, Σ) be a Datalog ± ontology where Σ = ΣT ∪ ΣE ∪ connection between the head and body is weaker.
ΣNC . A query answering semantics S is said to be tolerant to
ΣT 0 = {sing loud (X) → sore throat(X), Example 9 From the defeasible Datalog ± ontology in
rock singer (X) → can sing(X) Example 8, we can get the following (minimal) annotated
ΣD = {rock singer (X) – sing loud (X), derivation for atom sore throat(axl):
has fans(X) – famous(X)}
Derivations from a defeasible Datalog ± ontology rely in
∂ = rock singer (axl ),
the application of (strict or defeasible) TGDs. Given a de- rock singer (X) – sing loud (X),
feasible Datalog ± ontology KB = (F, D, ΣT , ΣD , ΣN C ), sing loud (axl ),
a (strict or defeasible) TGD σ is applicable if there exist a sing loud (X) → sore throat(X),
homomorphism mapping the atoms in the body of σ into sore throat(axl )
F ∪ D. The application of σ on KB generates a new atom
from the head of σ if it is not already in F ∪ D, in the same Then, we have that KB ` rock singer (axl ) and that
way as explained in the preliminaries of this work. KB ∼sore throat(axl).
The following definitions follow similar ones first intro- Classical query answering in defeasible Datalog ± ontolo-
duced by Martinez et al. (2012). Here we adapt the notions gies is equivalent to query answering in Datalog ± ontolo-
to defeasible Datalog ± ontologies. An atom has a deriva- gies.
tion from a KB iff there is a finite sequence of applications
of (strict or defeasible) TGDs that has the atom as its last Proposition 3 ( (Martinez et al. 2014)) Let L be a ground
component. atom, KB = (F, D, ΣT , ΣD , ΣNC ) be a defeasible Datalog ±
ontology, KB0 = (F ∪ D, Σ0T ∪ ΣNC ) is a classical
Definition 5 Let KB = (F, D, ΣT , ΣD , ΣNC ) be a defea-
Datalog ± ontology where Σ0T = ΣT ∪ {Υ(X, Y) →
sible Datalog ± ontology and L an atom. An annotated
∃Z Ψ(X, Z) | Υ(X, Y) – ∃Z Ψ(X, Z)}. Then, KB0 |= L iff
derivation ∂ of L from KB consists of a finite sequence
KB ` L or KB ∼L.
[R1 , R2 , . . . , Rn ] such that Rn is L, and each atom Ri is
either: (i) Ri is a fact or defeasible atom, i.e., Ri ∈ F ∪ D, Proposition 3 states the equivalence between derivations
or (ii) there exists a TGD σ ∈ ΣT ∪ ΣD and a homomor- from defeasible Datalog ± ontologies and entailment in tra-
phism h such that h(head(σ)) = Ri and σ is applicable to ditional Datalog ± ontologies whose database instance cor-
the set of all atoms and defeasible atoms that appear before responds to the union of facts and defeasible atoms, and the
Ri in the sequence. When no defeasible atoms and no defea- set of TGDs corresponds to the union of the TGDs and the
sible TGDs are used in a derivation, we say the derivation is strict version of the defeasible TGDs. As a direct conse-
a strict derivation, otherwise it is a defeasible derivation. quence, all the existing work done for Datalog ± directly ap-
Note that there is non-determinism in the order in which the plies to defeasible Datalog ± . In particular, it is easy to spec-
elements in a derivation appear; TGDs (strict and defeasi- ify a defeasible Chase procedure over defeasible Datalog ±
ble) can be reordered, and facts and defeasible atoms could ontologies, based on the revised notion of application of (de-
be added at any point in the sequence before they are needed feasible) TGDs, whose result is a universal model. There-
to satisfy the body of a TGD. These syntactically distinct fore, a (B)CQ Q over a defeasible Datalog ± ontology can
derivations are, however, equivalent for our purposes. It is be evaluated by verifying that Q is a classical consequence
possible to introduce a canonical form for representing them of the chase obtained from the defeasible Datalog ± ontol-
and adopt that canonical form as the representative of all ogy.
of them. For instance, we might endow the elements of the Argumentation-based Reasoning in Defeasible Datalog ±
program from which the derivation is produced with a to- Conflicts in defeasible Datalog ± ontologies come, as in
tal order; thus, it is possible to select one derivation from classical Datalog ± , from the violation of NCs or EGDs. In-
the set of all the derivations of a given literal that involve tuitively, two atoms are in conflict relative to a defeasible
the same elements by lexicographically ordering these se- Datalog ± ontology whenever they are both derived from the
quences. When no confusion is possible, we assume that a ontology (either strictly or defeasible) and together map to
unique selection has been made. the body of a negative constraint or they violate an equality-
We say that an atom a is strictly derived from KB iff generating dependency.
there exists a strict derivation for a from KB, denoted with
KB ` a, and a is defeasibly derived from KB iff there exists Definition 6 Given a set of NCs ΣNC and a set of non-
a defeasible derivation for a from KB and no strict derivation conflicting EGDs ΣE , two ground atoms (possibly with
exists, denoted with KB ∼ a. . A derivation ∂ for a is minimal nulls) a and b are said to be in conflict relative to ΣE ∪ ΣNC
if no proper sub-derivation ∂ 0 of ∂ (every member of ∂ 0 is a iff there exists an homomorphism h such that h(body(υ)) =
member of ∂) is also an annotated derivation of a. Consid- a ∧ b for some υ ∈ ΣNC or h(Xi ) 6= h(Yj ) for some ν ∈ ΣE
ering minimal derivations in a defeasible derivation avoids where h(Xi ) is a term in a and h(Yj ) is a term in b.
the insertion of unnecessary elements that will weaken its In what follows, we say that a set of atoms is a conflicting set
ability to support the conclusion by possibly introducing un- of atoms relative to ΣE ∪ΣNC if and only if there exist at least
necessary points of conflict. Given a derivation ∂ for a, there two atoms in the set that are in conflict relative to ΣE ∪ ΣNC ,
exists at least one minimal sub-derivation ∂ 0 ⊆ ∂ for an atom otherwise will be called non-conflicting. Whenever is clear
a. Thus, through the paper we only consider minimal deriva- from the context we omit the set of NCs and EGDs.
tions (Martinez et al. 2014).
Example 10 Consider the NC {sore throat(X) ∧ As {sore throat(axl ), can sing(axl )} is conflicting rel-
can sing(X) → ⊥} in ΣNC from the defeasible on- ative to ΣNC , we have that hA, sore throat(axl )i and
tology in Example 8. In this case, the set of atoms hB, can sing(axl )i attack each other.
{sore throat(axl ), can sing(axl )} is a conflicting set
relative to ΣNC . However, this is not the case for the set
S = {rock singer (axl )}: even when such set generates
a violation when applied to the set of TGDs, it is not
conflicting in itself.
Whenever defeasible derivations of conflicting atoms ex-
ist, we use a dialectical process to decide which informa-
tion prevails, i.e., which piece of information is such that no
acceptable reasons can be put forward against it. Reasons
are supported by arguments; an argument is an structure that
supports a claim from evidence through the use of a rea-
soning mechanism. We maintain the intuition that led to the
classic definition of arguments by Simari and Loui (1992),
as shown in the following definition.
Definition 7 Let KB be a defeasible Datalog ± ontology and
L a ground atom. A set A of facts, defeasible atoms, TGDs, Figure 2: Attack between arguments.
and defeasible TGDs used in an annotated derivation ∂ of
L is an argument for L constructed from KB iff ∂ is a ⊆- Once the attack relation is established between argu-
minimal derivation and no conflicting atoms can be defeasi- ments, it is necessary to analyze whether the attack is strong
ble derived from A ∪ ΣT . An argument A for L is denoted enough so one of the arguments can defeat the other. Given
hA, Li, and AKB will be the set of all arguments that can be an argument A and a counter-argument B, a comparison
built from KB. criterion is used to determine if B is preferred to A and,
Example 11 Consider the derivation ∂ in Example 9. We therefore, defeats A. For our defeasible Datalog ± frame-
have that hsore throat(axl ), ∂i is an argument in AKB . Fig- work, unless otherwise stated, we assume an arbitrary pref-
ure 1 shows the argument. erence criterion among arguments where A B means
that B is preferred to A and thus defeats it. More properly,
given two arguments hA1 , L1 i and hA2 , L2 i we say that
argument hA1 , L1 i is a defeater of hA2 , L2 i iff there ex-
ists a sub-argument hA, Li of hA2 , L2 i such that hA1 , L1 i
counter-argues hA, Li at L, and either hA1 , L1 i hA, Li
(it is a proper defeater) or hA1 , L1 i 6 hA, Li, and hA, Li 6
hA1 , L1 i (it is a blocking defeater).
Finally, the combination of arguments, attacks and com-
parison criteria gives raise to Datalog ± argumentation
frameworks.
Figure 1: An argument for sore throat(axl ).
Definition 8 Given a Defeasible Datalog ± ontology KB de-
fined over a relational schema R, a Datalog ± argumentation
Answers to atomic queries are supported by arguments framework F is a tuple hLR , AKB , i, where specifies a
built from the ontology. However, it is possible to build ar- preference relation defined over AKB .
guments for conflicting atoms, and so arguments can at- To decide whether an argument hA0 , L0 i is undefeated
tack each other. We now adopt the definitions of counter- within a Datalog ± argumentation framework, all its de-
argument and attacks for defeasible Datalog ± ontologies featers must be considered, and there may exist defeaters for
from (Garcı́a and Simari 2004). First, an argument hB, L0 i their counter-arguments as well, giving raise to argumen-
is a sub-argument of hA, Li if B ⊆ A. Argument hA1 , L1 i tation lines. The dialectical process considers all possible
counter-argues, rebuts, or attacks hA2 , L2 i at literal L, iff admissible argumentation lines for an argument, which to-
there exists a sub-argument hA, Li of hA2 , L2 i such that L gether form a dialectical tree. An argument line for hA0 , L0 i
and L1 conflict. is defined as a sequence of arguments that starts at hA0 , L0 i,
Example 12 Consider derivation ∂ from Example 9 and let and every element in the sequence is a defeater of its pre-
A be the set of (defeasible) atoms and (defeasible) TGDs decessor in the line (Garcı́a and Simari 2004). Note that for
used in ∂. A is an argument for sore throat(axl ). Also, defeasible Datalog ± ontologies arguments in an argumenta-
we can obtain a minimal derivation ∂ 0 for can sing(axl ) tion line can contain both facts and defeasible atoms.
where B, the set of (defeasible) atoms and (defea- Different argumentation systems can be defined by set-
sible) TGDs used in ∂ 0 , is such that no conflict- ting a particular criterion for proper attack or defining the
ing atoms can be defeasibly derived from B ∪ ΣT . admissibility of argumentation lines. Here, we adopt the one
from (Garcı́a and Simari 2004), which states that an argu- can sing. Consider the conflict between arguments A and B
mentation line has to be finite, and no argument is a sub- shown in Example 12. As we have stated, we do not define
argument of an argument used earlier in the line; further- any particular criterion to solve attacks. Nevertheless, for
more, when an argument hAi , Li i is used as a blocking de- the sake of example assume now that we are indeed using a
feater for hAi−1 , Li−1 i during the construction of an argu- criterion that is such that B A. Under such supposition
mentation line, only a proper defeater can be used for de- we have the labelled dialectical tree shown in Figure 3.
feating hAi , Li i.
The dialectical process considers all possible admissible
argumentation lines for an argument, which together form a
dialectical tree. Dialectical trees for defeasible Datalog ± on-
tologies are defined following (Garcı́a and Simari 2004), and
we adopt the notion of coherent dialectical tree from (Mar-
tinez, Garcı́a, and Simari 2012), which ensures that the use
of defeasible atoms is coherent in the sense that conflict-
ing defeasible atoms are not used together in supporting (or
attacking) a claim. We denote with Args(T ) the set of argu-
ments in T .
Definition 9 Let hA0 , L0 i be an argument from a Datalog ±
argumentation framework F. A dialectical tree for hA0 , L0 i
from F, denoted T (hA0 , L0 i), is defined as follows:
(1) The root of the tree is labeled with hA0 , L0 i.
(2) Let N be a non-root node of the tree that is labeled
hAn , Ln i, and C = [hA0 , L0 i, hA1 , L1 i, . . . , hAn , Ln i]
be the sequence of labels of the path from the root to Figure 3: A labelled dialectical tree for atom can sing(axl ).
N . Let hB1 , Q1 i, hB2 , Q2 i, . . . , hBk , Qk i be all the de-
featers for hAn , Ln i. For each defeater hBi , Qi i(1 ≤
As can be seen in the dialectical tree, if we assume that
i ≤ k), such that the argumentation line C 0 =
B A then we have reasons to think that Axl cannot sing
[hA0 , L0 i, hA1 , L1 i, hA2 , L2 i, . . . , hAn , Ln i, hBi , Qi i] is
due to its throat being sore.
admissible, the node N has a child Ni labeled hBi , Qi i. If
there is no defeater for hAn , Ln i or there is no hBi , Qi i such In Definition 10 we specify a semantics based on the
that C 0 is admissible, then N is a leaf. use of argumentative inference. From now on we denote
Argument evaluation, i.e., determining whether the root such semantics as D2 (Defeasible Datalog ± ). Such seman-
node of the tree is defeated or undefeated, is done by means tics relies on the transformation of classic Datalog ± ontolo-
of a marking or labelling criterion. Each node in an ar- gies to defeasible ones and then obtaining answers from the
gument tree is labelled as either defeated (D) or unde- transformed one. So, we begin by establishing how a clas-
feated (U ). We denote the dialectical tree built for the ar- sic Datalog ± ontology can be transformed to a defeasible
gument A supporting claim L as T (hA, Li), Args(T ) the one. Intuitively, the transformation of a classic ontology to a
set of arguments in T , and the root of T (hA, Li) with defeasible one involves transforming every atom and every
root(T (hA, Li)). Also, marking(N ), where N is a node in TGD in the classic ontology to its defeasible version.
a dialectical tree, denotes the value of the marking for node Definition 11 (Transformation between ontologies)
N (either U or D). Deciding whether a node is defeated or Let KB = (D, ΣT ∪ ΣE ∪ ΣNC ) be a classic Datalog ±
undefeated depends on whether or not all its children are de- ontology. Then, its transformation to a defeasible Datalog ±
feated: (1) if node N is a leaf then marking(N ) = U , (2) ontology, denoted D(KB), is a defeasible ontology
node N is such that marking(N ) = D iff at least one of its KB0 = (F, D0 , Σ0T , ΣD , ΣE ∪ ΣNC ) where F = ∅, D0 = D,
children that is marked with U , and (3) node N is such that Σ0T = ∅ and ΣD = {Υ(X, Y) – ∃Z Ψ(X, Z) | Υ(X, Y) →
marking(N ) = U iff all its children are marked with D. ∃Z Ψ(X, Z)}.
By means of the marking procedure we can define when
Next, we define the set of answers in D2 for an atomic
an atom is warranted in the argumentation framework.
query. Intuitively, a literal is an answer for a classical
Definition 10 Let KB be a Defeasible Datalog ± on- Datalog ± ontology KB under the D2 semantics iff it is war-
tology and F the corresponding Datalog ± argumenta- ranted in the transformation of KB to a defeasible one.
tion framework where ∈ F is an arbitrary argument
comparison criterion. An atom L is warranted in F Definition 12 (Answers in D2 ) Let KB be a Datalog ± on-
(through T ) iff there exists an argument hA, Li such that tology, KB0 = D(KB) its defeasible transformation, Q a
marking(root(T (hA, Li))) = U . We say that L is entailed query and a comparison criterion. Then, an atom L is
from KB (through F), denoted with KB |=F L, iff it is war- an answer for Q from KB under D2 , denoted KB D2 L, iff
ranted in F. KB0 |=F L where F = hLR , AKB0 , i.
Example 13 Suppose that we have the query Q = Note that the semantics is parametrized by the comparison
can sing(axl), i.e., we want to know whether or not Axl criterion , which helps to solve conflicts when they arise.
Influence of incoherence in Defeasible Datalog ± sources of information. Nevertheless, most of the works in
Now, we focus on the behaviour of Defeasible Datalog ± query answering for Datalog ± ontologies and DLs have fo-
regarding atoms relevant to unsatisfiable sets of TGDs. cused on consistency issues making the assumption that the
It can be shown that the argumentation framework F = set of constraints correctly represents the semantics of the
hLR , AD(KB) , i is such that one relevant atom L to data and therefore any conflict can only come from the data
an unsatisfiable set is warranted (and thus an answer), itself.
provided that the comparison criterion is such that In this work we have introduced the concept of incoher-
marking(root(TF (hA, Li))) = U for some dialectical tree ence for Datalog ± ontologies, relating it to the presence of
TF (hA, Li) built upon F. It is interesting to see that such sets of TGDs such that their application inevitably yield to
comparison criterion can always be found: intuitively, it suf- violations in the set of negative constraints and equality-
fices to arbitrary establish A as the most preferred argument generating dependencies. We have shown how incoherence
in AD(KB) (note however that other criteria can have the ex- affects classic inconsistency-tolerant semantics to the point
act same result). that for some incoherent ontologies these semantics may
produce no useful answer. Finally, we have introduced the
Proposition 4 Let KB be a Datalog ± ontology defined over concept of incoherency-tolerant semantics, and shown a par-
a relational schema R, and KB0 be a Defeasible Datalog ± ticular semantics satisfying that property. Nevertheless, it
ontology such that D(KB) = KB0 . Finally, let L ∈ D and is important to remark that our definition of incoherency-
U ∈ U(KB) such that L is relevant to U . Then, it holds that tolerant semantics is not tied to our particular proposal or
there exists such that KB D2 L. the Datalog ± language, and that there exists other frame-
Corollary 2 (Corollary from Proposition 4) Given a works that also falls under our definition, as it is the case of
Datalog ± ontology KB there exists such that D2 applied the work (also argumentation-based) by Black et al. (2009)
to KB is tolerant to incoherence. where dialogue games between agents are used to solve
queries under Description Logics ontologies that can be in-
As an example of the above corollary, consider again the
coherent.
running example.
Example 14 Let KB0 = D(KB) be the defeasi- References
ble transformation of KB in Example 1, where the
sets ΣE and ΣNC are the same, F = ∅, D = Arenas, M.; Bertossi, L. E.; and Chomicki, J. 1999. Con-
{can sing(simone), rock singer (axl ), sing loud (ronnie), sistent query answers in inconsistent databases. In Proc. of
has fans(ronnie), manage(band1 , richard )}, and PODS, 68–79.
ΣD = {rock singer (X) – sing loud (X), Besnard, P., and Hunter, A. 2008. Elements of Argumenta-
sing loud (X) – sore throat(X), tion. MIT Press.
has fans(X) – famous(X), Bienvenu, M., and Rosati, R. 2013. Tractable approxi-
rock singer (X) – can sing(X)} mations of consistent query answering for robust ontology-
based data access. In Proc. of IJCAI.
Here, we have the dialectical tree with argument
h rock singer (axl ) , rock singer (axl )i as its undefeated Bienvenu, M. 2012. On the complexity of consistent query
root, since no counterargument for it can be built (Figure 4). answering in the presence of simple ontologies. In Proc. of
AAAI.
Black, E.; Hunter, A.; and Pan, J. Z. 2009. An argument-
based approach to using multiple ontologies. In SUM, 68–
79.
Calı̀, A.; Gottlob, G.; and Lukasiewicz, T. 2012a. A gen-
eral Datalog-based framework for tractable query answering
over ontologies. In J. Web Sem., volume 14, 57–83.
Calı̀, A.; Gottlob, G.; and Lukasiewicz, T. 2012b. A gen-
Figure 4: A labelled dialectical tree for atom eral Datalog-based framework for tractable query answering
rock singer (axl ). over ontologies. J. of Web Semant. 14:57–83.
Calı̀, A.; Lembo, D.; and Rosati, R. 2003. On the decid-
Then, clearly KB0 |=F rock singer(axl), and thus ability and complexity of query answering over inconsistent
KB D2 rock singer(axl). and incomplete databases. In Proc. of PODS 2003, 260–271.
Note that in Example 14 the atom rock singer(axl) is ACM.
warranted under any criterion comparison , and thus we Delgrande, J. P., and Jin, Y. 2012. Parallel belief revision:
have not needed to perform any restriction on the criterion. Revising by sets of formulas. Artif. Intell. 176(1):2223–
2245.
Conclusions Flouris, G.; Huang, Z.; Pan, J. Z.; Plexousakis, D.; and
Incoherence is an important problem in knowledge repre- Wache, H. 2006. Inconsistencies, negations and changes
sentation and reasoning, specially when integrating different in ontologies. In AAAI, 1295–1300. AAAI Press.
Garcı́a, A. J., and Simari, G. R. 2004. Defeasible logic pro-
gramming: An argumentative approach. TPLP 4(1-2):95–
138.
Konieczny, S., and Pérez, R. P. 2002. Merging information
under constraints: A logical framework. J. Log. Comput.
12(5):773–808.
Lembo, D.; Lenzerini, M.; Rosati, R.; Ruzzi, M.; and Savo,
D. F. 2010. Inconsistency-tolerant semantics for description
logics. In Proc. of RR, 103–117.
Lukasiewicz, T.; Martinez, M. V.; and Simari, G. I. 2012.
Inconsistency handling in Datalog+/– ontologies. In Proc.
of ECAI, 558–563.
Martinez, M. V.; Deagustini, C. A. D.; Falappa, M. A.; and
Simari, G. R. 2014. Inconsistency-tolerant reasoning in
datalog± ontologies via an argumentative semantics. In
proc. of IBERAMIA 2014, 15–27.
Martinez, M. V.; Garcı́a, A. J.; and Simari, G. R. 2012. On
the use of presumptions in structured defeasible reasoning.
In Proc. of COMMA, 185–196.
Qi, G., and Hunter, A. 2007. Measuring incoherence in
description logic-based ontologies. In ISWC/ASWC, 381–
394.
Rahwan, I., and Simari, G. R. 2009. Argumentation in Arti-
ficial Intelligence. Springer.
Simari, G. R., and Loui, R. P. 1992. A mathematical treat-
ment of defeasible reasoning and its implementation. Artif.
Intell. 53(2-3):125–157.