This paper investigates the definition of belief revision operators that correspond to the inconsistency tolerant semantics in the Ontology Based Data Access (OBDA) setting. By doing this, we aim at providing a more general characterisation, as well as the construction, of the above mentioned semantics. In fact, the main result of this paper is the idea of using kernel consolidation in Datalog+ to achieve a new semantic for inconsistent tolerant ontology query answering.
We position ourselves in the Ontology Based Data Access
(OBDA) setting where a query is being asked over a set of
knowledge bases defined over a common ontology. When
the union of knowledge bases along with the ontology is
inconsistent, several semantics have been defined
In this paper we take a new approach and aim to define new characterisations of two such semantics IAR and ICR which are specially interesting because these give us a unique result and because of their data complexity. We argue that such characterisation can provide an alternative way of comparing the semantics and can provide new insights into their properties. Furthermore, such characterisation can be used when proposing a generalisation of inconsistency tolerant semantics.
In order to provide the new characterisation we define
belief revision operators that correspond to IAR and ICR based
on kernel consolidation. This characterization will be more
general than the one proposed in
2
There are two major approaches in the literature used to
represent an ontology for the OBDA problem: Description
Logics (such as E L
In this paper we represent the ontology via rules using the Datalog+ language. We consider a (potentially inconsistent) knowledge base composed of a set F of facts corresponding to existentially closed conjunctions of atoms1, which can contain n-ary predicates; a set of negative constraints N which represent the negation of a fact and an ontology composed of a set of rules R that represent general implicit knowledge that can introduce new variables in their head (conclusion).
A rule is applicable to set of facts F if and only if the set entails the hypothesis of the rule. If rule R is appli1For technical reasons we consider F as a set of atoms and not as a conjunction of atoms. While the two are equivalent when dealing with consistent knowledge bases, this is no longer the case when dealing with inconsistent knowledge bases. This work convention is very important in the remaining parts of the paper. cable to the set F , the application of R on F produces a new set of facts obtained from the initial set with additional information from the rule conclusion. We then say that the new set is an immediate derivation of F by R denoted by R(F ). Let F be a set of facts and let R be a set of rules. A set Fn is called an R-derivation of F if there is a sequence of sets (derivation sequence) (F0; F1; : : : ; Fn) such that: (i) F0 F , (ii) F0 is R-consistent, (iii) for every i 2 f1; : : : ; n 1g, it holds that Fi is an immediate derivation of Fi 1. Given a set fF0; : : : ; Fkg and a set of rules R, the closure of fF0; : : : ; Fkg with respect to R, denoted ClR(fF0; : : : ; Fkg), is defined as the smallest set (with respect to ) which contains fF0; : : : ; Fkg, and is closed for R-derivation (that is, for every R-derivation Fn of fF0; : : : ; Fkg, we have Fn ClR(fF0; : : : ; Fkg)). Finally, we say that a set F and a set of rules R entail a fact G (and we write F ; R j= G) iff the closure of the facts by all the rules entails G (i.e. if ClR(F ) j= G). Given a set of facts fF1; : : : ; Fkg, and a set of rules R, the set of facts is called R-inconsistent if and only if there exists a constraint N = :F such that ClR(fF1; : : : ; Fkg) j= F . A set of facts is said to be R-consistent iff it is not R-inconsistent. A knowledge base K = (F ; R; N ) is said to be consistent if and only if F is R-consistent. A knowledge base is inconsistent if and only if it is not consistent.
Several semantics have been proposed to handle
consistency based on the concept of data repairs
Definition 1
Definition 3
It has been shown
3
Definition 4 A selection function is a function such that for every set F of formulae and any fact it holds: (F ? ) if this set is non-empty, othis a non-empty subset of F ? erwise, it is (F ? ) = fF g.
Definition 5 (Updated AGM85
F
= \ (F ? )
Two limiting cases have been thoroughly studied: when gives back either only one element of F ? or all members of F ? . In the first case, we are talking about Maxichoice contraction and in the second it is called Full meet contraction(FMC).
There are other special and interesting cases when the selection function is based on a relation (that may be considered as a preference relation).
Definition 6 A selection function for a belief base F in a knowledge base K, and the contraction operator based on it, are 1. relational if and only if there is a binary relation v such that for every fact , if F ? is non-empty, then
(F ? ) = fA 2 F ? jC v A for all C 2 F ? g 2. transitively relational if and only if there is such a relation that is transitive.
Based on partial meet contraction, one can define a partial meet consolidation as F ? which is the intersection of the “most preferred” maximal consistent subsets of F , i.e. F ! = F ? = \ (F ??) where ? denotes logical contradiction.
Partial meet consolidation has been axiomatically
characterized as follows:
Theorem 1 ( Adapted
F .
Relevance: If 2 F F !, then there is some F 0 with F ! F 0 F , such that F 0 is R-consistent and F 0 [ f g is R-inconsistent.
In addition, it is a full meet consolidation if and only if it also satisfies: Core identity: 2 F ! if and only if 2 F and there is no F 0 F such that F 0 is R-consistent but F 0 [ f g is R-inconsistent.
On the other hand, an operator is a maxi-choice consolidation if and only if it satisfies the postulates consistency, inclusion, and: Fullness: If inconsistent.
2 F and 2 F ! then F ! [ f g is R1. A F . 2. 2 ClR(A). 3. If B A, then F?? F .
62 ClR(B).
There are different ways to characterize belief base
functions. In fact, we would say that there is an axiomatic
characterization and an infinite number of constructions, four
of them were extensively studied in the literature: using
remainder sets, using kernel sets, epistemic entrenchment and
spheres system. In
IAR semantics. 2. If ! is a Full Meet Consolidation for ClR(F ) then we get the ICR semantics.
Furthermore, in
In the following section, we will define the operators corresponding to the inconsistency tolerant semantics above using kernel sets.
4
In this section, we are considering an alternative point of
view which is based on the simple hypothesis that a fact
is R-entailed from a subset A of F if and only if it contains
some minimal -entailing subset of A. Hence, in this
context, in order to remove from F , it is only necessary to
remove at least one fact of each minimal -entailing
subset of F . In formal terms, this approach was formalized by
Hansson in
F
It turns out that all partial meet contractions on belief bases are kernel contractions, but the converse relationship does not hold, i.e. there are kernel contractions that are not partial meet contractions. In other words, kernel contraction is a generalization of partial meet contraction.
However, the next observation gives a direct connection
between them (see
The above definition of kernel contraction can be straightforwardly transferred to consolidation. Thus, Kernel Consolidationz is defined in the following way:
F z = F ? = F (F?? ?)
Hence, if a set of facts F is inconsistent with a new fact f ,
a straight solution to gain consistency is to repair the joined
theory F [ ff g, by removing from it the minimal number of
facts that support the contradiction. This simple idea
underlies kernel sets plus incision function as mentioned above.
Example 1 (
T eamM ember(y)g.
T eamM ember(x); Driver(y) ! In words, K specifies that drivers and mechanics are team members, but drivers are not mechanics (and viceversa, because N states that the two concepts Driver and Mechanic are disjoint). The facts M echanic(f elipe) and Driver(f elipe) asserts that f elipe is both a driver and a mechanic. It is easy to see that K is unsatisfiable, since f elipe violates the disjointness between driver and mechanic. There is only one -kernel in this case: F?? ? = fM echanic(f elipe); Driver(f elipe)g. Therefore, the incision function must select a non-empty subset of F?? ?. There are three different possibilities, i.e. (F?? ?) is any of the following: fM echanic(f elipe)g; fDriver(f elipe)g; fM echanic(f elipe); Driver(f elipe)g.
According to Observation 1 and the results given
in
is a kernel set, and its elements are the -kernels of A contraction operation can be based on the simple principle that no -kernel should be included in F . This can be obtained with an incision function, a function that selects at least one element from each -kernel for removal. It was defined by Hansson and adapted for our setting here as follows: Definition 8 An incision function for F is a function such that for every : i) (F?? ) [(F?? ). ii) If ; =6 A 2 F?? , then A \ (F?? ) 6= ;.
An operation that removes exactly those elements that are selected for removal by an incision function is called an operation of kernel contraction and it responds to the following definition: In this section we go one step further in the definition of kernel consolidation operators through a set of postulates. In order to give logical properties of that kind of consolidation operators, we first rephrase Hansson’s postulates within our framework. Let K = (F ; R; N ) be a knowledge base, the original postulates can be rewritten in the following way: F Consistency: Kz = (F z; R; N ) is consistent.
Inclusion: Kz = (F z; R; N ) v K = (F ; R; N ).
such that F 0 is R-consistent and F 0 [ ff g does not. The first postulate says that the result of every consolidation is always consistent. Inclusion says that the new knowledge base should not contain anything that was not already in the original set. The postulate of core-retainment tries to capture the intuition that if a fact has to be removed, then this fact is relevant to imply ?. The representation theorem for this kind of consolidation operators can be formulated as follows: Theorem 2 An operator z is an operation of kernel consolidation if and only if it satisfies Consistency, Inclusion and Core-retainment.
Proof Checking that operations of kernel consolidation satisfy postulates: Consistency and Inclusion follow directly from definition. To see that kernel consolidation satisfies Core-retainment, let f 2 F F z. Then f 2 (K?? ?). Since (F?? ?) [(F?? ?), there should be some set D such that f 2 D 2 F?? ?. Let F 0 = D ff g. Thus F 0 6` ? and F 0 [ ff g ` ?. Hence, z satisfies Core-retainment.
On the contrary direction, let z be an operator that satisfies the three postulates mentioned in the theorem. We need to show there exists a incision function such that F z = F (F?? ?). For that, we define (F?? ?) = F F z. Clearly, it follows from inclusion that F z = F (F?? ?). Therefore, it only remains to verify that is an incision function. Of course, is a function. Then, we need to show that it satisfies the two conditions of Definition 8.
For the first condition, we are going to show that (F ? ? ?) [(F ?? ?). We take f 2 (F ?? ?). From that and Core-retainment, we conclude there exists F 0 F such that F 0 is R-consistent and F 0 [ ff g does not. Hence, f 2 [(F?? ?).
For the second condition, we need to show for any D 2 F?? ? that D \ (F?? ?) 6= ;. By consistency, F z 6` ?.Then, we conclude that D * F z, and thus, there is some f 0 2 D such that f 0 62 F z. Since D F it follows that f 0 2 F F z, i.e. f 0in (F?? ?). Therefore, f 0 2 D \ (F?? ?), which is enough to show that ii) in Definition 8 is satisfied. This concludes the proof.
5
In this paper we have shown how to get a more general
characterisation of the tolerance inconsistence semantics in the
OBDA setting. We did this by covering the semantics
using known kernel consolidation operators from belief
revision. Note that by using the equivalence showed in