Chapter 5: Spatio-temporal Models and Languages: An Approach Based on Constraints
Lecture notes in computer sciencePublished 1 January 2003
Stéphane Grumbach, Manolis Koubarakis, Philippe Rigaux, Micheł Scholl, Spiros Skiadopoulos
Citations4
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The constraint data model is adopted, first introduced by Kanellakis, Kuper, and Revesz, and shown that it is a very successful paradigm for the representation of spatio-temporal data in a unified framework, and enables the straightforward modeling of indefinite information.
Abstract
The introduction of spatio-temporal information in database systems presents us with an important data modelling challenge: the design of data models general and powerful enough to handle conventional thematic data, purely temporal or spatial concepts and spatio-temporal concepts.
Keywords
Computer ScienceSocial Sciences
Journal of the Operational Research SocietyTheory of Linear and Integer Programming
5,693 Citations2000Adam N. Letchford, Alexander Schrijver
An Introduction to Modal Logic
1,842 Citations1968M. J. Cresswell, G. E. Hughes
Artificial IntelligenceTemporal constraint networks
1,800 Citations1991Rina Dechter, Itay Meiri +1 more
It is shown that the STP, which subsumes the major part of Vilain and Kautz's point algebra, can be solved in polynomial time and the applicability of path consistency algorithms as preprocessing of temporal problems is studied, to demonstrate their termination and bound their complexities.
Journal of the ACMIncomplete Information in Relational Databases
1,018 Citations1984Tomasz Imieliński, Witold Lipski
There are precise conditions that should be satisfied in a semantically meaningful extension of the usual relational operators, such as projection, selection, union, and join, from operators on relations to operators on tables with “null values” of various kinds allowed.
Journal of Computer and System SciencesConstraint Query Languages
679 Citations1995Paris C. Kanellakis, Gabriel M. Kuper +1 more
It is shown that efficient, declarative database programming can be combined with efficient constraint solving and the key intuition is that the generalization of a ground fact is a conjunction of constraints over a small number of variables.
The TSQL2 Temporal Query Language
633 Citations1995Richard T. Snodgrass
To break the boredom in reading, one that the authors will refer to is choosing tsql2 temporal query language as the reading material.
Modeling and querying moving objects
610 Citations2002A. Prasad Sistla, Ouri Wolfson +2 more
This work proposes a data model for representing moving objects in database systems called the Moving Objects Spatio-Temporal (MOST) data model, and devise an algorithm for processing FTL queries in MOST.
IEEE Transactions on Software EngineeringPROBE spatial data modeling and query processing in an image database application
273 Citations1988Jack Orenstein, Frank Manola
An overview of PROBE is provided, focusing on the facilities for dealing with spatial and temporal data, and how thePROBE database system and simple application-specific object classes combine to efficiently support PROBe's spatial data model.
IEEE Transactions on Software EngineeringAn efficient pictorial database system for PSQL
226 Citations1988N. Roussopoulos, Christos Faloutsos +1 more
A description is given of PSQL, a query language that allows pictorial domains to be presented to the user in their analog form and allows him or her to do direct manipulation on the objects found on those domains.
Constraint Databases
210 Citations2010Gabriel M. Kuper, Leonid Libkin +1 more
The VLDB JournalRealm-based spatial data types: The ROSE algebra
209 Citations1995Ralf Hartmut Güting, Markus Schneider
The ROSE algebra is described within a polymorphic type system and interacts with a DMBS data model and query language through an abstractobject model interface and an example integration of ROSE into the object-oriented data model O2 and its query language is presented.
Constraint query languages (preliminary report)
197 Citations1990Paris C. Kanellakis, Gabriel M. Kuper +1 more
It is shown that bottom-up, efficient, declarative database programming can be combined with efficient constraint solving, and the key intuition is that the generalization of a ground fact, or tuple, is a conjunction of constraints.
Lecture notes in computer scienceThe Problem of Incomplete Information in Relational Databases
186 Citations1991
Handling infinite temporal data
145 Citations1990F. Kabanza, J.-M. Stevenne +1 more
It is proved that relations formed from generalized tuples are closed under the operations of relational algebra, and a characterization of the expressiveness of generalized relations is given in terms of predicates definable in Presburger arithmetic.
Theoretical Computer ScienceA closed-form evaluation for Datalog queries with integer (gap)-order constraints
121 Citations1993Péter Révész
A generalization of Datalog based on generalizing databases with the addition of integer-order constraints to relational tuples and it is shown that there is a closed-form evaluation.
The DEDALE system for complex spatial queries
121 Citations1998Stéphane Grumbach, Philippe Rigaux +1 more
DEDALE is presented, a spatial database system intended to overcome some limitations of current systems by providing an abstract and non-specialized data model and query language for the representation and manipulation of spatial objects that generalizes the constraint database model of [KKR90].
Gral: an extensible relational database system for geometric applications
119 Citations1989Ralf Hartmut Güting
The central concept is to use languages based on many-sorted algebra to represent queries as well as query execution plans that leads to a simple and clean extensible system architecture that eases the task of an application developer by providing a uniform framework, and also simplifies rule-based optimization.
Temporal Deductive Databases.
111 Citations1993Marianne Baudinet, Jan Chomicki +1 more
A number of approaches to the problem of nite representation of innnite temporal extensions of Datalog 1S and Templog are surveyed, providing precise characterizations of the expressiveness and the computational complexity of these languages.
Towards a theory of spatial database queries (extended abstract)
106 Citations1994Jan Paredaens, Jan Van den Bussche +1 more
GeoInformaticaConstraint-based Interoperability of Spatiotemporal Databases*
96 Citations1999Jan Chomicki, Péter Révész
This work proposes constraint databases as an intermediate level facilitating the interoperability of spatiotemporal data models and illustrates the approach in the context of a number of temporal, spatial, and spatiotechnological data models.
Lecture notes in computer scienceThematic map modeling
92 Citations1990Micheł Scholl, Agnès Voisard
The model presented here is a first step toward a high level spatial query language adapted to the manipulation of thematic maps and provides the designer of geographic databases with a database query language extensible and customizable.
Information SystemsDatabase models for infinite and indefinite temporal information
76 Citations1994Manolis Koubarakis
A hierarchy of temporal data models: temporal relations, generalized temporal relations and temporal tables is presented and the semantics of these models are studied and algebraic and calculus query languages for them are developed.
Lecture notes in computer scienceDesign and Implementation of Large Spatial Databases
66 Citations1990Alejandro Buchmann, Oliver Günther
A geometric framework for specifying spatiotemporal objects
65 Citations2003Jan Chomicki, Péter Révész
A framework for specifying spatiotemporal objects using spatial and temporal objects, and a geometric transformation, is presented, which defines a number of classes of spatiotmporal objects and study their closure properties.
Lecture notes in computer scienceLinear constraint query languages expressive power and complexity
58 Citations1995Stéphane Grumbach, Jianwen Su +1 more
An AC0 upper bound on the complexity of first-oder queries over (infinite) databases defined by restricted linear constraints is given and the non-expressibility of various usual queries is deduced.
Theoretical Computer ScienceThe complexity of query evaluation in indefinite temporal constraint databases
52 Citations1997Manolis Koubarakis
The complexity of query evaluation in an important instance of this abstract scheme: indefinite temporal constraint databases is studied and precise bounds on the complexity of decision/quantifier elimination for a subtheory of Presburger arithmetic and a sub theory of real addition with order are provided.
Representation and querying in temporal databases: the power of temporal constraints
45 Citations2002Manolis Koubarakis
A temporal database model capable of representing absolute, relative, imprecise, and infinite temporal data is proposed, and an algebraic query language for temporal tables is defined, and some problems related to query answering are discussed.
Lecture notes in computer scienceParametric Rectangles: A Model for Querying and Animation of Spatiotemporal Databases
44 Citations2000Mengchu Cai, Dinesh Keshwani +1 more
It is proved that the model is closed under relational algebra and new spatiotemporal operators and that relational algebra queries can be evaluated in PTIME in the size of any input quadratic non-periodic parametric rectangle database.
Lecture notes in computer sciencededale, a spatial constraint database
42 Citations1998Stéphane Grumbach, Philippe Rigaux +2 more
This paper presents a first prototype of a constraint database for spatial information, dedale, implemented on top of the O2 DBMS, with special functions for constraint solving and geometric operations.
The Journal of Logic ProgrammingDatalog with integer periodicity constraints
42 Citations1998David Toman, Jan Chomicki
A closed-form bottom-up evaluation procedure for the class of periodic constraints combined with gap-order constraints in the framework of Datalog is developed and complexity bounds are provided for the query evaluation procedures.
The Montage extensible DataBlade architecture
41 Citations1994Michael Ubell
The Montage database system supports general extensibility of integrated data types, and in this architecture the database management system can be thought of as a “razor” into which technology specific “DataBlades” are inserted.
IEEE Transactions on Knowledge and Data EngineeringAn extended algebra for constraint databases
40 Citations1998Alberto Belussi, Elisa Bertino +1 more
This work shows that the relational model is not the only possible semantic reference model for constraint relational databases and it shows how constraint relations can be interpreted under the nested relational model, and introduces two distinct classes of constraint algebras.
ACM SIGMOD RecordThe MLPQ/GIS constraint database system
39 Citations2000Péter Révész, Rui Chen +4 more
MLPQ/GIS is a constraint database system like CCUBE and DEDALE but with a special emphases on spatio-temporal data and features include data entry tools and icon-based queries, which optimize linear objective functions.
ConstraintsThe CCUBE Constraint Object-Oriented Database System
35 Citations1997Alexander Brodsky, Victor E. Segal +2 more
The CCUBE constraint calculus guarantees polynomial time data complexity, and is tightly integrated with the monoid comprehensions to allow deeply interleaved global optimization.
Lecture notes in computer scienceData models and languages for databases
34 Citations1983Catriel Beeri
Extensions of the relational model that allow users to specify and manipulate structurally complex objects and their languages are discussed, including a formal model for objects with identity, and declarative languages for the model.
Lecture notes in computer scienceManipulating spatial data in constraint databases
32 Citations1997Alberto Belussi, Elisa Bertino +1 more
This paper extends the model and the algebra to directly deal with the set of points represented by a generalized tuple (a spatial object), retaining at the same time the ability of expressing all computations that can be expressed by other constraint database languages.
A constrant-based spatial extension to SQL
30 Citations1998Gabriel M. Kuper, Sridhar Ramaswamy +2 more
This paper describes the proposal for a query language for GISS based on CSQL, as it is based on SQL, which provides the full query capabilities of SQL on the non-spatial part of the database while being tightly integrated with the spatial part.
The MLPQ/GIS constraint database system
29 Citations2000Péter Révész, Rui Chen +4 more
Lecture notes in computer scienceOn the Orthographic Dimension of Constraint Databases
27 Citations1999Stéphane Grumbach, Philippe Rigaux +1 more
It is proved that orthographic dimension preserving Boolean combination of conjunctive queries can be evaluated independently of the global dimension, with operators limited to the Orthographic dimension, in parallel on the components.
Lecture notes in computer scienceFoundations of indefinite constraint databases
22 Citations1994Manolis Koubarakis
This work develops the scheme of indefinite L-constraint databases where L, the parameter, is a first-order constraint language and proposes declarative and procedural query languages for the new scheme and study the semantics of query evaluation.
Handling temporal grouping and pattern-matching queries in a temporal object model
17 Citations1998Marlon Dumas, Marie-Christine Fauvet +1 more
This paper presents a language for expressing temporal pattern-matching queries, and a set of temporal grouping operators for structuring histories following calendar-based criteria, embedded into the TEMPOS temporal data model.
ACM SIGMOD RecordThe CCUBE constraint object-oriented database system
16 Citations1999Alexander Brodsky, Victor E. Segal +2 more
Lecture notes in computer scienceAnimating Spatiotemporal Constraint Databases
15 Citations1999Jan Chomicki, Yuguo Liu +1 more
This work presents a novel approach that makes the efficient animation of constraint databases possible, based on a new construct: parametric polygon, and presents an algorithm to construct the set of parametric polygons that represent a given linear constraint database.
Lecture notes in computer scienceTractable Query Answering in Indefinite Constraint Databases: Basic Results and Applications to Querying Spatiotemporal Information
13 Citations1999Manolis Koubarakis, Spiros Skiadopoulos
The main technical problem that is addressed in this paper is the discovery of tractable classes of databases and queries in the scheme of indefinite constraint databases proposed by Koubarakis.
Workshops in computingDatabases and Temporal Constraints: Semantics and Complexity
12 Citations1995Manolis Koubarakis
This work gives a detailed characterization of the computational complexity of query answering for various classes of temporal constraint databases and queries and considers several instances of these schemes where ℒ is a language for expressing information about atomic data values and time.
National Conference on Artificial IntelligenceQuerying temporal constraint networks in PTIME
10 Citations1999Manolis Koubarakis, Spiros Skiadopoulos
The frequency of observing the germinal disc according to the preincubation positioning direction and time found that it depended on those conditions, but only a few chicks hatched using the windowed method, so this method can be effective for in ovo artificial incubation.