We present a new method for detecting logical di erences between EL-terminologies extended with role inclusions, domain and range restrictions of roles using a hypergraph representation of ontologies. In this paper we consider di erences given by pairs consisting of a conjunctive query and of an ABox formulated over a vocabulary of interest. We de ne a simulation notion between such hypergraph representations and we show that the existence of simulations coincides with the absence of a logical di erence. To demonstrate the practical applicability of our approach, we evaluate a prototype implementation on large ontologies.
The aim of this paper is to propose and investigate a novel and coherent approach
to the logical di erence problem as introduced in [
Our approach is based on representing ontologies as hypergraphs and
computing simulations between them. Hypergraphs are a generalisation of graphs
with many applications in computer science and discrete mathematics. In
knowledge representation, hypergraphs have been used implicitly to de ne
reachabilitybased modules of ontologies [
In this paper we consider the conjunctive query di erence between ontologies
formulated as terminologies in the description logic E LHr, i.e. the extension of
E L with role inclusions and domain & range restrictions [
In this paper we develop an alternative approach for nding witnesses based
on checking for the existence of certain simulations between hypergraph
representations of ontologies. The detection of witnesses is performed by checking
for the existence of forward and backward simulations. The existence of such
simulations between hypergraphs characterises the fact that the corresponding
ontologies cannot be distinguished from each other with conjunctive queries, i.e.
no logical di erence exists. Our approach is unifying in the sense that the
existence of both types of witnesses can be characterised via graph-theoretic notions.
We focus on backward simulations only as checking for forward simulations is
similar to checking for simulations between canonical models [
The paper is organised as follows. After some preliminaries, we introduce a
hypergraph representation of E LHr-terminologies and the notion of a backward
simulation in hypergraphs. We show that the existence of backward simulations
corresponds to the absence of right-hand witnesses. A prototype
implementation of an algorithm that checks for the existence of both types of simulations
demonstrates that witnesses can typically be found at least as quickly as with the
previous tool CEX 2.5 [
This paper uses results from [
We start by brie y reviewing the description logic E L and its extensions E Lran,
E Lran;u;u with range restrictions, conjunctions of roles, and the universal role, as
well as concept subsumptions based on E Lran;u;u and E Lran. For a more detailed
introduction to description logics, we refer to [
Let NC and NR be countably in nite and disjoint sets of concept names and role names. The sets of E L-concepts C, E Lran-concepts D, E Lran;u;u-concepts E and the sets of E Lran;u;u-inclusions and E Lran-inclusions are built according to the following grammar rules:
C ::= > j A j C u C j 9r:C D ::= > j A j D u D j 9r:D j ran(r) E ::= > j A j E u E j 9r1 u : : : u rn:E j 9u:E ::= D v E j r v s ::= D v C j r v s where A 2 NC, r; r1; : : : ; rn; s 2 NR, n 1, and u 2= NR is the universal role. Concept inclusions of the form ran(r) v D are also called range restrictions, and those of the form dom(r) v D are termed domain restrictions, where dom(r) stands for 9r:>. A TBox is a nite set of inclusions, which are also called axioms.
An E LHr-terminology T is a TBox in which every axiom is of the form A v C, A C, r v s, ran(r) v C or dom(r) v C, where A is a concept name, C an E L-concept and no concept name occurs more than once on the left-hand side of an axiom.1
The semantics is de ned using interpretations I = ( I ; I ), where the domain I is a non-empty set, and I is a function mapping each concept name A to a subset AI of I , every role name r to a binary relation rI over I , and uI = I I . The extension CI of a concept C is de ned inductively as: (>)I := I , (C u D)I := CI \ DI , (9r1 u : : : u rn:C)I := f x 2 I j 9 y 2 CI : (x; y) 2 Tin=1 riI g, and (ran(r))I := fy 2 I j 9x : (x; y) 2 rI g.
An interpretation I satis es a concept C, an inclusion C v D or r v s if, respectively, CI 6= ;, CI DI , or rI sI . We write I j= ' if I satis es the axiom '. An interpretation I satis es a TBox T if I satis es all axioms in T ; in this case, we say that I is a model of T . An axiom ' follows from a TBox T , written T j= ', if for all models I of T , we have that I j= '.
To simplify the presentation we assume that terminologies do not contain axioms of the form A B or A > (after having removed multiple B or >-conjuncts) for concept names A and B. A terminology is acyclic if it can 1 A concept equation A
C stands for the inclusions A v C and C v A. be unfolded (i.e., the process of substituting concept names by their de nitions terminates). An E LHr-terminology T is normalised i it only contains axioms of the forms r v s, { ' v B1 u : : : u Bn, A v 9r:B, A v dom(r), and { A B1 u : : : u Bm, A 9r:B, where ' 2 fA; dom(s); ran(s)g, n 1, m 2, A; B; Bi are concept names, r; s roles names, and each conjunct Bi is non-conjunctive in T , i.e. there does not exist an axiom of the form Bi B10 u: : :uBm0 2 T for concept names B10; : : : ; Bm0 with m 2 (otherwise Bi is said to be conjunctive in T ).
Every E LHr-terminology T can be normalised in polynomial time such that
the resulting terminology is a conservative extension of T [
A signature is a nite set of symbols from NC and NR. The signature sig(') of a syntactic object ' is the set of concept and role names occurring in '. Note that sig(9u:C) = sig(C) for every concept C. The symbol is used as a subscript to a set of concepts or inclusions to denote that its elements only use symbols from , e.g., E L , E Lran, E LHr , etc.
The logical di erence between two terminologies for E Lran;u;u-inclusions as
query language is de ned as follows [
De nition 1 (Concept Inclusion Di erence). The E Lran;u;u-concept inclur-terminologies T1 and T2 w.r.t. a signature is the sion di erence between E LHran;u;u-inclusions ' such that T1 j= ' and T2 6j= '. set Di (T1; T2) of all E L
If the set Di (T1; T2) is not empty, then it typically contains in nitely many
concept inclusions. We make use of the primitive witnesses theorems from [
The set of all E Lran;u;u-concept inclusion di erence witnesses is de ned as
Wtn (T1; T2) = (roleWtn (T1; T2); lhsWtn (T1; T2); rhsWtn (T1; T2));
where the set roleWtn (T1; T2) consists of all role inclusions in Di (T1; T2), and
the sets lhsWtn (T1; T2) (NC \ ) [ f dom(r) j r 2 g [ f ran(r) j r 2 g
and rhsWtn (T1; T2) NC \ of left-hand and right-hand concept di erence
witnesses consist of the left-hand sides of the type- 2 inclusions in Di (T1; T2)
and the right-hand sides of type- 3 inclusions in Di (T1; T2), respectively.
Observe that the set Wtn (T1; T2) is nite. Consequently, it can be seen as a
succinct representation of the typically in nite set Di (T1; T2) in the sense that:
Di (T1; T2) = ; i Wtn (T1; T2) = (;; ;; ;) [
In this paper, we focus on right-hand witnesses in rhsWtn (T1; T2), i.e., only the inclusions of types 3 are relevant.
Our approach for detecting logical di erences is based on nding appropriate
simulations between the hypergraph representations of terminologies. The
hypergraph notion in this paper is such that the existence of certain simulations
between the ontology hypergraphs of terminologies T1 and T2 coincides with
lhsWtn (T1; T2) = ; and rhsWtn (T1; T2) = ;. For every concept name A 2
(or role name r 2 ), we verify whether A (or dom(r); ran(r)) belongs to
lhsWtn (T1; T2), or whether A is a member of rhsWtn (T1; T2). For the former,
we check for the existence of a forward simulation, and for the latter, for the
existence of a backward simulation between the ontology hypergraphs of T1 and T2.
In this paper we present backward simulations only. Checking for left-hand side
witnesses and for witnesses in roleWtn (T1; T2) using ontology hypergraphs can
be done similarly to [
We start with de ning ontology hypergraphs and we subsequently introduce the notion of a backward simulation between such hypergraphs. 3.1
We introduce a hypergraph representation of E LHr-terminologies. A directed hypergraph is a tuple G = (V; E ), where V is a non-empty set of nodes (or vertices), and E is a set of directed hyperedges of the form e = (S; S0), where S; S0 V. A node v 2 V is reachable in G from a set of nodes V0 V (written V0 G v) if v 2 V0, or there is a hyperedge e = (S; S0) 2 E such that v 2 S0 and every node in S is reachable from V0.
We now show how to represent terminologies as hypergraphs.
De nition 2 (Ontology Hypergraph). Let T be a normalised E LHr-terminology and let be a signature. The ontology hypergraph GT of T for is a directed hypergraph GT = (V; E ) de ned as follows:
V =f xA j A 2 NC \ (
[ sig(T )) g [ f xr; xdom(r); xran(r) j r 2 NR \ (
[ sig(T )) g; and E =f(fx`g; fxBi g) j ` ./ B1 u : : : u Bn 2 T ; ./ 2 fv; g;
` 2 NC [ f dom(s); ran(s) j s 2 NR gg [ f(fxAg; fxdom(r)g) j A v dom(r) 2 T or A ./ 9r:B 2 T ; ./ 2 fv; gg [ f(fxAg; fxr; xran(r)uBg); (fxran(r)uBg; fxBg);
(fxran(r)uBg; fxran(r)g) j A ./ 9r:B 2 T ; ./ 2 fv; gg [ f (fxr; xBg; fxAg) j A
9r:B 2 T g [ f (fxB1 ; : : : ; xBn g; fxAg) j A
B1 u : : : u Bn 2 T g [ f (fxdom(r)g; fxr; xran(r)g) j r 2 NR \ (
[ sig(T ) g
[ f(fxrg; fxsg); (fxdom(r)g; fxdom(s)g); (fxran(r)g; fxran(s)g) j r v s 2 T g
The ontology hypergraph GT = (V; E ) contains a node x` for every signature
symbol ` in and T .2 Additionally, we represent concepts of the form dom(r)
2 Note that, di erently to [
Example 1. Let T = fA 9r:X; X Y u Z; B v Z; ran(r) v Y g, and = fA; B; rg. The ontology hypergraph GT of T for can be depicted as follows. xran(t)
xZ xt xdom(t) xB xY xran(r) xX
xr xdom(r) xA xran(r)uX
In the following we introduce a relation !T on nodes xl; xl0 of an ontology hypergraph such that xl !T xl0 holds i T j= l v l0.
De nition 3. Let GT = (V; E ) be the ontology hypergraph of a normalised E LHr-terminology T for a signature . We de ne !T V V to be the smallest re exive and transitive relation closed under the following conditions: { x !T x0 if (fxg; fx0g) 2 E ; { x !T x0 if (fxg; fxr; xAg) 2 E , (fxs; xBg; fx0g) 2 E , xr !T xs, and xA !T xB; { x !T x0 if (fxB1 ; : : : ; xBm g; fx0g) 2 E and x !T xBi for every 1 i
It can be readily seen that the relation !T can be computed in polynomial time in the size of T . Note that !T does not coincide with the usual reachability notion in a hypergraph. 3.2
We introduce backward simulations between ontology hypergraphs whose existence coincides with the absence of right-hand witnesses. The simulations are de ned such that a node xA in GT1 is simulated by a node xA0 in GT2 i A0 is entailed in T2 by exactly the same E Lran-concepts that entail A in T1. To de ne backward simulations we need to take all the axioms into account that cause -concepts to entail a concept name. Axioms of the forms A 9r:B, A B1 u : : : u Bn, and ran(r) v A require special treatment, while it is more straightforward to deal with the other types of axioms. For the former, consider T1 = fA 9r:Xg, T2 = fA v 9r:>g, and = fA; rg. It holds that 3 These hyperedges are relevant for the forward simulation only.
Di (T1; T2) = ;. Observe that there does not exist an E Lran-concept that entails A in T1 as the concept name X is not entailed by any -concept in T . Thus, the node xA in GT1 should be simulated by the node xA in GT2 . To handle such cases, we want to characterise the entailment by an E Lran-concept in terms of (a special) reachability notion in ontology hypergraphs.
For a signature , let Ran = [ dom [ ran, where dom = f dom(t) j t 2 NR \ g and ran = f ran(t) j t 2 NR \ g are the sets consisting of concepts of the form dom(t) and ran(t) for every role name t in , respectively. De nition 4 ( Ran-Reachability). Let GT = (V; E ) be the ontology hypergraph of a normalised E LHr-terminology T for a signature . We set VRan = f x 2 V j x !T x for some 2 Ran g to be the set of nodes in GT that are reachable via !TRanfr-oremacahanboldeeinlaGbeTlleid with elements from Ran. We say that a node v 2 V is VRan GT v.
polynomial time w.r.t. the size of T .
Ran-reachable nodes can be identi ed in Example 2. Let T = fA 9r:X; X Y u Z; B v Z; ran(r) v Y g (cf. Ex. 1) and let = fB; rg. Then all the nodes are Ran-reachable in GT and we have that T j= 9r:B v A.
The following example demonstrates that the relation !T is not su cient to characterise entailment by E Lran-concepts in every case.
Example 3. Let T = fA 9r:X; X 9r:Bg and let = fA; B; rg. The nodes xA and xB are Ran-reachable in GT , T j= 9r:9r:B v A, but xB 6!T xA.
Ran-reachable nodes that we obtain.
Lemma 1. Let T be a normalised E LHr-terminology and let Then the following statements hold: be a signature. (i) xA 2 V is
T j= D v A; (ii) xs 2 V is Ran-reachable in GT i there is s0 2 NR \
Ran-reachable in GT i there is an E Lran-concept D such that such that T j= s0 v s.
For axioms of the form A B1 u : : : u Bn, we introduce the following
notion which associates with every node xA in a hypergraph GT a set of concept
names non-conj(xA) that are essential to entail A in T (cf. [
de ne { otherwise, let non-conjT (xA) = fxAg.
non-conjT (xA) = fxB1 ; : : : ; xBm g; 2 (i.e. A
B1 u : : : u Bm 2 T ), we
Note that for any concept name A in a normalised E LHr-terminology T the concept names B1; : : : ; Bm with non-conjT (xA) = fxB1 ; : : : ; xBm g are nonconjunctive in T .
We need to take special care of axioms of the form ran(r) v X as they might cause non-obvious entailments. Let T = fX B1 u B2; A 9r:Xg and = fA; B1; B2; rg. Then the -concept 9r:(B1uB2) entails A in T . If we add the axiom ran(r) v B1 to T , then already the -concept 9r:B2 (of smaller signature) is su cient to entail A in T . Intuitively, the conjunct B1 of X is already covered by ran(r) in the presence of the axiom ran(r) v B1 (as T j= ran(r) u B2 v X). To de ne backward simulations for axioms of the form A 9r:X, all axioms of the form ran(r) v Y need to be taken into account.
We will therefore de ne the notion of backward simulation using an additional parameter 2 C = f g [ (NR \ ), called the role context. Such a parameter stands for an expression of the form ran( ) in which a node x 2 V1 should be simulated by a node x0 2 V2. We treat as a special role name and set ran( ) = >.
Additionally, we say that a node y 2 V in an ontology hypergraph GT = (V; E ) is relevant for a node x in T w.r.t. a set of node labels L used in GT if y 2 non-conjT (x) and x` 6!T y for every ` 2 L.
We now give the de nition of backward simulations as subsets of V1 V2 C . De nition 6 (Backward Simulation). Let rG-Tt1er=min(Vol1o;gEie1s), TG1Ta2n=d T(2V2fo;Er2a) be the ontology hypergraphs of normalised E LH signature . A relation - V1 V2 C is a backward -simulation if the following conditions are satis ed: (ib) if (x; x0; ) 2 -, then for every 2 Ran: x !T1 x implies x !T2 y0 for every y0 2 V2 relevant for x0 in T2 w.r.t. fran( )g; (iib) if (x; x0; ) 2 -, (fxr; yg; fxg) 2 E1, and y is Ran-reachable in GT1 , then for every s 2 such that xs !T1 xr, and for every y0 2 V2 relevant for x0 in T2 w.r.t. fran( ); dom(s)g, there exists (fxr0 ; z0g; fy0g) 2 E2 with xs !T2 xr0 and (y; z0; s) 2 -; (iiib) if (x; x0; ) 2 - and (fxX1 ; : : : ; xXn g; fxg) 2 E1, then for every y0 2 V2 relevant for x0 w.r.t. fran( )g there exists y 2 V1 relevant for x in T1 w.r.t. fran( )g with (y; y0; ) 2 -.
We write GT1 - GT2 i there exists a backward such that (xA; xA; ) 2 - for every A 2 NC \ .
-simulation
V1
V2
C Members of a backward simulation - are called simulation triples.
For a node x in GT1 to be backward simulated by x0 in GT2 , Condition (ib) enforces that appropriate -concept names B or concepts of the form ran(s), dom(s) with s 2 that entail x in T1 must also entail x0 in T2. Condition (iib) applies to nodes xA 2 GT1 for which there exists an axiom A 9r:X in T1 and propagates the simulation to the successor node xX by taking into account possible entailments regarding domain or range restrictions in T2. Condition (iiib) handles axioms of the form A B1 u : : : u Bn in T1. We have to match every conjunct y0 that is relevant for x0 in T2 with some conjunct y relevant for x in T1 (possibly leaving some conjuncts y unmatched) since, intuitively speaking, some conjuncts in the de nition of A in T1 can be ignored to preserve logical entailment. For instance, let T1 = fA B1 u B2g, T2 = fB1 v Ag and = fA; B1; B2g. Then rhsWtn (T1; T2) = ; and, in particular, T2 j= B1 u B2 v A holds as well. Note that the simulation between conjuncts is propagated in the context only as all the conjuncts that are entailed by ran( ) have been ltered out already. Example 4. Let T1 = fA 9r:X; X Y u Z; B v Z; ran(r) v Y g (cf. Ex. 1), T2 = fA X u Y; X 9r:B; dom(s) v Y; r v sg, and = fA; B; rg.
It can be readily seen that the nodes xB, xY , xZ , and xX are Ran-reachable in GT1 . As only xB !T1 xB, we have that the node xB in GT1 can be simulated by the node xB in GT2 in the contexts and r. Similarly, as only xB !T1 xZ , the node xZ in GT1 can be simulated by the node xB in GT2 in the contexts and r. Hence, as non-conjT2 (xB) = fxBg and as xZ is relevant for xX in T1 w.r.t. fran(r)g, we have that xX in GT1 can be simulated by xB in GT2 in the context r. Finally, as non-conjT2 (xA) = fxX ; xY g and as only xX is relevant for xA in GT2 (due to xdom(r) !T2 xY ), we can conclude that the node xA in GT1 can be simulated by xA in GT2 in the contexts and r. Overall,
S = f (xA; xA; ) j 2 f ; rg g [ f (xB; xB; ) j 2 f ; rg g
[ f (xZ ; xB; ) j 2 f ; rg g [ f(xX ; xB; r)g is a backward -simulation between GT1 and GT2 such that (xA; xA; ) 2 S. Example 5. Let T1, T2, and be de ned as in Ex. 4. Now let T10 = T1 [fran(t) v Zg and 0 = [ ftg. We observe that xran(t) !T2 x0 does not hold for any node x0 2 GT20 , i.e., the node xZ in GT100 cannot be simulated by any node in GT20 (in any context) as Condition (ib) cannot be ful lled. Hence, the node xX in GT100 cannot be simulated by xB in GT100 in the context r as Condition (iiib) is violated. Thus, there cannot exist a backward -simulation such that xA in GT100 is simulated by xA in GT20 in the context as Condition (iib) cannot be ful lled.
We can now show that the existence of a backward simulation coincides with the absence of right-hand witnesses and that one can check in polynomial time whether backward simulations exist.
Theorem 1. Let T1; T2 be normalised ELHr-terminologies, and let nature. Then it holds that rhsWtn (T1; T2) = ; i GT1 - GT2 . be a sigTheorem 2. Let T1, T2 be normalised ELHr-terminologies and let be signature. Then it can be checked in polynomial time whether GT1 - GT2 holds.
So far we focused on nding concept names A contained in rhsWtn (T1; T2), which, together with the sets roleWtn (T1; T2) and lhsWtn (T1; T2), is su cient to decide the existence of a logical di erence between T1 and T2. However, in practical applications users may require concrete concept inclusions D v A SM09a SM09b SM09b SM10a SM09b SM10a SM09a SM09b
Time (s) - CEX 2.5 with ex.
Time (s) - Prototype
with ex. (or A v E) in Di (T1; T2) that correspond to a witness A. We note that such example concept inclusions (and also example conjunctive queries) can be constructed recursively from triples for which the simulation conditions failed. 4
To investigate the practical applicability of our simulation-based approach for
detecting right-hand witnesses, we implemented a prototype tool in OCaml that
is based on the CEX 2.5 tool [
In our experiments involving Snomed CT we used signatures composed of the intersection of the concept names in the two versions that were compared, together with the same 31 role names (including \RoleGroup") that were chosen at random initially (and which occur in every version). The results that we obtained are shown in Table 1. The rst two columns indicate which versions were used as ontologies T1 and T2. The next two columns then show the computation times (CPU time) required by CEX 2.5, with column four depicting the computation times if additionally examples illustrating the witnesses were computed. The last two columns then indicate the computation times of our prototype tool. The times required when additionally examples were computed are shown in the last column. One can see that in all the cases our prototype tool required less time to compute di erence witnesses (also together with example inclusions) than CEX 2.5. 4 More precisely, we rst extracted the ELHr-fragment of the NCI versions by removing up to 8% of the axioms which were not expressed in this fragment. 1000 Prototype
CEX2.5 )s 100 ( e m i T U PC 10 1
For each considered version of NCI, we computed conjunctive query witnesses for T1 = NCI and T2 = NCI +1 on signatures = sig(NCI ) \ sig(NCI +1), where + 1 denotes the successor version of , together with corresponding examples. The results that we obtained are depicted in Fig. 1. The computations are sorted chronologically along the x-axis according to the publication date of version NCI . Each pair of bars represents the computation times required by our prototype tool and by CEX 2.5, respectively, for one comparison. In the cases where only one bar is shown, the ontology T1 = NCI was cyclic and CEX 2.5 could not be used.
Generally speaking, both tools required longer computation times on more recent NCI versions than on older releases, which could be explained by the fact that the size of NCI versions increased with every new release. In the comparisons before version 10.03h our prototype tool could typically compute the witnesses and example inclusions faster than CEX 2.5. However, on later versions our new tool then required slightly longer computation times. One can also see that overall it took the longest time to compute witnesses for cyclic versions of NCI.
Finally, we note that in our experiments all the computations required at most 2.85 GiB of main memory. 5
We presented a unifying approach to solving the logical di erence problem for possibly cyclic E LHr-terminologies. We showed that the existence of backward simulations in hypergraph representations of terminologies corresponds to the absence of right-hand witnesses (an analogous correspondence exists between forward simulations and left-hand witnesses). We also demonstrated the applicability of the hypergraph approach using a prototype implementation. The experiments showed that in most cases our prototype tool outperformed the previous tool, CEX 2.5, for computing the logical di erence. Moreover, our prototype tool could be successfully applied on fairly large cyclic terminologies, whereas previous approaches only worked for acyclic (or rather small cyclic) terminologies.
We plan to further improve our prototype implementation. Moreover, extensions of our techniques to DL-Lite, general E LHr-TBoxes, or even Horn-SHIQ ontologies could be investigated.