Survey of Spatio-Temporal Databases

Spatio-temporal databases aim to support extensions to existing models of Spatial Information Systems (SIS) to include time in order to better describe our dynamic environment. Although interest into this area has increased in the past decade, a number of important issues remain to be investigated. With the advances made in temporal database research, we can expect a more unified approach towards aspatial temporal data in SIS and a wider discussion on spatio-temporal data models. This paper provides an overview of previous achievements within the field and highlights areas currently receiving or requiring further investigation.     

Spatio-Temporal Data Types: An Approach to Modeling and Querying Moving Objects in Databases

Spatio-temporal databases deal with geometries changing over time. In general, geometries cannot only change in discrete steps, but continuously, and we are talking about moving objects. If only the position in space of an object is relevant, then moving point is a basic abstraction; if also the extent is of interest, then the moving region abstraction captures moving as well as growing or shrinking regions. We propose a new line of research where moving points and moving regions are viewed as 3-D (2-D space+time) or higher-dimensional entities whose structure and behavior is captured by modeling them as abstract data types. Such types can be integrated as base (attribute) data types into relational, object-oriented, or other DBMS data models; they can be implemented as data blades, cartridges, etc. for extensible DBMSs. We expect these spatio-temporal data types to play a similarly fundamental role for spatio-temporal databases as spatial data types have played for spatial databases. The paper explains the approach and discusses several fundamental issues and questions related to it that need to be clarified before delving into specific designs of spatio- temporal algebras.     

Conceptual Modeling and Querying in Multimedia Databases

In this paper, we discuss some design principles that will aid in the design and querying of multimedia databases. We use an object-relational data model and argue that multimedia objects should normally have a special attribute called core which stores the real object itself in contrast to the abstraction which is reflected in the rest of the attributes. We present an extension to the ER Diagram that takes advantage of the core notion to facilitate design of multimedia databases. We discuss some desirable features in a query language for multimedia databases: simplifications like the use of path expressions and implicit use of functions (methods) as attributes, and explicit specification of the display layout and format either at the data definition level or query specification level. To materialize this last feature, we propose a display specification extension to SQL (SQL+D) that we have implemented.     

An XML-Based Approach to Publishing and Querying the History of Databases

There is much current interest in publishing and viewing databases as XML documents. The general benefits of this approach follow from the popularity of XML and the tool set available for visualizing and processing information encoded in this universal standard. In this paper, we explore the additional and unique benefits achieved by this approach on temporal database applications. We show that XML with XQuery can provide surprisingly effective solutions to the problem of supporting historical queries on past content of database relations and their evolution. Indeed, using XML, the histories of database relations can be naturally represented by temporally grouped data models. Thus, we identify mappings from relations to XML that are most conducive to modeling and querying database histories, and show that temporal queries that would be difficult to express in SQL can be easily expressed in standard XQuery. This approach is very general, insofar as it can be used to store the version history of arbitrary documents and, for relational databases, it also supports queries on the evolution of their schema. Then, we turn to the problem of supporting efficiently the storage and the querying of relational table histories. We present an experimental study of the pros and cons of using native XML databases, versus using traditional databases, where the XML-represented histories are supported as views on the historical tables.     

PIST: An Efficient and Practical Indexing Technique for Historical Spatio-Temporal Point Data

Despite pressing need, current relational database management systems (RDBMS) support for spatio-temporal data is limited and inadequate, and most existing spatio-temporal indices cannot be readily integrated into existing RDBMSs. This paper proposes a practical index for spatio-temporal (PIST) data, an indexing technique, rather than a new indexing structure, for historical spatio-temporal data points that can be fully integrated within existing RDBMSs. PIST separates the spatial and temporal components of the data. For the spatial component, we develop a formal cost model and a partitioning strategy that leads to an optimal space partitioning for uniformly distributed data and an efficient heuristic partitioning for arbitrary data distributions. For the temporal component of the data a B^?+?-tree is used. We show that this layer’s performance can be maximized if an optimal maximal temporal range is enforced, and we present a procedure to determine such an optimal value. Being fully mapped onto a RDBMS, desirable and important properties, such as concurrency control, are immediately inherited by PIST. Using ORACLE as our implementation platform we perform extensive experiments with both real and synthetic datasets comparing its performance against other RDBMS-based options, as well as the MV3R-tree. PIST outperforms the former by at least one order of magnitude, and is competitive or better with respect to the latter, with the unarguable advantage that it can readily used on top of virtually any existing RDBMS.     

基于受限移动对象当前及将来时刻检索的时空索引结构研究

在给定的空间及时间范围内,如何构建高效的时空索引结构,以实现对移动对象快速有效的检索,是实现定位服务、智能交通、数字化战争等诸多应用中所迫切需要解决的问题.本文依据移动对象的运动特点,提出了一种面向当前及将来时刻快速更新及有效检索的索引结构—PQR树.PQR树是综合PMRQuad树和R*树的结构,首先依据道路分布用PMRQuad树将移动对象的索引空间实行粗略的层分割,将所有快速移动对象与道路相关联.然后用R*树索引分布在各个子空间块内的类静止对象.实验结果表明PQR树具有良好的更新和查询性能.     

Classes of Spatio-Temporal Objects and their Closure Properties

We present a data model for spatio-temporal databases. In this model spatio-temporal data is represented as a finite union of objects described by means of a spatial reference object, a temporal object and a geometric transformation function that determines the change or movement of the reference object in time.We define a number of practically relevant classes of spatio-temporal objects, and give complete results concerning closure under Boolean set operators for these classes. Since only few classes are closed under all set operators, we suggest an extension of the model, which leads to better closure properties, and therefore increased practical applicability. We also discuss a normal form for this extended data model.     

Constraint-based Interoperability of Spatiotemporal Databases*

We propose constraint databases as an intermediate level facilitating the interoperability of spatiotemporal data models. Constraint query languages are used to express translations between different data models. We illustrate our approach in the context of a number of temporal, spatial, and spatiotemporal data models.     

Beyond Schema Versioning: A Flexible Model for Spatio-Temporal Schema Selection

Schema versioning provides a mechanism for handling change in the structure of database systems and has been investigated widely, both in the context of static and temporal databases. With the growing interest in spatial and spatio-temporal data as well as the mechanisms for holding such data, the spatial context within which data items are formatted also becomes an issue. This paper presents a generalized model that accommodates temporal, spatial and spatio-temporal schema versioning within databases.     

A data model and algebra for probabilistic complex values

We present a probabilistic data model for complex values. More precisely, we introduce probabilistic complex value relations, which combine the concept of probabilistic relations with the idea of complex values in a uniform framework. We elaborate a model-theoretic definition of probabilistic combination strategies, which has a rigorous foundation on probability theory. We then define an algebra for querying database instances, which comprises the operations of selection, projection, renaming, join, Cartesian product, union, intersection, and difference. We prove that our data model and algebra for probabilistic complex values generalizes the classical relational data model and algebra. Moreover, we show that under certain assumptions, all our algebraic operations are tractable. We finally show that most of the query equivalences of classical relational algebra carry over to our algebra on probabilistic complex value relations. Hence, query optimization techniques for classical relational algebra can easily be applied to optimize queries on probabilistic complex value relations.     

Spatio-Temporal Data Handling with Constraints

Most spatial information systems are limited to a fixed dimension (generally 2) which is not extensible. On the other hand, the emerging paradigm of constraint databases allows the representation of data of arbitrary dimension, together with abstract query languages. The complexity of evaluating queries though might be costly if the dimension of the objects is really arbitrary. In this paper, we present a data model, based on linear constraints, dedicated to the representation and manipulation of multidimensional data. In order to preserve a low complexity for query evaluation, we restrict the orthographic dimension of an object O, defined as the dimension of the components ^O ₁ ,..., O _n such that O=O ₁×...× O _n. This allows to process queries independently on each component, therefore achieving a satisfying trade-off between design simplicity, expressive power of the query language and efficiency of query evaluation. We illustrate these concepts in the context of spatio-temporal databases where space and time are the natural components. This data model has been implemented in the DEDALE system and a spatio-temporal application, with orthographic dimension 2, is currently running, thus showing the practical relevance of the approach.     

Continuous Query Processing of Spatio-Temporal Data Streams in PLACE

The tremendous increase in the use of cellular phones, GPS-like devices, and RFIDs results in highly dynamic environments where objects as well as queries are continuously moving. In this paper, we present a continuous query processor designed specifically for highly dynamic environments (e.g., location-aware environments). We implemented the proposed continuous query processor inside the PLACE server (Pervasive Location-Aware Computing Environments); a scalable location-aware database server developed at Purdue University. The PLACE server extends data streaming management systems to support location-aware environments. These environments are characterized by the wide variety of continuous spatio-temporal queries and the unbounded spatio-temporal streams. The proposed continuous query processor includes: (1) New incremental spatio-temporal operators to support a wide variety of continuous spatio-temporal queries, (2) Extended semantics of sliding window queries to deal with spatial sliding windows as well as temporal sliding windows, and (3) A shared-execution framework for scalable execution of a set of concurrent continuous spatio-temporal queries. Experimental evaluation shows promising performance of the continuous query processor of the PLACE server. This work was supported in part by the National Science Foundation under Grants IIS-0093116, IIS-0209120, and 0010044-CCR.     

Object-Oriented Databases with Relational DBMSs

The expediency of the use of object-oriented models of data as datalogical models in designing databases is shown, and methods of integration of relational and object-oriented models are considered. A relational scheme for storage of attributes and relations of object-oriented models is proposed.     

Efficient Window Block Retrieval in Quadtree-Based Spatial Databases

An algorithm is presented to answer window queries in a quadtree-based spatial database environment by retrieving all of the quadtree blocks in the underlying spatial database that cover the quadtree blocks that comprise the window. It works by decomposing the window operation into sub-operations over smaller window partitions. These partitions are the quadtree blocks corresponding to the window. Although a block b in the underlying spatial database may cover several of the smaller window partitions, b is only retrieved once rather than multiple times. This is achieved by using an auxiliary main memory data structure called the active border which requires O(n) additional storage for a window query of size n×n. As a result, the algorithm generates an optimal number of disk I/O requests to answer a window query (i.e., one request per covering quadtree block). A proof of correctness and an analysis of the algorithm's execution time and space requirements are given, as are some experimental results.     

A Filter Flow Visual Querying Language and Interface for Spatial Databases

In this paper a visual approach to querying in spatial databases is presented. A filter flow methodology is used to consistently express different types of queries in these systems. Filters are used to represent operations on the database and pictorial icons are used throughout the language for filters, operators and spatial relations. Different granularities of the relations are presented in a hierarchical fashion for spatial constraints. The language framework and functions are described and examples are used to demonstrate its capabilities in representing different levels of queries, including spatial joins and composite spatial joins. Here, the primary focus is on the query language itself but an overview of the implemented interface of the language is also provided.     

On the expressive power of the relational algebra with partially ordered domains

Assuming data domains are partially ordered, we define the partially ordered relational algebra (PORA) by allowing the ordering predicate ? to be used in formulae of the selection operator σ. We apply Paredaens and Bancilhon's Theorem to examine the expressiveness of the PORA, and show that the PORA expresses exactly the set of all possible relations which are invariant under order-preserving automorphisms of databases. The extension is consistent with the two important extreme cases of unordered and linearly ordered domains. We also investigate the three hierarchies of: (1) computable queries, (2) query languages and (3) partially ordered domains, and show that there is a one-to-one correspondence between them.     

Context-Aware Fuzzy Databases

The development of mechanisms to ease human machine interaction is an issue about which there is increasing interest within both the software world in general, and database systems in particular. A way to tackle this problem is to try to approach the natural way of user expression. The Fuzzy Sets Theory and its application to build Fuzzy Databases constitute a consolidated advance in the literature. Another way is to adapt the interaction of the system to the context where it is running. In this sense, this paper presents an approach to build a model of Fuzzy Databases that dynamically adapts to user context. In order to do this, we have studied the management of the context in Fuzzy Database applications and we propose an architecture for the development of intelligent, flexible and customized context-aware database systems. We also present a proof of concept implementation to be used with SQL:99 standard in Oracle ORDBMS. Finally, through a real application in the medical area, we demonstrate the feasibility of the proposal.     

一种利用模糊关系数据库构建模糊OWL本体的方法

经典OWL本体不能直接表示和处理语义Web应用中广泛存在的模糊知识,鉴于模糊关系数据库在模糊数据表示与处理方面的优势,提出利用模糊关系数据库来构建模糊OWL本体.通过对RDF数据类型进行模糊扩展,并从模糊数据类型角度扩展OWL,解决了模糊OWL本体的表示问题;在此基础上,研究了以模糊关系数据库为数据源的模糊OWL本体的构建方法,该方法为语义Web中模糊本体的构建提供了一个有效的解决方案.     

Fast Nearest-Neighbor Query Processing in Moving-Object Databases

A desirable feature in spatio-temporal databases is the ability to answer future queries, based on the current data characteristics (reference position and velocity vector). Given a moving query and a set of moving objects, a future query asks for the set of objects that satisfy the query in a given time interval. The difficulty in such a case is that both the query and the data objects change positions continuously, and therefore we can not rely on a given fixed reference position to determine the answer. Existing techniques are either based on sampling, or on repetitive application of time-parameterized queries in order to provide the answer. In this paper we develop an efficient method in order to process nearest-neighbor queries in moving-object databases. The basic advantage of the proposed approach is that only one query is issued per time interval. The time-parameterized R-tree structure is used to index the moving objects. An extensive performance evaluation, based on CPU and I/O time, shows that significant improvements are achieved compared to existing techniques.     

从关系数据库到面向对象数据库的发展概述

该文主要论述了在数据库技术发展的过程中起主导作用的关系数据库的特征及其发展历程,同时阐述了面向对象数据库的特征以及其必然取代关系数据库成为数据库技术发展和研究的新的热点.