Spatiotemporal databases

Publications on Spatiotemporal databases

A Comparative Study of Temporal DBMS Architectures

C. Vassilakis, P. Georgiadis, A. Sotiropoulou
in Proceedings of DEXA 96 workshop, Zurich, September 1996.

Abstract:
In the past years, a number of implementations of temporal DBMSs has been reported. Most of these implementations share a common feature, which is that they have been built as an extension to a snapshot DBMS. In this paper, we present three alternative design approaches that can be used for extending a snapshot DBMS to support temporal data, and evaluate the suitability of each approach, with respect to a number of design objectives.

Note:This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Year: 
Research area: 

A Flexible Framework for Managing Temporal Clinical Trial Data

Michael Souillard , Carine Souveyet, Costas Vassilakis, Anya Sotiropoulou
International Journal of Electronic Healthcare, Volume 1, Number 4, 2005.

Abstract:
Clinical trials are processes that produce large volumes of complex data, with inherent temporal requirements, since the state of patients evolves during the trials, and the data acquisition phase itself needs to be monitored. Additionally, since the requirements for all clinical trials have a significant common portion, it is desirable to capture these common requirements in a generalised framework, which will be instantiated for each specific trial by supplementing the trial-specific requirements. In this paper, we present an integral approach to clinical trial management, using a temporal object-oriented methodology to capture and model the requirements, a temporal OODBMS for data storage and a generalised template application, through which trial-specific applications may be generated.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Year: 
Research area: 

An Optimization Scheme for Coalesce/Valid Time Selection Operator

Costas Vassilakis
SIGMOD Record, vol. 29, number 1, March 2000, pp. 38-43.

Abstract:
Queries in temporal databases often employ the coalesce operator, either to coalesce results of projections, or data which are not coalesced upon storage. Therefore, the performance and the optimisation schemes utilised for this operator is of major importance for the performance of temporal DBMSs. Insofar, performance studies for various algorithms that implement this operator have been conducted, however, the joint optimisation of the coalesce operator with other algebraic operators that appear in the query execution plan has only received minimal attention. In this paper, we propose a scheme for combining the coalesce operator with selection operators which are applied to the valid time of the tuples produced from a coalescing operation. The proposed scheme aims at reducing the number of tuples that a coalescing operator must process, while at the same time allows the optimiser to exploit temporal indices on the valid time of the data.

Article available through the ACM Author-izer service:

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Year: 
Research area: 

Composing Cardinal Direction Relations

S. Skiadopoulos and M. Koubarakis
In Artificial Intelligence, 152(2):143--171, 2004

Abstract:
We study the recent proposal of Goyal and Egenhofer who presented a model for qualitative spatial reasoning about cardinal directions. Our approach is formal and complements the presentation of Goyal and Egenhofer. We focus our efforts on the composition operator for two cardinal direction relations. We consider two interpretations of the composition operator: consistency-based and existential composition. We point out that the only published method to compute the consistency-based composition does not always work correctly. Then, we consider progressively more expressive classes of cardinal direction relations and give consistency-based composition algorithms for these classes. Our theoretical framework allows us to prove formally that our algorithms are correct. When we consider existential composition, we demonstrate that the binary relation resulting from the composition of two cardinal direction relations cannot be expressed using the relations defined by Goyal and Egenhofer. Finally, we discuss some extensions to the basic model and consider the composition problem for these extensions.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Year: 
Research area: 

Composing Cardinal Directions Relations

S. Skiadopoulos and M. Koubarakis
In Proceedings of the 7th International Symposium on Spatial and Temporal Databases (SSTD'01), volume 2121 of LNCS, pages 299--317. Springer, July 2001

Abstract:
We study the recent proposal of Goyal and Egenhofer who presented a model for qualitative spatial reasoning about cardinal directions. Our approach is formal and complements the presentation of Goyal and Egenhofer. We focus our eorts on the operation of composition for two cardinal direction relations. We point out that the only published method to compute the composition does not always work correctly. Then we consider progressively more expressive classes of cardinal direction relations and give composition algorithms for these classes. Our theoretical framework allows us to prove formally that our algorithms are correct. Finally, we demonstrate that in some cases, the binary relation resulting from the composition of two cardinal direction relations cannot be expressed using the relations defined by Goyal and Egenhofer

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Year: 
Research area: 

Composition Algorithm for Cardinal Direction Relations

S. Skiadopoulos and M. Koubarakis
In Proceedings of the 2nd Hellenic Conference on Artificial Intelligence (SETN'02), short paper, April 2002.

Abstract:
We present a formal model for qualitative spatial reasoning with cardinal directions that is based on a recent proposal in the literature. We use our formal framework to study the composition operation for the cardinal direction relations of this model. We consider progressively more expressive classes of cardinal direction relations and give composition algorithms for these classes. Finally, when we consider the problem in its generality, we show that the binary relation resulting from the composition of some cardinal direction relations cannot even be expressed using the relations which are currently employed by the related proposal.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Year: 
Research area: 

Computing and Handling Cardinal Direction Information

S. Skiadopoulos, C. Giannoukos, P. Vassiliadis, T. Sellis, and M. Koubarakis
In Proceedings of the 9th Int'l Conference on Extending Database Technology (EDBT'04), volume 2992 of LNCS, pages 329--347. Springer, 2004

Abstract:
Qualitative spatial reasoning forms an important part of the commonsense reasoning required for building intelligent Geographical Information Systems (GIS). Previous research has come up with models to capture cardinal direction relations for typical GIS data. In this paper, we target the problem of efficiently computing the cardinal direction relations between regions that are composed of sets of polygons and present the first two algorithms for this task. The first of the proposed algorithms is purely qualitative and computes, in linear time, the cardinal direction relations between the input regions. The second has a quantitative aspect and computes, also in linear time, the cardinal direction relations with percentages between the input regions. The algorithms have been implemented and embedded in an actual system, CarDirect, that allows the user to annotate regions of interest in an image or a map, compute cardinal direction relations and retrieve combinations of interesting regions on the basis of a query.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Year: 
Research area: 

Computing and Managing Cardinal Direction Relations

S. Skiadopoulos, C. Giannoukos, N. Sarkas, P. Vassiliadis, T. Sellis, and M. Koubarakis
in IEEE Transaction on Knowledge and Date Engineering, 17(12):1610--1623, 2005

Abstract:
Qualitative spatial reasoning forms an important part of the commonsense reasoning required for building intelligent Geographical Information Systems (GIS). Previous research has come up with models to capture cardinal direction relations for typical GIS data. In this paper, we target the problem of efficiently computing the cardinal direction relations between regions that are composed of sets of polygons and present two algorithms for this task. The first of the proposed algorithms is purely qualitative and computes, in linear time, the cardinal direction relations between the input regions. The second has a quantitative aspect and computes, also in linear time, the cardinal direction relations with percentages between the input regions. Our experimental evaluation indicates that the proposed algorithms outperform existing methodologies. The algorithms have been implemented and embedded in an actual system, CARDIRECT, that allows the user to 1) specify and annotate regions of interest in an image or a map, 2) compute cardinal direction relations between them, and 3) pose queries in order to retrieve combinations of interesting regions.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Year: 
Research area: 

Consistency Checking for Qualitative Spatial Reasoning with Cardinal Directions

S. Skiadopoulos and M. Koubarakis
In Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming (CP'02), volume 2470 of LNCS, pages 341--355. Springer, September 2002.

Abstract:
We present a formal model for qualitative spatial reasoning with cardinal directions and study the problem of checking the consistency of a set of cardinal direction constraints. We present the first algorithm for this problem, prove its correctness and analyze its computational complexity. Utilizing the above algorithm we prove that the consistency checking of a set of basic cardinal direction constraints can be performed in O(n^5) time while the consistency checking of an unrestricted set of cardinal direction constraints is NP-complete. Finally, we briefly discuss some extensions to the basic model.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Year: 
Research area: 

Function Oriented History Representation in Databases

L. Kovacs and C. Vassilakis
Computers and Artificial Intelligence, vol. 19, 2000, pp. 417-444.

Abstract:
In the past years the management of temporal data has attracted numerous researchers resulting to a large number of temporal data extensions to the relational and object oriented data models. In this paper, the proposed temporal data model focuses on the functional characteristics of the histories. The paper introduces a set oriented description of the calendars together with a function oriented history concept with a history-algebra. The completeness of the proposed model with respect to the reduced temporal algebra TA is also proven. The expressive power of the proposed model is demonstrated at the end of the paper by a hospital example.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Year: 
Research area: 

Implementation of Transaction and Concurrency Control Support in a Temporal DBMS

C. Vassilakis, N. Lorentzos and P. Georgiadis
Information Systems, vol. 23, No 5, pp. 335-350, 1998.

Abstract:
Transactions and concurrency control are significant features in database systems, facilitating functions both at user and system level. However, the support of these features in a temporal DBMS has not yet received adequate research attention. In this paper, we describe the techniques developed in order to support transaction and concurrency control in a temporal DBMS which was implemented as an additional layer to a commercial DBMS. The proposed techniques make direct use of the transaction mechanisms of the DBMS. In addition, they overcome a number of limitations such as automatic commit points, lock release and log size increment, which are imposed by the underlying DBMS. Our measurements have shown that the overhead introduced by these techniques is negligible, less than 1% in all cases. The approach undertaken is of general interest, it can also be applied to non-temporal DBMS extensions.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Year: 
Research area: 

Implementing Embedded Valid Time Query Languages

C. Vassilakis, P. Georgiadis, T. Selis
Proceedings of the DEXA '98 Conference, pp. 561-572.

Abstract:
Application development on top of database systems is heavily based on the existence of embedded and 4GL languages. However, the issue of designing and implementing embedded or 4GL temporal languages has not been addressed insofar. In this paper, we present a design approach for implementing an embedded temporal language that supports valid time. Furthermore, we introduce implementation techniques that can be used for implementing any embedded temporal language that supports valid time on top of a DBMS.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Year: 
Research area: 

On the Consistency of Cardinal Directions Constraints

S. Skiadopoulos and M. Koubarakis
In Artificial Intelligence, 163(1):91--135, 2005

Abstract:
We present a formal model for qualitative spatial reasoning with cardinal directions utilizing a co-ordinate system. Then, we study the problem of checking the consistency of a set of cardinal direction constraints. We introduce the first algorithm for this problem, prove its correctness and analyze its computational complexity. Using the above algorithm, we prove that the consistency checking of a set of basic (i.e., non-disjunctive) cardinal direction constraints can be performed in O(n^5) time. We also show that the consistency checking of a set of unrestricted (i.e., disjunctive and non-disjunctive) cardinal direction constraints is NP-complete. Finally, we briefly discuss an extension to the basic model and outline an algorithm for the consistency checking problem of this extension.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Year: 
Research area: 

Querying Indefinite Spatial and Temporal Information: The New Frontier

M. Koubarakis and S. Skiadopoulos
In Proceedings of the IJCAI Workshop on Hot Topics in Spatial and Temporal Reasoning, August 1999.

Abstract:
Temporal and spatial constraint networks do not live alone in the wilderness. In many cases they are components of larger systems e.g., temporal database systems, spatial database systems, knowledge representation systems, natural language systems, planning systems, scheduling systems, multimedia systems and so on. We believe that an interesting new frontier for temporal and spatial reasoning research is the formalisation, analysis and possible re-implementation of systems where temporal or spatial reasoners are an important component. In this paper we will make a first contribution to this exciting area of research. We will consider temporal constraint networks complemented by a database for storing the information typically used to label network nodes. We will then study the computational complexity of querying the combined system using a first order modal query language.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Year: 
Research area: 

Querying Temporal Constraint Networks in PTIME

M. Koubarakis and S. Skiadopoulos
In Proceedings of AAAI'99, pages 745--750, July 1999.

Abstract:
We start with the assumption that temporal knowledge usually captured by constraint networks can be represented and queried more effectively by using the scheme of indefinite constraint databases proposed by Koubarakis. Although query evaluation in this scheme is in general a hard computational problem, we demonstrate that there are several interesting cases where query evaluation can be done in PTIME. These tractability results are original and subsume previous results by van Beek, Brusoni, Console and Terenziani.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Year: 
Research area: 

Querying Temporal and Spatial Constraint Networks in PTIME

M. Koubarakis and S. Skiadopoulos
Artificial Intelligence, 123(1-2):223--263, 2000.

Abstract:
We start with the assumption that temporal and spatial knowledge usually captured by constraint networks can be represented and queried more effectively by using the scheme of indefinite constraint databases. Because query evaluation in this scheme is in general a hard computational problem, we seek tractable instances of query evaluation. We assume that we have a class of constraints C with some reasonable computational and closure properties (the computational properties of interest are that the satisfiability problem and an appropriate version of the variable elimination problem for C should be solvable in PTIME). Under this assumption, we exhibit general classes of indefinite constraint databases and first-order modal queries for which query evaluation can be done with PTIME data complexity. We then search for tractable instances of C among the subclasses of Horn disjunctive linear constraints over the rationals. From previous research we know that the satisfiability problem for Horn disjunctive linear constraints is solvable in PTIME, but not the variable elimination problem. Thus we try to discover subclasses of Horn disjunctive linear constraints with tractable variable elimination problems. The class of UTVPI^{\ne} constraints is the largest class that we show to have this property. Finally, we restate our general tractability results with C ranging over the newly discovered tractable classes. Interesting tractable query answering problems for indefinite temporal and spatial constraint databases are identified in this way. We close our complexity analysis by precisely outlining the frontier between tractable and possibly intractable query answering problems

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Year: 
Research area: 

Spatiotemporal Models and Languages: An Approach Based on Constraints

S. Grumbach, M. Koubarakis, M. Scholl, and S. Skiadopoulos
In M. Koubarakis, T. Sellis, A. Frank, S. Grumbach, R.-H. Gueting, C. Jensen, N. Lorentzos, Y. Manolopoulos, E. Nardelli, B. Pernici, B. Theodoulidis, N. Tryfona, H.-J. Schek and M. Scholl (eds.) Spatiotemporal Databases: The CHOROCHRONOS Approach, volume 2520 of LNCS. Springer, 2003.

Abstract:

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Year: 
Research area: 

TOOBIS: Application of the Management of Temporal Data in Clinical Research

M. Souillard, C. Vassilakis, A. Sotiropoulou
INFORSID '98 Actes des Conferences, pp. 145-168 (in French).

Abstract:
Temporal data, i.e. data varying over time dimension whose history of evolutions is maintained, are not used in the industrial world. But, far from managing only non-temporal data, numerous and various applications and industrial sectors such as banking, insurance, disease management in medicine, booking and so on, face the management of temporal data. These applications often use results of own developments, simulating temporal data in a more or less effective ways. This paper presents the results of the European project TOOBIS - Temporal Object Oriented dataBase within Information System - underlying an application using and managing temporal data, in the domain of Clinical Research. TOOBIS offers an extension of the object-oriented database standard in order to provide a full temporal object-oriented database management system, as well as a temporal methodology of analysis and design.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Year: 
Research area: 

Temporal Extension to ODMG

A. Sotiropoulou, M. Souillard, C. Vassilakis
in Proceedings of the 3rd Biennial World Conference on Integrated Design and Process Technology, Vol. 2, Issues and Applications of Database Technology (IADT), Berlin, Germany, 1998, pp. 304-311.

Abstract:
In the past years a number of temporal extensions to the different database models have been proposed. Extensions to the relational model have been following the different SQL standards, while no attempts have been made to extend the OO-databases' standard, defined by ODMG. In this paper we present a temporal extension to the ODMG standard, as this has been specified in the TOOBIS project. A Temporal Object Data Model, a Temporal Object Definition Language and a Temporal Object Query Language have been specified and have been proposed as extensions to the ODM, ODL and OQL of ODMG. This extension has been implemented over a commercial OODBMS, reinforcing and validating the effort of standardisation and portability of this extension.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
AttachmentSize
PDF icon temporal-extension-odmg.pdf247.68 KB
Year: 
Research area: 

Tractable Query Answering in Indefinite Constraint Databases: Basic Results&Applications to Querying SpatioTemporal Information

M. Koubarakis and S. Skiadopoulos
T. In Proceedings of Int'l Workshop on Spatio-Temporal Database Management (STDBM'99), volume 1678 of LNCS, pages 204--223. Springer, September 1999

Abstract:
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^{\ne} 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.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Year: 
Research area: 

Transaction Support in a Temporal DBMS

C. Vassilakis, N. Lorentzos and P. Georgiadis
in Proceedings of International Workshop on Temporal Databases, Zürich, September 1995

Abstract:
Transactions are a significant concept in database systems, facilitating functions both at user and system level. However transaction support in temporal DBMSs has not yet received enough research attention. In this paper, we present techniques for incorporating transaction support in a temporal DBMS, which is implemented as an additional layer to a commercial RDBMS. These techniques overcome certain limitations imposed by the underlying RDBMS, and avoid excessive increment of the log size.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
AttachmentSize
PDF icon transaction-support-in-tdbms.pdf203.19 KB
Year: 
Research area: