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.
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.