A Framework for Update Process in GIS

Laurent Spéry
LIRMM, 161 rue ADA, 34392 Montpellier Cedex 5, France
Email: spery@lirmm.fr

Abstract

Data update is a significant stage in the life of a geographical information system (GIS). In many cases, GIS are based on data provided by organizations such as the cadaster. The data transfer between a producer and a user is then often a bulk transfer. We study problems arising from the integration of this new data in the user GIS. To improve this data integration, we propose a two-step process: (1) Altered objects are detected in the transfer dataset. (2) Then, connections between altered reference data and data that replace it are established.

1. Introduction

Nowadays, GIS are used by many local or federal authorities. These information systems help decision-makers. They are based on specific geographical data. This data is often provided by specialized institutes. These organizations have specific missions. For instance, in France the cadaster manages the cadrastal map for tax ends. The cadaster is thus a data producer who delivers information to users.

In this context, the update process is a difficult task. Initially, the producer updates its products. He delivers regularly new datasets to users. Users should integrate this new data in their information system.

We present in section 2 the producer and user context within the framework of an update process. We specify in section 3 problems raised by operations described in section 2. Section 4 presents a process in order to improve the update task carried out by the user.

2. Context

2.1 The user information system

For users, GIS are set up to answer specific tasks such as town planning, facility management. Thus, such information systems focus on operations that are useful to perform these tasks.

Data stored in these information systems is described according to a schema (called User Schema in figure 1). This schema translates the user representation of the real world made according to a model (entity-association, object, ...) . This schema should also take user needs into account. However, data may have distinct origin.

Figure 1: User GIS

We distinguish (according to its origin) data that we call:

Reference data. This data provides information in order to describe the user area of interest. The production of reference data is often complex and expensive. The user seldom has the technical skill to produce such data. Therefore, he purchases such data from institutional producers. In France, for the cadastral map, the Direction Générale des Impôts is such an institutional producer. In this context, production specifications and data definition are often predefined by the producer.
User data. It is specific to each user. The user produces and manages this reference data. AThis data is associated with the reference data to allow its localization, sometimes it completes reference data with information that is useful to the user.

Reference and user data follow distinct constitution processes. For user data, the user is responsible for the initial data capture and the process undergone by this data. Hence, he is a data producer. We are not interested in this process. Otherwise, reference data is built up by a producer who delivers it.

Reference data and user data coexist in the user information system. Moreover, they are bound by semantic and spatial relations. Commercial GIS makes it possible to separate data in distinct information layers. For [Laurini and Thompson, 1992], such an organization may correspond to various perceptions of the real world made by the user. Hence, these layers are ``views'' such as those defined for databases. Thus, a layer corresponds to a specific topic. This organization in layers enables us to distinguish between reference data and user data. Two implementations are thus possible:

Several information layers are used to store reference data and user data. Spatial relations between two information layers are not managed. The superposition of these layers makes it possible to determine spatial relations between objects. Therefore, two information layers should be crossed in order to compare them.
A single information layer is used to store reference data and user data. In this configuration, spatial relations between reference and user data are explicitly managed by the GIS. All possible intersections are stored (this results for example in the creation of nodes. These nodes are the intersection of arcs corresponding to user data and reference data).

Example: We consider the management of a utility network. The information system often uses cadastral data (e.g. parcel, buildings) to locate the network. Therefore, this cadastral data is reference data. The description of the network, the meter relative to each building are user data. There is a spatial relation between a meter and the building to which this meter is attached. If this data is divided in several information layers, buildings and meters are only graphically superimposed (see figure 2(a)). In the case of a single information layer, spatial relations (which can be topological) between reference and user data are managed (see figure 2(b)).

Figure 2: Different Implementations

These two implementations imply different problems relative to reference data update. These problems are the subject of section 3. In the following subsection, we present how reference data may be integrated in a user GIS.

2.2 The integration of reference data

Data transfer between the producer and the user is relative to reference data. Data delivered by the producer is included in a specific product. We call this product the transfer dataset. Only bulk transfer is considered here. This transfered dataset describes, like a snapshot, the state of the world at transfer time. Such a data transfer is composed of data, a schema that structures transfered data (called transfer schema) and sometimes metadata (see figure 3). The transfer dataset is encoded according to a given format.
Example: The transfer of the French digital cadastral map (DCM) obeys to the EDIGéO format. The transfer schema is specified by the producer [Direction Générale des Impôts, 1995]. Information contained in a dataset is mainly graphic. The description concerns land parcels, buildings and topographic data. Information relative to land owners is delivered separately.

Figure 3: Data Transfer

The user can not directly use data provided by the producer. This data must undergo some transformations during the integration process.

Format translation. Commercial GIS use their own proprietary data format (also called internal format). In order to be understandable by a GIS, transfered data has to be translated from the transfer format to the internal format. Tools such as proposed by [Clement et al., 1997] may help users during this translation stage. To improve data transfer between GIS, transfer standards such as SAIF or DIGEST are implemented. However, it remains necessary to translate transfered data.
Establishing correspondences between the transfer and the user schema. The user schema may be different from the transfer schema. To integrate the data provided by the producer, relations between these two schemata have been established. Problems due to this operation are presented by [Nyerges, 1989]. [Spaccapietra et al., 1996] propose an approach to solve conflicts which appear during this process.
Importing of data in the user database. Data undergoes modifications like the change of geodetic datum, ellipsoid (example: change from WGS84 to a national system as in France NTF). Objects contained in the transfer dataset are modified to be in accordance with the user schema (example: a road section is defined in the transfer schema as a portion of road between two crossroads. For the user schema, a road section is defined as a portion of road having a homogeneous road surface. In this case, it is necessary to adapt road sections to their new semantic definition).

These three stages should be reached to integrate information provided by the producer. They are long and tedious. Reference data may also be completed with user data. This happens after the integration of this reference data in the user information system.

However, due to human intervention or natural phenomena, the geographical space evolves. The information system has to represent these evolutions:

User data is under the responsibility of the user. He has to take occurred changes into account.
Reference data depends on the producer. He regularly delivers new datasets. We call this transfer the update transfer.

3. The update transfer

3.1 Context of the update transfer

The producer regularly provides to the user new datasets. These datasets describe the state of the studied area at the transfer time. Such successive data transfers allow to update reference data in the user information system.

For each data transfer, the user has to repeat the integration process described in the previous section. If transfer schema and user schema do not evolve, rules and correspondences established between both schemata are still valid. This data integration process leads to the creation of a new dataset in the user database. Now, the user information system has two different datafiles:

An up-to-date reference dataset. We call this dataset the new dataset;
A reference dataset that was previously integrated with user data associated with it. We call this dataset the old dataset.

This state is described in figure 4.

Figure 4: User GIS after the integration of a new dataset

According to the implementations:

If several information layers coexist, reference data may be stored in two layers: one layer for the old dataset and another layer for the new dataset. The old dataset should then be replaced by the new dataset and links established with user data should be managed.
If there is only one information layer, new reference data is incorporated in this information layer. Old reference data, new reference data and user data coexist in the same information layer.

For the user, old reference data have to be replaced with new data. Inconsistencies may thenappear wiyhin the system. Indeed, during the modification of reference data, relations previously established with this object should also be modified. In a GIS, semantic relations are explicitly managed. For an altered object, new semantic relations are then established in accordance with the database schema. Moreover, spatial relations between objects are implicitly managed. Therefore, the user should check that spatial relations between objects are not in contradiction with their semantic definition. Therefore, the user has to establish spatial integrity constraints between object types.

3.2 Constitution of new reference data

The integration process is dependent on the final functionality of the information system. Problems arising from the introduction of new reference data are relative to the management of the existing relations between reference and user data. According to user implementation (one or multiple information layers) and to the way of using reference data, the introduction of new reference data in an information system may be more or less complex.

Several information layers. Reference data is stored in a specific information layer.

Reference data and user data are independent. Reference data is used as a base map. Such data forms a picture of the space which is superposed on user data. In this context, there is no interaction between user data and reference data. No processing is related to this reference data.
Example: The cadastral map is used to locate gas networks. It is then possible to remove the old reference dataset and to replace it by a new dataset. Inconsistencies may potentially appear in the information system but they do not affect processings performed by the user.
Reference data and user data are correlated. Users have to deal with two main problems:
- Data should comply with spatial integrity constraints relative to semantics.
  Example: A user captures trees (user data). Reference data consist of buildings. Buildings are surrounded with trees. An integrity constraint may be expressed as: ``trees are located outside buildings''. If a side extension is built onto a house, some trees may be located in this building. However this violates the integrity constraint.
  The user has to specify which constraints stored data should conform to. In this context, [Ubeda and Egenhofer, 1997] propose a process to define, to detect and to correct such errors in a GIS. It is however necessary to apply this mechanism to the whole dataset.
- Geometrical relations between multiple information layers. User data may rely on reference data. Then, if this reference data is deleted, user data associated with this reference data is meaningless.
  Example: The department of transportation locates traffic accidents. These traffic accidents are user data. It is stored in a specific information layer. This data is superposed to the road which is a reference data stored in another information layer. After an update transfer, new reference data is imported in the information system. Sometimes, traffic accidents are no more placed on a road. Indeed, the road alignment may have changed [Dubreil, 1996].
  In this configuration, information layers are distinct. Therefore, each layer has its own geometrical description. Updates relative to reference data should be propagated towards user data which is connected to it.

A single information layer. Reference data and user data are stored in the same information layer. In this context, the GIS manages spatial relations between these two data types. We identify several problems:

Data should comply with spatial integrity constraints relative to semantics. This problem has been previously described.
Spatial relations between user and reference data should be defined. The GIS manages these spatial relations. Therefore, the GIS may introduce new elements such as nodes which correspond to the intersection between reference data and user data. This reference data and user data may share the common graphic primitive.
Example: the intersection between a house (a reference data) and a power line (a user data) is represented by a node. If the power line is removed, this node must also be deleted.
Reference and user data may share a common graphic primitive. Then, reference data should be updated in accordance with user data. Sometimes, for reference data, spatial property may not be updated.

In many cases, inconsistencies appearing in the user information system are relative to data semantics or to spatial relations semantics. These problems are closely connected with the implementation chosen by the user for its information system. We present several problems arising with the introduction of a new reference data in the user information system. The complete replacement of reference data is then a difficult task. Hence, user often seeks to limit this update process to data items which evolved.

4. To improve the update integration process

To reduce the number of operations to be carried out during the update process, the user seeks to isolate data which underwent transformations among the update dataset. After the integration process, it is possible to compare new and old reference datasets in order to detect changes that occurred. Hence, this step is made up of a systematic comparison of objets stored in these datasets. For each object, modifications that affect spatial and non-spatial properties are searched. [Lemarié and Raynal, 1996] presents some tools which allow to compare datasets.

However, we believe that the identification of changes that occurred must be done before the integration process. Indeed, the number of changes that occurred is small compared to the volume of transfered data in a bulk transfer. If altered objects are identified in the dataset transfer before their integration, the amount of objects to be integrated is limited. We present in the following paragraph how geographical features which underwent modifications may be isolated within the dataset transfer.

4.1 To isolate changes

We use information contained in the dataset transfer to isolate altered objects. The DCM transfer is our case study. So, basic evolutions are relative to the following operations:

A land parcel is divided. A land parcel may be subdivided into several new parcels. There is an ancestry relation between the old land parcel (ancestor) and new parcels (descendant). Each new land parcel has a new identifier.
Land parcels are merged. Several contiguous land parcels are merged to form a new parcel. Hence, several objects are deleted and replaced by the new item. This new item, which is a parcel, has a new identifier.
Extraction or integration in the State property: In France, the State property is called ``domaine public''. This State property is not registered, parcels that belong to the State property are not shown on cadastral map. It is possible to alter the State property: a portion of territory that belongs to the State property then becomes private ownership of the State. It is called ``extraction'' from the State property. This is equivalent to the creation of a new land parcel. A new object is added in the digital cadastral map. Land parcels may also fall into public domain. In that case, they are deleted.

To isolate changes that occur we use either the object identifier, which is a geographic identifier or temporal information on update time.

Geographical identifier. Each land parcel has a single geographical identifier. The land register allocates these identifiers. Any modification of a parcel boundary implies the creation of a new land parcel. This new parcel get a new identifier. It is possible to use this identifier to determine whenever an objet is created or deleted.
We suggest to maintain a list of geographical identifiers for land parcels that are already integrated in the user information system. This data stems from the old dataset. Identifiers that stem from the update dataset transfer form a second list. These two lists are then compared. Table 1 presents the result of this process. The user gets a list of unchanged parcels, a list of deleted parcels (called old parcels) and a list of new parcels.

		Old Dataset
		Present	Missing
New Dataset	Present	Unaltered	Created
New Dataset	Missing	Deleted	-

Table 1: Result of the comparison of two datasets based on identifiers

Object dating. For each object, information about the time at which the last update happened is stored. This update time is a metadata relative to quality. This metadata is part of the transfer. This temporal information is the transactional time at which the modification was recorded by the producer.
Objects whose temporal information (transactional time) is greater than the time at which the previous data transfer occurred are altered. Then, for the new update dataset, the user gets a list of altered object. However, he has no information about changes that could affect data items stored in his information system. It is not possible to know if altered items refer to an item creation or if there is a modification of an existing item. We use temporal metadata to detect altered buildings.

Both mechanisms allow the user to draw up a list of objects that must be integrated in his information system. These items and information relative to them (e.g. metadata) should be extracted from the transfer dataset. Each altered object is separately integrated in the user information system. This process extracts spatial and non-spatial descriptions of this data. Possible relations between objects and their neighbourhood are not taken into account.

Spatial relations: an altered object is spatially related to his neighbours. These relations are not considered.
- If this spatial relation is modified. Both objects are in a new state. Then their new state is detected.
- If this spatial relation remains unchanged. In this context, there is only one altered object. The spatial relations between the altered object and its neighbours remains unchanged. Therefore, his neighbours are not identified as new.
We believe this process restricts the propagation of updates between neighbour objects.
Semantic relations: For the DCM transfer, the schema does not allow such relations. Thus, we do not take them into account.

Such processes enable us to extract a subset from the bulk transfer. This subset is limited to the new state of objects which underwent modifications. Hence, only the new state for altered objects is integrated in the user information system. It is then useful to analyze filiations between the old and the new state of reference data.

4.2 To establish filiation

Several reference data coexist in the user information system. The old dataset may include objects which are no more up-to-date. Moreover, objects which underwent evolutions are also stored in this information system. These new objects should then be associated with data they replace. Therefore, from the previous results, we establish filiations between old and new objects.

The user has a list of the altered items. This list includes a set of items that appeared in the new dataset (i.e. new parcels) and a set of items that disappeared from the old dataset (i.e. old parcels).

Between successive data transfers, the cadaster performs several updates. Basic updates follow one another in a combination of division/merging/extraction or integration in the State property. There is a large number of updates if the area undergoes lots of successive cadastral reconfigurations. Hence, a new land parcel may result from several fractions of destroyed parcels. Then, to associate new and old land parcels, we use the following mechanism:

For each parcel included in the list of new parcels, its intersection with every parcel belonging to the list of old parcels is done.
- If the intersection is empty or is a segment: the new parcel is extracted from the State property.
- If the intersection includes several old parcels: for each new parcel, an old parcel or a part of parcel may be associated with. Each subpart of a deleted parcel is associated with an unique new parcel.
After this stage, an ancestry instance connection is introduced between a destroyed parcels (i.e old parcel) and a new parcel.
Subpart of old parcels that are not associated with new land parcel belongs now to the State property. This old parcel is incorporated in the State property.

This mechanism establishes a relation between an old parcel and its descendant. However, this mechanism does not provide any information about intermediate events that led a land parcel to its final state. Therefore, a complete history can not be built for these land parcels.

The user only has the list of the objects modified in the new dataset. In this context, we carry out the intersection between reference data already integrated in the user information system (i.e. old buildings) and the new objects (i.e. new buildings). The mechanism is similar to the previous one. However, we do not know which objects (old reference data) were modified.

For each building included in the list of new buildings, we carry out the intersection with the buildings previously integrated (the old reference dataset).
- If the intersection is empty. A new building is created.
- If the intersection in not empty. A new building is associated with old buildings.
Deleted buildings: Metadata about temporal information contains information about the kind of evolution undergone by an object. This information is used to detect if the considered building is still present.

To substitute reference data. The proposed mechanism does not solve all the problems that arise during the integration process. However, we believe that this mechanism makes this process easier. Indeed, establishing correlation between user data and reference data is now limited to a subset of the new dataset that has been modified. Thus, it is possible to determine which user data is associated with the reference data that changed. This process may be carried out while calculating the intersection between the user data and reference data. Then, for each new object, user data that is potentially associated with it is known.

5. Conclusion

In the context of GIS, we study the problems arising from the data transfer between a producer and an user. For the user, the integration of new reference data in an existing information system is a difficult operation. Indeed, according to the implementation chosen by the user, links between reference data and user data should be managed. Therefore, we analyze the relations and problems arising when an update occurs. This enables us to present an approach based on the detection of changes before the integration of reference data in the user information system. We believe that our process simplifies integration and incorporation of new reference data. So, established ancestry instance connections should improve the substitution of old reference data and the management of possible relations between this data and user data. This new task constitutes the base of our future work.

Acknowledgement

The author is grateful to Dr Thérèse Libourel for her valuable advices and comments.

References

[Clement et al., 1997] Clement, G., Larouche, C.,Gouin, D., Morin, P. and Kucera, H., 1997. OGDI: Toward Interoperability among Geospatial Databases. SIGMOD RECORD 26(3), pp. 18-23.

[Direction Générale des Impôts, 1995] Direction Générale des Impôts. Standard d'échange des objets du plan cadastral informatisé. 1995.

[Dubreil, 1996] Dubreil, F., 1996. Etude de l'intégration de la mise � jour des données BDCarto dans les bases utilisateur de l'équipement. Master's thesis, Ecole Nationale des Sciences Géographiques, Saint-Mandé France.

[Laurini and Thompson, 1992] Laurini, R. and Thompson, D., 1992. Fundamentals of Spatial Information Systems. The A.P.I.C. Series, Academic Press.

[Lemarié and Raynal, 1996] Lemarié, C. and Raynal, L., 1996. Geographic data matching : first investigations for a generic tool. In: GIS/LIS'96, pp. 405-420.

[Nyerges, 1989] Nyerges, T. L., 1989. Schema Integration Analysis for the Development of GIS Databases.Int. Journal of Geographical Information Systems 3(2), pp. 153-183.

[Spaccapietra et al., 1996] Spaccapietra, S., Parent, C. and Devogele, T., 1996. Analysis of Discrepancies in Spatial Data Representation. In: Cooperative Database Systems for Advanced Systems (CODAS), University of Kyoto and ACM Japan and ACM SIGMOD Japan, Kyoto (Japon).

[Ubeda and Egenhofer, 1997] Ubeda, T. and Egenhofer, M. J., 1997. Topological Error Correcting in GIS. In: M. Scholl and A. Voisard (eds), Advances in Spatial Databases SSD'97, LNCS 1262, Springer, pp. 283-297.