=Paper=
{{Paper
|id=Vol-1205/paper9
|storemode=property
|title=Similarity-based Relaxed Instance Queries in EL++
|pdfUrl=https://ceur-ws.org/Vol-1205/00010101.pdf
|volume=Vol-1205
|dblpUrl=https://dblp.org/rec/conf/cade/Ecke14
}}
==Similarity-based Relaxed Instance Queries in EL++==
https://ceur-ws.org/Vol-1205/00010101.pdf
Similarity-based Relaxed Instance Queries in
EL++
Andreas Ecke?
Theoretical Computer Science, TU Dresden
ecke@tcs.inf.tu-dresden.de
Abstract. Description Logic (DL) knowledge bases (KBs) allow to
express knowledge about concepts and individuals in a formal way.
This knowledge is typically crisp, i.e., an individual either is an in-
stance of a given concept or it is not. However, in practice this is often
too restrictive: when querying for instances, one may often also want
to find suitable alternatives, i.e., individuals that are not instances of
query concept, but could still be considered ‘good enough’. Relaxed
instance queries have been introduced to gradually relax this infer-
ence in a controlled way via the use of concept similarity measures
(CSMs). So far, those algorithms only work for the DL EL, which
has limited expressive power. In this paper, we introduce a suitable
CSM for EL++ -concepts. EL++ adds nominals, role inclusion axioms,
and concrete domains to EL. We extend the algorithm to compute
relaxed instance queries w.r.t. this new CSM, and thus to work for
general EL++ KBs.
1 Introduction
Description Logics (DLs) are a family of knowledge representation formalisms
widely used in AI to describe and reason about categories and objects (individu-
als) of an application domain [1]. Each DL has a set of concept constructors, that
allow to build complex concepts to formalize those categories, and are used in
axioms and assertions to define the relations between different concepts and in-
dividuals. The set of axioms and assertions that describe the terminological and
the assertional knowledge of the application domain, respectively, are collected
in the TBox and the ABox. Together, TBox and ABox form a DL knowledge
base (KB).
The formal semantics of DLs allows for the definition of reasoning services,
i.e., inferences that allow to compute implicit knowledge from that explicitly
described in the KB. Standard reasoning services include consistency of a KB,
subsumption tests between different concepts, and instance checking, which de-
rives whether an individual is an instance of a concept or not. Those reasoning
services have been implemented in many highly optimized DL systems. One DL
?
Supported by the German Research Foundation (DFG) Graduiertenkolleg 1763
(QuantLA).
that is especially interesting in terms of reasoning is EL; while quite restricted in
the constructors it offers, all the standard inferences can be implemented using
polynomial-time algorithms. EL has been extended to a maximal superset EL++
that still retains the favorable computational properties in [2, 3].
Since DLs are the underlying logics of the OWL ontology language and its
profiles (including OWL 2 EL, which is based on EL++ ) standardized by the
W3C, their usage has increased rapidly in many fields like the Semantic Web,
biomedical ontologies and more. By now, there is a large collection of different
KBs available written in those languages. However, for many applications, re-
trieving strict instances from these KBs is often too restrictive, as often one may
want to find suitable alternatives, even in cases where no individual completely
matches the query concept. Those alternatives may be individuals that are not
strict instances, but fulfill most of the requirement and are thus quite similar to
the query concept.
The reasoning services of relaxed instance queries has been introduced in [4].
This inference relaxes the instance retrieval problem to return more individuals
by the use of concept similarity measure (CSM). Given a CSM and a threshold
t, this inference will return all instances of concepts that have a similarity of at
least t to the query concept. Algorithms to compute relaxed instances have been
introduced for unfoldable and general EL-TBoxes in [4, 5].
However, the limited expressiveness of EL is often a problem; especially for
query answering, it is useful to be able to use concrete domains to describe quan-
titative aspects of individuals and use these for querying. For example, one can
use this to describe the geographic location of objects, the bandwidth of servers
or time points in measurement series and incorporate the similarity between
these values to find relaxed instances. Similarly, other features of EL++ , like
nominals, that allow to refer to specific individuals in concepts, role inclusions,
and domain and range restrictions can be very useful in practice.
In this paper, we will extend the problem of relaxed query answering to EL++ .
To do so, after formally defining EL++ and CSMs in Section 2, we introduce
pseudo-interpretations in Section 3, which can than be used to define simulations
and canonical models that correspond to the semantics of EL++ . In Section 4 we
define a parameterizable similarity measure on pointed pseudo-interpretations,
which can be lifted to EL++ -concepts using the canonical models. This CSM can
then be used to query for relaxed instances in general EL++ -KBs as shown in
Section 5. We conclude the paper in Section 6.
2 Preliminaries
This section will give a brief introduction to the DL EL++ and define concept
similarity measures and some of their properties.
2.1 The DL EL++
EL++ concepts are built from four countable, pairwise disjoint sets: The set NC
of concept names; the set NR of role names; the set NI of individual names; and
syntax usual semantics
concept name A AI ⊆ ∆I
top concept > > I = ∆I
bottom concept ⊥ ⊥I = ∅
nominal {o} {o}I = {oI }
conjunction C uD (C u D)I = C I ∩ DI
existential ∃r.C (∃r.C)I = {d ∈ ∆I | ∃e ∈ ∆I :
restriction (d, e) ∈ rI ∧ e ∈ C I }
concrete domain p(f1 , . . . , fn ) p(f1 , . . . , fn )I = {d ∈ ∆I |
(f1I (d), . . . , fnI (d)) ∈ pD }
GCI CvD C I ⊆ DI
role inclusion r1 ◦ · · · ◦ rn v s r1I ◦ · · · ◦ rnI ⊆ sI
domain restriction dom(r) v C r I ⊆ C I × ∆I
range restriction ran(r) v C rI ⊆ ∆I × C I
concept assertion C(a) aI ∈ C I
role assertion r(a, b) (aI , bI ) ∈ rI
Table 1. Concept constructors, TBox axioms, and ABox assertions for EL++
the set NF of feature names. Using the concept constructors given in the upper
part of Table 1, these names are used to construct complex concept descriptions.
The set of all EL++ -concept descriptions is denoted with C(EL++ ).
When formulating a knowledge domain in terms of DLs, one expresses all
classes of interest as (possibly complex) EL++ -concepts, and possible relations
between those classes as roles. The general knowledge about the classes can
then be formalized using the axioms given in the middle part of Table 1, while
the knowledge about specific objects can be expressed using concept and role
assertions of the form C(a) and r(a, b). The axioms and assertions are collected in
the TBox and ABox, respectively, which together form a knowledge base (KB).
EL++ allows the use of p-admissible concrete domains. Such a concrete do-
main D = (∆D , P D ) consist of a set of concrete values ∆D and a set of predi-
cates p ∈ P , each associated with an arity n > 0 and an extension pD ⊆ (∆D )n .
Features connect objects described by the DL to elements of the concrete do-
main. For example, using the concrete domain Q with ∆Q = Q the set of ra-
tional numbers and predicates P = {=, ≥p , =p } for p ∈ Q with the obvious
meanings, one can express that adults are persons that are at least 18 using
Adult v Person u ≥18 (age) or that Anna is 171 cm tall and her age is the same
as her shoe size: (=171 (height) u =(age, shoeSize))(anna).
P-admissible concrete domains in EL++ only allow for limited expressive-
ness, in order to retain tractability. Besides the obvious requirement that satis-
fiability and implication in these concrete domains must be decidable in poly-
nomial time, there are two other changes when compared to general concrete
domains: First, as there are no abstract features, predicates can only compare
features of a single element. This means that EL++ does not allow to express
Person v <(age, mother ◦ age) u <(age, father ◦ age), i.e., that every person is
younger than her parents. Second, the concrete domains need to be convex, i.e.,
if a set of predicates implies the disjunction of some predicates, then it must
also imply one of the disjuncts. This is a rather big restriction, but there still
exist useful p-admissible concrete domains, like those given in [2], which allow
to refer to rational numbers and strings. Indeed, we argue that for our purpose,
relaxed instance queries, for any set of concrete values ∆D , even a single unary
predicate =d for d ∈ ∆D to attach concrete values to individuals is useful.
Example 1. Consider the concrete domain G to represent geographic coordinates
as a pair of latitude and longitude, with ∆G = [−90, 90] × [−180, 180] ⊆ R × R
and the unary predicates =p for p ∈ ∆G . This allows a service provider to
describe the location of all its branch offices in the ABox using assertions like
(=(51.026,13.723) (location))(office1). If we construct the similarity measure used for
relaxing the queries in such a way that it assigns larger similarities to locations
closer together, an instance query which includes the predicate =l (location) for
the location of the user will try to find the closest branch offices that also match
the rest of the query. Indeed, one could also construct a similarity measure that
returns similarity 0 for locations more than a set distance away, allowing the
user to specify the maximum distance. Thus, while the concrete domain itself
is extremely inexpressive, it allows the relaxed instance queries to include the
distance between locations in its similarity evaluation.
Note that in this paper we restrict to a single concrete domain D, but it is
easy to generalize the similarity measure and the algorithms to compute relaxed
instance queries to handle multiple concrete domains at once. Also note that it is
possible to remove domain and range restrictions from the KB without changing
its semantics [3]. To do so, we can replace every domain restrictions dom(r) v C
with ∃r.> v C and for any range restrictions ran(r) v C, we replace all ∃r.D
occurring in the KB with ∃r.(C u D) and for any role assertion r(a, b) we add
D(b). Thus, in the remainder of this paper, we assume that KBs do not contain
any domain or range restrictions.
The semantics of EL++ -concepts is given by means of interpretations. An
interpretation I = (∆I , ·I ) is a tuple consisting of a domain ∆I and an interpre-
tation function ·I that assigns to each concept name C ∈ NC a subset C I ⊆ ∆I
of the the domain, to each role name r ∈ NR a binary relation rI ⊆ ∆I × ∆I ,
to each individual name a ∈ NI an element aI ∈ ∆I , and to each feature name
f ∈ NF a partial function f I : ∆I 9 ∆D . The interpretations can be extended
to complex EL-concepts as shown in the last column of Table 1.
Instead of viewing an interpretation I as a tuple of functions that assign
subsets, binary relations and elements of ∆I to the elements of NC , NR and NI ,
and partial functions to the elements of NF , one can also view it as a tuple of
functions
I : (∆I → P(NC ), ∆I → P(NR × ∆I ), ∆I → P(NI ), ∆I → NF 9 ∆D )
from the domain ∆I to a subset of NC (the concept names that this element is
an instance of), to a binary relation between NR and ∆I (the successors of the
element), to a subset of NI (the individual names that map to this element), and
to a partial function mapping feature names to concrete values, respectively. If we
require that each individual name occurs only once, this definition is equivalent
to the usual one.
2.2 Concept similarity measures
Given a EL++ -KB K, a concept similarity measure (CSM) is a function ∼K :
C(EL++ ) × C(EL++ ) → [0, 1] such that C ∼K C = 1 for all concepts C. In-
tuitively, a value C ∼K D = 0 means that the concepts C and D are totally
dissimilar w.r.t. K, while a value of 1 indicates total similarity. We often simply
write ∼ instead of ∼K if the KB K is clear from the context.
In [6] a set of properties for CSMs is defined. We extend the definition of
these properties to the case of general TBoxes.
Definition 1. A CSM ∼K : C(EL++ ) × C(EL++ ) → [0, 1] is:
symmetric iff C ∼K D = D ∼K C;
equivalence invariant iff for all C ≡K D it holds that C ∼K E = D ∼K E;
equivalence closed iff C ≡K D ⇐⇒ C ∼K D = 1;
bounded iff the existence of E 6≡K > with C vK E and D vK E implies C ∼K
D > 0; and
dissimilar closed iff C, D 6≡K > and there is no E 6≡K > with C vK E and
D vK E implies C ∼K D = 0.
These formally defined properties make CSMs more predictable for users. The
measures in [5–7] fulfill most of these properties. The measures from [5, 6] are
additionally parameterizable, which allows users to calibrate the measure to fit
their expectations. In our setting these parameterizable CSMs enable users to
specify which features of query concepts should be relaxed.
3 Pseudo-interpretations
Unlike in EL without concrete domains, the definition of interpretations for EL++
given in the last section does not admit canonical models. For example, in the
concrete domain of the rational numbers Q = (Q, P Q ) introduced before, a
concept like >0 (f ) will have infinitely many models (one for each positive rational
number) without any of them being preferable and therefore canonical. One way
to avoid this problem and ensure the existence of canonical models is to only
consider pseudo-interpretations.
These pseudo-interpretations differ from the usual interpretations in just the
fourth component: Instead of assigning each domain element a partial function
from the feature names to concrete elements, we simply assign to each element
directly a subset of the set of all predicates of D over the feature names, denoted
with PredD (NF ). In that way, each pseudo-interpretation corresponds to a set
of usual interpretations, namely all those whose concrete elements assigned to
the feature names of a domain element satisfy all the predicates mapped to the
domain element by the pseudo-interpretation.
Definition 2. A pseudo-interpretation J = (∆J , fCJ , fRJ , fIJ , fFJ ) consists of
an interpretation domain ∆J and the interpretation functions fCJ : ∆J →
P(NC ), fRJ : ∆J → P(NR × ∆J ), fIJ : ∆J → P(NI ), and fFJ : ∆J →
P(PredD (NF )), such that for each a ∈ NI there exists exactly one d ∈ ∆J with
a ∈ fIJ (d), and the conjunction
^
conj((J , d)) = p(f1 , . . . , fn )
J
p(f1 ,...,fn )∈fF (d)
is satisfiable in D for any d ∈ ∆J .
Pseudo-interpretations can be used exactly as usual interpretations, with
the exception that it does not interpret feature names itself; however, it does
interpret predicates of the concrete domain:
AJ = {d ∈ ∆J | A ∈ fCJ (d)}
rJ = {(d, e) ∈ ∆J × ∆J | (r, e) ∈ fRJ (d)}
aJ = d ⇐⇒ a ∈ fIJ (d)
p(f1 , . . . , fn )J = {d ∈ ∆J | D |= conj((J , d)) ⇒ p(f1 , . . . , fn )}
Any other concept constructors, axioms, and assertions can then be interpreted
as given in Table 1. We say that a pseudo-interpretation J is a model a KB K,
if it satisfies all axioms and assertions in K. This is the case if and only if all
corresponding usual interpretations are models of K.
We call a pair (J , d) consisting of a pseudo-interpretation J and an element
d ∈ ∆J a pointed pseudo-interpretation and denote the set of all pointed pseudo-
interpretations as P. We sometimes use fC (p) (and similarly for fR , fI and fF )
instead of fCJ (d) for p = (J , d).
3.1 Simulations
Simulations allow the characterization of elements of interpretations w.r.t. the
concepts they are instance of. To extend the simulation relation between in-
terpretations w.r.t. EL given in [8] to pseudo-interpretations w.r.t. EL++ , we
observe the following:
– role inclusions, range and domain restrictions are not concept constructors,
and thus do not matter for the set of concepts that an element of a pseudo-
interpretation is instance of;
– the bottom concept ⊥ can not occur in pseudo interpretations;
– nominals allow to use individual names in concepts, and thus simulations
need to preserve individuals; and
– for concrete domains, simulations need to preserve the valuations that sat-
isfy the elements, which can be formalized using implications between the
predicate sets of pointed pseudo-interpretations.
Thus, we can define a simulation relation for EL++ as follows:
Definition 3. Let J1 and J2 be pseudo-interpretations. A relation S ⊆ ∆J1 ×
∆J2 is a simulation between J1 and J2 , if the following conditions hold:
1. For all (d, e) ∈ S and A ∈ NC , if d ∈ AJ1 then e ∈ AJ2 .
2. For all (d, e) ∈ S, r ∈ NR and (d, d0 ) ∈ rJ1 , there is an (e, e0 ) ∈ rJ2 with
(d0 , e0 ) ∈ S.
3. For all (d, e) ∈ S and a ∈ NI , if d = aJ1 then e = aJ2 .
4. For all (d, e) ∈ S, we have that D |= conj((J2 , e)) ⇒ conj((J1 , d)).
Given two pointed pseudo-interpretations p = (J1 , d) and q = (J2 , e), we say
that p simulates q (denoted p . q), if there exists a simulation S ⊆ ∆J1 × ∆J2
between J1 and J2 with (d, e) ∈ S. p and q are equisimilar (denoted p ' q), if
p . q and q . p.
This definition of simulations is reasonable, as it corresponds with the set
of concepts that the elements in the simulation are instances of. Indeed, we can
extent the following result from [8] to simulations of pseudo-interpretations in
EL++ :
Theorem 1. Let p and q be pointed pseudo-interpretations, then:
1. p . q iff C(p) ⊆ C(q), and
2. p ' q iff C(p) = C(q).
3.2 Canonical models
Next, we need to define canonical models for EL++ . For these, the additional
axioms like role inclusions are important. However, if the concept C contains
the bottom concept ⊥, it must be equivalent to ⊥, and thus can not be instance
of any element in an interpretation – in particular, it does not have a canonical
model. Thus, by requiring that C is satisfiable w.r.t. K, we do not have to worry
about ⊥ at all.
Since individuals can be part of concepts via nominals, we need to take care
of the case that 2 individuals are equivalent, e.g. by the GCI {a} v {b}. In this
case, we cannot create two elements in the canonical interpretation for the two
concepts {a} and {b}, since this would not yield a model of the TBox anymore.
Instead, we need to take one representative for all equivalence classes of concepts
that are subsumed by the same individual:
[C] = {D ∈ C(EL++ ) | ∃a ∈ NI : K |= C v {a} ∧ K |= D v {a}}
Finally, we need the notion Sig(X) of the signature of X, i.e., the set of all con-
cept, role, individual and feature names occurring in X, and the notion sub(C)
and sub(K) of the set of all sub-concepts of C and all sub-concepts of concepts
occurring in K, respectively. Then, we can define canonical models as follows:
Definition 4. Let K be a satisfiable EL++ -KB and C ∈ C(EL++ ) be an EL++ -
concept with C 6≡K ⊥. The canonical model JC,K = (∆JC,K , fC , fR , fI , fF ) of C
w.r.t. K is a pseudo-interpretations defined as follows:
– ∆JC,K = {d[C] } ∪ {d[{a}] | a ∈ (Sig(K) ∪ Sig(C)) ∩ NI } ∪ {d[D] | ∃r.D ∈
sub(C) ∪ sub(K)},
and for all d[D] in ∆JC,K :
– fC (d[D] ) = {A ∈ NC | K |= D v A},
– fR (d[D] ) = {(r, d[E] ) ∈ NR × ∆JC,K | K |= D v ∃r.E},
– fI (d[D] ) = {a ∈ NI | K |= D v {a}}, and
– fF (d[D] ) = {p(f1 , . . . , fn ) ∈ PredD (NF ) | K |= D v p(f1 , . . . , fn )}.
It can be shown that the canonical model JC,K is indeed a model of the KB
K, and its elements d[D] are instances of the corresponding concept D, for all
d[D] ∈ ∆JC,K .
Lemma 1. Let K be a satisfiable EL++ -KB and C, D be EL++ -concepts with
C 6≡K ⊥. Then:
1. if d[D] ∈ ∆JC,K , then d[D] ∈ DJC,K , and
2. JC,K |= K.
Finally, it can be shown that the canonical model is indeed ‘canonical’, i.e.,
it can simulate all other models (and is thus least w.r.t. .):
Theorem 2. Let K be a satisfiable EL++ -KB and C, D be EL++ -concepts with
C 6≡K ⊥. Then:
1. for all pseudo-models J of K and all elements d ∈ ∆J it holds d ∈ C J iff
(JC,K , d[C] ) . (J , d),
2. for all pseudo-models J of K, all individuals a occurring in K, and all ele-
ments d ∈ ∆J it holds d = aJ iff (JK , d[{a}] ) . (J , d), and
3. C vK D iff d[C] ∈ DJC,K iff (JD,K , d[D] ) . (JC,K , d[C] ).
Those results, besides being needed to prove formal properties of the simi-
larity measure, show that canonical models are reasonably defined.
4 A Concept Similarity Measure for EL++
Similarly to [5], we will define the CSM via a similarity measure on pointed
pseudo-interpretations, by translating the concepts into interpretations by tak-
ing their canonical model. To define the similarity measure on pointed pseudo-
interpretations, we need a few basic ingredients:
– a primitive measure ∼prim : NC × NC ∪ NR × NR ∪ NI × NI → [0, 1] that
assigns a similarity value to each pair of concept names, role names, and
individual names,
– a weighting function g : NC ∪ NR ∪ NI ∪ NF → R>0 , which allows more im-
portant features of interpretations to contribute more to the final similarity
values than others,
– a similarity measure ∼D : ∆D × ∆D → [0, 1] on the concrete domain,
– a discounting factor w ∈ (0, 1), and a concrete domain factor c > 0.
We will extend the concrete similarity measure ∼D to handle undefined val-
ues, i.e., ∼D : (∆D ∪{⊥})×(∆D ∪{⊥}) → [0, 1] by setting ⊥ ∼D d = d ∼D ⊥ = 0
for d ∈ ∆D and ⊥ ∼D ⊥ = 1. This can be further extended to similarity on val-
uations, i.e., partial functions u, v : NF 9 ∆D , by computing the weighted
average of the similarity values for all features:
P
f ∈dom(u)∪dom(v) g(f ) · simD (u(f ), v(f ))
u ∼D v = P .
f ∈dom(u)∪dom(v) g(f )
Finally, we can define the similarity of conjunctions of predicates on the concrete
domain using a similar construction to the Hausdorff metric, where the valua-
tions u, v are restricted to those feature names occurring in fF (p) or fF (q):
!
simD (p, q) = min inf sup u ∼D v, inf sup u ∼D v
u|=conj(p) v|=conj(q) u|=conj(q) v|=conj(p)
All other things, i.e., concept names, successors, and individual names, can
be compared directly. For this, we introduce a new role r> and a new individual
a> , in case that a pointed pseudo-interpretation does not have any successors or
individuals, similarly to how > is used for concept names. Then we can define
for a pointed (pseudo-interpretation p:
fC (p) if fC (p) 6= ∅
– CN(p) = , the set of concept names of p,
{>} otherwise
(
fR (p) if fR (p) 6= ∅
– SC(p) = , the set of successors of p,
{(r> , d)} otherwise
(
fI (p) if fI (p) 6= ∅
– IN(p) = , the set of individuals of p.
{a> } otherwise
To compare how similar two pointed pseudo-interpretations are for these
aspects, we use pairings. A pairing P ⊆ X × Y between sets X and Y is a total
binary relation, where totality means that all elements x ∈ X and y ∈ Y occur
in some some tuple of P . For two pointed pseudo-interpretations p = (J1 , d) and
q = (J2 , e), we are mainly interested in the following pairings:
– PC (p, q) ⊆ P((CN(p) × CN(q)) \ {(>, >)}) is the set of all concept name
pairings on the concepts that p and q are instance of.
– PS (p, q) ⊆ P((SC(p) × SC(q)) \ {((r> , d), (r> , e))}) is the set of all successor
pairings of p and q.
– PI (p, q) ⊆ P((IN(p) × IN(q)) \ {(a> , a> )}) is the set of all individual pairings
of p and q.
Using these pairings, we can finally define the similarity measure ∼i for
pointed pseudo-interpretations. It works by averaging over the weighted simi-
larity of the pairs in the best concept name, successor, and individual pairings.
The similarity between pairs of successors is computed recursively. If at least
one of the pointed interpretations contain any predicates, the similarity between
these predicates as defined before is added, weighted with the concrete domain
factor c.
simC (pC ) + simS (pS ) + simI (pI ) + simF (p, q)
p ∼i q = max X X X
pC ∈PC (p,q) g(A, B) + g(r, s) + g(a, b) + gF (p, q)
pS ∈PS (p,q)
pI ∈PI (p,q) (A,B)∈pC ((r,d),(s,e))∈pS (a,b)∈pI
with:
X
simC (pC ) = g(A, B)(A ∼prim B),
(A,B)∈pC
X
simS (pS ) = g(r, s)(r ∼prim s)(w + (1 − w)(J1 , d) ∼i (J2 , e)),
((r,d),(s,e))∈pS
X
simI (pI ) = g(a, b)(a ∼prim b),
(a,b)∈pI
simF (p, q) = gF (p, q) · simD (p, q),
(
c if fF (p) 6= ∅ ∨ fF (q) 6= ∅
gF (p, q) = .
0 otherwise
Since ∼i can be seen as a contraction mapping on the similarity values be-
tween all elements of J1 and J2 , the Banach fixed-point theorem will yield the
following result:
Theorem 3. ∼i is well-defined, i.e., p ∼i q has a unique solution.
This definition of ∼i is not equivalence invariant and equisimulation closed.
In order to regain these properties, we need to normalize the pointed pseudo-
interpretations before evaluating ∼i . We say that an pseudo-interpretation J is
in normal form if there are no elements a, b, c ∈ ∆J with {(a, b), (a, c)} ∈ rJ
and (J , b) . (J , c), i.e., no node has two successor nodes for the same role name
that are in a simulation relation.
Any pseudo-interpretation J can be transformed into normal form as follows:
1. remove all edges (a, b) ∈ rJ from J , for which there exists an edge (a, c) ∈ rJ
such that (J , b) . (J , c) but not (J , b) ' (J , c);
2. for all edges (a, b0 ) ∈ rJ , check if there are other edges (a, bi ) ∈ rJ , i > 0,
with (J , b0 ) ' (J , bi ) and choose one representative bj ; then remove all
other edges (a, bi ), i 6= j, from rJ .
Finally, we can define the CSM ∼c for concept descriptions w.r.t. an EL++
KB K as follows:
0 0
C ∼c D = (JC,K , d[C] ) ∼i (JD,K , d[D] ),
0 0
where JC,K and JD,K are the normalized canonical models of C and D w.r.t. K.
If C or D are equivalent to ⊥, they do not have a canonical model. In this case,
we set C ∼c ⊥ = ⊥ ∼c D = 0 for C, D 6≡K ⊥. ∼c has all of the properties given
in Definition 1:
Theorem 4. The CSM ∼c is symmetric, bounded, dissimilar closed, equivalence
invariant, and equivalence closed.
5 Relaxed instance queries w.r.t. ∼c
We established in [5] that in order to compute the maximal similarity between a
query concept C and all concepts that an individual a is instance of, it is enough
to check all generalized concepts of the msc of a, or in terms of ∼i : It is enough to
0
compute the maximal similarity (JC,K , d[C] ) ∼i q for all pointed interpretations
(J>,K , d[{a}] ) . q. This can also be achieved by using (J>,K , d[{a}] ) directly
in the computation of the ∼i and allowing to generalize this pointed pseudo-
interpretations, i.e. finding the best subsets of fC , fR , and fI , and taking the
best set of predicates that follow from fF .
Since fC , fR and fI are finite, finding the best subsets is always possible by
checking all of them. However, there can be infinitely many predicate sets fol-
lowing from fF . Note that in order to maximize simconc (p, q), generalizing q can
always increase the left part of simconc (p, q), inf u|=conj(p) supv|=conj(q) simD (u, v),
to a value of 1, by simply taking the empty set of predicates (which has all
valuations as model), but it can never increase the right part. Thus, the max-
imal value for simconc (p, q) that can be achieved by generalizing q is simply
inf u|=conj(q) supv|=conj(p) simD (u, v).
Procedure: maxsim (J1 , J2 , ∼prim , ∼D , g, w, c)
Input: J1 , J2 : finite pseudo-interpretations; ∼prim : primitive measure; ∼D : similarity
measure on D; g: weighting function; w ∈ (0, 1): discount factor; c > 0: concrete
domain factor
Output: maximal similarities between p = (J1 , a) and all generalizations of q = (J2 , b)
1: msim0 (d, e) ← 0 for all d ∈ ∆J1 and e ∈ ∆J2
2: for i ← 1, 2, 3, . . . do
3: for all d ∈ ∆J1 and e ∈ ∆J2do
4: msimi (d, e) ← max max similarity(pC , pS , pI , d, e, i)
SCN ⊆CN(e) pC ⊆CN(d)×SCN
SSC ⊆SC(e) pS ⊆SC(d)×SSC
SIN ⊆IN(e) pI ⊆IN(d)×SIN
5: end for
6: end for
Procedure: similarity (pC , pS , pI , d, e, i)
P
1: sim(pC ) ← g(A, B)(A ∼prim B)
(A,B)∈pC
g(r, s)(r ∼prim s) (1 − w) + w · msimi−1 (p0 , q)
P
2: sim(pS ) ←
((r,p0 ),(s,q 0 ))∈pS
P
3: sim(pI ) ← g(a, b)(a ∼prim b)
(a,b)∈pI
4: gF ← c if fF (p) 6= ∅ ∨ fF (q) 6= ∅; gF ← 0 otherwise
sim(pC ) + sim(pS ) + sim(pI ) + gF (p, q) · inf sup u ∼D v
u|=conj(J2 ,e) v|=conj(J1 ,d)
5: return X X X
g(A, B) + g(r, s) + g(a, b) + gF (p, q)
(A,B)∈pC ((r,d),(s,e))∈pS (a,b)∈pI
Fig. 1. Algorithm to compute the maximal similarities between all elements of the finite
pseudo interpretation J1 and all generalizations of the finite pseudo interpretation J2 .
Procedure: relaxed-instances (Q, K, t, ∼prim , ∼D , g, w, c)
Input: Q: EL-concept; K = (T , A): EL++ -KB; t ∈ [0, 1]: threshold; ∼prim : primitive
measure; ∼D : concrete measure; g: weighting function; w ∈ (0, 1): discounting
factor; c > 0: concrete factor
Output: individuals a ∈ Relax∼ c
t (Q)
1: compute canonical models IQ,T and IK
2: maxsim(d, e) ← maxsim(JQ,K , J>,K , ∼prim , ∼D , g, w, c)
3: return {a ∈ NI ∩ Sig(K) | maxsim(d[Q] , d[{a}] ) > t}
Fig. 2. Algorithm to compute all relaxed instances of a query concept Q w.r.t. a knowl-
edge base K and threshold t.
The algorithm to compute the maximal similarities between elements of
a pseudo-interpretation J1 and all generalizations of elements of a pseudo-
interpretation J2 is shown in Figure 1. Using this, the algorithm to actually
compute all relaxed instances of a query concept Q w.r.t. ∼c and an EL++ -KB
K is conceptually quite easy, as it only needs to compute the maximal similar-
ities between Q and the individuals a ∈ K and check whether they are larger
than t. The algorithm is depicted in Figure 2.
The maxsimi values computed in the algorithm monotonically converge from
below to the maximal similarities between generalized concepts of the individ-
uals and the query concept. Thus, the algorithm is sound and complete in the
following sense:
Theorem 5. Let ∼c be the CSM derived from ∼i with the primitive measure
∼prim , concrete measure ∼D and factor c, weighting function g and discounting
factor w. Then the algorithm relaxed-instances is sound and complete:
1. Soundness: If a ∈ relaxed-instances(Q, K, t, ∼prim , ∼D , g, w, c) for a number
n of iterations, then a ∈ Relax∼ c
t (Q).
∼c
2. Completeness: If a ∈ Relaxt (Q), then there exists an i ∈ N such that for
n ≥ i iterations it holds that a ∈ relaxed-instances(Q, K, t, ∼prim , ∼D , g, w, c).
Note the the number of of iterations i needed in the completeness part of
Theorem 5 is not bounded. However, since the algorithm converges quite fast,
this should not be a problem in most practical applications.
6 Conclusions
In this paper we extended the concepts similarity measure for general TBoxes
introduced in [5] to the DL EL++ . Since concrete domains do not allow do
define canonical models for standard interpretations in EL++ , we defined pseudo-
interpretations, which correspond to a set of standard interpretations. This is
used to define a similarity measure on pointed pseudo-interpretations, which
is extended to concept descriptions w.r.t. a KB via the canonical models. We
use the proposed CSM for relaxed instance querying of EL++ KBs and give an
algorithm that computes all relaxed instances.
References
1. Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F., eds.:
The Description Logic Handbook: Theory, Implementation, and Applications. Cam-
bridge University Press, New York, NY, USA (2003)
2. Baader, F., Brandt, S., Lutz, C.: Pushing the EL envelope. In: Proceedings of
the Nineteenth International Joint Conference on Artificial Intelligence IJCAI-05,
Edinburgh, UK, Morgan-Kaufmann Publishers (2005)
3. Baader, F., Brandt, S., Lutz, C.: Pushing the el envelope further. In Clark, K.,
Patel-Schneider, P.F., eds.: In Proceedings of the OWLED 2008 DC Workshop on
OWL: Experiences and Directions. (2008)
4. Ecke, A., Peñaloza, R., Turhan, A.Y.: Towards instance query answering for con-
cepts relaxed by similarity measures. In Godo, L., Prade, H., Qi, G., eds.: Workshop
on Weighted Logics for AI (in conjunction with IJCAI’13), Beijing, China (2013)
5. Ecke, A., Peñaloza, R., Turhan, A.Y.: Answering instance queries relaxed by concept
similarity. In: Proceedings of the Fourteenth International Conference on Principles
of Knowledge Representation and Reasoning (KR’14), Vienna, Austria, AAAI Press
(2014) To appear.
6. Lehmann, K., Turhan, A.Y.: A framework for semantic-based similarity measures
for ELH-concepts. In del Cerro, L.F., Herzig, A., Mengin, J., eds.: Proc. of the
13th European Conf. on Logics in A.I. (JELIA 2012). Lecture Notes In Artificial
Intelligence, Springer (2012) 307–319
7. Suntisrivaraporn, B.: A similarity measure for the description logic EL with unfold-
able terminologies. In: 5th International Conference on Intelligent Networking and
Collaborative Systems (INCoS). (2013) 408–413
8. Lutz, C., Wolter, F.: Deciding inseparability and conservative extensions in the
description logic EL. Journal of Symbolic Computation 45(2) (2010) 194–228