Zeit in Geografischen Informations-Systemen

6.5 Indizierung der Geo-Objekte

Neben der Selektion anhand der thematischen Attribute muß es möglich sein, die räum­lichen Eigenschaften als Selektionskriterium zu spezifizieren. Ein typisches Beispiel ist eine Bereichsabfrage in der Form ”Finde alle Objekte, die durch das Rechteck R überdeckt werden.”. Ab einer gewissen Datenbankgröße ist es nicht mehr effizient möglich, alle ge­speicherten Geo-Objekte zu durchlaufen und für jedes den erforderlichen geometrischen Test auszuführen (OOSTEROM 1999, S. 385).

Indizes sollen die zielgerichtete Suche in großen Datenbeständen beschleunigen, indem sie die Datensätze anhand eines Attributes vorsortieren. Durch diese Vorsortierung kann das Datenbanksystem schnell mittels entsprechender Suchalgorithmen auf die relevanten Daten­sätze zugreifen. Konventionelle DBMS verwenden hierzu in der Regel einfache Strukturen wie Binärbäume, die die Daten in einer Dimension sortieren können. Räum­liche Daten benötigen aber eine Indizierung in mindestens zwei Dimensionen bzw. bei dreidimensionalen Daten und zeitvariablen räumlichem Bezug in drei bzw. vier Dimen­sionen. (WORBOYS 1995, S. 64; OOI 1990, S. 4f.)

Angenommen, in einem kommunalen GIS soll ermittelt werden, durch welche Grund­stücke die Versorgungsleitung 4711 läuft. Die Abfrage würde vom Anwender –unabhängig von der darunterliegenden Datenstruktur- in einer SQL-ähnlichen Syntax folgender­maßen aussehen:

”SELECT X FROM Grundstück WHERE Cross(Grundstück X, 4711) = TRUE ”

Entsprechend der Organisation der Daten stehen zwei Strategien zur Verfügung :

1. Sequentielle Suche: Jedes Grundstück in der Datenbank wird daraufhin überprüft, ob das Prädikat ”Cross(X, ”4711”) zutrifft. Diese Strategie wäre höchst ineffizient und der Zeitbedarf für die Ausführung wächst linear mit der Anzahl der gespeicherten Grundstücke. Jedes Grundstück muß aus der Datenbank ausgelesen werden, und für jede Seite und jeder Eckpunkt ist ein Schnittest mit der Linie von ”4711” auszuführen.

2. Indexgestützte Suche: Die Suche kann dann auf eine Teilmenge aller Grundstücke eingeschränkt werden, wenn im System einen Struktur existiert, die zumindest näherungsweise die relative Lage der Geo-Objekte zueinander abbildet. Solche räum­lichen Indizes ermöglichen eine zweistufige Suche: über den Index als Grobfilter kön­nen ohne den aufwendigen geometrischen Schnitt diejenigen Kandidaten ermittelt werden, die aufgrund ihrer relativen Lage überhaupt in Frage kommen können. Diese Auswahl ist deshalb grob, weil die Objekte anhand einer Approximation wie z.B. dem kleinsten umgebenden Rechteck erfaßt werden. Grundstücke, deren Approximation disjunkt zu ”4711” sind, können von vorneherein ausgeschlossen werden. Die vor­selektierten Kandidaten werden dann im zweiten Schritt dem genauen Test für alle Seiten und Eckpunkte unterzogen und nur die tatsächlich betroffenen Grundstücke in die Ergebnismenge aufgenommen.

Beide Verfahren führen zwar zum gleichen Ergebnis, weisen aber in der Ausführungsge­schwindigkeit signifikante Unterschiede auf. Es ist offensichtlich, daß die Performanz der Abfrageausführung wesentlich davon beeinflußt wird, wie groß die zu überprüfende Kan­didatenmenge für den aufwendigen Feintest ist.

In der Literatur wird dazu eine Vielzahl spezieller Datenstrukturen angebotenen. Jede Methode weist für unterschiedliche Situationen spezifische Vor- und Nachteile auf, wobei sich Baumstrukturen in einem objektorientierten Umfeld anbieten, da sich die Knoten, Verzweigungen und Blätter eines Baumes direkt in Form von Objekten und entsprechen­den Pointern implementieren lassen. Ein bekannter Vertreter dieser Art im GIS-Bereich ist der Quadttree, der auch zur komprimierten Speicherung von Rasterdaten Verwendung findet.(SAMET 1995a, S. 2f.)

Abbildung 40: Der Point-Quadtree

Quelle: SAMET 1995b, S. 11.

Die Grundidee bei der Verwendung einer Baumstruktur wie dem Quadtree besteht in der rekursiven Zerlegung des Raumes. Auf jeder Stufe wird ein Raumausschnitt in vier Quadranten unterteilt. Die Unterteilung wird dadurch ausgelöst, daß nacheinander Geo-Objekte entsprechend ihrer Lage in den Baum eingefügt werden, bis ein zuvor festgelegter Schwellenwert überschritten wird. Die Objekte des ursprünglichen Blattes werden auf die einzelnen Folgeblätter aufgeteilt. Dieses Verfahren gewährleistet ein dynamisches Wachsen des Baumes mit unterschiedlich tiefen Ästen, so daß kein regelmäßiges Gitter entsteht, sondern ein an die räumliche Verteilung der erfaßten Geo-Objekte angepaßtes Suchmuster (BARTELME 1995, S. 220ff.). Abbildung 40 zeigt diese Zerlegung für punktförmige Objekte.

Problematischer ist die Indizierung ausgedehnter Objekte wie Linien und Polygone. Hier werden in der Literatur drei Strategien vorgeschlagen (GÜNTHER 1992, S. 18f.):

1. Clipping: die Blätter des Baumes teilen den Raum in disjunkte Teilräume und die ausgedehnten Geo-Objekte werden entlang der Partitionslinien unterteilt (”geclippt”). Dadurch kann ein Polygon mehrfach indiziert werden.

2. Überlappende Partitionen: die durch die Blätter abgebildeten Partitionen müssen nicht disjunkt sein, sondern können sich gegenseitig überlappen. Jedes Objekt ist aber nur genau einer Partition zugewiesen.

3. Transformationsansatz: ausgedehnte räumliche Objekte werden funktional auf höher­dimensionale Punkte abgebildet und diese Punkte werden indiziert. Ein um­schließendes Rechteck in der Ebene wird durch die Abbildung zu einem vierdimen­sionalen Punkt.

Hier soll aber eine andere Methode verwendet werden, die die Verwaltung der Elemente im Baum erleichtert. Um die Ergebnismenge einer räumlichen Abfrage zu bilden, ist es günstig, wenn jedes Geo-Objekt nur einmal im Baum enthalten ist. Entspricht das Objekt dem Abfrageprädikat, müßte das System andernfalls noch überprüfen, ob das Element nicht bereits in der Ergebnismenge enthalten ist. Ähnlich ist die Situation beim Löschen eines Objektes, da zunächst alle Blätter gesucht werden müssen, die dieses Objekt referen­zieren. Überlappende Partitionen sind insofern ungünstig, als auch hier eine Mehrfach­indizierung auftreten kann. Der Transformationsansatz scheidet aus, da die relativen Be­ziehungen zwischen den Geo-Objekten zum Teil verloren gehen.

Günstiger scheint hier eine Erweiterung der Datenstruktur zu sein, indem Geo-Objekte nicht nur von Blättern, sondern auch von inneren Knoten referenziert werden können. Kann bei einer Überlaufsituation ein Objekt nicht an einen der Nachfolgerknoten weiter­gegeben werden, da es nicht vollständig innerhalb der durch den Nachfolger abzudecken­den Raumeinheit enthalten ist, so verbleibt es im Knoten. Dazu muß man lediglich deb Suchalgorithmus erweitern, so daß auch die inneren Knoten nach Ergebniselementen durchsucht werden.

In der vorliegenden Arbeit ist eine Indizierung der Geo-Objekte in drei Dimensionen not­wendig. Dazu bietet sich die dreidimensionale Erweiterung des Quadtrees, der Octtree, an (SAMET 1995a, S. 4ff.). Jeder Knoten erfaßt alle Geo-Objekte, die innerhalb eines be­stimmten Tetraeders liegen. Kommt es zu einem Überlauf, teilt sich das Blatt in acht Nachfolger und überträgt die von ihm referenzierten Geo-Objekte.

Abbildung 41: Raumaufteilung durch einen Octtree



Quelle: Eigener Entwurf

Der Octtree paßt sich ebenfalls dynamisch an die Verteilung der Daten an und unterteilt sich nur dort, wo einen vorbestimmte Anzahl an Elementen überschritten wird. Damit ist eine effiziente Datenstruktur gegeben, die die räumliche Suche für zweidimensionale Daten mit einer dritten temporalen Achse unterstützt.

© 2014 Zeit in Geografischen Informationssystemen (GIS), Frank Hellwich