The concept of incoherence naturally arises in ontological settings, specially when integrating knowledge. In this work we study a notion of incoherence for Datalog ontologies based on the definition of satisfiability of a set of existential rules regarding the set of integrity constraints in a Datalog ontology. We show how classical inconsistency-tolerant semantics for query answering behaves when dealing with atoms that are relevant to unsatisfiable sets of existential rules, which may hamper the quality of answers-even under inconsistency-tolerant semantics, which is expected as they were not designed to confront such issues. Finally, we propose a notion of incoherency-tolerant semantics for query answering in Datalog , and present a particular one based on the transformation of classic Datalog ontologies into defeasible Datalog ones, which use argumentation as its reasoning machinery.
The problem of inconsistency in ontologies has been widely
acknowledged in both the Semantic Web and Database
Theory communities, and several methods have been developed
to deal with it, e.g.,
Although to consider the constraints as always satisfiable
is a reasonable assumption to make, specially in the case of
a single ontology, in this work we will focus on a more
general setting and consider that both data and constraints can
change through time and become conflicting. In this more
general scenario, as knowledge evolves (and so the ontology
that represents it) not only data related issues can appear,
but also constraint related ones. The problem of conflicts
among constraints is known in the Description Logics
community as incoherence
This work integrates three different building blocks: first, we introduce the notion of incoherence for Datalog ontologies, relating it to the problem of satisfiability of concepts for Description Logics; second, we show how such notion affects most of well-known inconsistency-tolerant semantics which, since they were not designed to confront such issues, can go up to the point of not returning any useful answer; finally, we propose a definition for incoherency-tolerant semantics, introducing an alternative semantics based on an argumentative reasoning process over the transformation of Datalog ontologies to their correspondent defeasible Datalog ontologies. We show how this semantics behaves in a satisfactory way in the presence of incoherence, as the process can return as answers atoms that trigger incoherency, which we show that cannot be done by classical inconsistency-tolerant semantics.
First, we briefly recall some basics on Datalog
Given a relational schema R, a
tuple-generating dependency (TGD) is a first-order formula
8X8Y (X; Y) ! 9Z (X; Z), where (X; Y) and
(X; Z) are conjunctions of atoms over R (without
nulls), called the body and the head of , respectively.
Satisfaction of TGDs are defined via homomorphisms,
which are mappings : [ N [ V ! [ N [ V
such that (i) c 2 implies (c) = c, (ii) c 2 N
implies (c) 2 [ N , and (iii) is naturally extended to
atoms, sets of atoms, and conjunctions of atoms. Consider a
database D for a relational schema R, and a TGD on R of
the form (X; Y) ! 9Z (X; Z). Then, is applicable
to D if there exists a homomorphism h that maps the atoms
of (X; Y) to atoms of D. Let be applicable to D, and
h0 be a homomorphism that extends h as follows: for each
Xi 2 X, h0(Xi) = h(Xi); for each Zj 2 Z, h0(Zj ) = zj ,
where zj is a “fresh” null, i.e., zj 2 N , zj does not
occur in D, and zj lexicographically follows all other nulls
already introduced. The application of on D adds to D
the atom h0( (X; Z)) if it is not already in D. After the
application we say that is satisfied by D. The Chase for a
database D and a set of TGDs T , denoted chase(D; T ),
is the exhaustive application of the TGDs
A conjunctive query (CQ) over R has the form
Q(X) = 9Y (X; Y), where (X; Y) is a conjunction of
atoms (possibly equalities, but not inequalities) with the
variables X and Y, and possibly constants, but without
nulls. In this work we restrict our attention to atomic queries.
A Boolean CQ (BCQ) over R is a CQ of the form Q(),
often written as the set of all its atoms, without
quantifiers. 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 2 Q(B)
for all B 2 mods(D; ). The answer for a BCQ Q to D and
is Yes, denoted D [ j= Q, iff ans(Q; D; ) 6= ;. It is
important to remark that BCQs Q over D and T can be
evaluated on the chase for D and T , i.e., D [ T j= Q is
equivalent to chase(D; T ) j= Q
Negative constraints (NCs) are first-order formulas of the form 8X (X) ! ?, where the body X is a conjunction of atoms (without nulls) and the head is the truth constant false, denoted ?. Intuitively, the head of these constraints have to evaluate to false in D under a set of TGDs T . That is, an NC is satisfied by a database D under a set of TGDs T iff there not exists a homomorphism h that maps the atoms of (X) to D, where D is such that every TGD in T is satisfied. As we will see through the paper, negative constraints are important to identify inconsistencies in a Datalog ontology, as their violation is one of the main inconsistency sources. In this work we restrict our attention to binary negative constraints (or denial constraints), which are NCs such that their body is the conjunction of exactly two atoms, e.g., p(X; Y ) ^ q(X; Z) ! ?. As we will show later, this class of constraints suffices for the formalization of the concept of conflicting atoms.
Equality-generating dependencies (EGDs) are first-order
formulas of the form 8X (X) ! Xi = Xj , where (X) is
a conjunction of atoms, and Xi and Xj are variables from X.
An EGD is satisfied in a database D for R iff, whenever
there exists a homomorphism h such that h( (X)) D, it
holds that h(Xi) = h(Xj ). In this work we will focus on
a particular class of EGDs, called separable
We usually omit the universal quantifiers in TGDs, NCs and EGDs, and we implicitly assume that all sets of dependencies and/or constraints are finite.
Datalog Ontologies. A Datalog ontology KB = (D; ), where = T [ E [ NC , consists of a database D, a set of TGDs T , a set of separable EGDs E , and a set of negative constraints NC . Example 1 illustrates a simple Datalog ontology.
Example 1 Consider the following KB. 8 > > > > > > > > > > > > > > > > > > > > > <
D : NC : E : T : fa1 : can sing(simone) a2 : rock singer (axl ); a3 : sing loud (ronnie); a4 : has fans(ronnie); a5 : manage(band1 ; richard )g f 1 : sore throat (X) ^ can sing(X) ! ?; 2 : unknown(X) ^ famous(X) ! ?g f 1 : rock singer (X) ! sing loud (X); 2 : sing loud (X) ! sore throat (X);
3 : has fans(X) ! famous(X); 4 : rock singer (X) ! can sing(X)g
Following the classical notion of consistency, we say that a consistent Datalog ontology has a non-empty set of models.
tent iff mods(D; ) 6= otherwise. ontology KB = (D; ) is consis;. We say that KB is inconsistent
The problem of obtaining consistent knowledge from an inconsistent knowledge base is natural in many computer science fields. As knowledge evolves, contradictions are likely to appear, and these inconsistencies have to be handled in a way such that they do not affect the quality of the information obtained from the knowledge base.
In the setting of Consistent Query Answering (CQA),
database repairing, and inconsistency-tolerant query
answering in ontological languages
Qi and Hunter 2007). Incoherence can be particularly
important when combining multiple ontologies since the
constraints imposed by each one of them over the data could
(possibly) represent conflicting modellings of the
application at hand. Clearly, the notions of incoherence and
inconsistency are highly related; in fact,
Our proposed notion of incoherence states that given a set of incoherent constraints it is not possible to find a set of atoms D such that KB = (D; ) is a consistent ontology and at the same time all TGDs in T are applicable in D. This means that a Datalog ontology KB can be consistent even if the set of constraints is incoherent, as long as the database instance does not make those dependencies applicable. On the other hand, a Datalog ontology KB can be inconsistent even when the set of constraints is coherent. Consider, as an example, the following KB = (ftall(peter); small(peter)g; ftall(X) ^ small(X) ! ?g), where the (empty) set of dependencies is trivially coherent; the ontology is, nevertheless, inconsistent.
In the last decades, several approaches to handling
inconsistency were developed in Artificial Intelligence and
Database Theory (e.g.,
Before formalizing the notion of incoherence that we use in our Datalog setting we need to identify the set of atoms relevant to a given set of TGDs. Intuitively, we say that a set of atoms A is relevant to a set T of TGDs if the atoms in the set A are such that the application of T over A generates the atoms that are needed to apply all dependencies in T , i.e., A triggers the application of every TGD in T . Formally, the definition of atom relevancy is as follows:
Let R be a relational schema, T be a set of TGDs, and A a (possibly existentially closed) non-empty set of atoms, both over R. We say that A is relevant to T iff for all 2 T of the form 8X8Y (X; Y) ! 9Z (X; Z) it holds that chase(A; T ) j= 9X9Y (X; Y).
When it is clear from the context, if a singleton set A = fag is relevant to T T we just say that atom a is relevant to T . The following example illustrates atom relevancy.
ing constraints:
T = f 1 : supervises(X; Y ) ! supervisor(X); 2 : supervisor(X) ^ take decisions(X) !
leads department(X; D); 3 : employee(X) ! works in(X; D)g First, let us consider the set A1 = fsupervises(walter; jesse); take decisions(walter); employee(jesse)g. This set is a relevant set of atoms to the set of constraints T = f 1; 2; 3g, since 1 and 3 are directly applicable to A1 and 2 becomes applicable when we apply 1 (i.e., the chase entails the atom supervisor(walter), which together with take decisions(walter) triggers 2).
However, the set A2 = fsupervises(walter; jesse); take decisions(gus)g is not relevant to T . Note that even though 1 is applicable to A2, the TGDs 2 and 3 are never applied in chase(A2; T ), since the atoms in their bodies are never generated in chase(A2; T ). For instance, consider the TGD 2 2 T . In the chase of T over D we create the atom supervisor(walter), but nevertheless we still cannot trigger 2 since we do not have and cannot generate the atom take decisions(walter), and the atom take decisions(gus) that is already in A2 does not match the constant value.
We now present the notion of coherence for Datalog ,
which adapts the one introduced by Flouris et al. for
DLs
In the rest of the paper sometimes we write that a set of TGDs is (un)satisfiable omitting the set of constraints, we do this in the context of a particular ontology where we have a fixed set of constraints NC [ E . Also, through the paper we denote by U (KB) the set of minimal unsatiasfiable sets of TGDs in T for KB (i.e., unsatisfiable set of TGDs such that every proper subset of it is satisfiable). The following example illustrates the concept of satisfiability of a set of TGDs in a Datalog ontology
following sets of constraints.
1 NC = f : risky job(P ) ^ unstable(P ) ! ?g 1T = f 1 : dangerous work (W ) ^ works in(W; P ) ! risky job(P ); 2 : in therapy (P ) ! unstable(P )g The set 1 is a satisfiable set of TGDs, and even though the
T simultaneous application of 1 and 2 may violate some formula in 1NC [ 1E , that does not hold for every relevant set of atoms. Consider as an example the relevant set D1 = fdangerous work(police); works in(police; marty); ians wtheehraavpeyt(hrautsmt)ogd;s(DD11i;s a1T r[elev1NaCnt[set1Ef)o r6= ;1Tt,hheonwe1Tveirs, satisfiable.
On the other hand, as an example of unsatisfiability consider the following constraints: 2 NC = f 1 : sore throat (X) ^ can sing (X) ! ?g 2T = f 1 : rock singer (X) ! sing loud (X); 2 : sing loud (X) ! sore throat (X); 3 : rock singer (X) ! can sing (X)g The set 2T is an unsatisfiable set of dependencies, as the application of TGDs f 1; 2; 3g on any relevant set of atoms will cause the violation of 1. For instance, consider the relevant atom rock singer (axl): we have that the application of 2T over frock singer (axl)g causes the violmaotidosn(forfock1 swihnegnerc(oanxsli)dge;red2T t[oge2NthCe[r wi2Eth) = 2T;,. Nthoetreeftohraet any set of relevant atoms will cause the violation of 1.
We are now ready to formally define coherence for a Datalog ontology. Intuitively, an ontology is coherent if there is no subset of their TGDs that is unsatisfiable w.r.t. the constraints in the ontology.
Definition 3 (Coherence) Let KB = (D; ) be a Datalog ontology defined over a relational schema R, and = T [
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 iff T is satisfiable w.r.t. NC [ E . Also, KB is said to be incoherent iff it is not coherent.
Example 4 (Coherence) Consider the sets of dependencies and constraints defined in Example 3 and an arbitrary database instance D. Clearly, the Datalog ontology (KDB;1 =2T [(D2N;C 1T[ [2E )1NiCs i[ncoh1Ee)reinst.coherent, while KB2 =
Finally, we look deeper into the relation between incoherence and inconsistency. Looking into Definitions 2 and 3 we can infer that an incoherent KB will induce an inconsistent KB when the database instance contains any set of atoms that is relevant to the unsatisfiable sets of TGDs. This result is captured in the following proposition.
Proposition 1 Let KB = (D; ) be a Datalog ontology where = T [ E [ NC . If KB is incoherent and there exists A D such that A is relevant to some unsatisfiable set U 2 U (KB) then KB = (D; ) is inconsistent. Example 5 (Relating Incoherence and Inconsistency) As an instance of the relationship expressed in Proposition 1, consider once again the ontology presented in Example 1. As hinted previously in Example 3, there we have the set A D = frock singer (axl)g and the unsatisfiable set of TGDs U T = f 1 : rock singer (X) ! sing loud (X); 2 : sing loud (X) ! sore throat (X); 4 : rock singer (X) ! can sing (X)g. Since A is relevant to U the conditions in Proposition 1 are fulfilled, and indeed the ontology KB = (D; ) from Example 1 is inconsistent since 1 2 T is violated.
We have established the relation between incoherence and inconsistency. As explained, classic inconsistency-tolerant techniques do not account for coherence issues since they assume that such kind of problems will not appear. Nevertheless, if we consider that both components in the ontology evolve (perhaps being collaboratively maintained by a pool of users) then certainly incoherence is prone to arise. In the following we show that it may be important for inconsistency-tolerant techniques to consider incoherence in ontologies as well, since if not treated appropriately an incoherent set of TGDs may lead to the trivial solution of removing every single relevant atom in D (which in the worst case could be the entire database instance). This may be adequate for some particular domains, but does not seem to be a desirable outcome in the general case.
Although classical query answering in Datalog is not
tolerant to inconsistency issues, a variety of
inconsistencytolerant semantics have been developed in the last decade
for ontological languages, including lightweight
Description Logics (DLs), such as E L and DL-Lite
Depending on how repairs are obtained we can have
different semantics. In the following we recall
ARsemantics
AR Semantics. The AR semantics corresponds to the
notion of consistent answers in relational databases
E [ NC ). We denote by KB 2AR a the fact that a cannot be AR-consistently inferred from KB. We extend entailment to set of atoms straightforwardly, i.e., for a set of atoms A it holds that KB j=AR A iff for every a 2 A it holds that KB j=AR a, and KB 2AR A otherwise.
CAR Semantics. As noted by
Incoherence has great influence when calculating repairs, as can be seen in the following result: independently of the semantics (i.e., AR or CAR) no atom that is relevant to an unsatisfiable set of TGDs belongs to a repair of an incoherent KB.
Lemma 1 Let KB = (D; ) be an incoherent Datalog ontology where = T [ E [ NC and R(KB) be the set of (A-Box or Closed A-Box) repairs of KB. If A D is relevant to some unsatisfiable set U 2 U (KB) then A * R for every R 2 R(KB).
The proof of Lemma 1 follows from Proposition 1, since any set of atoms relevant to an unsatisfiable set of TGDs will be conflictive with NC [ E , thus not qualifying to be part of a proper repair.
Example 6 Consider the atom rock singer (axl) from the ontology presented in Example 1. As we have explained in Example 5, such atom is relevant to U T = f 1 : rock singer (X) ! sing loud (X); 2 : sing loud (X) ! sore throat (X); 4 : rock singer (X) ! can sing (X)g.
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. Consider the case of A-Box repairs. We have that they are maximally consistent subsets of the component D. We have that mods(rock singer (axl); ) = ;, as the NC 1 : sore throat (X) ^ can sing (X) ! ? is violated. Moreover, clearly this violation happens for every set A D such that rock singer (axl) 2 A, and thus we have that mods(A; ) = ;, i.e., rock singer (axl) cannot be part of any A-Box repair for the KB.
In an analogous way we can show that for any D0 D such that mods(D0; ) 6= ; it holds that (D0; T ) 6j= rock singer (axl), and thus it holds that rock singer (axl) 2= CCL(KB). Then, since Closed A-Box repairs are subsets of CCL(KB) it cannot happen that rock singer (axl) belongs to any of these repairs.
Then, from Lemma 1 follows that every atom that is relevant to an unsatisfiable set of TGDs cannot be ARconsistently (resp, CAR-consistently) entailed.
Proposition 2 Let KB = (D; ) be an incoherent Datalog ontology where = T [ E [ NC . If A D is relevant to some unsatisfiable set U T then KB 2AR A and KB 2CAR A.
The proof follows from Lemma 1: since a relevant set of atoms does not belong to any repair then it cannot be part of the answers of the AR and CAR semantics. As a corollary, in the limit case that every atom in the database instance is relevant to some unsatisfiable subset of the TGDs in the ontology then the set of AR-answers (resp, CAR-answers) is empty.
Corollary 1 Let KB = (D; ) be an incoherent Datalog ontology where = T [ E [ NC , and let AAR and ACAR be the set of atoms AR-consistently and CARconsistenly entailed from KB, respectively. If for every a 2 D there exists A D such that a 2 A and A is a minimal set of TGDs relevant to some U 2 U (KB) then AAR = ; and ACAR = ;.
Since they follow from Proposition 1, both Proposition 2
and Corollary 1 can be straightforwardly extended to other
repair based inconsistency-tolerant semantics such as ICAR
and ICR
Example 7 Consider once again KB in Example 1, and the atom a2 : rock singer(axl) in D. Such atom is relevant to the unsatisfiable set U T = f 1 : rock singer (X) ! sing loud (X); 2 : sing loud (X) ! sore throat (X); 4 : rock singer (X) ! can sing (X)g, and indeed it holds that KB 2AR rock singer(axl) and KB 2CAR rock singer(axl). As explained in Example 6, this is because rock singer(axl) cannot belong to any repair since its consistent application to is not feasible, i.e., mods((rock singer(axl); )) = ;.
We have shown how incoherence affects classic
inconsistency-tolerant semantics up to the point of not
returning any meaningful answer (since they were not
develop to consider such kind of issues). In this section we
propose the notion of tolerance to incoherence for query
answering semantics. Such semantics will allow to be able
to obtain useful answers from incoherent ontologies. We
continue this section by showing an alternative semantics
for Datalog based on the use of argumentative inference
that is tolerant to incoherence. For the elements of
argumentation we refer the reader to
Definition 4 (Incoherence-tolerant semantics) Let KB = (D; ) be a Datalog ontology where = T [ E [ NC . A query answering semantics S is said to be tolerant to incoherence (or incoherency-tolerant) iff there exists A D and U 2 U (KB) such that A is relevant to U and it holds that KB j=S A.
Intuitively, a query answering semantics is tolerant to incoherence if it can entail atoms that trigger incoherent sets of TGDs as answers. Clearly, from Proposition 2 it follows that inconsistency-tolerant semantics based on repairs are not tolerant to incoherence.
incoherency-tolerant semantics. semantics are not
We begin by recalling Defeasible Datalog (for the
interested reader, a more complete presentation of the framework
can be found in
Defeasible Datalog
ontology KB consists of a finite set F of ground atoms, called facts, a finite set D of defeasible atoms, a finite set of TGDs T , a finite set of defeasible TGDs D, and a finite set of binary constraints
E [ NC .
The following example shows a defeasible Datalog ontology that encodes the knowledge from Example 1 changing some of the facts and TGDs to defeasible ones. Example 8 The information from the ontology presented in Example 1 can be better represented by the following defeasible Datalog ontology KB = (F; D; 0T ; D; NC), where F = fcan sing (simone); rock singer (axl ); sing loud (ronnie); has fans(ronnie)g and D = fmanage(band1 ; richard )g. Note that we have changed the fact stating that richard manages band1 to a defeasible one, since reports indicates that the members of band1 are looking for a new manager. The sets of TGDs, and defeasible TGDs are now given by the following sets; note that we have changed some of the TGDs into defeasible TGDs to make clear that the connection between the head and body is weaker. T 0 = fsing loud (X) ! sore throat (X);
rock singer (X) ! can sing (X) D = frock singer (X) – sing loud (X);
has fans(X) – famous(X)g
Derivations from a defeasible Datalog ontology rely in the application of (strict or defeasible) TGDs. Given a defeasible Datalog ontology KB = (F; D; T ; D; NC ), a (strict or defeasible) TGD is applicable if there exist a homomorphism mapping the atoms in the body of into 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 way as explained in the preliminaries of this work.
The following definitions follow similar ones first
introduced by
Definition 5 Let KB = (F; D; T ; D; NC) be a defeasible Datalog ontology and L an atom. An annotated derivation @ of L from KB consists of a finite sequence [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 2 F [ D, or (ii) there exists a TGD 2 T [ D and a homomorphism h such that h(head( )) = Ri and is applicable to the set of all atoms and defeasible atoms that appear before Ri in the sequence. When no defeasible atoms and no defeasible TGDs are used in a derivation, we say the derivation is a strict derivation, otherwise it is a defeasible derivation. Note that there is non-determinism in the order in which the elements in a derivation appear; TGDs (strict and defeasible) can be reordered, and facts and defeasible atoms could be added at any point in the sequence before they are needed to satisfy the body of a TGD. These syntactically distinct derivations are, however, equivalent for our purposes. It is possible to introduce a canonical form for representing them and adopt that canonical form as the representative of all of them. For instance, we might endow the elements of the program from which the derivation is produced with a total order; thus, it is possible to select one derivation from the set of all the derivations of a given literal that involve the same elements by lexicographically ordering these sequences. When no confusion is possible, we assume that a unique selection has been made.
We say that an atom a is strictly derived from KB iff
there exists a strict derivation for a from KB, denoted with
KB ` a, and a is defeasibly derived from KB iff there exists
a defeasible derivation for a from KB and no strict derivation
exists, denoted with KB a. . A derivation @ for a is minimal
if no proper sub-derivation @0 of @ (every member of @0 is a
member of @) is also an annotated derivation of a.
Considering minimal derivations in a defeasible derivation avoids
the insertion of unnecessary elements that will weaken its
ability to support the conclusion by possibly introducing
unnecessary points of conflict. Given a derivation @ for a, there
exists at least one minimal sub-derivation @0 @ for an atom
a. Thus, through the paper we only consider minimal
derivations
Example 9 From the defeasible Datalog ontology in Example 8, we can get the following (minimal) annotated derivation for atom sore throat (axl):
@ = rock singer (axl ); rock singer (X) – sing loud (X);
sing loud (axl ); sing loud (X) ! sore throat (X);
sore throat (axl ) Then, we have that KB KB sore throat (axl).
` rock singer (axl ) and that
Classical query answering in defeasible Datalog gies is equivalent to query answering in Datalog gies. ontoloontolo
atom, KB = (F; D; T ; D; NC) be a defeasible Datalog ontology, KB0 = (F [ D; 0T [ NC) is a classical Datalog ontology where 0T = T [ f (X; Y) ! 9Z (X; Z) j (X; Y) – 9Z (X; Z)g. Then, KB0 j= L iff KB ` L or KB L.
Proposition 3 states the equivalence between derivations from defeasible Datalog ontologies and entailment in traditional Datalog ontologies whose database instance corresponds to the union of facts and defeasible atoms, and the set of TGDs corresponds to the union of the TGDs and the strict version of the defeasible TGDs. As a direct consequence, all the existing work done for Datalog directly applies to defeasible Datalog . In particular, it is easy to specify a defeasible Chase procedure over defeasible Datalog ontologies, based on the revised notion of application of (defeasible) TGDs, whose result is a universal model. Therefore, a (B)CQ Q over a defeasible Datalog ontology can be evaluated by verifying that Q is a classical consequence of the chase obtained from the defeasible Datalog ontology.
Conflicts in defeasible Datalog ontologies come, as in classical Datalog , from the violation of NCs or EGDs. Intuitively, two atoms are in conflict relative to a defeasible Datalog ontology whenever they are both derived from the ontology (either strictly or defeasible) and together map to the body of a negative constraint or they violate an equalitygenerating dependency.
Definition 6 Given a set of NCs NC and a set of nonconflicting EGDs E , two ground atoms (possibly with nulls) a and b are said to be in conflict relative to E [ NC iff there exists an homomorphism h such that h(body( )) = a ^ b for some 2 NC or h(Xi) 6= h(Yj ) for some 2 E where h(Xi) is a term in a and h(Yj ) is a term in b. In what follows, we say that a set of atoms is a conflicting set of atoms relative to E [ NC if and only if there exist at least two atoms in the set that are in conflict relative to E [ NC , otherwise will be called non-conflicting. Whenever is clear from the context we omit the set of NCs and EGDs. Example 10 Consider the NC fsore throat (X) ^ can sing (X) ! ?g in NC from the defeasible ontology in Example 8. In this case, the set of atoms fsore throat (axl ); can sing (axl )g is a conflicting set relative to NC. However, this is not the case for the set S = frock singer (axl )g: 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
exist, we use a dialectical process to decide which
information 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
reasoning mechanism. We maintain the intuition that led to the
classic definition of arguments by
Definition 7 Let KB be a defeasible Datalog ontology and L a ground atom. A set A of facts, defeasible atoms, TGDs, and defeasible TGDs used in an annotated derivation @ of L is an argument for L constructed from KB iff @ is a minimal derivation and no conflicting atoms can be defeasible derived from A [ T . An argument A for L is denoted hA; Li, and AKB will be the set of all arguments that can be built from KB.
Answers to atomic queries are supported by arguments
built from the ontology. However, it is possible to build
arguments for conflicting atoms, and so arguments can
attack each other. We now adopt the definitions of
counterargument and attacks for defeasible Datalog ontologies
from
Example 12 Consider derivation @ from Example 9 and let A be the set of (defeasible) atoms and (defeasible) TGDs used in @. A is an argument for sore throat (axl ). Also, we can obtain a minimal derivation @0 for can sing (axl ) where B, the set of (defeasible) atoms and (defeasible) TGDs used in @0, is such that no conflicting atoms can be defeasibly derived from T .
As fsore throat (axl ); can sing (axl )g is conflicting relative to NC , we have that hA; sore throat (axl )i and hB; can sing (axl )i attack each other.
Once the attack relation is established between arguments, it is necessary to analyze whether the attack is strong enough so one of the arguments can defeat the other. Given an argument A and a counter-argument B, a comparison criterion is used to determine if B is preferred to A and, therefore, defeats A. For our defeasible Datalog framework, unless otherwise stated, we assume an arbitrary preference criterion among arguments where A B means that B is preferred to A and thus defeats it. More properly, given two arguments hA1; L1i and hA2; L2i we say that argument hA1; L1i is a defeater of hA2; L2i iff there exists a sub-argument hA; Li of hA2; L2i such that hA1; L1i counter-argues hA; Li at L, and either hA1; L1i hA; Li (it is a proper defeater) or hA1; L1i 6 hA; Li, and hA; Li 6 hA1; L1i (it is a blocking defeater).
Finally, the combination of arguments, attacks and comparison criteria gives raise to Datalog argumentation frameworks.
Definition 8 Given a Defeasible Datalog
fined over a relational schema R, a Datalog
framework F is a tuple hLR; AKB; i, where
preference relation defined over AKB.
ontology KB
deargumentation
specifies a
To decide whether an argument hA0; L0i is undefeated
within a Datalog argumentation framework, all its
defeaters must be considered, and there may exist defeaters for
their counter-arguments as well, giving raise to
argumentation lines. The dialectical process considers all possible
admissible argumentation lines for an argument, which
together form a dialectical tree. An argument line for hA0; L0i
is defined as a sequence of arguments that starts at hA0; L0i,
and every element in the sequence is a defeater of its
predecessor in the line
Different argumentation systems can be defined by
setting a particular criterion for proper attack or defining the
admissibility of argumentation lines. Here, we adopt the one
from
The dialectical process considers all possible admissible
argumentation lines for an argument, which together form a
dialectical tree. Dialectical trees for defeasible Datalog
ontologies are defined following
Definition 9 Let hA0; L0i be an argument from a Datalog argumentation framework F. A dialectical tree for hA0; L0i from F, denoted T (hA0; L0i), is defined as follows: (1) The root of the tree is labeled with hA0; L0i. (2) Let N be a non-root node of the tree that is labeled hAn; Lni, and C = [hA0; L0i; hA1; L1i; : : : ; hAn; Lni] be the sequence of labels of the path from the root to N . Let hB1; Q1i; hB2; Q2i; : : : ; hBk; Qki be all the defeaters for hAn; Lni. For each defeater hBi; Qii(1 i k), such that the argumentation line C0 = [hA0; L0i; hA1; L1i; hA2; L2i; : : : ; hAn; Lni; hBi; Qii] is admissible, the node N has a child Ni labeled hBi; Qii. If there is no defeater for hAn; Lni or there is no hBi; Qii such that C0 is admissible, then N is a leaf.
Argument evaluation, i.e., determining whether the root node of the tree is defeated or undefeated, is done by means of a marking or labelling criterion. Each node in an argument tree is labelled as either defeated (D) or undefeated (U ). We denote the dialectical tree built for the argument A supporting claim L as T (hA; Li), Args(T ) the set of arguments in T , and the root of T (hA; Li) with root(T (hA; Li)). Also, marking(N ), where N is a node in a dialectical tree, denotes the value of the marking for node N (either U or D). Deciding whether a node is defeated or undefeated depends on whether or not all its children are defeated: (1) if node N is a leaf then marking(N ) = U , (2) node N is such that marking(N ) = D iff at least one of its children that is marked with U , and (3) node N is such that marking(N ) = U iff all its children are marked with D.
By means of the marking procedure we can define when an atom is warranted in the argumentation framework. Definition 10 Let KB be a Defeasible Datalog ontology and F the corresponding Datalog argumentation framework where 2 F is an arbitrary argument comparison criterion. An atom L is warranted in F (through T ) iff there exists an argument hA; Li such that marking(root(T (hA; Li))) = U . We say that L is entailed from KB (through F), denoted with KB j=F L, iff it is warranted in F.
Example 13 Suppose that we have the query Q = can sing(axl), i.e., we want to know whether or not Axl can sing. Consider the conflict between arguments A and B shown in Example 12. As we have stated, we do not define any particular criterion to solve attacks. Nevertheless, for the sake of example assume now that we are indeed using a criterion that is such that B A. Under such supposition we have the labelled dialectical tree shown in Figure 3.
As can be seen in the dialectical tree, if we assume that B A then we have reasons to think that Axl cannot sing due to its throat being sore.
In Definition 10 we specify a semantics based on the use of argumentative inference. From now on we denote such semantics as D2 (Defeasible Datalog ). Such semantics relies on the transformation of classic Datalog ontologies to defeasible ones and then obtaining answers from the transformed one. So, we begin by establishing how a classic Datalog ontology can be transformed to a defeasible one. Intuitively, the transformation of a classic ontology to a defeasible one involves transforming every atom and every TGD in the classic ontology to its defeasible version.
Let KB = (D; T [ E [ NC ) be a classic Datalog ontology. Then, its transformation to a defeasible Datalog ontology, denoted D(KB), is a defeasible ontology KB0 = (F; D0; 0T ; D ; E [ NC ) where F = ;, D0 = D, 0T = ; and D = f (X; Y) – 9Z (X; Z) j (X; Y) ! 9Z (X; Z)g.
Next, we define the set of answers in D2 for an atomic query. Intuitively, a literal is an answer for a classical Datalog ontology KB under the D2 semantics iff it is warranted in the transformation of KB to a defeasible one.
tology, KB0 = D(KB) its defeasible transformation, Q a query and a comparison criterion. Then, an atom L is an answer for Q from KB under D2, denoted KB D2 L, iff KB0 j=F L where F = hLR; AKB0 ; i.
Note that the semantics is parametrized by the comparison criterion , which helps to solve conflicts when they arise.
Now, we focus on the behaviour of Defeasible Datalog regarding atoms relevant to unsatisfiable sets of TGDs. It can be shown that the argumentation framework F = hLR; AD(KB); i is such that one relevant atom L to an unsatisfiable set is warranted (and thus an answer), provided that the comparison criterion is such that marking(root(TF(hA; Li))) = U for some dialectical tree TF(hA; Li) built upon F. It is interesting to see that such comparison criterion can always be found: intuitively, it suffices to arbitrary establish A as the most preferred argument in AD(KB) (note however that other criteria can have the exact same result).
Proposition 4 Let KB be a Datalog ontology defined over a relational schema R, and KB0 be a Defeasible Datalog ontology such that D(KB) = KB0. Finally, let L 2 D and U 2 U (KB) such that L is relevant to U . Then, it holds that there exists such that KB D2 L.
Datalog ontology KB there exists such that D2 applied to KB is tolerant to incoherence.
As an example of the above corollary, consider again the running example.
Example 14 Let KB0 = D(KB) be the defeasible transformation of KB in Example 1, where the sets E and NC are the same, F = ;, D = fcan sing (simone); rock singer (axl ); sing loud (ronnie); has fans(ronnie); manage(band1 ; richard )g, and D = frock singer (X) – sing loud (X); sing loud (X) – sore throat (X); has fans(X) – famous(X); rock singer (X) – can sing (X)g
Here, we have the dialectical tree with argument h rock singer (axl ) ; rock singer (axl )i as its undefeated root, since no counterargument for it can be built (Figure 4).
Then, clearly KB0 j=F rock singer(axl), and thus
D2 rock singer(axl).
Note that in Example 14 the atom rock singer(axl) is warranted under any criterion comparison , and thus we have not needed to perform any restriction on the criterion.
Incoherence is an important problem in knowledge representation and reasoning, specially when integrating different sources of information. Nevertheless, most of the works in query answering for Datalog ontologies and DLs have focused on consistency issues making the assumption that the set of constraints correctly represents the semantics of the data and therefore any conflict can only come from the data itself.
In this work we have introduced the concept of
incoherence for Datalog ontologies, relating it to the presence of
sets of TGDs such that their application inevitably yield to
violations in the set of negative constraints and
equalitygenerating dependencies. We have shown how incoherence
affects classic inconsistency-tolerant semantics to the point
that for some incoherent ontologies these semantics may
produce no useful answer. Finally, we have introduced the
concept of incoherency-tolerant semantics, and shown a
particular semantics satisfying that property. Nevertheless, it
is important to remark that our definition of
incoherencytolerant semantics is not tied to our particular proposal or
the Datalog language, and that there exists other
frameworks that also falls under our definition, as it is the case of
the work (also argumentation-based) by