STATE AND TIME TOPOLOGIES FOR GEOGRAPHIC INFORMATION 
Hazem Raafat, Zhongsen Yang 
Department of Computer Science 
University of Regina 
Regina, Saskatchewan 
Canada S4S 0A2 
and 
David Gauthier 
Department of Geography 
University of Regina 
Regina, Saskatchewan 
Canada S4S 0A2 
ABSTRACT 
Research on time and data models has focused mainly on 
the identification of extensions to the conventional rela- 
tional model for non-spatial data. Although these models 
provide adequate semantic capability to deal with time, 
they are not suitable for spatial data such as geographical 
information in which historical information must be spa- 
tially referenced. This paper proposes two-level state topo- 
logies: a state topology for geographic objects in a GIS 
database and a state topology for a geographic object. 
From a temporal perspective, these two-level state topolo- 
gies may also be viewed as two-level time topologies: a 
time topology for a GIS database and a time topology for a 
geographic object. Based on these state and time topolo- 
gies, the storage approach for geographic historical infor- 
mation are provided. 
KEY WORDS: State Topology, Time Topology, 
Geographic Information Systems 
1. INTRODUCTION 
More and more it is being realized that the element of time 
should be introduced into data models in order to represent 
the dynamically changing world (Snodgrass 1990, S00 
1991, Stam et al. 1988). The goal of historical databases is 
to make the time dimension accessible to users. Snodgrass 
and Ahn (1985, 1986) have introduced two important 
aspects of time: world time (or valid time) and system time 
(or transaction time). They can be represented by two axes. 
The world-time axis traces the changes which occur in the 
real world, and the system-time axis traces the changes that 
are recorded in the database. A historical database only 
contains world time. A temporal database contains both 
world time and system time. In this paper, we focus on 
historical database for GIS. 
There are three possible approaches to include world time 
into the relations: relation-based world time stamping, 
tuple-based world time stamping, and attribute-based world 
time stamping. In the relation-based world time stamping 
approach (Klopprogge 1981, Mckenzie et al. 1987), each 
relation includes a world time interval during which the 
data in the relation is effective. The approach creates and 
stores a new snapshot of a relation when any of its attri- 
bute values changes. This approach is simple, but highly 
155 
data redundant and obscures individual object histories. 
Tuple-based world time stamping approach (Ariav 1986, 
Lum et al. 1984, Sarda 1990a, Sarda 1990b) maintains a 
world time interval for each tuple. Whenever any of the 
attribute values of a tuple changes, its tuple-time stamp is 
amended and a new tuple may be appended to the relation. 
Consequently, each relation contains the history for each 
tuple. This approach is mostly used for representation and 
implementation of time modelling. One tuple-based time 
stamping method (Ariav 1986) orders tuples within each 
relation. Another tuple-based time stamping method (Lum 
et al. 1984) uses two relations to segregate current data 
from historical data and connect them by history chains. 
Attribute-based world time stamping approach (Gadia 
1988) maintains a world-time interval for each attribute 
value. Thus, each tuple contains a history for each attri- 
bute. Although this approach is compact, it requires 
variable-length fields of a complex domain to hold lists of 
time-stamped attribute versions and needs an alternate rela- 
tional algebra to manage them. 
The historical database attempts to model an enterprise 
over time, but it is not suitable for spatial applications 
which deal not only with thematic and time information, 
but also with location and topological information. In 
recent years, more attention has been directed to 
temporal/historical GIS design related to vector data struc- 
tures (Langran 1989a, Langran 1989b, Langran et al. 
1988). 
The earliest historical GIS was designed by Basoglu and 
Morrison (1978). They produced a hierarchical data struc- 
ture to store and retrieve the historical changes of U.S. 
county boundaries. Although the system could produce a 
snapshot of how the particular boundaries appeared on a 
given time, it did not represent widely-used topological 
relationships and could not recognize that one line segment 
might be no longer a particular county boundary, but 
remain in use as another county boundary through histori- 
cal subdivision. 
Langran and Chrisman (1988) proposed a space-time com- 
posite data model to treat spatial changes over time. In this 
conceptual model, each change causes the changed portion 
of the coverage to break from its parent object and become 
a discrete object with its own distinct history. Therefore, 
this method decomposes the object over time into increas- 
ingly smaller fragments (objects) and describes them by a