Datenbanken für bewegte Objekte
Final Report Abstract
Ziel des Projektes war die Verbesserung der Fähigkeiten von Datenbanksystemen zur Verwaltung beweglicher Objekte. Klassische Geo-Datenbanksysteme unterstützen bisher die Verwaltung statischer Geometrien oder bestenfalls schrittweise veränderlicher Geometrien. Seit einigen Jahren gibt es das neue Forschungsgebiet der "moving objects databases", in dem kontinuierlich veränderliche Geometrien, also bewegliche Objekte, betrachtet werden. Beispiele dafür sind Personen, Fahrzeuge, Flugzeuge, Polarbären, Waldbrände oder Ölteppiche. Dieses Gebiet findet großes Interesse in der Forschung. Ein Grund dafür ist die Tatsache, daß sich mobile Endgeräte, die zur Ortsbestimmung in der Lage sind (GPS, global positioning System) und die drahtlos mit Servern kommunizieren, rasant ausbreiten, z.B. in Fahrzeugen, PDAs (persönlichen digitalen Assistenten) oder in Mobiltelefonen. Die Entwicklung von Anwendungen für Millionen bewegter Objekte ist deshalb ein wichtiges Problem. Die zu Beginn des Projektes existierenden Ansätze unterstützten im wesentlichen die freie Bewegung von Punkten, Linienzügen und Gebieten in der Ebene. Von besonderer Relevanz sind aber punktförmig zu modellierende Objekte (Personen, Fahrzeuge), die sich in Netzwerken bewegen (Wege, Straßen, Flußläufe). Ziel des Projektes war die Weiterentwicklung von Datenmodellen und Anfragesprachen für mobile Objekte und die auch prototypische Studie von Implementierungsstrategien. Ein besonderer Schwerpunkt sollte dabei auf der Behandlung in die Ebene eingebetteter Netze und sich darin bewegender Objekte liegen. Einige wichtige Ergebnisse des Projekts sind die folgenden: • Ein prototypisches Datenbanksystem für die Verwaltung beweglicher Objekte wurde realisiert. Systemumgebung ist die erweiterbare DBMS-Architektur SECONDO, die am Lehrgebiet von Prof. Güting in den vergangenen ca. 10 Jahren entwickelt wurde. Dieses System bietet Datentypen für bewegliche Objekte wie etwa moving point und moving region mit geeigneten Operationen, die in Anfragen verwendet werden können. SECONDO ist im Web Öffentlich zum Download verfügbar (dna.fernuni-hagen.de/Secondo.html). Es ist der fortschrittlichste bisher existierende Prototyp für die Verwaltung von Bewegungsverläufen. • Als Erweiterung des in SECONDO realisierten Datenmodells für frei bewegliche Objekte wurde ein Datenmodell und eine Anfragesprache für netzbasierte Bewegung entwickelt. Dieses Modell erlaubt kompaktere Darstellung von Bewegungen und bietet spezialisierte Konzepte für Anfragen auf Netzen. Eine prototypische Realisierung wurde begonnen. • Ein Modell und ein Prototyp für periodische Bewegung wurde vorgeschlagen bzw. realisiert. Damit lassen sich z.B. Fahrpläne kompakt und nichtredundant darstellen. • Ein Benchmark für Datenbanksysteme für bewegliche Objekte, der BerlinMOD-Benchmark, wurde definiert. Der Benchmark beschreibt, wie umfangreiche und skalierbare Datenbanken mit beweglichen Objekten konstruiert werden können und enthält einen Satz von Testanfragen. Software auf der Basis des SECONDO-Systems zum Aufbau der Testdatenbank wird ebenfalls im Web zur Verfügung gestellt. Ein solcher Benchmark ist ein wichtiges Werkzeug für die Forschung und Prototypentwicklung. • Eine Indexstruktur für netzbasierte Bewegung, der MON-Tree, wurde vorgeschlagen und experimentell untersucht.
Publications
- A Simple But Effective Improvement to the Plumbline Algorithm. Information Processing Letters 91, 6 (2004), 251-257
Güting, R.H., and Z. Ding
- Indexing the Trajectories of Moving Objects in Networks. Short Paper in Proc. of the 16th Intl. Conf. on Scientific and Statistical Database Management (SSDBM, Santorini Island, Greece), 2004, 115-118
Almeida, V.T. de, and R.H. Güting
- Managing Moving Objects on Dynamic Transportation Networks. Proc. of the 16th Intl. Conf. on Scientific and Statistical Database Management (SSDBM, Santorini Island, Greece), 2004, 287-296
Ding, Z., and R.H. Güting
- Modeling Temporally Variable Transportation Networks. Proc. of the 9th Int. Conf. on Database Systems for Advanced Applications (DASFAA, Jeju Island, Korea), 2004, 154-168
Ding, Z., and R.H. Güting
- SECONDO: An Extensible DBMS Architecture and Prototype. Fernuniversität Hagen, Informatik-Report 313, 2004
Güting, R.H., T. Behr, V.T. de Almeida, Z. Ding, F. Hoffmann, and M. Spiekermann
- Uncertainty Management for Network Constrained Moving Objects. Proc. of the 15th Intl. Conf. on Database and Expert Systems Applications (DEXA, Zaragoza, Spain), 2004, 411-421
Ding, Z., and R.H. Güting
- Fuzzy Spatial Objects: An Algebra Implementation in SECONDO. Demo-Paper, 21st Intl. Conf. on Data Engineering (ICDE, Tokyo, Japan), 2005, 1137-1139
Behr, T., and R.H. Güting
- Indexing the Trajectories of Moving Objects in Networks. Geolnformatica 9, 1 (2005), 33-60
Almeida, V.T. de, and R.H. Güting
- SECONDO: An Extensible DBMS Platform for Research Prototyping and Teaching. Demo-Paper, 21st Intl. Conf. on Data Engineering (ICDE, Tokyo, Japan), 2005, 1115-1116
Güting, R.H., V. Almeida, D. Ansorge, T. Behr, Z. Ding, T. Höse, F. Hoffmann, M. Spiekermann
- Supporting Uncertainty in Moving Objects in Network Databases. 13th ACM Intl. Workshop on Geographic Information Systems (ACM-GIS, Bremen, Germany), 2005, 31-40
Almeida, V. T. de, and R.H. Güting
- Modeling and Querying Moving Objects in Networks. The VLDB Journal 15, 2 (2006), 165-190
Güting, R.H., V.T. de Almeida, and Z. Ding
- Moving Objects in Networks Databases. EDBT Ph.D. Workshop (Munich, Germany), 2006, 75-85
Almeida, V. T. de
- Querying Moving Objects in SECONDO. Demo-Paper, 7th Intl. Conf. on Mobile Data Management (MDM, Nara, Japan), 2006, 47-51
Almeida, V. T. de, R.H. Güting, and T. Behr
- Representation of periodic moving objects in databases. 14th ACM Intl. Symp. on Geographic Information Systems (ACM-GIS, Arlington, Virginia), 2006, 43-50
Behr, T., V.T. de Almeida, and R.H. Güting
- Towards Optimal Continuous Nearest Neighbor Queries in Spatial Databases. 14th ACM Intl. Symp. on Geographic Information Systems (ACM-GIS, Arlington, Virginia), 2006, 227- 234
Almeida, V. T. de
- Using Dijkstra's Algorithm to Incrementally Find the k-Nearest Neighbors in Spatial Network Databases. Proc. ACM Symposium on Applied Computing (SAC, Dijon, France), 2006, 58-62
Almeida, V. T. de, and R.H. Güting
- BerlinMOD: A Benchmark for Moving Object Databases. Fernuniversität in Hagen, Informatik-Report 340 - 12/2007. VLDB Journal
Düntgen, C., T. Behr, and R.H. Güting
- How to Build Your Own Moving Objects Database System. Keynote at the 8th Intl. Conf. on Mobile Data Management (MDM, Mannheim, Germany), 2007, 1-2
Güting, R.H.
- Multiple Entry Indexing and Double Indexing. 11th Intl. Database Engineering and Applications Symposium (IDEAS, Banff, Alberta, Canada) 2007, 181- 189
Almeida, V. T. de, R.H. Güting, and C. Düntgen
