Forschungsthemen: Geo-Datenbanksysteme und erweiterbare Datenbanksysteme

Ein Datenbanksystem ist ein Software-System, das die von einem Unternehmen (oder irgendeiner Art von Institution) benötigten Daten in einer einheitlichen, strukturierten Form für verschiedene Anwendungen verwaltet und einen effizienten Zugriff auf interessierende Information ermöglicht. Ein Datenbanksystem bietet seinem Benutzer ein relativ einfach zu verstehendes Datenmodell an, d.h. eine Vorstellung, wie die Daten gespeichert sind, sowie eine Anfragesprache, die sich auf dieses Datenmodell bezieht. Die wirkliche, viel komplexere Darstellung der Daten im Speicher, die auf effizienten Zugriff hin angelegt ist, wird dadurch vor dem Benutzer verborgen; er wird davon unabhängig. Ein weitverbreitetes Datenmodell ist das sog. relationale Modell, bei dem man sich vorstellt, daß Daten in Tabellen gespeichert sind. Informationen über Städte könnte man also z.B. so verwalten:


Staedte Name Einwohnerzahl Land
Hagen 206 000 Nordrhein-Westfalen
Dortmund572 000Nordrhein-Westfalen
Muenchen1 267 000Bayern

Die Anfragesprache zu diesem Modell erlaubt es beispielsweise, Zeilen und Spalten aus einer Tabelle auszuwählen. So könnte man etwa nach den Einwohnerzahlen aller Großstädte in Nordrhein-Westfalen auf folgende Art fragen:

select Name, Einwohnerzahl
from Staedte
where Land = "Nordrhein-Westfalen" and Einwohnerzahl > 500 000

Als Ergebnis erhält man wiederum eine Tabelle, die allerdings nur noch die Spalten Name und Einwohnerzahl und die durch die Bedingung ausgewählten Zeilen enthält.

Datenbanksysteme werden praktisch überall in der Datenverarbeitung eingesetzt und sie funktionieren gut für sog. Standard-Anwendungen. Die Forschung im Bereich der Datenbanksysteme zielt nun darauf ab, solche Systeme auch für Anwendungsbereiche zugänglich zu machen, bei denen die Daten eine komplexere Struktur haben. Eine Einschränkung der Standardsysteme liegt z.B. darin, daß die Einträge in Tabellen nur Zahlen oder Zeichenketten sein können. Eine andere Einschränkung liegt darin, daß die Beziehungen zwischen darzustellenden Objekten der Realwelt oft in Tabellen nur unzureichend beschrieben werden können.

Am Lehrgebiet Datenbanksysteme für neue Anwendungen untersuchen wir die Anforderungen an Datenbanksysteme, die von Anwendungen gestellt werden, die geometrische Information verwalten müssen. Ein Beispiel dafür sind geographische Informationsysteme, in denen (in globalem oder lokalem Maßstab) Ausschnitte der Erdoberfläche beschrieben und für Anfragen und Auswertungen zugänglich gemacht werden müssen. Eine relativ einfache Anfrage könnte etwa lauten: "Wieviele Menschen leben in Dörfern oder Städten innerhalb eines Abstands von bis zu 10 km entlang des Rheins?" Eine Frage im Zusammenhang mit Verkehrsnetzen wäre: "Finde den schnellsten Weg von Dortmund nach München über das Autobahn- und Straßennetz unter Umgehung eines (durch ein Polygon beschriebenen) Nebelgebietes!" Datenbanksysteme, die Konzepte für die Verwaltung geometrischer Information bieten, heißen Geo-Datenbanksysteme.

Die Aufgabe besteht also darin, zunächst ein möglichst einfaches, aber auch ausdrucksstarkes Modell für die zu speichernde Information zu finden und dazu eine geeignete Anfragesprache zu definieren. Im nächsten Schritt muß man dann überlegen, wie dieses Modell auf interne Speicherungsstrukturen eines Datenbanksystems (bereits bekannte oder auch neue) abgebildet werden kann und wie die effiziente Ausführung von Anfragen erreicht werden kann. Ein wichtiges Grundkonzept für die Realisierung von Geo-Datenbanksystemen ist die Einführung geometrischer Datentypen. Ein Datentyp besteht aus einer Menge von Werten zusammen mit Operationen auf diesen Werten. Ein einfacher Datentyp ist z.B. die Menge der ganzen Zahlen mit den Operationen Addition, Subtraktion, Multiplikation und (ganzzahliger) Division, sowie mit Vergleichsoperationen (=, <, >, <=, >=). Im oben skizzierten relationalen Modell steht ein solcher Datentyp (integer) zur Verfügung, deshalb kann man einerseits Einwohnerzahlen von Städten abspeichern und andererseits eine Bedingung "Einwohnerzahl > 500000" formulieren. Übrigens sind Datentypen nicht nur isoliert zu betrachten, da Operationen eines Datentyps durchaus Werte eines anderen Datentyps liefern können (z.B. eine Operation "length", die angewandt auf eine Zeichenkette eine ganze Zahl liefert, nämlich die Anzahl ihrer Zeichen). Ein System mehrerer zueinander in Beziehung stehender Datentypen ist eine (mehrsortige) Algebra. Ein Forschungsthema ist nun die Frage, wie eine Algebra für geometrische Datentypen entworfen werden sollte, also welche Arten von Werten sie enthalten und welche Operationen sie anbieten sollte.

Am Lehrgebiet wurde ein solches System geometrischer Datentypen, die ROSE-Algebra, definiert. Sie bietet drei Datentypen für die Modellierung von Geometrie in der Ebene an, die POINTS, LINES, und REGIONS heißen. Werte dieser Typen sind in der folgenden Abbildung gezeigt.


Abbildung 1


Ein REGIONS-Wert kann also aus mehreren getrennten Polygonen bestehen, die auch "Löcher" haben dürfen. Ein wichtiges Kriterium beim Entwurf einer Algebra ist ihre Abgeschlossenheit unter Operationen. Mit dieser Struktur von REGIONS-Werten kann man z.B. die Vereinigung oder die Differenz (der Punktmengen) zweier beliebiger REGIONS-Werte bilden und erhält stets wieder einen REGIONS-Wert. Das wäre nicht der Fall bei einem Datentyp, der nur einfache Polygone darstellen könnte (da die Differenz Löcher erzeugt). Die ROSE-Algebra bietet nun einen recht umfangreichen Satz von Operationen an, um solche geometrischen Werte zu vergleichen oder damit zu "rechnen". Vergleichsoperationen sind z.B. inside (liegt ein Wert eines der drei Typen vollständig innerhalb eines REGIONS-Wertes) oder adjacent (berühren sich zwei LINES oder REGIONS-Werte). Es gibt aber auch Operationen, um neue geometrische Werte zu berechnen, z.B. intersection angewandt auf zwei LINES-Werte ergibt einen POINTS-Wert (die Menge der Schnittpunkte), contour liefert für einen REGIONS-Wert einen LINES-Wert, der seine begrenzenden Linien enthält. Andere Operationen liefern Maße, etwa die Fläche usw., geben also Zahlenwerte zurück.

Wichtige Kriterien für die Beurteilung solcher Entwürfe von Algebren sind die schon erwähnte Abgeschlossenheit, die präzise formale Definition der Bedeutung aller Operationen (damit es keine Irrtümer bei der Benutzung oder Fehler bei der Implementierung gibt), die Erklärung der Bedeutung der Operationen in bezug auf Arithmetik beschränkter Genauigkeit (da diese üblicherweise in der Implementierung verwendet wird), und die Möglichkeit, die Algebra in ein beliebiges Datenmodell einzubetten (also auch an Datenbanksysteme anzukoppeln, die nicht das relationale Modell verwenden). Schließlich sollten die Operationen der Algebra auch effizient implementierbar sein. Die ROSE-Algebra erfüllt alle diese Kriterien und ist am Lehrgebiet auch als Programmsystem realisiert worden.

Wenn geometrische Datentypen verfügbar sind, kann man z.B. in einem relationalen System Relationen (Tabellen) anlegen, die solche Werte enthalten. Eine sehr einfache Beispieldatenbank könnte Relationen für Städte und Bundesländer in Deutschland enthalten:

Staedte (SName: STRING, Einwohnerzahl: INTEGER, Ort: POINTS)
Laender (LName: STRING, Gebiet: REGIONS)

Auf dieser Datenbank kann man dann Anfragen formulieren:

"Welche Nachbarländer hat Bayern?"

select Y.LName
from Laender X, Laender Y
where X.LName = "Bayern" and X.Gebiet adjacent Y.Gebiet

"Wieviele Menschen leben in Städten im Abstand von bis zu 100 km von der deutschen Grenze?"

select sum(Einwohnerzahl)
from Staedte
where distance(Ort, contour(sum(select Gebiet from Laender))) < 100

Hier bildet der Ausdruck "select Gebiet from Länder" eine Menge von REGIONS-Werten; die darauf angewandte sum Operation bildet die Vereinigung aller dieser Gebiete; schließlich berechnet contour die Grenze dieses Gebietes, also die deutsche Grenze.

Der "Einbau" einer solchen Algebra in ein Datenbanksystem erfordert allerdings noch Erweiterungen des Systems auf vielen Ebenen. Z.B. werden spezielle Indexstrukturen gebraucht, mit denen man gezielt auf geometrische Objekte zugreifen kann (um etwa die Städte im Umkreis von 50 km von Hagen zu finden, ohne sämtliche Städte zu überprüfen). Eine Komponente des Datenbanksystems, der Optimierer, ist dafür zuständig, aus vielen möglichen Auswertungsstrategien für eine Anfrage die kostengünstigste auszuwählen (die am wenigsten Zeit und Speicherplatz benötigt). Der Optimierer muß nun ebenfalls erweitert werden, damit er z.B. eine geometrische Indexstruktur tatsächlich für den Zugriff einsetzen kann. Die Technologie, mit der man Datenbanksysteme so konstruiert, daß derartige Änderungen leicht vorzunehmen sind, ist die der erweiterbaren Datenbanksysteme.

Geo-Datenbanksysteme und erweiterbare Datenbanksysteme sind zentrale Forschungsthemen am Lehrgebiet Datenbanksysteme für neue Anwendungen. Die beiden Themen hängen eng zusammen: Das Anwendungsgebiet der Geo-Datenbanken stellt Anforderungen an die Konstruktion erweiterbarer Systeme; diese bieten die geeignete Systemumgebung für die Realisierung von Geo-Datenbanksystemen. Ein größerer Prototyp für ein erweiterbares Datenbanksystem mit geometrischen Erweiterungen, das Gral-System, ist am Lehrgebiet u.a. im Rahmen etlicher Diplomarbeiten konstruiert worden.



Letzte Änderung: 2016-11-22 ()