Spatio-Temporal Databases

by Koubarakis, Manolis; Sellis, Timos; Frank, Andrew U.; Grumbach, Stephane; Guting, Ralf Hartmut

• ISBN13: 9783540405528
• ISBN10: 3540405526
• Format: Paperback
• Copyright: 2003-09-01
• Publisher: Springer-Verlag New York Inc

Summary

This book summarizes in a timely and representative manner research carried out in the CHOROCHRONOS Project, established as an EC funded Training and Mobility Research Network with the objective of studying the design, implementation, and application of spatio-temporal database management systems.The nine coherent chapters by leading research groups are written in a tutorial style, making the research contributions of the project accessible to a wider audience interested in spatio-temporal information processing. Follwing an introductory overview, the book presents chapters on ontologies for spatio-temporal databases, conceptual models, spatio-temporal models and languages, access methods and query processing, architectures and implementation of spatiotemporal DBMS, interactive spatio-temporal documents, and future perspectives.

Table of Contents

1 Introduction	1	(8)
Manolis Koubarakis, Timos Sellis
1.1 Why Databases?	1	(1)
1.2 CHOROCHRONOS	2	(1)
1.3 Contributions	3	(1)
1.4 Organization of the Book	4	(1)
References	5	(4)
2 Ontology for Spatlo-temporal Databases	9	(69)
Andrew U. Frank
2.1 Introduction	11	(2)
2.1.1 Ontology to Drive Information System Design	11	(1)
2.1.2 Ontological Problems of Geographic Information Systems and Other Spatio-temporal Information Systems	12	(1)
2.1.3 Structure of the Chapter	13	(1)
2.2 The Notion of Ontology	13	(2)
2.2.1 Classical View	13	(1)
2.2.2 Social Reality	14	(1)
2.3 Application Domains	15	(3)
2.3.1 Table-Top Situation	16	(1)
2.3.2 Cityscape	17	(1)
2.3.3 Geographic Landscape	18	(1)
2.4 Model of Information Systems	18	(6)
2.4.1 Information Systems as Vehicles of Exchange between Multiple Agents	20	(2)
2.4.2 Correctness of Information System Related to Observations 2l
2.4.3 Semantics for Terms in Information Systems	22	(1)
2.4.4 Grounding of Semantics in Physical Operations	23	(1)
2.5 The Five Tiers of the Ontology	24	(6)
2.5.1 Physical Reality Seen as an Ontology of a Four-Dimensional Field	24	(1)
2.5.2 Observation of Physical Reality	25	(1)
2.5.3 Operations and Ontology of Individuals	26	(3)
2.5.4 Social Ontology	29	(1)
2.5.5 Ontology of Cognitive Agents	30	(1)
2.6 The Language to Describe the Ontology	30	(6)
2.6.1 Tools to Implement Ontologies	32	(3)
2.6.2 Multi-agent Systems and Formalization of Database Ontologies	35	(1)
2.7 Ontological Tier 0: Ontology of the Physical Reality	36	(2)
2.7.1 Properties	37	(1)
2.7.2 Physical Space-Time Field	38	(1)
2.8 Ontological Tier 1: Our Limited Knowledge of the World through Observations of Reality	38	(2)
2.8.1 Observations	38	(2)
2.8.2 Measurement Units	40	(1)
2.8.3 Classification of Values	41	(1)
2.8.4 Special Observations: Points in Space and Time	42	(2)
2.8.5 Approximate Location	44	(2)
2.8.6 Discretization and Sampling	46	(1)
2.8.7 Virtual Datasets: Validity of Values	47
2.9 Ontological Tier 2: Representation - World of Individual Objects	40	(17)
2.9.1 Objects Are Defined by Uniform Properties	49	(1)
2.9.2 Geometry of Objects	49	(3)
2.9.3 Properties of Objects	52	(1)
2.9.4 Geographic Objects Are not Solid Bodies	52	(1)
2.9.5 Objects Endure in Time	52	(4)
2.9.6 Temporal, but A-Spatial Objects	56	(1)
2.10 Ontological Tier 3: Socially Constructed Reality	57	(4)
2.10.1 Social Reality Is Real within a Context	57	(1)
2.10.2 Names	58	(1)
2.10.3 Institutional Reality	59	(2)
2.11 Ontological Tier 4: Modeling Cognitive Agents 8I
2.11.1 Logical Deduction	61	(1)
2.11.2 Two Time Perspectives	62	(1)
2.11.3 Sources of Knowledge	63	(1)
2.12 Ontological Commitments Necessary for a Spatio-temporal Database	64	(2)
2.12.1 Existence of a Single Reality	64	(1)
2.12.2 Values for Properties Can Be Observed	64	(1)
2.12.3 Assume Space and Time	64	(1)
2.12.4 Observations Are Necessarily Limited	64	(1)
2.12.5 Processes Determine Objects	65	(1)
2.12.6 Names of Objects	65	(1)
2.12.7 Social, Especially Institutionally Constructed Reality	65	(1)
2.12.8 Knowledge of an Agent Is Changing in Time	65	(1)
2.13 Conclusions	66	(1)
References	67	(11)
3 Conceptual Models for Spatio-temporal Applications	78	(39)
Nectaria Tryfona, Rosanne Price, Christian S. Jensen
3.1 Motivation	79	(1)
3.2 Foundations	80	(2)
3.3 Spatio-temporal Entity-Relationship Model	82	(13)
3.3.1 Extending the ER with Constructs	82	(9)
3.3.2 A Textual Notation for STER	91	(2)
3.3.3 Example of Usage of STER	93	(2)
6.4 Spatio-temporal Unified Modeling Language	95	(16)
3.4.1 Using UML Core Constructs for Spatio-temporal Data	95	(4)
3.4.2 Overview of Extended Spatio-temporal UML	99	(1)
3.4.3 Basic Constructs: Spatial, Temporal, Thematic	99	(10)
3.4.4 Additional Constructs: Specification Box, Existence Time, and Groups	109	(1)
3.4.5 Example of Usage	110	(1)
3.5 Related work	111	(3)
3.6 Conclusions	114	(1)
References	114	(3)
4 Spatio-temporal Models and Languages: An Approach Based on Data Types	117	(60)
Ralf Hartmut Güting, Michael H. Böhlen, Martin Erwig, Christian S. Jensen, Ninos Lorentzos, Enrico Nardelli, Martius Schneider, Jose R.R. Viqueira
4.1 Introduction	117	(2)
4.2 The Data Type Approach	119	(10)
4.2.1 Motivation	119	(2)
4.2.2 Modeling	121	(2)
4.2.3 Some Example Queries	123	(2)
4.2.4 Some Basic Issues	125	(4)
4.3 An Abstract Model: A Foundation for Representing and Querying Moving Objects	129	(17)
4.3.1 Spatio-temporal Data Types	129	(4)
4.3.2 Language Embedding of Abstract Data Types	133	(1)
4.3.3 Overview of Data Type Operations	134	(1)
4.3.4 Operations on Non-temporal Types	135	(5)
4.3.5 Operations on Temporal Types	140	(5)
4.3.6 Application Example	145	(1)
4.3.7 Summary	146	(1)
4.4 A Discrete Model: Data Structures for Moving Objects Databases	146	(14)
4.4.1 Overview	146	(3)
4.4.2 Definition of Discrete Data Types	149	(11)
4.5 Outlook	160	(14)
4.5.1 Spatio-temporal Predicates and Developments	160	(4)
4.5.2 Spatio-temporal Partitions	164	(3)
4.5.3 On a Spatio-temporal Relational Model Based on Quanta	167	(3)
4.5.4 Spatio-temporal Statement Modifiers	170	(4)
References	174	(3)
5 Spatio-temporal Models and Languages: An Approach Based on Constraints	177	(26)
Stephane Grumbach, Manolis Koubarakis, Philippe Rigaux, Michel Scholl, Spiros Skiadopoulos
5.1 Introduction	177	(2)
5.2 Representing Spatiotemporal Information Using Constraints	179	(4)
5.2.1 An Algebra for Relations with Constraints	181	(2)
5.3 Indefinite Information in Spatiotemporal Databases	183	(7)
5.3.1 Querying Indefinite Information	186	(4)
5.4 Beyond Flat Constraint Relations: The DEDALE Approach	190	(4)
5.4.1 The DEDALE Algebra	192	(2)
5.5 The User Query Language of DEDALE	194	(4)
5.5.1 The Syntax	195	(1)
5.5.2 Example Queries	196	(2)
5.6 Conclusions	198	(1)
References	199	(4)
6 Access Methods and Query Processing Techniques	203	(60)
Adriano Di Pasquale, Luca Forlizzi, Christian S. Jensen, Yannis Manolopoulos, Enrico Nardelli, Dieter Pfoser, Guido Proietti, Simonas Saltenis, Yannis Theodoridis, Theodorus Tzouramanis, Michael Vassilakopoulos
6.1 Introduction	203	(1)
6.2 R-Tree-Based Methods	204	(17)
6.2.1 Preliminary Approaches	204	(3)
6.2.2 The Spatio-bitemporal R-Tree	207	(5)
6.2.3 The Time-Parameterized R-Tree	212	(5)
6.2.4 Trajectory Bundle	217	(4)
6.3 Quadtree-Based Methods	221	(15)
6.3.1 The MOE-Tree	222	(3)
6.3.2 The MOF+-Tree	225	(2)
6.3.3 Overlapping Linear Quadtrees	227	(4)
6.3.4 Multiversion Linear Quadtree	231	(5)
6.4 Data Structures and Algorithms for the Discrete Model	236	(8)
6.4.1 Data Structures	236	(3)
6.4.2 Two Example Algorithms	239	(5)
6.5 Benchmarking and Data Generation	244	(4)
6.5.1 Benchmarking	244	(2)
6.5.2 Data Generation	246	(2)
6.6 Distribution and Optimization Issues	248	(5)
6.6.1 Distributed Indexing Techniques	248	(3)
6.6.2 Query Optimization	251	(2)
6.7 Related Work	253	(2)
6.8 Conclusions	255	(1)
References	255	(8)
7 Architectures and Implementations of Spatio-temporal Database Management Systems	263	(56)
Martin Breunig, Can Türher, Michael H. Böhlen, Stefan Dieker, Ralf Hartmut Güting, Christian S. Jensen, Lukas Relly, Philippe Rigaux, Hans-Jörg Schek, Michel Scholl
7.1 Introduction	263	(1)
7.2 Architectural Aspects	263	(7)
7.2.1 The Layered Architecture	264	(2)
7.2.2 The Monolithic Architecture	266	(1)
7.2.3 The Extensible Architecture	266	(1)
7.2.4 Commercial Approaches to Spatial-temporal Extensions	267	(3)
7.3 The Concert Prototype System	270	(9)
7.3.1 Introduction	270	(1)
7.3.2 Architecture	270	(2)
7.3.3 Spatio-temporal Extensions	272	(3)
7.3.4 Implementation Details	275	(1)
7.3.5 Case Studies	276	(3)
7.4 The Secondo Prototype System	279	(11)
7.4.1 Introduction	279	(1)
7.4.2 Second-Order Signature	280	(3)
7.4.3 Architecture	283	(5)
7.4.4 Implementing Spatio-temporal Algebra Modules	288	(2)
7.5 The Dedale Prototype System	290	(7)
7.5.1 Introduction	290	(1)
7.5.2 Interpolation in the Constraint Model: Representation of Moving Objects	291	(1)
7.5.3 Architecture	292	(1)
7.5.4 Implementation Details	293	(1)
7.5.5 Example of Query Evaluation	294	(3)
7.6 The Tiger Prototype System	297	(6)
7.6.1 Introduction	297	(1)
7.6.2 Architecture	297	(1)
7.6.3 Spatio-temporal Extensions	298	(2)
7.6.4 TIGER'S Implementation	300	(2)
7.6.5 Processing Queries Using External Modules-Case Study	302	(1)
7.7 The GeoToolKit Prototype System	303	(7)
7.7.1 Introduction	303	(1)
7.7.2 Architecture	304	(1)
7.7.3 Spatio-temporal Extensions	305	(3)
7.7.4 Implementation Details	308	(1)
7.7.5 Case Studies	309	(1)
7.8 Conclusions	310	(3)
References	313	(6)
4 Advanced Uses: Composing Interactive Spatio-temporal Documents	319	(26)
Isabelle Mirbel, Barbara Pernici, Babis Theodoulidis, Alex Vakalondis, Michalis Vazirgiannis
8.1 Introduction	319	(1)
8.2 Interactive Presentations and Spatio-temporal Databases	320	(1)
8.3 Modeling the Components of Spatio-temporal Interactive Documents	321	(9)
8.3.1 Particularities of 3D-Spatio-temporal Modeling for Scenario Components	321	(1)
8.3.2 Meta-modeling	322	(3)
8.3.3 Temporal Semantics	325	(2)
8.3.4 3D-Spatial Semantics	327	(1)
8.3.5 3D-Spatio-temporal Semantics	328	(2)
8.4 Modeling of Spatio-temporal Behavior	330	(5)
8.4.1 Modeling Interaction with Events	330	(5)
8.5 Database Support for Scenario Components	335	(3)
8.5.1 Querying and Accessing Stored Components	336	(2)
8.5.2 A Global Architecture	338	(1)
8.6 Examples of Applications	338	(2)
8.7 Related Work	340	(3)
8.8 Conclusions	343	(1)
References	344	(1)
9 Spatio-temporal Databases in the Years Ahead	345	(4)
Manolis Konbarakis, Yannis Theodoridis, Timos Sellis
9.1 Introduction	345	(1)
9.2 Mobile and Wireless Computing	345	(1)
9.3 Data Warehousing and Mining	346	(1)
9.4 The Semantic Web	346	(1)
9.5 Conclusions	346	(1)
References	347	(2)
List of Contributors	349