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 instance 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 nd 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 inference 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.
Description Logics (DLs) are a family of knowledge representation formalisms
widely used in AI to describe and reason about categories and objects
(individuals) of an application domain [
The formal semantics of DLs allows for the de nition 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 di erent concepts, and instance checking, which
derives 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 o ers, 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 [
Since DLs are the underlying logics of the OWL ontology language and its pro les (including OWL 2 EL, which is based on EL++) standardized by the W3C, their usage has increased rapidly in many elds like the Semantic Web, biomedical ontologies and more. By now, there is a large collection of di erent KBs available written in those languages. However, for many applications, retrieving strict instances from these KBs is often too restrictive, as often one may want to nd suitable alternatives, even in cases where no individual completely matches the query concept. Those alternatives may be individuals that are not strict instances, but ful ll most of the requirement and are thus quite similar to the query concept.
The reasoning services of relaxed instance queries has been introduced in [
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 quantitative 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 nd relaxed instances. Similarly, other features of EL++, like nominals, that allow to refer to speci c 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 de ning EL++ and CSMs in Section 2, we introduce pseudo-interpretations in Section 3, which can than be used to de ne simulations and canonical models that correspond to the semantics of EL++. In Section 4 we de ne 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 de ne 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 concept name top concept bottom concept nominal conjunction existential restriction syntax A > ? fog C u D 9r:C concrete domain 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 speci c 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 domain D = ( D; P D) consist of a set of concrete values D and a set of predicates p 2 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 domain. For example, using the concrete domain Q with Q = Q the set of rational numbers and predicates P = f=; p; =pg for p 2 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
expressiveness, in order to retain tractability. Besides the obvious requirement that
satisability and implication in these concrete domains must be decidable in
polynomial 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 [
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 [
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 interpretation function I that assigns to each concept name C 2 NC a subset CI I of the the domain, to each role name r 2 NR a binary relation rI I I , to each individual name a 2 NI an element aI 2 I , and to each feature name f 2 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 de nition is equivalent to the usual one. 2.2
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. Intuitively, 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 [
De nition 1. A CSM K : C(EL++) C(EL++) ! [0; 1] is: symmetric i C K D = D K C; equivalence invariant i for all C K D it holds that C K E = D K E; equivalence closed i C K D () C K D = 1; bounded i the existence of E 6 K > with C vK E and D vK E implies C K
D > 0; and dissimilar closed i 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 de ned properties make CSMs more predictable for users. The
measures in [5{7] ful ll most of these properties. The measures from [
Pseudo-interpretations Unlike in EL without concrete domains, the de nition 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 in nitely 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 di er 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.
De nition 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 2 NI there exists exactly one d 2 J with a 2 fIJ (d), and the conjunction conj((J ; d)) =
^ p(f1;:::;fn)2fFJ (d) is satis able in D for any d 2
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 = fd 2
J j A 2 fCJ (d)g rJ = f(d; e) 2
J
J j (r; e) 2 fRJ (d)g aJ = d ()
a 2 fIJ (d) p(f1; : : : ; fn)J = fd 2
J j D j= conj((J ; d)) ) p(f1; : : : ; fn)g 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 satis es 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 2 J a pointed pseudo-interpretation and denote the set of all pointed pseudointerpretations 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 allow the characterization of elements of interpretations w.r.t. the
concepts they are instance of. To extend the simulation relation between
interpretations w.r.t. EL given in [
Thus, we can de ne a simulation relation for EL++ as follows: De nition 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) 2 S and A 2 NC , if d 2 AJ1 then e 2 AJ2 . 2. For all (d; e) 2 S, r 2 NR and (d; d0) 2 rJ1 , there is an (e; e0) 2 rJ2 with (d0; e0) 2 S. 3. For all (d; e) 2 S and a 2 NI , if d = aJ1 then e = aJ2 . 4. For all (d; e) 2 S, we have that D j= 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) 2 S. p and q are equisimilar (denoted p ' q), if p . q and q . p.
This de nition 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 [
Next, we need to de ne 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 satis able 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 fag v fbg. In this case, we cannot create two elements in the canonical interpretation for the two concepts fag and fbg, 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] = fD 2 C(EL++) j 9a 2 NI : K j= C v fag ^ K j= D v fagg Finally, we need the notion Sig(X) of the signature of X, i.e., the set of all concept, 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 de ne canonical models as follows: De nition 4. Let K be a satis able EL++-KB and C 2 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 de ned as follows: { JC;K = fd[C]g [ fd[fag] j a 2 (Sig(K) [ Sig(C)) \ NI g [ fd[D] j 9r:D 2 sub(C) [ sub(K)g, and for all d[D] in JC;K : { fC (d[D]) = fA 2 NC j K j= D v Ag, { fR(d[D]) = f(r; d[E]) 2 NR JC;K j K j= D v 9r:Eg, { fI (d[D]) = fa 2 NI j K j= D v fagg, and { fF (d[D]) = fp(f1; : : : ; fn) 2 PredD(NF ) j K j= D v p(f1; : : : ; fn)g. d[D] 2
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
JC;K .
Lemma 1. Let K be a satis able EL++-KB and C; D be EL++-concepts with C 6 K ?. Then: 1. if d[D] 2 JC;K , then d[D] 2 DJC;K , and 2. JC;K j= 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 satis able 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 2 J it holds d 2 CJ i (JC;K; d[C]) . (J ; d), 2. for all pseudo-models J of K, all individuals a occurring in K, and all elements d 2 J it holds d = aJ i (JK ; d[fag]) . (J ; d), and 3. C vK D i d[C] 2 DJC;K i (JD;K; d[D]) . (JC;K; d[C]).
Those results, besides being needed to prove formal properties of the similarity measure, show that canonical models are reasonably de ned. 4
A Concept Similarity Measure for EL++
Similarly to [
We will extend the concrete similarity measure D to handle unde ned values, i.e., D: ( D [f?g) ( D [f?g) ! [0; 1] by setting ? D d = d D ? = 0 for d 2 D and ? D ? = 1. This can be further extended to similarity on valuations, i.e., partial functions u; v : NF 9 D, by computing the weighted average of the similarity values for all features: u
D v =
Pf2dom(u)[dom(v) g(f ) simD(u(f ); v(f ))
Pf2dom(u)[dom(v) g(f ) : Finally, we can de ne the similarity of conjunctions of predicates on the concrete domain using a similar construction to the Hausdor metric, where the valuations u, v are restricted to those feature names occurring in fF (p) or fF (q): simD(p; q) = min
inf sup uj=conj(p) vj=conj(q) u
D v;
inf sup uj=conj(q) vj=conj(p) u
D v ! { CN(p) = { SC(p) = (fR(p) (
f(r>; d)g
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 de ne for a pointed pseudo-interpretation p: ( fC (p) if fC (p) 6= ; , the set of concept names of p, f>g otherwise if fR(p) 6= ; , the set of successors of p, otherwise { IN(p) = fI (p) if fI (p) 6= ; , the set of individuals of p.
fa>g 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 2 X and y 2 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)) n f(>; >)g) 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)) n f((r>; d); (r>; e))g) is the set of all successor pairings of p and q. { PI (p; q) P((IN(p) IN(q)) n f(a>; a>)g) is the set of all individual pairings of p and q.
Using these pairings, we can nally de ne the similarity measure i for pointed pseudo-interpretations. It works by averaging over the weighted similarity 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 de ned before is added, weighted with the concrete domain factor c.
max pC2PC(p;q) pS2PS(p;q) pI 2PI (p;q) (A;B)2pC simC (pC ) + simS (pS ) + simI (pI ) + simF (p; q) X g(A; B) +
X g(r; s) +
X g(a; b) + gF (p; q) ((r;d);(s;e))2pS (a;b)2pI with: simC (pC ) = simS (pS ) = simI (pI ) =
X (A;B)2pC
X ((r;d);(s;e))2pS
X (a;b)2pI g(A; B)(A
prim B); g(a; b)(a
prim b); g(r; s)(r prim s)(w + (1 w)(J1; d) i (J2; e)); simF (p; q) = gF (p; q) simD(p; q); gF (p; q) = (c if fF (p) 6= ; _ fF (q) 6= ; :
0 otherwise
Since i can be seen as a contraction mapping on the similarity values between all elements of J1 and J2, the Banach xed-point theorem will yield the following result:
i is well-de ned, i.e., p
i q has a unique solution.
This de nition of i is not equivalence invariant and equisimulation closed. In order to regain these properties, we need to normalize the pointed pseudointerpretations before evaluating i. We say that an pseudo-interpretation J is in normal form if there are no elements a; b; c 2 J with f(a; b); (a; c)g 2 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) 2 rJ from J , for which there exists an edge (a; c) 2 rJ such that (J ; b) . (J ; c) but not (J ; b) ' (J ; c); 2. for all edges (a; b0) 2 rJ , check if there are other edges (a; bi) 2 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 de ne the CSM c for concept descriptions w.r.t. an EL++ KB K as follows:
C
c D = (JC0 ;K; d[C]) i (J D0;K; d[D]); where JC0 ;K and J D0;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 De nition 1: Theorem 4. The CSM c is symmetric, bounded, dissimilar closed, equivalence invariant, and equivalence closed.
Relaxed instance queries w.r.t.
c
We established in [
Since fC , fR and fI are nite, nding the best subsets is always possible by checking all of them. However, there can be in nitely many predicate sets following from fF . Note that in order to maximize simconc(p; q), generalizing q can always increase the left part of simconc(p; q), infuj=conj(p) supvj=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 maximal value for simconc(p; q) that can be achieved by generalizing q is simply infuj=conj(q) supvj=conj(p) simD(u; v).
Procedure: maxsim (J1; J2; prim; D; g; w; c) Input: J1; J2: nite pseudo-interpretations; prim: primitive measure; D: similarity measure on D; g: weighting function; w 2 (0; 1): discount factor; c > 0: concrete domain factor Output: maximal similarities between p = (J1; a) and all generalizations of q = (J2; b) J2 1: msim0(d; e) 0 for all d 2 J1 and e 2 2: for i 1; 2; 3; : : : do 3: for all d 2 J1 and e 2 J2 do 4: msimi(d; e) max max similarity(pC ; pS; pI ; d; e; i) SSCSNC CSCN((ee)) ppCS CSCN((dd)) SSSCCN
SIN IN(e) pI IN(d) SIN 5: end for 6: end for 1: compute canonical models IQ;T and IK 2: maxsim(d; e) maxsim(JQ;K; J>;K; prim; D; g; w; c) 3: return fa 2 NI \ Sig(K) j maxsim(d[Q]; d[fag]) > tg Fig. 2. Algorithm to compute all relaxed instances of a query concept Q w.r.t. a knowledge 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 pseudointerpretation 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 similarities between Q and the individuals a 2 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 individuals 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 2 relaxed-instances(Q; K; t; prim; D; g; w; c) for a number n of iterations, then a 2 Relaxt c (Q). 2. Completeness: If a 2 Relaxt c (Q), then there exists an i 2 N such that for n i iterations it holds that a 2 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 [