Next: Entity-Relationship Diagrams Up: No Title Previous: Introduction

# Theoretical Foundation

We believe that the semantics of representational devices used for VL theory should be well understood. That is, the meanings of represented language concepts should be unambiguously determined by explicit notational devices whose meanings (semantics) are understood, so that algorithms can operate on the representation in accordance with the semantics of the notation, without needing ad hoc provisions for specific VL domains. In the following we outline a fully formalized theory for describing visual notations that consists of three components. Each component is defined by precise semantics. The definition of objects and relations is based on point-sets and topology. Description logic theory can be based on model-theoretic semantics appealing to first-order logic or using a compositional axiomatization with set theory.

## Objects and Topology

The definition of basic geometric objects (the elementary vocabulary of a visual notation) usually relies on topology which is itself a basis for defining relationships between objects. In the following we assume the usual concepts of point-set topology with open and closed sets [7]. The interior of a set (denoted by ) is the union of all open sets in . The closure of (denoted by ) is the intersection of all closed sets in . The complement of (denoted by ) with respect to the embedding space is the set of all points of not contained in . The boundary of (denoted by ) is the intersection of the closure of and the closure of the complement of . It follows from these definitions that , , and are mutually exclusive and is .

These definitions form the basis for Egenhofer's approach [8] to define topological relations between objects using the so-called 9-intersection . This method defines relations between two objects by nine set intersections (every pairwise combination of interior, boundary, and complement). The following restrictions apply to every pair of sets. (1) , be n-dimensional and , , (2) , Ø, (3) all boundaries, interiors, and complements are connected, and (4) = and = . A major drawback of this approach is the failure to describe true one-dimensional objects.

This was the motivation for the proposal by Clementini et al. [6]. They extended Egenhofer's approach by introducing points and lines as additional object types and the dimension of intersections as new feature for discriminating more cases. Three types of geometric objects are modeled. Regions have to be convex, connected and without holes. Lines and arrows must not be self-intersecting, are either circular or directed, and have exactly two end points. Points are elements of lines and describe their start or end points. The boundary of a point is an empty point-set, the boundary of a line is either an empty point-set (for a circular line) or a point-set consisting of its two end points (for a non-circular line). The boundary of a region is a circular line. The interior of an object is the object without its boundary. In case of points and circular lines their interior is identical to the object itself. Both approaches cannot deal with concave objects.

A third but different approach is based on the work of Clarke about `individuals and points' [9,10]. Clarke's calculus interprets individual variables as ranging over spatio-temporal regions and the two-place primitive predicate, `x is connected with y ', as a rendering of `x and y share a common point '. Randell and Cohn [11] developed their RCC theory based on this single property of connectedness. The RCC theory is a superset of Egenhofer's theory. It can even describe relationships with concave objects by using a convex hull operator.

Of course, there exists a strong interaction between the way of defining basic geometric objects and a set of corresponding spatial relations that can hold between these objects. Each of the above mentioned approaches defines a set of spatial (topological) relationships which are outlined in the next section.

## Spatial Relations

Egenhofer's approach distinguishes eight mutually exclusive relations (out of 92 = 18 different cases). The other cases can be eliminated since the above mentioned restrictions on sets have to hold. The remaining relations cover all possible cases. The 9-intersection is defined as matrix.

With this definition the eight cases (disjoint, meet, equal covers, contains, overlap) can be easily characterized by the distinction between empty and non-empty intersections. For instance, the contains relation is specified by the 9-intersection as follows.

Clementini et al. have to deal with 44 = 256 different cases caused by taking into account the dimension of intersections. The number can be reduced to a total of 52 real cases considering the restrictions on objects. They furthermore reduced this still large number of possible relationships to five with the help of an object calculus. These five binary topological relations (touch, overlap, cross, in, disjoint) are mutually exclusive and cover all possible cases (see [6] for a proof). For instance, the in relation is defined as follows: object is in object if the intersection between 's and 's region is equal to and the interiors of their regions intersect. It is transitive and applies to every situation.

Cohn and Randell define nine spatial relations (that are similar to Egenhofer's set) in terms of a single primitive relation `C(x,y)' read as `x is connected with y'. The authors also introduce an operator `conv(x)' which computes the convex hull of a possibly concave object. Its definition enables reasoning with concave objects. This approach is motivated by the idea that spatial databases might easily compute whether the single relation C(x,y) holds between two objects in the database. Further deductions could be based on this primitive relation. For instance, the relation `x is a part of y' (denoted as P(x,y) ) is defined as follows.

## Description Logic

This section gives a brief introduction to some aspects of description logic (DL) theory. We do not attempt to give a thorough overview and formal account of DL theory. However, we try to summarize the notions important for VL theory. We refer to [12,13,14] for more complete information about description logic theory.

DL theories are based on the ideas of structured inheritance networks [15]. A DL can be considered as a term rewriting language restricting the left side of equations to single unique term names. The specification of a DL consists of a set of concepts (or terms), a set of roles (binary relations that may hold between individuals of concepts), a set of disjointness assertions among concepts and among roles, a set of concept membership assertions for individuals, and a terminology, which maps names to specifications of concepts or roles. Concepts may be primitive or defined . A specification of a primitive concept represents conditions that are necessary but not sufficient. The specification of a defined concept represents conditions that are both necessary and sufficient. Primitive and defined roles are similarly specified. If a role holds between individuals, these individuals are referred to as fillers of this role.

Concept specifications may consist of a set of anonymous concept terms or other concept names. Unary (e.g. ) and binary operators (e.g. , ) are used as connectives. A concept term can also be given as a restriction of a role. Number restrictions specify the maximum or minimum number of allowed fillers (e.g. ( touching) , ( inside)). Value restrictions constrain the range of roles and allow only fillers that are individuals of a specific concept (e.g. ( touching arrow)). Value and number restrictions may also be combined (e.g. ( touching arrow) ). The above mentioned concept specifications are only a subset of all possible specifications. Figure 1 lists the model-theoretic semantics of commonly used specification elements (see also Section 3 for the specification of entity-relationship diagrams). The expressiveness and tractability of a particular DL depends on the type and allowed combinations of connectives and restrictions. The underlying algorithms can be NP-complete regarding their worst-case time complexity with respect to the size of the terms or even undecidable [14].

Figure 1: Semantics of DL Elements

There exist several theorem provers for special types of DLs. These theorem provers (referred to as DL systems) offer powerful reasoning mechanisms that are based on the DL semantics. DL systems usually distinguish two separate reasoning components. The terminological reasoner or classifier (TBox) classifies concepts with respect to subsumption relationships between these concepts and organizes them into a taxonomy. The TBox language is designed to facilitate the construction of concept expressions describing classes (types) of individuals. The classifier automatically performs consistency checking (e.g. for incoherence, cycles) of concept definitions and offers retrieval facilities about the classification hierarchy. The forward-chaining assertional reasoner or realizer (ABox) recognizes and maintains the type (concept membership) of individuals. The purpose of the ABox language is to state constraints or facts (usually restricted to unary or binary predications) that apply to a particular domain or world. Assertional reasoners support a query language as access to their state. Some query languages offer the expressiveness of the full first-order calculus.

## Extension of DL: Concrete Domains

Existing DL systems usually cannot deal with concepts defined with the help of algebra. For instance, it is not possible to specify a defined concept SmallCircle that resembles every circle whose radius is less than 10mm . It is only possible to specify SmallCircle as primitive concept (which can never automatically be recognized) and to assert the concept membership externally. Some DL systems offer extra-logical, user-defined help functions that may assert the property (radius less than 10mm ) automatically. However, these functions and their related concepts escape the DL semantics and prevent any reasoning. For instance, a concept VerySmallCircle resembling circles with a radius less than 5mm should be recognized as a specialization (subconcept) of SmallCircle . The idea of incorporating concrete domains into DL theory is to extend semantics and subsumption in a corresponding way (see [16]). CTL [17] is an example for a DL system that combines DL and concrete domains. CTL uses constraint logic programming (CLP) systems that can cope with systems of (in)equalities over (non)linear polynomials (e.g. CLP() [18]). The above mentioned concepts SmallCircle and VerySmallCircle can be easily specified in CTL as defined concepts. CTL would immediately recognize the subsumption relationship between these concepts.

## Application to VL

We argue that the main characteristics of DL systems are directly applicable to VL theory (see also [3] and Section 3 for a specific application):

• The TBox language is used to define VL elements as concept definitions. They are based on primitive concepts representing basic geometric objects (e.g. region, line, point). The primitive concepts form the roots of the taxonomy and are viewed as elementary lexical tokens. Defined concepts express (intermediate) semantic categories and are based on specializations of these primitive concepts.

• The classifier automatically constructs and maintains the specialization hierarchy of VL elements (defined as concepts). This hierarchy is used by the realizer to control the assertional reasoning process.

• Database-like assertion and query languages are used to state and retrieve spatial knowledge about individuals of VL programs. Example programs may be entered into the ABox by asserting primitive concept memberships for geometrical objects and spatial relationships between objects (as role fillers).

• The forward-chaining realizer automatically recognizes the most specialized concept membership (i.e. semantic category of VL element) of individuals (e.g. input tokens). It is the main source for driving the recognition process and is utilized as general visual parser.

• The automatic detection of inconsistent concept definitions or individuals is an important advantage of this approach. It is used to detect unsound (e.g. inconsistent) formal specifications (TBox) or erroneous parser input (e.g. errors in syntax or semantics).

Other (but still non-standard) characteristics are also very useful:

• The retraction of facts (stated in the ABox) is useful for supporting incremental and predictive parsing techniques in the editing process. Non-monotonic changes of users are automatically recognized and obsolete deductions retracted.

• Default reasoning can make useful assumptions about parser input while incomplete information exists.

• A DL extended to handle concrete domains could be very useful. The definition of VL elements and the possible spatial relationships between them could be solely based on DL theory with a concrete domain over . The need for an extra-logical component that recognizes geometric features and asserts them to the DL system would be obsolete.

Next: Entity-Relationship Diagrams Up: No Title Previous: Introduction

Volker Haarslev
Tue Jul 2 13:23:22 MET DST 1996