Temporal and Spatial Databases (TSDB)

Academic Year:	2008/09, 2nd semester
Lecturer:	Johann Gamper
Lectures:	WE 08:30-10:30, Room E411
Labs:	WE 15:00-16:00, Room D003
Office hours:	WE 11:00-12:00 or email arrangement

Home | Lectures | Project | Exam

Objectives: This course will introduce principles and foundations of temporal and spatial databases, including data models, query languages, algebras, and algorithms for selected operators.

Prerequisites: Students should be familiar with basic concepts in databases (including relational databases, SQL, and relational algebra) and algorithms, as well as having good pogramming skills. This material is taught in the following courses: Introduction to Databases, Introduction to Programming, and Data Structures and Algorithms.

Syllabus:

Introduction and motivation
Time ontology, structure, and granularity
Temporal data models
Temporal relational algebras
Temporal query lanaguages
Algorithms for temporal join and aggregation
Spatial databases and data models

References: There is no single textbook that covers the entire course. The course material is collected from the following books and papers:

Zaniolo et al.: Advanced Database Systems, (chapter 5, 6, and 7), Morgan Kaufmann Publishers, Inc., 1997
R.T. Snodgrass (ed.): The TSQL2 temporal query language, Kluwer Academic Publishers, 1995.
R.H. Güting and M. Schneider: Moving objects databases (chapter 1 and 2),Morgan Kaufmann Publishers, Inc., 2005
M. Böhlen, J. Gamper, and C.S. Jensen. Multi-dimensional aggregation for temporal data. In Proc. of EDBT-2006, pp. 257-275, 2006.
D. Gao, C.S. Jensen, R.T. Snodgrass, and M.D. Soo: Join operations in temporal databases. VLDB Journal, vol. 14, pp. 2-29, 2005.
C.S. Jensen, M.D. Soo, and R.T. Snodgrass: Unifying temporal data models via a conceptual model. Information Systems, vol. 19, no. 7, pp. 513-547, 1994.

Lectures

1.	WE 04.03.09	Introduction: syllabus, administration and organisation, the DB field, short overview of RDMS, motivation for temporal DBMS, a case study	pdf
2.	WE 11.03.09	Time domain and calendars: time domain and structure, granularities, calendars, modeling instants/periods/intervals, now	pdf
3.	WE 18.03.09	Temporal data models I: dimensions of time, timestamp types, point-based data models, interval-based data models, data models with temporal elements, attribute value timestamping, the bitemporal conceptual data model (BCDM)	pdf
4.	WE 08.04.09	Temporal data models II: interaction of BCDM and representational models, Snodgrass' tuple timestamping model, Jensen's backlog model, Ben-Zvi's tuple timestamped model, Gadia's attribute value timestamped model, McKenzie's attribute value timestamped model	pdf
5.	WE 15.04.09	Relational algebra for bitemporal relations: algebra for BCDM, algebra for Sondgrass' tuple timestamped data model, reducibility of operators, semantic equivalence	pdf
6.	WE 29.04.09	Temporal query languages: Language design criteria, comparison of timestamps, comparative analysis of temporal query languages (SQL + ADT, IXSQL, SQL/TP, TSQL2, ATSQL)	pdf
7.	WE 06.05.09	Evaluation of temporal joins: Query processing, definition of temporal Cartesian product and temporal joins, evaluation algorithms for temporal joins (nested-loop, sort-merge, partition-based, index-based)	pdf
8.	WE 13.05.09	Evaluation of temporal aggregation: snapshot vs. temporal aggregation, aggregation tree algorithm, balanced tree algorithm, merge-sort algorithm, bucket algorithm	pdf
9.	WE 20.05.09	Evaluation of temporal aggregation: a general temporal aggregation framework, parsimonious temporal aggregation	pdf
10.	WE 27.05.09	Spatial databases: introduction, modeling spatial concepts, organizing the underlying space, spatial data types and algebras, spatial relationships	pdf
12.	WE 03.06.09	Spatial databases: integrating geometry into DBMS data model, querying spatial databases, spatial indexes
12.	WE 10.06.09	Spatial network databases: k-NN search, isochrones	pdf

Project

The exercise part of the course consists in the elaboration of a mini-project, which can be done alone or in groups of 2 students. The project consists in the implemenation and evaluation of one of the following temporal aggregation algorithms:

M. H. Böhlen, J. Gamper, and C. S. Jensen. Multi-dimensional Aggregation for Temporal Data. In Proc. EDBT, pp. 257-275, 2006. (pdf)
N. Kline and R. T. Snodgrass. Computing Temporal Aggregates. In Proc. ICDE, pp. 222-231, 1995. (pdf)
B. Moon, I. F. Vega Lopez, and V. Immanuel. Efficient Algorithms for Large-Scale Temporal Aggregation. IEEE TKDE, 15(3): 744-759, 2003. (pdf)
J. Yang and J. Widom. Incremental Computation and Maintenance of Temporal Aggregates. The VLDB Journal, 12(3): 262-283, 2003. (pdf)

The project concludes with a final report of 5-10 pages which clearly states the problem and describes the solution, implementation and evaluation.

For the implementation we recommend Java or C as programming language and Oracle, Postgres, or MySQL as database system, but you are free to choose any other programming language and relational database system. For the evaluation, the following data sets of different size (200K, 400K, 600K, 800K, 1000K of tuples) are available here ("nn" indicates the size of the data set, e.g., 02 = 200000 tuples):

data-seq-nn: Sequential tuples, i.e., the timestamps of the tuples are disjoint.
data-equal-nn: All tuples have the same timestamp.
data-random-nn: Start time and duration of the tuples are uniformly distributed.
data-worst-nn: All start and end points are different, and there is a time interval (in the middle) where all tuples hold.

All data sets have the schema (Name, Salary, TS, TE): Name is intended as the name of an employee and is represented as a number between 0 and 9; Salary is an integer and represents the salary of an employee; TS and TE are integers and represent the start time and end time of the tuple, respectively.

Schedule and Organization

WE, 04.03.09: Presentation of the project
WE, 11.03.09: Read the paper, create a small sample data set (from any application domain), create a database with the sample data and test data
...
FR 12.06.09: Final version of project report is handed in

Exam

The exam is oral and consists of two parts:
1. the defense of the project and the evaluation of the project report (40% of the total grade);
2. questions from the TSDB course (60% of the total grade).
Both parts are required to pass the exam.
Each student will be examined individually for approx. 20 minutes.
This is an open book exam, i.e. the student is allowed to use the lecture notes and additional readings in the exam.