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 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 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 [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 individuals. 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 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 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, retrieving 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 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 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.
This section will give a brief introduction to the DL EL ++ and define concept similarity measures and some of their properties. 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 domain D = (∆ D , P D ) consist of a set of concrete values ∆ D and a set of predicates p ∈ P , each associated with an arity n > 0 and an extension p D ⊆ (∆ 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 = {=, ≥ p , = p } for p ∈ Q with the obvious meanings, one can express that adults are persons that are at least 18 using Adult Person ≥ 18 (age) or that Anna is 171 cm tall and her age is the same as her shoe size: (= 171 (height) =(age, shoeSize))(anna).
P-admissible concrete domains in EL ++ only allow for limited expressiveness, in order to retain tractability. Besides the obvious requirement that satisfiability 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 <(age, mother • age) <(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
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) C with ∃r.
C and for any range restrictions ran(r) C, we replace all ∃r.D occurring in the KB with ∃r.(C 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 interpretation function • I that assigns to each concept name C ∈ N C a subset C I ⊆ ∆ I of the the domain, to each role name r ∈ N R a binary relation r I ⊆ ∆ I × ∆ I , to each individual name a ∈ N I an element a I ∈ ∆ I , and to each feature name f ∈ N F a partial function f I : ∆ I ∆ 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 N C , N R and N I , and partial functions to the elements of N F , one can also view it as a tuple of functions
from the domain ∆ I to a subset of N C (the concept names that this element is an instance of), to a binary relation between N R and ∆ I (the successors of the element), to a subset of N I (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.
Given a EL ++ -KB K, a concept similarity measure (CSM) is a function
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 [6] a set of properties for CSMs is defined. We extend the definition of these properties to the case of general TBoxes.
and there is no
These formally defined properties make CSMs more predictable for users. The measures in [5][6][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.
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 Pred D (N F ). 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.
consists of an interpretation domain ∆ J and the interpretation functions f J C : ∆ J → P(N C ), f J R : ∆ J → P(N R × ∆ J ), f J I : ∆ J → P(N I ), and f J F : ∆ J → P(Pred D (N F )), such that for each a ∈ N I there exists exactly one d ∈ ∆ J with a ∈ f J I (d), and the conjunction conj((J , d)) = p(f1,...,fn)∈f J F (d)
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:
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 pseudointerpretations as P. We sometimes use f C (p) (and similarly for f R , f I and f F ) instead of f J C (d) for p = (J , d).
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 [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 pseudointerpretation 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 satisfy 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 J 1 and J 2 be pseudo-interpretations. A relation S ⊆ ∆ J1 × ∆ J2 is a simulation between J 1 and J 2 , if the following conditions hold: 1. For all (d, e) ∈ S and Given two pointed pseudo-interpretations p = (J 1 , d) and q = (J 2 , e), we say that p simulates q (denoted p q), if there exists a simulation S ⊆ ∆ J1 × ∆ J2 between J 1 and J 2 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).
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} {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:
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 define canonical models as follows:
It can be shown that the canonical model J C,K is indeed a model of the KB K, and its elements d [D] are instances of the corresponding concept D, for all
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 ≡ K ⊥. Then: 1. for all pseudo-models J of K and all elements d ∈ ∆
for all pseudo-models J of K, all individuals a occurring in K, and all elements d ∈ ∆ J it holds d = a J iff (J K , d [{a}] ) (J , d), and 3.
Those results, besides being needed to prove formal properties of the similarity measure, show that canonical models are reasonably defined.
Similarly to [5], we will define the CSM via a similarity measure on pointed pseudo-interpretations, by translating the concepts into interpretations by taking their canonical model. To define the similarity measure on pointed pseudointerpretations, we need a few basic ingredients:
a primitive measure ∼ prim :
that assigns a similarity value to each pair of concept names, role names, and individual names, a weighting function g :
.
Finally, we can define the similarity of conjunctions of predicates on the concrete domain using a similar construction to the Hausdorff metric, where the valuations u, v are restricted to those feature names occurring in f F (p) or f F (q): sim D (p, q) = min inf
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:
, the set of successors of p,
, the set of individuals of p.
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 = (J 1 , d) and q = (J 2 , e), we are mainly interested in the following pairings:
-P C (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. -P S (p, q) ⊆ P((SC(p) × SC(q)) \ {((r , d), (r , e))}) is the set of all successor pairings of p and q. -P I (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 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 defined before is added, weighted with the concrete domain factor c. p ∼ i q = max p C ∈P C (p,q) p S ∈P S (p,q) p I ∈P I (p,q) sim C (p C ) + sim S (p S ) + sim I (p I ) + sim F (p, q) sim F (p, q) = g F (p, q) • sim D (p, q), g F (p, q) = c if f F (p) = ∅ ∨ f F (q) = ∅ 0 otherwise .
Since ∼ i can be seen as a contraction mapping on the similarity values between all elements of J 1 and J 2 , 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 pseudointerpretations 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)} ∈ r J 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) ∈ r J from J , for which there exists an edge (a, c) ∈ r J such that (J , b) (J , c) but not (J , b) (J , c); 2. for all edges (a, b 0 ) ∈ r J , check if there are other edges (a, b i ) ∈ r J , i > 0, with (J , b 0 ) (J , b i ) and choose one representative b j ; then remove all other edges (a, b i ), i = j, from r J . Finally, we can define the CSM ∼ c for concept descriptions w.r.t. an EL ++ KB K as follows:
Supported by the German Research Foundation (DFG) Graduiertenkolleg 1763 (QuantLA).
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 compute the maximal similarity (J C,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 pseudointerpretations, i.e. finding the best subsets of f C , f R , and f I , and taking the best set of predicates that follow from f F .
Since f C , f R and f I are finite, finding the best subsets is always possible by checking all of them. However, there can be infinitely many predicate sets following from f F . Note that in order to maximize sim conc (p, q), generalizing q can always increase the left part of sim conc (p, q), inf u|=conj(p) sup v|=conj(q) sim D (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 sim conc (p, q) that can be achieved by generalizing q is simply inf u|=conj(q) sup v|=conj(p) sim D (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)
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) The algorithm to compute the maximal similarities between elements of a pseudo-interpretation J 1 and all generalizations of elements of a pseudointerpretation J 2 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 ∈ K and check whether they are larger than t. The algorithm is depicted in Figure 2.
The maxsim i 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 ∈ relaxed-instances(Q, K, t, ∼ prim , ∼ D , g, w, c) for a number n of iterations, then a ∈ Relax ∼c t (Q). 2. Completeness: If a ∈ Relax ∼c t (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.
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 pseudointerpretations, 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.