Representations of Topological Relations Between Simple Regions in Description Logics: From Formalization to Consistency Checking

Representations of Topological Relations Between Simple Regions in Description Logics: From Formalization to Consistency Checking

Catherine Roussey (French Institute for Agricultural and Environnemental Engineering, Campus des Cézeaux, Aubière, France), François Pinet (French Institute for Agricultural and Environnemental Engineering, Campus des Cézeaux, Aubière, France) and Michel Schneider (Computer Science, Blaise Pascal University, Clermont-Ferrand, France)
DOI: 10.4018/jaeis.2013040105
OnDemand PDF Download:
$37.50

Abstract

This paper proposes an operational approach to (1) formalize, in Description Logics (DL), the topological relations between simple regions and (2) automatically check whether a set of relations is consistent. The solution allows for the use of traditional DL reasoners (Pellet, Fact++, etc.) to check the consistency of relations and detect the sources of error. The solution does not require any specific extension of the DL or reasoner. The authors demonstrate how to apply this approach with Protégé and Fact++. Different spatial relations in agricultural and environmental applications are also provided to illustrate the possible uses of our method.
Article Preview

1. Introduction

Checking the consistency of topological relations between spatial regions is an important problem, for example during the design of spatial databases and the specification of integrity constraints (Pinet, 2012; Pinet, Duboisset, & Soulignac, 2007).

  • Relation 1:A is inside B;

  • Relation 2:B is disjoint from C;

  • Relation 3:C is inside A.

This set of relations is inconsistent because A is inside B and B is disjoint from C imply that C is disjoint from A. Thus, it is not possible to draw these three simple regions in a 2D space in a way that satisfies the three topological relations simultaneously. While this example is simple, it can be difficult to manually check the consistency of a larger set of topological relations.

This paper proposes an operational approach based on Description Logics (DL) (Nardi & Brachman, 2002) to automatically check whether a set of topological relations is consistent. Our approach works with the 8 topological relations proposed in other studies (Cohn, Bennett, Gooday, & Gotts, 1997; Egenhofer & Herring, 1990) between two simple regions in a 2D space. Figure 1 illustrates these 8 relations.

Figure 1.

Set of topological relations

Some algorithms already exist for checking the consistency of a set of spatial relations (Cohn et al., 1997). These algorithms are based on a composition table and use a path consistency algorithm. For two topological relations R1(A,B) and R2(B,C), the composition table lists all the possible topological relations between the two regions A and C.

Our objective is to propose a general approach that can easily be extended to different types of regions or spatial objects, such as complex regions (Schneider & Behr, 2006) or vague regions (Bejaoui, Pinet, Bedard, & Schneider, 2009; Cohn & Gotts, 1996).

Our approach is to formalize the properties of spatial regions and their relations directly in DL (Nardi & Brachman, 2002), i.e., in a declarative and logical manner. Our method enables the use of DL reasoners (Fahad, Qadir, & Shah, 2008; Sirin, Parsia, Grau, Kalyanpur, & Katz, 2007) such as Pellet or Fact++ to check the consistency of a set of topological relations. The outputs of the reasoners will make it easier for users to explain the reasons for any inconsistencies. Our solution does not require a specific extension of the DL reasoner.

In our opinion, the description of spatial relations in DL opens up a new and promising field of research. The DL specification of topological relations could be extended to represent spatial relations between more complex regions (Bejaoui et al., 2009; Cohn & Gotts, 1996; Schneider & Behr, 2006) that cannot be analyzed by consistency checking algorithms. Our approach (1) defines the properties of topological relations using DL axioms and (2) uses standard DL reasoners to check the consistency of a set of topological relations.

This paper is organized as follows. Section 2 presents the limits of existing DL-based methods for topological relations checking. Section 3 presents the basic principles of DL. Section 4 details our formalization of topological relations in DL. Section 5 describes how we check the consistency of relations using a DL reasoner and Protégé software. The DL translation tool is implemented in section 6. Section 7 describes environmental examples of topological relations, and some conclusions and perspectives are presented in section 8.

2. State Of The Art

This section describes existing DL-based methods to check the consistency of topological relations.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 8: 4 Issues (2017): 3 Released, 1 Forthcoming
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 2 Issues (2012)
Volume 2: 2 Issues (2011)
Volume 1: 2 Issues (2010)
View Complete Journal Contents Listing