Morteza Fathi , Abbas alimohammadi
Geographic Information System
Department, KNToosi University of Technology,
Geographic Information System
Department, KNToosi University of Technology,
An important activity in the design of a particular database application consists in identifying the integrity constraints that must hold on the database, and that are used to detect and evaluate inconsistencies. It is possible to improve data quality by imposing constraints upon data entered into the database.
Within a geographic context, topological relations and other spatial relationships are fundamentally important in the definition of spatial integrity rules. Unfortunately in real situation, rules for consistency constraints are not so simple and we forced to use complex rules. There are many ways to construct this complex rules. For example we can construct complex rule by integrating simple rules together, and this simple rules can be topological rules or other spatial relationships. By gathering this complex rules for applications that needs a lot of rules (e.g. Land use planning), we face a large amount of simple rules. What is neglected is that, if these rules are consistent with each other or not.
This paper Discuss about this problem.
A number of integrity constraints must be observed when updating a database, in order to preserve the semantics and the quality of stored data [Elmasri et al ,2000]. Achieving and preserving integrity of data is an established field in the database area. However, within the scope of geographic applications, special problems come up due to the locational aspects of data [Plumber et al, 1997]. Most geographical information systems (GIS) use data that depend on topological relationships, and sometimes these data must be explicitly represented in the database, requiring special attention for the maintenance of the semantic integrity. Enforcing the integrity constraints must be considered one of the main implementation goals.
The issue of spatial data quality in relation to integrity constraints has received much recent attention [(Servigne et al., 2000), (Medeiros and Magalhaes, 1993), (Medeiros and Cilia, 1995), (Medeiros and Andrade, 1994), (Medeiros and Pires, 1994), (Cockcroft, 1997).
There are some ways to maintaining these rules in database. One way is storing the rules in rule repository. In a well designed data base management system mechanisms are provided for the management of relationships between data items as well as the implementation of integrity constraints. This is done by means of a repository [Sophie Cockcroft, 1996].
This repository can be in the form of table (for example in Geodatabase) that rules are stored in it and this rules can enforces into database by making spatial queries.
In the spatial domain Gaede et al  are particularly interested in integrating constraints into database systems by means of queries. Queries can be interpreted as a kind of constraint, each query predicate represents a constraint that the objects in the result have to satisfy [Sophie Cockcroft, 1996].
The form of enforcing constraints or making spatial queries is topic of some attempts.
In particular Pullar et al. (1997) explore the potential of decision tables to express query and modeling problems in a conceptually intuitive way. Decision tables express condition-action clauses in a tabular form [Plumber et al, 1997]. Arentze et al. (1995) show this to be a flexible technique for decision support in facility planning. Pullar et al. (1997) further explore their integration with operational semantics of GIS. They propose that decision tables be used in combination with object-oriented methods to provide a very direct and concise way to solve geographical problems. To demonstrate the concept, a prototype development is described where decision tables are integrated with the programming framework used by a commercial GIS [Plumber et al, 1997].
Rule-based paradigm for making spatial queries and therefore enforcing integrity constraints is the way that has chosen in this paper.
After all, rules in the rule repository that are in the If-Then form can be inconsistent with each other. The form of rule definition can help us to detect inconsistency easily.
This paper is organized as follows. Section 2 presents a classification of the spatial integrity constraints. Section 3 describes rule-based modeling method to defining spatial query. In section 4 some inconsistent rules (in Urban planning application) that can be defined are presented. Finally, Section 5 presents the conclusions.
2. Spatial integrity constraints
One important activity in the design of a schema for a particular database application consists in identifying the integrity constraints that must hold on the database. The main types of integrity constraints that occur frequently in database modeling are: domain constraints, key and relationship structural constraints, and general semantic integrity constraints [Elmasri et al, 2000]. Cockcroft [Cockcroft, 1997] extends that classification in order to encompass the peculiarities of spatial data. This classification is based on the distinction between topological, semantic, and user rules, as follows.
Topological integrity constraints. Topology is the study of geometrical properties and spatial relations. There has been some theoretical research into the principles of formally defining spatial relationships . These principles can be applied to application specific entities and relationships to provide a basis for integrity control. Area subdivision is an example of this constraint. One city’s administrative regions must be contained within the city limits, and there must not have any spot in the municipal territory that belongs to more than one administrative region or to none.
Semantic integrity constraints. These constraints are concerned with the meaning of geographic features. Semantic integrity constraints apply to database states that are valid by virtue of the properties of the objects that need to be stored. An example of this constraint is the rule that does not allow a building to be intercepted by a street segment.
User defined integrity constraints.User defined integrity constraints allow database consistency to be maintained as defined by the equivalent of “business rules” in non-spatial DBMS. This type of constraint acts, for instance, on the location of a gas station, which, for legal reasons, must lie farther than 200 meters from any existing school. The municipal permitting process must consider this limitation in its analysis. User defined rules may be stored and enforced by an active repository.
Serviane [Servigne et al, 2000] presented topological-semantic integrity constraints, which define mandatory or prohibited topological relationships according to the semantic of the spatial feature. Considering only the geometric representation of spatial features most topological relationships are possible. Considering their meaning, it is possible to define which topological relation is consistent and which one is inconsistent.
Extending the approach to specify topological-semantic constraints proposed by Bogorny [Bogorny et al, 2001], in order to support the cardinality “all”, for mandatory disjoint relationships, a topological-semantic constraint between two spatial feature types A and B can be defined as:
The predicate of a spatial constraint is given by a relationship type relType, a minimum cardinality , and a maximum cardinality . The predicate can express mandatory constraints, which are given by the cardinalities (a,a) for the relationship disjoint, and (1,1) for the remaining topological relationships. A spatial constraint for Hospital with Factory, for example, can be defined as , where all instances of Hospital are disjoint to ALL instances of Factory. A spatial constraint for Island with Water Resource, for example, where every Island has a within relationship with only one Water Resource can be expressed such as:
Prohibited constraints are defined through the cardinalities (0,0). For example,
In this application (LUP), spatial constraints are subdivided to 2 branches: 1- topologicalsemantic and 2- metric constraints.
The OGC (Open GIS Consortium), which is an organization dedicated for developing standards for spatial operations and spatial data interchange to provide interoperability between Geographic Information Systems (GIS), defines a standard set of topological operations: disjoint, overlaps, touches, contains, within, crosses and equals.
Distance (or metric) relations are based on the Euclidean distance between two spatial features.
3. Rule-based modeling
Pullar offered a rule-based modeling for performing spatial queries. In this paper his paradigm is used for defining spatial constraints rules.
Rule-based programming is a special case of logic programming. The language is based on a procedural scheme with the canonical condition-action form:
IF condition-pattern THEN actions.
The left-hand side consists of several conditions that return a logical result. The right-hand side consists of several actions. Actions can fire other rules, establish new facts, and perform procedural operations. Rules express relationships and meta-information. Rules are grouped in rule-sets known to the inference engine. The engine works in a continuous loop, at each cycle a rule that matches some condition-pattern is chosen and the related actions are fired. The execution stops when no more rules are fireable.
Rule-based programming uses a simple procedural abstraction to search for goals that satisfy the condition-pattern and then subsequently firing the action clauses. Queries are solved as proofs computed from the facts and rule set. Rule-based programming does not directly support data abstractions but relationships can be expressed by metarules [Pullar et al. (1997)].
Rule-based programming provides a model of the decision process that suits a range of problems used for spatial reasoning (Scarponcini et al., 1995).The techniques have been used in several ad hoc system developments for decision support (Lowes and Bellamy, 1994) (Davis and McDonald, 1993).
3.1. Spatial rules
Rule-sets are difficult to interpret for any reasonably sized knowledge base. An alternative technique for representing decision rules is as decision trees (Giarratano and Riley, 1994) or decision tables (Reilly et al., 1987).
The different forms for representing rules can be shown by example. These are some Land Use Planning rules (in Iran):
Given the following rule-set:
IF (Land use is educational) THEN (must not be neighbor by industrial Land use)
IF (Land use is hospital) AND (has bedridden section) THEN (must not be neighbor by educational Land use)
This can be represented in a graph form as a decision tree shown in Figure 1.
Figure 1: Decision tree
|A||Spatial rule||must not be neighbor by industrial Land use||must not be neighbor by educational Land use|
Figure 2: Decision Table.
Some of the advantages of decision tables include compactness, self-documentation, modifiability and completeness checking (Reilly et al., 1987). Given that information is stored and viewed in a tabular form in geo-relational databases, it seems fortuitous to represent the rules in a similar form. This presents the user with a very consistent representation of data and procedures.
3.2. Examples in LUP application
Three other complex examples of decision tables in LUP are described. The first example shows a simple query that may be expressed using an advanced query tool provided within desktop GIS. The second example demonstrates a more complex query that would not be readily represented by any table query tool, and the third is the multi condition query.
In the first example a decision table, see Figure 3, is used to express the following query:
In the range of 500m around LOCAL CENTRAL TRANSIT [LCT] (centers of Communication company) the height of buildings should be less than 50m.
In the range of 6000m up to 15000m from the end of airport, the height of any building must not be more than 150m.
In the second example a decision table, see Figure 4, is used to develop a more realistic query to permit the building height relative to distance from end of airport band:
In the range of 300m around the airport band, should not be any building, and up to 7500m of the end of band, the height of buildings must be 1:50 of the distance.
The first condition is:“in the range of 300m around the airport band, should not be any building”,the second condition is:”if distance from end of airport band is >300m and then the height of buildings must be 1:50 of the distance”.
Permitted height of building obviously varies relative to distance from the end of airport band. With pattern matching a decision table is found that lists this attribute (goal) in its action clause. Therefore it is able to infer this information from the decision table shown in Figure 4 and calculate the height of building that must be mentioned.
Note that both feature attributes for [Permitted height of the Building is derived for the purpose of the pattern inference and therefore are virtual attributes defined programmatically.
|c1||[Building].DistanceTo([ end of airport band ])||< 300m||300)|
|c2||[Building].height – ( Permitted height of building)||–||< 0||> 0|
Figure 3: Decision Table for first query example
|C||[Building].DistanceTo([ end of airport band ])||< 300m||>300 AND 7500|
|A1||[Permitted height of the Building]||0||[Building].DistanceTo([ end of airport band ])× 1/50||_|
Figure 4: Decision Table to deduce permitted building height.
4. Inconsistency example in LUP
In this section an example of inconsistent rules that may enter to rule-repository is presented: 1- With considering the second and third examples of LUP rules that presented in section 3.2, maybe we don’t notice any inconsistency and therefore we make spatial rules according to these constraints. But more accurate looking at these rules shows that it was inconsistency between these 2 rules. These are that rules: a- In the range of 6000m up to 15000m from the end of airport, the height of any building must not be more than 150m. b- In the range of 300m around the airport band, should not be any building, and up to 7500m of the end of band, the height of buildings must be 1:50 of the distance.
In this paper some subjects are discussed. First topic is about integrity constraints. By using rule-based model to creating queries and spatial constraints we can use a simple way to execute rules in decision tables. Other benefit of using this paradigm is using some computer algorithms for detecting inconsistency between rules. Although there are some problems for using these algorithms for spatial rules, but it can be subject of other attempts.
- Arentze T.A., Borgers A. and Timmermans H. (1995) The Integration of Expert Knowledge in Decision Support Systems for Facility Location Planning. Computers, Environment and Urban Systems 19(4), pp.227-247
- Bogorny, V., Iochpe, C.: Extending the OpenGIS Model to Support Topological Integrity Constraints. In: Brazilian Symposium on Databases, COPPE/UFRJ, Rio de Janeiro, Brazil (2001) 25-39 (in Portuguese).
- Cockcroft, S. (1996), “Towards the automatic enforcement of integrity constraints in spatial database systems”. In: Pascoe, R. T., Sutherland, N. C., & Gorman, P. (eds.), Proceedings of the 8th Colloquium of the Spatial Information Research Centre, University of Otago, New Zealand, pp. 33-42
- Cockcroft, S. (1997) ‘A taxonomy of spatial data integrity constraints’, GeoInformatica, 1,4, pp. 327-343.
- David Pullar, ” Rule-Based Modeling In GIS”. In: the second annual conference of GeoComputation ’97 & SIRC ’97, University of Otago, New Zealand, 26-29 August 1997
- Davis J.R. and McDonald G. (1993) Applying a Rule-Based Decision Support System to Local Government Planning. In: Expert Systems in Environmental Planning, Editors J.R. Wright, et. al. Springer-Verlag, pp.23-45
- Egenhofer, M. J., Franzosa, R. D. Point-set topological spatial relations. Intl. J. GIS 5(2):161- 174, 1991.
- Elmasri, A. R. & Navathe, S. (2000), “Fundamentals of database systems”. New York: Addison-Wesleyli>
- Gaede, V., & O.Günther .  “Constraint-Based Query Optimization and Processing,”. In. Proceedings: First International Database Workshop on Constraint Database Systems (CDB’95).
- Lowes, D. and Bellamy J.A. (1994) Object Orientation in a Proceedings of GeoComputation ’97 & SIRC ’97 23 Spatial Decision Support System for Grazing Land Management. AI Applications 8(3), pp.55-66
- Opengis. Open GIS Simple Features Specification For SQL. In URL: (1999).
- Plumber, L., Groger, G. Achieving integrity in geographic information systems: maps and nested maps, GeoInformatica 1(4): 346-367, 1997.
- Reilly K.D., Salah A., and Yang C. (1987) A Logic Perspective on Decision Table Theory and Practice. Data and Knowledge Engineering (2), pp.191-210
- Scarponini P., Clair D., and Zobrist G. (1995) An Inferencing Language for Automated Spatial Reasoning About Graphic Entities. Advances in Spatial Information Systems, Proceedings SSD’95, Portland, pp.259-278
- Servigne, S. et al.: A Methodology for Spatial Consistency Improvement of Geographic Databases. Geoinformatica. 4-1 (2000) 7-34.