Combining OWL with RCC for Spatioterminological Reasoning on Environmental Data

Abstract

A new approach to spatioterminological reasoning is presented which is based on a hybrid knowledge representation system architecture and on a representation of the RCC family tree in OWL. The knowledge base into which the family tree is imported holds role assertions in terms of RCC-8 relations between individual regions. It is a key component of a semantic layer constructed on top of an environmental database which aims at facilitating access to users by supporting a sophisticated while easy-to-use search engine. Issues of world assumption and spatial extension to OWL are discussed.

Introduction

The core of the Datacenter Nature and Landscape (DNL) of the Swiss Federal Office for the Environment (FOEN) which is operated by the Swiss Federal Institute for Forest, Snow and Landscape Research (WSL) is a relational database system implementing a process-oriented data model. It holds data of several inventories of different kinds of biotopes (bogs, fens, floodplains, grasslands, amphibians spawning grounds, etc.) which are described using a number of specific terminologies (e.g., botanic, zoological). A small part of these terminologies has been made explicit in terms of vocabulary used in metadata descriptions. The biotopes cover neighboring or overlapping regions and are further related to non-inventory administrative regions such as communes or cantons. These regions are described by geometries. Spatial relations between regions can be computed geometrically by a Geographic Information System (GIS). However, there is currently no means to make the calculated relations accessible to logic formalism which is needed in order to process queries combining thematic aspects with (qualitative) spatial aspects such as “endangered butterflies in Birmensdorf and neighboring communes”. This query implies both a spatial expansion, namely “Birmensdorf and neighboring communes”, and a thematic expansion, namely “endangered butterflies (in the answer set of the spatial expansion)”, which requires that the answer set is represented in a way that it can be further processed.

The DNL datacenter holds about 200,000 data records which are grouped into 12 inventories. The number of objects per inventory ranges from some tens to thousands. Overall, several thousands data records describe spatial objects. Currently, the DNL datacenter is exclusively accessible to users which have previous knowledge of the data model and the terminologies used. In order to provide an open and intuitive access also to non-expert users we are constructing a semantic layer on top of the database. This semantic layer integrates an OWL DL knowledge base as a key component which holds the classes, properties and individuals necessary to semantically and spatially pre-process user input such as search terms before searching the database. The TBox of the knowledge base holds the thematic terminology which is introduced by an ontology specifying the users’ conceptualization of the domain. The terminology also contains the relation names of the different RCC species structured in a hierarchy of object properties. These names are used to assert selected relations between individual regions in the ABox of the knowledge base. We refer to this as a minimal representation of RCC in OWL which is motivated by the observation that RCC cannot be fully expressed, neither in the current version of OWL nor in OWL 1.1, but still must be minimally represented in order to allow for a combination of terminological and spatial reasoning services. In this paper we present a new approach to spatioterminological reasoning which is based on a hybrid knowledge representation system architecture and define a minimal representation of RCC in OWL.

The paper is organized as follows: Section 2 provides a short introduction to RCC. In section 3 we review some related work on the combination of RCC with OWL. In section 4 we introduce a hybrid knowledge representation system architecture. Spatioterminological reasoning based on hierarchies of object properties in OWL is described in section 5. Our approach is discussed in section 6.

The work presented here builds on previous work on the design and implementation of a Web-based platform for visualizing, querying and analyzing environmental data [ 1 ]. It is further related to the virtual database project [2]. Conceptual issues concerning the design of a bilingual eco-ontology for open and intuitive search and of a hybrid knowledge representation system architecture – the latter with an extensive usage scenario for spatioterminological reasoning – have been presented [ 3, 4 ]. 2

The Region Connection Calculus

The Region Connection Calculus (RCC) is an axiomatization of certain spatial concepts and relations in first order logic [ 5, 6 ]. The basic theory assumes just one primitive dyadic relation: C(x, y) read as “x connects with y”. Individuals (x, y) can be interpreted as denoting spatial regions. The relation C(x, y) is reflexive and symmetric.

Using the primitive relation C(x, y) a number of intuitively significant relations can be defined. The most common of these are illustrated in figure 1 and their definitions together with those of additional relations are given in table 1. The asymmetrical relations P, PP, TPP and NTPP have inverses which we write, in accordance with [ 6 ], as Ri, where R ∈ {P, PP, TPP, NTPP}. These relations are defined by definitions of the form Ri(x, y) ≡def R(y, x).

Fig. 1. RCC-8 relations (for the entire names cf. table 1)

Of the defined relations, DC, EC, PO, EQ, TPP, NTPP, TPPi and NTPPi have been proven to form a jointly exhaustive and pairwise disjoint set, which is known as RCC8. Similar sets of one, two, three and five relations are known as RCC-1, RCC-2, RCC-3 and RCC-5, respectively: RCC-1 = {SR}, RCC-2 = {O, DR}, RCC-3 = {ONE, EQ, DR}, RCC-5 = {PP, PPi, PO, EQ, DR}. RCC also incorporates a constant denoting the universal region, a sum function and partial functions giving the product of any two overlapping regions and the complement of every region except the universe [ 6 ].

SR(x, y) ≡def (x, y) (Spatially Related) C(x, y) (primitive relation) (Connects with) DC(x, y) ≡def ¬C(x, y) (DisConnected from) P(x, y) ≡def ∀z[C(z, x) → C(z, y)] (Part of) O(x, y) ≡def ∃z[P(z, x) ∧ P(z, y)] (Overlaps) DR(x, y) ≡def ¬O(x, y) (DiscRete from) EC(x, y) ≡def C(x, y) ∧ ¬O(x, y) (Externally Connected to) EQ(x, y) ≡def P(x, y) ∧ P(y, x) (EQual to) ONE(x, y) ≡def O(x, y) ∧ ¬EQ(x, y) (Overlaps Not Equal) PP(x, y) ≡def P(x, y) ∧ ¬P(y, x) (Proper Part of) PO(x, y) ≡def O(x, y) ∧ ¬P(x, y) ∧ ¬P(y, x) (Partially Overlaps) TPP(x, y) ≡def PP(x, y) ∧ ∃z[EC(z, x) ∧ EC(z, y)] (Tangential Proper Part of) NTTP(x, y)≡def PP(x, y) ∧ ¬∃z[EC(z, x) ∧ EC(z, y)](Non-Tangential Proper Part of) According to [ 5 ], regions support either spatial or temporal interpretation. In case of spatial interpretation, there is a variety of models among which to choose. The authors provide some examples such as interpreting the relation C (“connects with”) in terms of two regions whose closures share a common point or stating that two regions connect when the distance between them is zero.

D DR(y, z) PO(y, z) EQ(y, z) PP(y, z)

DR(x, y) T(x, z) DR(x, z) PO(x, z) PP(x, z) DR(x, z) DR(x, z) PO(x, z)

PP(x, z) PPi(y, z)

DR(x, z)

PO(x, y) DR(x, z) PO(x, z) PPi(x, z) T(x, z) PO(x, z) PO(x, z) PP(x, z) DR(x, z) PO(x, z) PPi(x, z)

EQ(x, y) DR(x, z) PO(x, z) EQ(x, z) PP(x, z) PPi(x, z)

PPi(x, y) DR(x, z) PO(x, z) PPi(x, z) PO(x, z) PPi(x, z) PPi(x, z) PO(x, z) EQ(x, z) PP(x, z) PPi(x, z) PPi(x, z)

PP(x, y) DR(x, z) DR(x, z) PO(x, z) PP(x, z) PP(x, z) PP(x, z) T(x, z)

In order to check consistency of a knowledge base holding spatial relations, socalled composition tables are used (cf. the composition table for RCC-5 in table 2). The entries in these tables share a uniform inference pattern which can be formalized as composition axioms of the general form ∀x, y, z. S(x, y) ∧ T(y, z) → R1(x, z) ∨ … ∨ Rn(x, z) where S, T, and Ri are variables for relation symbols.

A similar approach which is based on the description of topological relations between two spatial regions was introduced as the 9-intersection model in [ 7 ]. In this model, eight out of nine relations can be interpreted in the same way as we interpret the RCC-8 relations, namely as spatial relations between polygons in the integral plane [ 4 ]. Only the ninth relation is specific for the model. Given this extensive agreement on the interpretation of the relations between the two approaches we believe that the latter, which is axiomatized in first order logic, is easier to combine with description logics than the first, which is based on a topological framework. The reason therefore is that description logics themselves can be seen as fragments of first order logic [ 8 ]. 3

Related Work

A review of existing approaches [ 9, 10, 11, 12 ] to combining RCC with extensions to the description logics ALC is provided in [ 4 ]. Since the reviewed extensions and OWL are not as closely related as one might expect, these approaches cannot be applied to the Semantic Web without a major revision of the existing Web ontology language. However, a major revision is not desirable as an alternate language would surely miss some of the favorable features of the existing, such as property hierarchies, which make it compatible with RDF (Resource Description Framework), the Web’s description language for resources.

In [ 13 ] the authors aim at representing qualitative spatial information in OWL DL. On the basis of the (assumed) close relationship between the RCC-8 calculus and OWL DL they extend the latter with the ability to define reflexive roles. The extension of OWL DL with a reflexive property is motivated by the requirement that such a property, together with the transitive one, is needed in order to describe the accessibility relation which relates possible worlds to each of the modal operators of the logic S4. The modal logic S4 is considered, because the RCC-8 calculus can be translated into an extension of it [ 6 ]. In order to represent RCC-8 knowledge bases the authors use a translation in which regions are expressed as non-empty regular closed sets. The RCC-8 relations are then translated into (sets of) concept axioms in OWL DL and the classes denoted by the introduced concepts are instantiated by asserting for each concept an individual in the ABox in order to ensure that the classes cannot be empty. While this approach requires only a minimal extension to OWL DL (which has been considered in the draft to OWL 1.1 [ 14 ]), the notion of regions as sets in the (abstract) object domain (and not in a concrete domain) prevents RCC from effectively combining with domain ontologies. The reason therefore is that OWL DL requires type separation: A class cannot also be an individual (or a property) [ 15 ]. However, in order to classify regions in a domain ontology they must be represented as individuals and not as concepts.

It seems to be more intuitive to define the RCC relations in terms of role descriptions than to translate them into (sets of) concept axioms. Since current OWL does not provide constructors for role descriptions (apart from inverse), the underlying description logics have to be extended with these constructors. In [ 16 ] it is shown that the extension of SHIQ with complex role inclusion axioms of the form S D T ‹ R is undecidable, even when these axioms are restricted to the forms S D T ‹ S or T D S ‹ S, but that decidability can be regained by further restricting them to be acyclic. Complex role inclusion axioms of the unrestricted form are supported by the description logic SROIQ which serves as a logical basis for OWL 1.1 [ 17 ]. However, a closer look at an arbitrary composition table (except for RCC-1) reveals that, in order to axiomatize the composition of RCC relations, a language must even support an extension of the unrestricted form of role inclusion axioms, namely S D T ‹ R1 ‰ … ‰ Rn (cf. table 2 for RCC-5). If decidability should be preserved, complex role inclusion axioms are, therefore, not a solution to the translation problem of RCC. Axioms describing the basic RCC relations even require additional role constructors such as intersection and complement. Extensions of SHIQ with these kinds of role constructors have, to our knowledge, not been investigated so far. SROIQ supports negation of roles (i.e., complement) but not intersection. 4

A Hybrid Knowledge Representation System Architecture

Taking into account the result of the review of related work in section 3 we are combining RCC with OWL at the level of the knowledge representation system architecture and not at the level of the formalisms. This implies that the architecture of a knowledge representation system based on DL is extended with RCC specific components.

Figure 2 shows the architecture of a hybrid system in its simplest form. The grey shaded components are extensions to the original architecture. The shortcut KB denotes the knowledge base. The TBox holds the thematic terminology which is introduced by an ontology specifying the users’ conceptualization of the domain (not shown). It also contains the relation names of the different RCC species structured in a hierarchy of object properties. These names are used to assert selected relations between connecting individual regions in the ABox. The label RCCBox stands for Region Connection Calculus Box, a term which is inspired by the role box in [ 11 ]. The RCCBox contains the composition tables for RCC-1, RCC-2, RCC-3, RCC-5 and RCC-8. The RCC reasoner uses the role assertions in the ABox in order to calculate those pairs of regions which are not connected, and it uses the composition tables in order to check spatial consistency of the ABox. The dotted arrow pointing from the RCCBox back to the ABox indicates, that the calculated relations can be asserted in the ABox in order to speed up the processing of similar queries in the future. Figure 3 shows an acyclic directed labeled graph with the names of the different RCC species which are structured in a hierarchy of object properties in OWL. By traveling down the hierarchy from the top to the bottom the relations are successively refined to yield the different RCC species.

As figure 3 shows only the relations rcc:inverseProperPartOf, rcc:inverseTangentialProperPartOf and rcc:inverseNonTangentialProperPartOf can be defined in terms of OWL DL. For the majority of relations the TBox contains necessary but not sufficient axioms of the form RRCC-i+ ‹ RRCC-i (i.e., rdfs:subPropertyOf) with i+, i ∈ {1, 2, 3, 5, 8} and i+ > i, where RRCC-i+ and RRCC-i denote arbitrary relations of the species RCC-i+ and RCC-i (cf. table 3 for examples). Note that because of the transitive property of rdfs:subPropertyOf it holds that ((R(RCC-i+)+ ‹ RRCC-i+) ∧ (RRCC-i+ ‹ RRCC-i)) → R(RCC-i+)+ ‹ RRCC-i.

5 Spatioterminological

Object Properties in OWL

Reasoning

Based on

Hierarchies of

Even though, in principle, all RCC relations can be geometrically computed and asserted in the ABox of an OWL DL knowledge base, it is, for at least two reasons, not favorable to do so. First, asserting for all pairs of regions all relations holding between them easily results in a very large knowledge base thereby bearing on the performance of the system (in our sample the number of asserted relations is roughly one tenth of the number of a full representation without counting the relations between regions which are not connected; cf. below). Second, as discussed in section 3, since the inferences implied by the entries in the RCC composition tables cannot be put in terms of OWL DL axioms [ 16 ], an OWL reasoner will be unable to check the consistency of the knowledge base w.r.t. spatial references. For these reasons we argue in favor of a minimal representation in the ABox of an OWL DL knowledge base and to infer or calculate those relations which are not represented when requested at runtime.

In order to define a minimal representation of RCC in OWL we assert for all connecting pairs of regions in the ABox of a sample knowledge base their relations in terms of RCC-8. The sample knowledge base holds a (small) part of the knowledge of the DNL datacenter introduced in section 1. To give an example, partiallyOverlaps(Albiskette-Reppischtal, Birmensdorf) is one of the 258 RCC-8 relations asserted between the 44 regions in the knowledge base. Note that in order to keep the number of asserted relations as small as possible we do not explicitly assert that two regions are disconnected if they are not connected.1

Based on this minimal representation a total of 2198 RCC relations can be inferred from the knowledge base using theorems which share the uniform pattern of the logical modus ponens: [(RRCC-i+ ‹ RRCC-i) ∧ RRCC-i+(x, y)] → RRCC-i(x, y) where RCC-i+ denotes the RCC species from which is inferred and RCC-i the species to which is inferred and x, y denote individual regions. We are using the OWL reasoner Pellet (version 1.4, OWL API) in order to access and manipulate the knowledge base. 1 In an upcoming paper we also explore a minimal representation which is based on the primitive RCC relation connectsWith and discuss the soundness and completeness of a calculus for this representation when compared to a calculus for the herein presented representation. partiallyOverlaps ‹ overlapsNotEqual partiallyOverlapsI ⊆ overlapsNotEqualI

Note that from the perspective of RCC the described inference corresponds to a translation from the relations of the RCC-8 species into the more coarse-grained relations of RCC-5, RCC-3, RCC-2 and RCC-1. For instance, inferring the theorem [(partiallyOverlaps ‹ overlapsNotEqual) ∧ partiallyOverlaps(Birmensdorf, Albiskette-Reppischtal)] → overlapsNotEqual(Birmensdorf, Albiskette-Reppischtal) translates the asserted RCC-8 relation partiallyOverlaps(Birmensdorf, Albiskette-Reppischtal) into the RCC-3 relation overlapsNotEqual(Birmensdorf, Albiskette-Reppischtal) which is not asserted in the knowledge base (cf. table 3). This translation can be useful since a coarse-grained classification of relations is easier to handle and might be sufficient for some queries while others might require a fine-grained classification. The translation also enables agents speaking different dialects of RCC to communicate with each other. 6

Discussion

Since our minimal representation only asserts connections the OWL reasoner cannot infer from the asserted relations those pairs of regions which are not connected. One reason therefore is that OWL DL does not allow negation of roles. Thus, an axiom like DC(x, y) ≡ ¬C(x, y) is not legal OWL DL (DC stands for “disconnected from”). However, even if negation of roles were allowed as it is in OWL 1.1 [ 14 ], the reasoner could not infer for two regions which are not connected that they must be disconnected (unless it is explicitly stated). The reason therefore is that OWL DL – like any description logics – assumes an open world: If two regions are not explicitly specified as connecting with each other (e.g., by asserting one of the RCC-8 relations) or as not connecting, their relation to each other is undefined. By combining OWL DL with RCC the former takes advantage of the closed world of the latter: RCC-8 (and also the other RCC species) forms a jointly exhaustive and pairwise disjoint set of relations. Any two spatial regions are in one and exactly one of the RCC-8 relations to each other. This means that in RCC-8 two regions are disconnected if none of the seven connection relations is asserted for them.

Taking into account the overview of related work which suggests that RCC cannot be easily expressed even in a future version of OWL we do not argue in favor of a spatial extension to OWL. Intuitively, it is not surprising that RCC cannot be fully represented in OWL. Both bear on models for making the real-world accessible to symbolic manipulation which are not interchangeable (and thus translatable) but rather complementary. To see the difference it might help to recall the ancient marketplace. The traded goods could roughly be divided into two distinct categories: countable goods which were traded by number (e.g., farm animals such as sheep) and measurable goods (such as flour) which were traded by mass. The first implies the existence of (identifiable) individuals which can be described in an ontology in accordance with their (assumed) kinship. The second implies the existence of dissective and cumulative properties which limit the consideration to the mereological notions of parts and wholes. With reference to individuals, we could denote goods of the second category as “dividuals” in the proper sense of the word. With regions the matter is more complex. In a naive sense, they share the dissective and cumulative properties (a part of a region still is a region and the sum of two (or more) regions still is a region) but at the same time they can be assigned with a name (or another identifier), distinguishing them as individuals. This double nature of regions explains the claims made by both ontological and mereological approaches, the reconciliation of which is reflected, for instance, by the attempts to combine RCC with OWL.

Future work is planned on the verification of the presented approach in the productive knowledge base of the DNL datacenter introduced in section 1 holding in a first version 413 spatial regions and on the identification of a minimal temporal representation for temporal reasoning. The latter will include exploring whether the existing features of OWL (including OWL 1.1) or of metadata standards like Dublin Core or ISO 19115 [ 18 ] for attributing resources with time labels are sufficiently expressive to capture the temporal references of environmental data.

Acknowledgements. The authors sincerely thank Jürg Schenker, Martin Hägeli and Martin Brändli for the fruitful discussions and leadership that made this research possible. This research has been funded and conducted in cooperation with the Swiss Federal Office for the Environment (FOEN). Related research was funded by the European Commission and by the Swiss Federal Office for Education and Science within the 6th-Framework Programme project REWERSE number-506779 (cf. http://rewerse.net).

References

1. 2. Baltensweiler , A. , Brändli , M. : Web-based Exploration of Environmental Data and Corresponding Metadata, in Particular Lineage Information . In: Scharl, A . (ed.): Environmental Online Communication. Springer-Verlag, London ( 2004 ) 127 - 132 Frehner, M. , Brändli , M. : Virtual Database: Spatial Analysis in a Web-based Data Management System for Distributed Ecological Data . Environmental Modelling & Software 21 ( 2006 ) 1544 - 1554

3. Bauer-Messmer , B. , Grütter , R.: Designing a Bilingual Eco-ontology for Open and Intuitive Search . In: Gómez, J.M. , Sonnenschein , M. , Müller , M. , Welsch , H. , Rautenstrauch , C. (eds.): Information Technologies in Environmental Engineering . ITEE 2007 - Third International ICSC Symposium . Springer-Verlag, Berlin Heidelberg ( 2007 ) 143 - 152

4. Grütter , R. , Bauer-Messmer , B. : Towards Spatial Reasoning in the Semantic Web: A Hybrid Knowledge Representation System Architecture . Lecture Notes in Geoinformation and Cartography . Springer, Berlin ( 2007 ) (to appear)

5. Randell , D.A. , Cui , Z. , Cohn , A.G. : A Spatial Logic based on Regions and Connections . In: Nebel, B. , Rich , C. , Swartout W . (eds.): Principles of Knowledge Representation and Reasoning . Morgan Kaufmann, San Mateo, CA ( 1992 ) 165 - 176

6. Bennett , B. : Logics for Topological Reasoning . In: 12th European Summer School in Logic, Language and Information (ESSLLI-MM) . Birmingham, UK ( 2000 , August , 6 - 18 )

7. Egenhofer , M. , Franzosa , R.: Point-Set Topological Spatial Relations. International Journal of Geographical Information Systems , 5 ( 2 ) ( 1991 ) 161 - 174

8. Baader , F. , Nutt , W. : Basic Description Logics . In: Baader, F. , Calvanese , D. , McGuinness , D. , Nardi , D. , Patel-Schneider , P . (eds.): The Description Logic Handbook . Cambridge University Press ( 2003 ) 47 - 100

9. Haarslev , V. , Lutz , C. , Möller , R.: Foundations of Spatioterminological Reasoning with Description Logics . In: Cohn, A.G. , Schubert , L.K. , Shapiro , S.C . (eds.): Principles of Knowledge Representation and Reasoning . Proceedings of the Sixth International Conference (KR'98) . Morgan-Kaufmann, San Mateo, CA ( 1998 ) 112 - 123

10. Haarslev , V. , Lutz , C. , Möller , R.: A Description Logic with Concrete Domains and a Role-Forming Predicate Operator . Journal of Logic and Computation , 9 ( 3 ) ( 1999 , June) 351 - 384

11. Wessel , M. : On Spatial Reasoning with Description Logics . Position Paper. In: Horrocks, I. , Tessaris , S. (eds.): Proceedings of the International Workshop on Description Logics (DL2002) , Toulouse, France. CEUR Workshop Proceedings 53 ( 2002 , April 19-21) 156 - 163

12. Lutz , C. , Milicic , M.: A Tableau Algorithm for Description Logics with Concrete Domains and GCIs . In: Proceedings of the 2005 International Workshop on De-scription Logics ( DL2005 ). CEUR Workshop Proceedings 147 ( 2005 )

13. Katz , Y. , Grau , B.C. : Representing Qualitative Spatial Information in OWL-DL . In: Proceedings of OWL: Experiences and Directions , Galway, Ireland ( 2005 )

14. Grau , B.C. , Motik , B. : OWL 1.1 Web Ontology Language: Model-Theoretic Semantics . Editor's Draft of 27 November 2006 . The University of Manchester ( 2006 )

15. McGuinness , D.L. , van Harmelen , F. : OWL Web Ontology Language: Overview. W3C Recommendation 10 February 2004 . World Wide Web Consortium ( 2004 )

16. Horrocks , I. , Sattler , U. : Decidability of SHIQ with Complex Role Inclusion Axioms . In: Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI 2003 ). Morgan Kaufmann, Los Altos ( 2003 ) 343 - 348

17. Horrocks , I. , Kutz , O. , Sattler , U. : The Even More Irresistible SROIQ . In: Proc. of the 10th International Conference of Knowledge Representation and Reasoning (KR-2006). Lake District, UK ( 2006 )

18. ISO 19115: 2003 : Geographic Information - Metadata. International Organisation for Standardization ( 2003 )