Spatio-Temporal Database Management

Currently, most models proposed for spatio-temporal databases describe changes that involve independent entities. However, many dynamic applications need new models to relate evolution of spatial entities linked by common properties and constraints or relationships. In transportation GIS, an activity-event matrix describes individual entity behaviours, travel activities and routes on a transportation network. On the other hand, modelling disaggregate travel choices behaviour for several entities implies the identification of new mechanisms to describe the evolution of their joint spatial distribution. This paper introduces and describes the concept of sets of geographical entities needed for the analysis of travel behaviour in metropolitan areas. We propose a taxonomy for the description of the evolution of entity sets in space and the selection of appropriate statistical indexes to analyse their geographical patterns. Such a framework may become a reference for the development of spatio-temporal database representations of spatial patterns evolution.

This paper proposes a unified formal environment for spatiotemporal databases and modeling the change in identity of objects. The real world is represented as a set of snapshots consisting of identifiable objects and relations among objects. A database needs transaction time for the consistent management of temporal links among identifiers. Four basic operations affecting object identity are proposed: create, destroy, suspend, and resume. Their compositions are either applicable on a single object (evolve), or on a group of objects (constructive and weak fusion, fission, aggregate and segregate). These operations build a finite set of identity affecting operations — lifestyles. Executable algebraic specifications, written in the functional programming language Haskell, are provided both for the database model and for lifestyles. The specifications of typical lifestyles can be re-used for various application domains.

We define a formal model of spatio-temporal partitions which can be used to model temporally changing maps. We investigate new applications and generalizations of operations that are well-known for static spatial maps. We then define a small set of operations on spatio-temporal partitions that are powerful enough to express all these tasks and more. Spatio-temporal partitions combine the general notion of temporal objects and the powerful spatial partition abstraction into a new, highly expressive spatio-temporal data modeling tool.

In order to develop a system to propagate updates we investigate the semantic and spatial relationships between independently produced geographic data sets of the same region (data set integration). The goal of this system is to reduce operator intervention in update operations between corresponding (semantically similar) geographic object instances. Crucial for this reduction is certainty about the semantic similarity of different object representations. In this paper we explore a framework for ontology-based geographic data set integration, an ontology being a collection of shared concepts. Components of this formal approach are an ontology for topographic mapping (a domain ontology), an ontology for every geographic data set involved (the application ontologies), and abstraction rules (or capture criteria). Abstraction rules define at the class level the relationships between domain ontology and application ontology. Using these relationships, it is possible to locate semantic similarity at the object instance level with methods from computational geometry (like overlay operations). The components of the framework are formalized in the Prolog language, illustrated with a fictitious example, and tested on a practical example.

In this paper we describe the technical and organizational solution that has been designed and implemented in Italy to deal with cadastral data management. The system, named “Sistema di Interscambio Catasto-Comuni“ (SICC), allows to exchange cadastral data among the principal entities interested in Italy to the treatment of cadastral information, that are Ministry of Finance, Municipalities, Notaries, and Certified Land Surveyors. The system is accessible nation-wide through a WEB-based interface since September 1998 and the effectiveness of its use is demonstrated by the sharp increase in the number of requests managed during the first months: in January 1999 it has been used by more than 15.000 end-users.

In recent years, spatio-temporal data are increasingly recorded in database-enabled information systems. To share the benefit, often, a public data access is provided utilizing WWW-based visual interfaces. If spatio-temporal data are queried, data visualization and exploration in a spatial and temporal context is needed to better present and analyze spatio-temporal behaviours and relationships. In existing WWW-based interfaces of temporal geographical information or scientific data visualization systems, only videos, static visualizations (images) or, recently, VRML-worlds (Virtual Reality Modeling Language) are applied which support neither 3D- nor temporal navigation, respectively. Additionally, these interfaces offer only small support for further exploratory tools according to the temporal domain and to conceptual database entities which users are often aware of. In this paper, we propose an extension to VRML which supports the description of spatio-temporal (temporal 3D-)graphics and entities by integrating the valid time dimension and the entity concept. This is realized by a set of new VRML-nodes representing temporal geometries, time references and database entities and a set of interactive visualization techniques extending standard VRML-browsers to perform temporal navigation and to further explore the visualization during presentation. One result of this proposal is that a new type of visualizations, i.e. interactive, temporal visualizations (animations), can be generated, stored in files, integrated in Web-pages and explored spatially and temporally by interaction or animation. This is demonstrated by two decision support applications from water management and urban planning.

Nearest neighbor queries have received much interest in recent years due to their increased importance in advanced database applications. However, past work has addressed such queries in a static setting. In this paper we consider instead a dynamic setting where data objects move continuously. Such a mobile spatiotemporal environment is motivated by real life applications in traffic management, intelligent navigation and cellular communication systems. We consider two versions of nearest neighbor queries depending on whether the temporal predicate is a single time instant or an interval. For example: “find the closest object to a given object o after 10 minutes from now”, or, “find the object that will be the closest to object o between 10 and 15 minutes from now”. Since data objects move continuously it is inefficient to update the database about their position at each time instant. Instead our approach is to employ methods that store the motion function of each object and answer nearest neighbor queries by efficiently searching through these methods.

In this paper we present the prototype database system Concert and the incorporation of a framework of a generic index tree for spatio-temporal data. We show the ideas behind the Concert architecture as far as they are important to understand the framework approach presented. We show how the index is based on the conceptual behaviour of data in contrast to generalized algorithms or methods. Because of the simplicity of R-trees we take an R-tree like structure to explain our generic spatio-temporal index. It is remarkable that in Concert a generic index can be defined without any predefined “hard-wired” spatial or temporal data types such as intervals or rectangles. As it turns out the only important properties needed are an OVERLAP and a SPLIT function, the first one checking for spatial or temporal overlap of objects, the second one providing a hierarchical decomposition of the data space into subspaces. If, in addition, splitting of data objects is allowed we are able to define manageable node sizes, leading to an improved generic index similar to R+-trees or other derivations.

This paper describes the design of the BASIS prototype system. BASIS stands for Benchmarking Approach for Spatial Index Structures. It is a prototype system aiming at performance evaluation of spatial access methods and query processing strategies, under different data sets, various query types, and different workloads. BASIS is based on a modular architecture, composed of a simple storage manager, a query processor, and a set of algorithmic techniques to facilitate benchmarking. The main objective of BASIS is twofold: (i) to provide a benchmarking environment for spatial access methods and related query evaluation techniques, and (ii) to allow comparative studies of spatial access methods in different cases but under a common framework. We currently extend it to support the fundamental features of spatiotemporal data management and access methods.

Several applications require management of data which is spatially dynamic, e.g., tracking of battle ships or moving cells in a blood sample. The capability of handling the temporal aspect, i.e., the history of such type of data, is also important. This paper presents and evaluates three temporal extensions of the R-tree, the 3D R-tree, the 2+3 R-tree and the HR-tree, which are capable of indexing spatiotemporal data. Our experiments focus on discretely moving points (i.e., points standing at a specific location for a time period and then moving “instantaneously”, and so on and so forth). We explore several parameters, e.g., initial spatial distribution, spatial query area and temporal query length. We found out that the HR-tree usually outperforms the other candidates, in terms of query processing cost, specially when querying time points and small time intervals. However, the main side effect of the HR-tree is its storage requirement, which is much larger than that of the other approaches. To reduce that, we explore a batch oriented updating approach, at the cost of some overhead during query processing time. To our knowledge, this study constitutes the first extensive, though not exhaustive, experimental comparison of access structures for spatiotemporal data.

Recently, there has been a lot of interest in temporal granularity, and its applications in temporal dependency theory and data mining. Generalization hierarchies used in multi-dimensional databases and OLAP serve a role similar to that of time granularity in temporal databases, but they also apply to non-temporal dimensions, like space. In this paper, we first generalize temporal functional dependencies for non-temporal dimensions, which leads to the notion of roll-up dependency (RUD).We show the applicability of RUDs in conceptual modeling and data mining. We then indicate that the notion of time granularity used in temporal databases is generally more expressive than the generalization hierarchies in multi-dimensional databases, and show how this surplus expressiveness can be introduced in non-temporal dimensions, which leads to the formalism of RUD with negation (RUD¬). A complete axiomatization for reasoning about RUD¬ is given.

We consider the scheme of indefinite constraint databases proposed by Koubarakis. This scheme can be used to represent indefinite information arising in temporal, spatial and truly spatiotemporal applications. The main technical problem that we address in this paper is the discovery of tractable classes of databases and queries in this scheme. We start with the assumption that we have a class of constraints C with satisfiability and variable elimination problems that can be solved in PTIME. Under this assumption, we show that there are several general classes of databases and queries for which query evaluation can be done with PTIME data complexity. We then search for tractable instances of C in the area of temporal and spatial constraints. Classes of constraints with tractable satisfiability problems can be easily found in the literature. The largest class that we consider is the class of Horn disjunctive linear constraints over the rationals. Because variable elimination for Horn disjunctive linear constraints cannot be done in PTIME, we try to discover subclasses with tractable variable elimination problems. The class of UTVPI^≠ constraints is the largest class that we show to have this property. Finally, we restate the initial general results with C ranging over the newly discovered tractable classes. Tractable query answering problems for indefinite temporal and spatial constraint databases are identified in this way.