COURSE NUMBER AND TITLE

CIS 6930, Moving Objects Databases

OVERVIEW

This is a graduate-level advanced course on the concepts and principles of moving objects databases. Moving objects databases are a relatively new research area that has received a lot of interest in recent years. The general goal of this research is to allow one to represent moving entities in databases and to ask queries about such movements. Moving entities could be cars, trucks, aircrafts, ships, mobile phone users, terrorists, or polar bears. For these examples, usually only the time-dependent position in space is relevant, not the extent. Hence, we can characterize them as moving points. However, there are also many moving entities with an extent like hurricanes, forest fires, oil spills, armies, epidemic diseases, and so forth. These can be characterized as moving regions.

Moving objects are essentially time-dependent geometries, and database support for them is a specific flavor of spatio-temporal databases. The term moving objects emphasizes the fact that geometries can now change continuously, in contrast to most of the earlier work on spatio-temporal databases that supported only discrete change. Note that discrete changes are a special case of continuous developments, and moving objects support both.

Some of the interest in this field is spurred by current trends in consumer electronics. Wireless, network-enabled and position-aware (i.e., GPS equipped) devices, such as personal digital assistants, on-board units in vehicles, or mobile phones, have become relatively cheap and are predicted to be in very widespread use in the near future. This will lead to many kinds of new applications, such as location-based services. Similarly, big retail companies are moving toward tracking their products by indoor location devices (e.g., using RFID tags). Both trends mean that a huge volume of movement information (sometimes called trajectories) will become available and will need to be managed and analyzed in database systems.

The focus of this course is on the underlying database technology to support such applications. Extending database technology to deal with moving objects means first, as for many other nonstandard database applications, to provide facilities in a data model of a database management system (DBMS) for describing such entities and to extend the query language by constructs for analyzing them (e.g., for formulating predicates about them). Second, it means that the implementation of a DBMS must be extended. The two major strategies for this are (i) to build a layer on top of an existing DBMS and so to map moving object representations and predicates to existing facilities of the DBMS or (ii) to actually extend the DBMS by providing data structures for moving objects, methods for evaluating operations, specialized indexes and join algorithms, and so forth.

There are two major ways of looking at moving objects in databases. Either we are interested in maintaining continuously information about the current position and predict near future positions, or we consider whole histories of movements to be stored in the database and to ask queries for any time in the past. This course treats both perspectives in depth.

PREREQUISITES

Basic knowledge of database systems (e.g., COP 5725) and algorithms, data structures, and discrete mathematics; familiarity with programming using a high-level language.

TEXTBOOK

MOVING OBJECTS DATABASES by Ralf Hartmut Güting and Markus Schneider, Morgan Kaufmann Publishers, 389 pages, 2005, ISBN: 0-12-088799-1.

OUTLINE OF COURSE TOPICS

The outline is subject to change! Chapter numbers refer to the textbook above. The term "LNO" means "Lecture Notes Only".
  1. Introduction (Ch. 1, LNO)
  2. Spatio-Temporal Databases in the Past (Ch. 2)
  3. Modeling and Querying Current Movement (Ch. 3)
  4. Modeling and Querying History of Movement (Ch. 4)
  5. Data Structures and Algorithms for Moving Objects Types (Ch. 5)
  6. The Constraint Database Approach (Ch. 6)
  7. Spatio-Temporal Indexing (Ch. 7)

EXAMINATIONS AND GRADES

Your course grade will be based on two equally-weighted exams as well as homeworks assignments. Please note that changes are possible.

WORKLOAD

This course is held for the first time. Hence, no statement can be made about the workload.