Finding concepts that are similar to a given concept can prove useful in constructing user-friendly interfaces for querying DLontologies|the concrete use case being a query answering system with an enhanced user interface that suggests semantically relevant keywords (based on concept similarity) during query formulation. Most investigations on the similarity of concepts rely on ad-hoc and non-robust constructions referring to syntactical relationships in the concept hierarchy. A more promising approach to concept similarity is rst to ground the concepts in a topological, geometrical, or more generally a spatial semantics and then to use the corresponding proximity or nearness relations provided by the spatial semantics for deciding concept similarity. Such an approach would not only describe a semantical justi cation for similarity of concepts but also provide a more cognitive semantics in the style of Gardenfors conceptual spaces that advance the comprehension by non-professional users of DL-systems. This paper discusses some possible directions for a spatially oriented semantics for DLs, starting o from conceptual spaces and the region connection calculus.
The cognitive hurdles that users who are not experts in logics have to overcome in order to use a DL based system (by e.g. constructing an appropriate ontology and using it for query answering), is quite high compared to those of other software systems. Hence there is a good reason (and there has been some work) to support non-experts with more intuitive means of accessing the services of a DL system within an enhanced user interface. Such an enhanced interface for query answering systems is also one of the aims in the FP7 EU project OPTIQUE (http://www.optique-project.eu/).
One well proven concept of supporting users in query construction (e.g., conjunctive queries in an ontology based data access (OBDA) scenario) is to ? This work has been supported by the European Commission as part of the FP7 project Optique. suggest the user who did not get expected results with a new query containing concepts relevant to those in the original query. While in most search engines the relevancy is determined by statistics, a semantical relevancy condition based on concept similarity would be more appropriate for query answering in OBDA.
Although concept similarity is a well investigated topic in knowledge
representation and reasoning, most of the proposals have a more syntactic avor in
that they measure the distances within the concept hierarchy. This seems to be
a mere ad-hoc and non-robust construction that can lead to changes in the
similarity relation in case the hierarchy is extended with further concepts. In this
paper, we try to lay the foundations for a semantically deeper notion of concept
similarity by interpreting the extensions of concepts with objects in some spatial
theory (be it some geometrical, topological or region oriented theory such as the
based on RCC and presented in [
Using a spatial foundation for concepts has not only positive e ects for more
intuitive query formulations (via concept similarity) but also for a better
understanding of ontologies. In DL Tboxes we may assert subsumption relationships
between concept (and role) descriptions and possibly further constraints such as
functionality and transitivity assertions for roles. Though this enables the user to
model a domain and thereby still keep the reasoning services (such as satis
ability, subsumption testing etc.) feasible, there are two main problems concerning
its application by non-expert users. The rst and main point is that the logical
notation with concept descriptions and its semantics does not seem to re ect
the cognitive mental concepts by the users, as Gardenfors argues [
The other point is that the lack of spatial aspects of concepts in standard
DL reduces the expressibility of some natural relationships. Rather than just
giving general inclusion (GCI) axioms for concepts one should be able to have a
more geometrical or topological view with which one can leverage intuitions on
concept similarity. Some examples are given by [
In contrast, saying Bistro fTPPg Restaurant not only expresses that bistros are restaurants but that there are also bistros that are not typical restaurants.
For simple concept descriptions as in the examples above, where only atomic concepts are used, we may have pretty strong intuitions on the meanings of the asserted spatial/topological relationships. Furthermore, we may clearly see the constraints in the common use of spatial relationships (e.g. the relations of RCC) and purely logical ones (e.g. subsumption). For example, saying that a concept is subsumed by another can be seen to imply that the former is a part of the latter, i.e., stand in the relation fTPP, NTPP, EQg.
For more complex descriptions, the intuitions may loose their strength. For example, taking the negation constructor, we may formulate that A v :B entails that A and B are disjoint, AfDCgB|and vice versa. But for a GCI where the negated concepts occur on the left-hand side, :A v B, there is no immediate connection to an RCC relationship between regions in pure RCC8 networks. In particular, if :A and B are chosen as convex regions, then A must be empty or a non-convex (unbounded) region with a hole.
In this paper we discuss possible spatial interpretations of DL concepts. The
kind of transformation of DL concepts and subsumption relations we have in
mind has to be such that non-logical users may rely on their spatial intuitions
for a better understanding of the mechanisms of the DL axioms which they
build. Clearly, we could try to reduce some kind of translation or transformation
of DL services to the satis ability check in RCC8 networks. And in fact, the
proof showing NP-hardness of satis ability testing of RCC8 networks shows a
reduction of 3SAT to it [
The structure of the paper is as follows: After this introduction we give overviews of the well known conceptual spaces of Gardenfors' cognitive semantics (Section 2) and the widely known member of calculi for qualitative spatial reasoning, the region connection calculus (Section 3). Then mainly technical section (Section 4) shows the existence of models with convex regions for DL-Lite ontologies. The subsequent sections discuss related work, state the conclusion, and give an outlook on future work. 2
Gardenfors' conceptual spaces (see the textbook [
Conceptual spaces are geometrical in nature. This may not come as a
surprise for a cognitively oriented model of semantics because human reasoning is
essentially spatial in many cases, as we have argued before. As such, conceptual
spaces are not only relevant for spatial (and temporal) reasoning, as argued in
[
To understand the ingredients of conceptual spaces, we consider the concept of a color. The color of an object is determined by three quality dimensions, chromaticness (saturation), brightness, and hue. The rst two of these are isomorphic to R with the usual ordering while the latter is isomorphic to a circle in the plane. Other examples of quality dimensions are force, height, width.
De ning the color of an object calls for assigning it a point in the space induced by the three quality dimensions, which, by the way, has the form of a spinner; one cannot assign the object a value on one dimension without giving it a value on the other dimensions. Gardenfors says that this set of quality dimensions is integral. The complementary notion is that of separability. The space made up of a set of integral quality dimensions that are separable from all other quality dimensions is called a domain. Note that according to this de nition, a domain is identi ed by its dimension. But the important component of such a domain is the betweenness relation. The betweenness relation B(x; y; z) is a ternary relation read as point y is between points x and z. This notion generalizes that of a metric d which induces a betweenness relation by setting Bd(x; y; z) i d(x; z) = d(x; y) + d(y; z).
The betweenness relation is the basis for de ning convex sets X in a domain: X is convex i for all pairs of points contained in X one has also all points lying in between them in X, formally: for all x; z 2 X: If B(x; y; z), then also y 2 X. Convex sets are in a way well-shaped and as such are candidates for the mental pendants of concepts. Gardenfors de nes a (natural) concept to be a set of convex regions in possibly multiple domains. To be more precise, a concept is represented as a set of convex regions in a number of domains, together with information about how the regions in di erent domains are correlated. The additional constraint in the de nition is due to the fact that though the quality dimensions in di erent domains may be separable they may not be independent in the sense that increasing the value in the one may lead to an increase in the latter. For example, take the concept of an apple. One of the domains in this concept is the color domain, and the (convex) region corresponding is the redyellow-orange region. Another domain is the taste domain with the region of the sweet and sour dimension. Now, there are connections between the color of an apple and its sweetness, though the quality dimensions are in di erent domains. In this paper, we will only work with Gardenfors concepts having exactly one domain. Gardenfors calls them properties. 2.2
What are the reasons to de ne concepts on the basis of convex regions? The main reason is that of \cognitive economy" [12, p. 70], as learning and reasoning with concepts on convex regions seems to demand less cognitive capacities, or, more technically, less resources such as space (memory) and time.
Technical underpinnings of this observation can be found in di erent areas in
which convex regions seem to ease the computation; one example from the area of
qualitative spatial and temporal reasoning can be found in [
Can we give a conceptual space semantics (abbreviated CSS in the following) for DLs such that, e.g., we can show: If a DL ontology has a (DL) model, then it has a CSS model. Or if that is not the case, can we characterize those DLs that have a DL model and not a CSS model? This paper will not give an answer to these questions, but will show the challenges in de ning a CSS for DLs. As a result, we will \downgrade" the complexity of the semantics to one based on RCC (see next section) but keep the convexity constraint.
The rst idea of interpreting concept descriptions with CSS concepts seems natural. But it is not at all clear whether a DL concept expressions has to be interpreted by CSS properties or CSS concepts. Even, if we ignore the problem of de ning correlations between di erent CSS domains (that are needed for de ning CSS concepts), it is not clear how to map DL concept constructors to constructors on CSS concepts and vice versa.
The only real concept constructor de ned in [
But the main problem with cognitive oriented semantics is the handling of negation and quanti ers [12, p.202]. The idea of using the convex hull operator on the complement of a convex region does not work here: If the convex set is bounded, then the complement of it will not be convex. Hence, the convex hull of this set will give the whole domain|resulting in the implausible result that some objects belong to a concept and its negation. But, may be this is a hint on the fact that indeed the negation of a concept (represented by a bounded convex region) should not be seen as a \natural" (convex) concept. The concept of an apple is di erently handled than the concept of a non-apple. Nonetheless, for pairs of concepts such as mortal/immortal it may be the case that they both can be represented by (unbounded) convex regions.
Even worse is the handling of roles and the quanti ers formed by them. Actually, the only types of roles which Gardenfors [12, p. 90] handles, are those de ned in some domain as a subset over two dimensions. Two examples discussed by him are the representation of the \longer than" and the \is a heir of" relation. The main point is to show that these can be represented as convex regions in some conceptual CSS domain. The longer relation can be reduced to length operators and their comparison on R. Drawing the pairs of lengths in the 2-dim area shows that all pairs of relations standing in this relation form the area above the line y = x, and as such constitute a convex region. But, regarding concepts in this space, CSS roles would have the same \type" as CSS concepts, whilst in DLs roles have higher dimension than concepts. Similar comments are in order for the heirity relation (though this is de ned on a completely di erent structure, namely the genealogy tree). 3
The region connection calculus (RCC)[
The base relations induce an algebra of 28 general relations in a relation algebra where a general relation is is represented as a set fr1; : : : ; rkg of base relations covers TPPi(Y; X)
contains NTPPi(Y; X) X : Y :
DC(X; Y ) disjointness
EC(X; Y ) externally connected
PO(X; Y ) partial overlap
EQ(X; Y ) equal
TPP(X; Y ) tangential proper part
NTPP(X; Y ) non-tangential proper part ri 2 BRCC8. The intended meaning of stating a general relation fr1; : : : ; rkg between regions X and Y , denoted by Xfr1; : : : ; rkgY is that X is related to Y in one of the base relations ri (1 i k) (but we do not know exactly which). As we will use it in the following, we abbreviate the part-of relations fTPP; NTPP; EQg by P. Giving relations between pairs of regions results in a network. Such a network may be consistent with the axiom system AxRCC8, but may also become inconsistent (as is the case for XfTPPgY; Y fNTPPgZ; XfTPPgZ. Consistent networks are also called satis able.
The set of regularly closed sets in R2 with the usual topology forms a model
of AxRCC8 that is complete for testing satis ability of RCC8 networks in the
sense that any satis able network has a model with the regions interpreted by
non-empty regularly closed sets. One can even show that a realization in R for
any d 1 (in particular d = 1) is possible by interpreting regions as (sets) of
ddimensional polytopes [27, Theorem 15]. Regarding the motivation for convexity
in the conceptual space approach, we plan to interpret regions as convex sets (in
some euclidean space Rd). And there is a recent result of [
If we want to introduce a geometrical (or more concrete) a region-based
interpretation of concepts into DL ontologies, then we have to detail out the interplay
between subsumption and the binary relations between regions as well as the
interplay of concept constructions and the constructions on regions. Though a
universal translation that holds for arbitrary DLs would be preferable, the
restrictions on the spatial target of the translation calls for di erent translations.
We will look here rst at a translation for ontologies into a fragment of a
member of the DL-Lite family [
R ! P j P B ! A j 9R Cl ! B Cr ! B j :B Tbox: Cl v Cr; R v R
Abox: A(a); P (a; b) Note that we do not allow for GCIs of the form A v 9R:C; but these can be modelled equisatis ably by A v 9Rnew, 9Rnew v C; Rnew v R [10, p.286].
Most of the results concerning DL-Lite (in particular those concerning FOL
rewritability) are based on a chase construction (originating in database theory).
If, e.g., the TBox contains the axiom A1 v A2 and the ABox contains A1(a)
but not A2(a), then it is enriched by the atom A2(a). This procedure is applied
stepwise to yield a monotonically increasing (with respect to set inclusion)
sequence of Aboxes starting with the original Abox. The resulting union of Aboxes
is termed chase(O) and induces a canonical model can(O) for the Abox and the
positive axioms of the Tbox, which are used in the chasing process. (For details
cf. [
We seek a translation of DL-LiteRp ontologies into RCC8 networks such that
the consistency for DL-Lite can be reduced to the satis ability test of RCC8
networks. We ignore the computational aspects at this stadium. Actually, in
the original RCC8 network, an empty region is not allowed; thus unsatis ability
of the RCC8 network would imply only incoherence of the ontology|where
incoherence means that a concept name in the ontology can be proved to be
equivalent to ?. This can be handled in the following two ways: We can extend
RCC such that the empty region is allowed (as done by [
The main restriction of the logic DL-LiteRp is that the negation symbols occur only on the right-hand sides of GCIs; hence we do not have to give an interpretation for the negations of concepts but only for basic concepts B. Let Base(RN; CN ) denote the basic concepts over RN and CN . Now, we can de ne CSS interpretations and the notion of a CSS model of an DL-LiteRp ontology. De nition 2. A CSS interpretation for an (ordinary) DL interpretation I = ( I ; I ) is a structure with a domain I and an interpretation function I such that { I is a DL interpretation in the usual sense (respecting the semantics of the inverse operation and of existentials) I is Rn for some n 2 N n f0g. { Every basic concept B is interpreted by a convex region (B)I in I w.r.t.
the euclidean metric.
A CSS model of a DL-LiteRp ontology O is an CSS interpretation which is a DL model of O.
In order to reduce the consistency test of DL-Lite ontologies to the satis ability test of RCC8 networks we give a translation. With basic concepts and constants B we associate its corresponding region XB and translate the GCIs and the Abox axioms as follows.
B1 v B2 B1 v :B2
A(a)
P (a; b) P1 v P2 P1 v P2
XafPgX9P ; XbfPgX9P X9P1 fPgX9P2 ; X9P1 fPgX9P2 X9P1 fPgX9P2 ; X9P1 fPgX9P2 similarly for P1 v P2 and P1 v P2 Additionally, for every pair of basic concepts B and constant c we add the constraint XBfDCgXc, and for all c1; c2 also add Xc1 fDCgXc2 (this implements the unique name assumption). For an ontology O let XO denote its corresponding RCC network. The main technical result is given in the following theorem. Theorem 1. A veri er complete DL-LiteRp ontology O is consistent i it has a CSS model.
Proof. If O has an CSS model and all CSS models are DL models, we directly get
a DL model for O. The proof of the other direction is more complicated. Assume
that O has a DL model. We show that XO must be satis able by interpreting
concepts by unions of polyeders in R. (This is in accordance with [
This theorem is essential to build more interesting logics that are able to model prototype relationships as those mentioned in the introduction. For example, adding the RCC8 base relations TPP; NTPP; EC to DL-LiteRp forces us to leave the general DL semantics and constrain it to CSS interpretations. But note that we can still investigate properties (such as FOL rewritability) by considering the narrower set of CSS interpretations. These investigations are planned for future work. 5
Ideas on specifying spatial semantics for a logical language can be traced back
to work of McKinsey and Tarski [
In the motivation for this paper we also stated the observation that spatial
semantics ease the understanding of logical systems by non-expert users. This
assumption nds its justi cation also in the area of diagrammatic reasoning
[
Convexity has an important role in conceptual spaces and also the spatial
semantics proposed in this paper. We deal with convexity only on the semantic
level. Clearly one can also introduce a primitive predicate for convexity in the
language level as done for euclidean logics in [
With respect to the use of conceptual spaces there are already approaches in
the recent literature that try to incorporate these cognitive ideas into ontologies
as described by [
A spatial semantics for DLs may prove useful in building intuitive interfaces for use by non-experts, the point in case being the suggestion of similar concept. This paper was intended to discuss possible approaches for de ning adequate spatial semantics for DLs that could be the basis for concept similarity. As a rst technical result following the survey and discussion we provide spatial semantics on the basis of convex regions for a member of DL-Lite family and show that the spatial interpretations of this logic are complete for satis ability testing.
But still the type of semantics presented here has to prove its bene ts. The main question is whether the ideas for interpreting DL-Lite basic concepts with convex regions can be extended to more expressive DLs. In Section 2 we hinted already on the challenges with incorporating negation and quanti ers. In future work we will deal with these challenges in the RCC framework.
By allowing boolean constructors on regions we get the more expressive logic
BRCC8 [
Quite more problematic is the incorporation of quanti ers into the RCC
framework. Here, we have to nd intuitions on what it means to apply the 9R
operator on a region? What kind of region do we expect to get (in contrast e.g.
to 8R)? One idea inspired by mathematical morphology [
DB(X) = fx 2 Rn j Bx \ X 6= ;g and EB(X) = fx 2 Rn j Bx
Xg
Here, \B de nes a neighborhood that is considered at each point" [
If at least the union (or sum) operator is added to RCC8, one can use the
framework of [