In this extended abstract we report on results recently achieved for answering instance queries relaxed by concept similarity measures [4]. Traditionally, Description Logic (DL) reasoning systems only support crisp inference services, like subsumption and instances queries. The latter can be e ectively used to perform di erent types of search tasks: Given an ABox describing a set of individuals, an instance query returns all those that are instance of the query concept Q, rejecting all others. However, often it is also interesting to consider those individuals that are not instances: Are they completely di erent to Q or how similar are they to Q? In cases where the original query does not retrieve any resulting individuals, those individuals that are `very close' to being an instance can still be a good alternative. The instance queries that do not only return the instances but also those that nearly match the query concept are called relaxed instance queries [3]. A natural way to relax instance queries is by using concept similarity measures (CSMs). Such a measure is a function that assigns to each pair of concepts a similarity value between 0 and 1. Together with a xed threshold t, the instance query can be relaxed by returning all individuals that are instance of a concept with a similarity value of at least t to the query concept w.r.t. . One advantage of using CSMs as a parameter for this inference is that they can implement di erent notions of similarity, and regard certain features more important than others. This allows to relax queries with respect to certain features, but leave others xed (compare Figure 1). Example 1. Mary likes cats [7] and has a few of them as pets. As such, her view on the similarity between other animals and cats is highly in uenced by how these animals behave as pets. A dog which lives inside the house, which likes getting stroked and begs for food is more similar to a cat than a wild lion in Africa. Or more formally put: Mary's view on similarity can be expressed by a CSM Mary, which weights features related to keeping animals as a pet higher than other features and therefore yields: (Cat Mary Dog) > (Cat Mary Lion). Jane, Mary's best friend, is a biologist and her view on the similarity of animals is characterized by the anatomy and evolution of animals and thus resembles the biological taxonomy of animals. As such, Jane nds lions are more similar to cats than dogs, since both cats and lions belong to the felidae family,
? Supported by DFG Graduiertenkolleg 1763 (QuantLA).
?? Partially supported by DFG within the Cluster of Excellence `cfAED' ? ? ? Partially supported by the German Research Foundation (DFG) in the Collaborative Research Center 912 \Highly Adaptive Energy-E cient Computing". QI; M(Q; a)I
M(Q; b)I b whereas dogs belong to the canidae family. Again, if we express her view on similarity as a CSM Jane, it incorporates mainly features related to the anatomy and evolution of animals and thus yields (Cat Jane Lion) > (Cat Jane Dog).
The CSMs Mary and Jane can be used to query a knowledge base describing di erent animals. If Mary is looking for a new pet and speci es its properties as an instance query, then using Mary yields more useful results than Jane, as Mary would rather keep a dog than a lion. Whereas, if Jane nds an animal unknown to her and wants to identify its species, a query using Jane's CSM
Jane yields better results.
We consider the Description Logic EL and distinguish between two kinds of
TBoxes: unfoldable TBoxes, which are acyclic and only contain concept de
nitions A C and general TBoxes which contain (possibly cyclic) GCIs C v D.
ABoxes, knowledge bases, the semantics via interpretations I, and common
inferences, are de ned as usual [
Let C(EL) be the set of all EL-concept descriptions. A concept similarity
measure T w.r.t. a TBox T is a function T : C(EL) C(EL) ! [0; 1], where
C T C = 1 for all concepts C 2 C(EL). Several properties of CSMs have been
formalized in [
The case of unfoldable TBoxes. To perform relaxed instance querying compute
for each individual a in the ABox a concept that has a as an instance and
resembles C most w.r.t. T . We call this the mimic of C w.r.t. a and T , and
denote it by M(C; a); see Figure 2. If M(Q; a) T Q t holds, then a is a
relaxed instance of Q; otherwise, it cannot be a relaxed instance, as no concept
can have a greater similarity value with Q while still containing a. In [
l A A2NC
X u 9r:B
l A2NC
A : The case of general TBoxes. For general EL-TBoxes, this role depth-based approach does not work, as the query concept may have a cyclic de nition. To solve this, we introduce a CSM c that uses the canonical models of a concept C w.r.t. a TBox T , denoted with IC;T , and a similarity measure i between interpretations as follows: C c D = (IC;T ; dC ) i (ID;T ; dD).
The family of CSMs c for EL inherits several formal properties from i, in particular symmetry and equivalence invariance. The interpretation similarity measure (ISM) i can be parametrized by a weighting function that assigns di erent weights to each concept and role name, by a primitive measure between concept and role names and by a discounting factor.
The ISM i is de ned as a xed point, and can be computed using an iterative algorithm, which converges towards the similarity value. By modifying this algorithm to generalize the pointed interpretation corresponding to the individual a to take those subsets of the concept names and role-successors that yield the highest similarity value, it actually computes the similarity between the query concept Q and the mimic of Q w.r.t. a. This is su cient to check if a is a relaxed instance of Q w.r.t. the threshold t. This way, we get an iterative algorithm that computes all relaxed instances of Q w.r.t. c and t, and that is sound and complete, i.e., it only returns individuals that are de nitely relaxed instances, and it will nd all relaxed instances in nitely many iterations.
To conclude, we have proposed a new reasoning service that allows relaxed
instance query answering for application-speci c notions of similarity by the
appropriate choice of a CSM T and threshold t. We investigated necessary
requirements for the CSMs to be employed. We devised computation algorithms
for relaxed instances in the setting with unfoldable and with general EL-TBoxes.
For the latter setting we needed to introduce a new family of CSMs that take
the whole information from general TBoxes into account. The c CSMs are, to
the best of our knowledge, the rst CSMs of this kind for general TBoxes. Based
on these we gave a computation algorithm for relaxed instances w.r.t. general
TBoxes. For more details see [