The world of the Semantic Web includes many inconsistent knowledge bases, whose axioms are often unreliable and can therefore be naturally interpreted as defaults. In this article we introduce an extension of Sengupta et. al.'s semantics [12] with a preference order on the defaults with respect to satisfaction. In particular, the semantics we propose is an improved version of Heymans et. al.'s semantics [8] for a defeasible ontology language. One crucial difference we adopt is that the preference relation between interpretations is not only defined with respect to the same individuals, but any. We provide an algorithm to translate the entailment problem with respect to ordered default knowledge bases to the one for classical knowledge bases, and show its soundness and completeness. As a practical application scenario, we test our algorithm on various subsets of LOD Cloud, and report on our result.
Many real world ontologies in the Semantic Web contain inconsistent data. These
inconsistencies arise due to different reasons. One reason is their extreme size, a second is
that they model very general domain knowledge with diversifying information, e.g.,
encyclopaedic knowledge [
In order to integrate the knowledge across different ontologies, one often confronts
the problem of alignment which is the process of determining correspondences between
matching entities [
The automatic approaches usually involve a change in the classical semantics to be
able to cope with inconsistent knowledge. One particular class of approaches avoids
inconsistency by decreasing the number of derivable facts [
In this article we introduce an extension of Sengupta et. al.’s semantics [
Furthermore, we provide an algorithm to transform the entailment problem from
the ordered default knowledge bases to the one for classical knowledge bases. We also
show the soundness and completeness of our algorithm. We test it on different
realworld semantic datasets i.e., subsets of the Linked Open Data Cloud (LOD Cloud) [
In the following we first go over some preliminaries for description logics with defaults. In Section 3, the introduced semantics is extended to implement a preference order on defaults. After presenting some theoretical results, we discuss advantages of this approach and test it on real data, in Section 4. In Section 5 we discuss related work. Conclusion and future work close the paper. 2
Our semantics is a generalisation of the semantics presented in Sengupta et. al. [
The semantics presented in [
Given a default knowledge base, the notion of an interpretation I is extended to the set of free defaults as DI = (X1I ; : : : ; XnI ), where XiI contains the interpreted set of named individuals that satisfy the ith default. That is, for Ci vd Di, the definition of XiI is ((:Ci)I [DiI )\ iInd).3 Here, iInd is the set of interpreted named individuals of 3 This definition is syntactically different from the original definition, but semantically equivalent. the knowledge base . In the following we always assume jDj = n and D = f(C1 vd D1); : : : ; (Cn vd Dn)g. Models of a default knowledge base h ; Di are defined using a preferred model semantics; that is, the preference relation > ;D on the interpretations is defined as follows: Given two interpretations I and J of the knowledge base , we say that I is preferred to J , denoted by I > ;D J , iff for all named individuals a appearing in , it holds that aI = aJ , XiJ XiI for all 1 i n, and
XiJ XiI for some 1 i n.
Moreover, an interpretation I is a d-model of h ; Di iff i: I (classically) satisfies , ii: CiI n iInd DiI for each (Ci vd Di) 2 D, iii: there is no J > ;D I, such that J also satisfies conditions i and ii. If a default knowledge base has a d-model, we say it is d-satisfiable. An axiom is then d-entailed by a default knowledge base h ; Di, written h ; Di j= , if it holds for every d-model I of the default knowledge base that I satisfies . 3
Before introducing our approach we motivate it by discussing an example. Thereafter, we show that d-satisfiability and d-entailment is decidable. In particular, to prove the decidability of d-entailment, we present an algorithm and show its sound- and completeness. 3.1
Consider the following scenario: We are given two ontologies O1 and O2 shown in Table 1, and we want to align them with regard to the statements in the third column of Table 1. Without further debugging, the resulting ontology does not carry any relevant Republican(mike) Republican(clara) likes(mike; clara) likes(clara; mike)
Republican u Democrat v ? Republican v 8likes:Republican Democrat v 8likes:Democrat
Democrat(sarah) DemocratO1 likes(robert; sarah) likesO1 likes(sarah; robert)
information any more, since everything follows from inconsistency. One solution is to
use the semantics of free defaults [
base h ; D; i where is a knowledge base, D is a finite set of free defaults and is a strict partial order on D. And given I and J are interpretations of , I is preferred over J (w.r.t. ), denoted as I >h ;D; i J , iff 1. for all named individuals a appearing in , aI = aJ , 2. for all i such that XiJ 6 XiI there exists j, such that XjI 6
Dj ) (Ci vd Di) 3. X I 6= X J XjJ and (Cj vd
For simplicity purposes we will from now on abuse the notation and adopt the shorthand > for >h ;D; i as long as it is clear from the context. Observe that if I > J , then there always exists i s.t. XiI ) XiJ , since is a strict order. The definitions of d-models, d-satisfiability and d-entailment are changed accordingly by replacing the order on interpretations > ;D with the new order > ;D; . This is a generalisation since for >D= ; the semantics are equivalent i.e. > ;D=> ;D; .
Going back to the previous example, we assume that D is ordered by , and
For the ordered default knowledge base h ; D; i, there exist strictly less d-models
than for the unordered default knowledge base we previously considered. Namely, the
d-models for the ordered knowledge base are exactly those of type 3 in Table 2.
Therefore, in contrast to the unordered default knowledge base, the ordered default knowledge
base entails both :Republican(sarah) and :Democrat(robert).
We show that decidability of d-satisfiability and d-entailment are maintained with this
generalisation. Let h ; D; i be an ordered default knowledge base in a decidable
description logics L, which can be extended with nominal concept expressions, while
maintaining decidability. Let Ind be the set of named individuals occurring in and
profile P = (P1; : : : ; Pn), where n = jDj and for 1 i n, Pi Ind . We
define P as the knowledge base obtained by adding the following axioms to for each
Ci vd Di 2 D, as similarly defined in [
With this definition in mind, we can show the decidability of d-satisfiability. Theorem 1 (Decidability of d-satisfiability). Let h ; D; i be an ordered default knowledge base, and P = (;; : : : ; ;). Then, h ; D; i is d-satisfiable iff P is classically satisfiable.
Next, we show decidability of the generalized d-entailment. For that, we first introduce some notation to move on with an auxiliary lemma.
Let h ; D; i be an ordered default knowledge base, and I an interpretation. We define profile P (I) by setting its every component Pi(I) = fa 2 Ind j aI 2 XiI g. Lemma 1. Let h ; D; i be an ordered default knowledge base. Then, fI j I d-model of h ; D; ig = fI j I j= P (J ); J d-model of h ; D; ig: Here, we are interested in P (J ) in which J is a d-model. Intuitively, the knowledge base P (J ) represents all d-model J 0 such that P (J ) = P (J 0). Therefore, we call it d-model representing knowledge base (i.e., d-KB in short). The above lemma implies that one can check d-entailment by checking classical entailment in all d-KBs, P (J ). This is useful, since in general there can be more than one d-model J for one profile P (J ).
In the following we give a non-deterministic algorithm, which generates d-KBs and show its soundness and completeness.
The algorithm generates a knowledge base by non-deterministically adding one named individual to the individuals which satisfy one of the default subsumption, and checks whether there is a d-model with the new profile. For the default that is nondeterministically chosen, it must hold that all defaults which are preferable to it have been applied exhaustively. This algorithm uses jInd j jDj satisfiability checks for knowledge bases of the form P before the termination. With the two following theorems below, we show that our algorithm is sound and complete.
Theorem 2 (Soundness). Let h ; D; i be a d-satisfiable ordered defaults knowledge base. Then, for every knowledge base P generated by Algorithm 1 there exists d-model I such that P = P (I).
Theorem 3 (Completeness). Let h ; D; i be a d-satisfiable ordered defaults knowledge base. Then, for any d-model I, there exist non-deterministic choices in Algorithm 1, such that the generated knowledge base is equal to P (I).
While the non-deterministic algorithm suffices for a decidability result, a naive implementation which tries all possibilities via breadth-first or depth-first search is highly inefficient. Therefore, we give an idea for a smarter algorithm which is (almost) deterministic, restricted to total orders. Its complete description is included in the appendix. In short, the algorithm iteratively tries to satisfy the currently most preferred default, for which there are named individuals that are not yet asserted to satisfy it, but can satisfy it. When adding the assertion that a named individual satisfies a default in the d-KB that is currently constructed, we check whether there exist named individuals, which cannot satisfy the current default any more, due to the addition of the assertion. In this case we know that there is another, different d-KB we have to consider. This approach leads to less non-deterministic choices being considered. 4 4.1
We consider the complexity of different tasks for both default knowledge bases with and without an order; namely for d-satisfiability and d-entailment. d-satisfiability The complexity of checking d-satisfiability does not depend on whether the default knowledge base is ordered or unordered, since there is a d-model for the ordered default knowledge base if and only if there is a d-model of the unordered default knowledge base, and one can be reduced to the other (and vice versa) in constant time. This follows from the proof of Theorem 1. This also means that we can check d-satisfiability by verifying the classic satisfiability of a knowledge base. d-entailment We consider the algorithm of generating all d-KBs for an ordered default knowledge base and checking d-entailment by checking classical entailment in all of them iteratively. It is easy to see that the time needed, after the knowledge bases have been generated, is linear in the number of generated knowledge bases. As an example, consider h m; Dni, where m = fC(a1); : : : ; C(am)g;
n Dn = fC vd D1; : : : ; C vd Dn; > vd G :Dig: i=1 One has to decide for each individual ai, which default of the n + 1 defaults is not satisfied. This is independent for each individual. Therefore, without an order, this default knowledge base has (n + 1)m d-KBs. However, with any total strict order on these defaults the ordered default knowledge base h m; Dn; i will only have one d-KB. We name this type of inconsistency that occurs when one has to decide which defaults are satisfied for some individual, horizontal inconsistency. Observe that in case of horizontal inconsistencies, the addition of an order can be very useful, as it can reduce the amount of d-KBs by a factor which is exponential in the number of individuals. While this seems promising, we do not have such guarantee in general. Consider h m0; Dn0i, where
m0 = fC(a1); : : : ; C(a2m); R(a1; a2); R(a3; a4); : : : ; R(a2m 1; a2m)g; Dn0 = fC vd D1 u 8R::D1; : : : ; C vd Dn u 8R::Dng: Checking the above for two individuals a2i 1; a2i and one default C vd Dj u 8R::Dj , we have the choice whether the default should be satisfied either for a2i 1, or a2i. Since we have m pairs of individuals and n defaults, and each of the choices are independent, we have 2mn d-KBs. We name this type of inconsistency that occurs when one has to decide for which individuals some default is satisfied, vertical inconsistency. In this example, the addition of any order on defaults does not change the number of d-KBs, since there are no horizontal inconsistencies.
Summarising, we see that in the worst case, checking d-entailment is exponential in the number of individuals times the number of rules. Further, it is independent of the presence of an order on the defaults. This, however, does not necessarily mean that the order is useless when it comes to real-world data. 4.2
In order to test the performance of the algorithm on real-world data, we acquired
inconsistent subsets of the LOD Cloud [
The ontologies obtained using this procedure were transformed to ordered default knowledge bases by, first, rewriting all disjointness and equivalence axioms for concepts to concept subsumptions. Afterwards, we removed all subsumption axioms, and used them as defaults. The choice of order was an arbitrary total order.
Using this approach we focused on three empirical questions: 1. How likely is it to find an inconsistent knowledge base, which has exactly one d
KB, when transformed into a default knowledge base with a total order? 2. How does the running time of our algorithm change with respect to the number of named individuals in the knowledge base? 3. How does the running time of our algorithm change with respect to the number of defaults in the knowledge base? On the first question, we considered 100 inconsistent knowledge bases, each with approximately 100 named individuals, at most 100 axioms relating concepts, at most 100 property assertions and up to 50 properties. For each corresponding ordered default knowledge base, we checked d-satisfiability and whether the ordered default knowledge base had one d-KB or more.
As a result, we found that all of the inconsistent knowledge bases were d-satisfiable and 98 out of the 100 had only one d-KB. For the remaining two we tried to calculate the exact amount of d-KBs. This was, however, possible only for one of them which had two d-KBs. For the other one, the calculation was interrupted due to time constraints, and it had at least 20 d-KBs. This 98% is not necessarily representative for any real-world scenarios in a strict sense. However, it is still plausible that inconsistent ontologies, where the corresponding ordered default knowledge base has more than one d-KB, is the exception rather than the rule. This could change for larger datasets with more intricate relationships between the concepts; however, considering a reasonable amount of big datasets was infeasible for us.
This brings us to the next two questions about the scalability of the approach to larger datasets. We considered an inconsistent knowledge base, which referred to a total of 253 named individuals and 22 concept subsumptions.
We ran the algorithm multiple times on this dataset with a different number of axioms referring defaults to named individuals. This regulated 25000 individuals the amount of named individuals appearing in the knowledge base. The sscoend1250000000 roersaunlgtienglinreunitnimFeigoufreth1e sahlogworsiththme ien along with the percentage of named itrnum10000 individuals occurring in the knowl5000 edge base. The number of consistency checks of a classic knowledge 0 base increases linearly in the number 0 20 percenta4g0e of defaults6/0individuals 80 100 of individuals, given that the knowledge base has exactly one d-KB.
Fig. 1. The running time of the algorithm on the same However, in Figure 1, we observe a ontology with different amounts of defaults or named convex behaviour in runtime in the individuals. number of named individuals. This is due to the fact that by adding more named individuals, the consistency checks also take longer. Yet, the runtime performance of our algorithm behaves almost linear in the number of individuals as it is illustrated in Figure 1. Here, the amount of named individuals remains unchanged, while the percentage of defaults included is increased. The reason that the graphs end in different points is due to different scheduling by the operating system. 5
Many frameworks [
Intuitively, the order should implement a way of solving conflicts by deciding which axiom should be applied, taking the preference relation into consideration. For the semantics of O SHOQ(D), classic SHOQ(D)-interpretations I = ( I ; I ) satisfying the Unique Naming and Common Domain Assumption are used. Such an interpretation is a model of hT ; i, if for each A v B 2 T and x 2 I it holds that, whenever x 2 AI then x 2 BI , or there exists another more preferred subsumption C v D, s. t. x 2 CI \ DI . Based on this definition of a model a preferred model semantics is introduced as follows: For a model I of a O SHOQ(D)-knowledge base hT ; i, its support is defined as
SI = f(x; A v B) j x 2
I ; A v B 2 T , and x 2 :A t Bg: A model I is then preferred over a model J for hT ; i if, for all pairs (x; A v B) 2 SJ n SI there exists a pair (x; C v D) 2 SI n SJ , s.t. C v D A v B. This is denoted by I J . If SI 6= SJ , this preference holds strictly and is denoted by I > J . By considering only the most preferred models, i.e. the ones that are maximal w.r.t. >, one obtains a semantics which makes sure that for each individual, if there is a choice between making two rules classically satisfied for that individual, one always chooses the more preferred one.
While this semantics is very similar to ours, it is not ideal. Because it does not take care of cases where one has to decide between classically satisfying a less preferred rule for one individual or a more preferred one for another individual. This can be fixed simply by relaxing the constraint that defines the order on the models and replacing it as follows; I > J iff for all pairs (x; A v B) 2 SJ n SI there exists a pair (y; C v D) 2 SI n SJ , s.t. C v D A v B.
Note that the replacement of x with y in the existential quantification is the only difference. With this semantics, when one has to decide between satisfying different concept subsumptions for different individuals, one shall choose the one where the more preferred concept subsumption is fulfilled.
This preference relation is very similar to ours. The main difference is that in our proposal only named individuals can be exceptions. Indeed, if we restrict the definition of the support to the named individuals, then the preference relations are equivalent.
Heymans et. al. showed that under the Common Domain and Unique Name
Assumption [
Another framework introduced by Baader and Hollunder also gives the possibility
to specify a preference order on defaults. Their approach uses fixed points semantics
and gives similar results to those of Heyman et. al., in the sense that a default can only
be defeated for a certain individual by asserting a more preferred default for the same
individual [
Two other semantics, which also concern themselves with orders on defaults are
those of Bonatti et. al.’s DLN semantics [
We have shown that it is possible to extend the semantics of free defaults with a
preference order on the axioms, without losing decidability of both satisfiability and
entailment. Our semantics improves both the semantics of Sengupta et. al.[
It remains questionable whether these results generalise to larger and possibly more complex real-world examples. Another open problem on the foundational frontier is to find ways of handling ordered default knowledge bases that are not d-satisfiable, or that have more than one d-KB.
As a part of future work, it could be interesting to investigate which existing desirable properties our approach satisfies. Moreover, we need to carry out a fine-grained complexity theoretic analysis, supplemented with an empirical evaluation. This research agenda could make preferential default reasoning practically feasible on sizeable ontologies.