ID 4071
Dangelmayer, Frank: Konzeption und Implementierung eines Verfahrens
für effiziente, nicht präzise Datenbankabfragen im Kontext eines skizzenbasierten GIS
Hamburg: Diplomica GmbH, 2005
Zugl.: Fachhochschule Ravensburg-Weingarten, Diplomarbeit, 2004
Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte,
insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von
Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der
Vervielfältigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen,
bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfältigung
dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen
der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik
Deutschland in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich
vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des
Urheberrechtes.
Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in
diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme,
dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei
zu betrachten wären und daher von jedermann benutzt werden dürften.
Die Informationen in diesem Werk wurden mit Sorgfalt erarbeitet. Dennoch können
Fehler nicht vollständig ausgeschlossen werden, und die Diplomarbeiten Agentur, die
Autoren oder Übersetzer übernehmen keine juristische Verantwortung oder irgendeine
Haftung für evtl. verbliebene fehlerhafte Angaben und deren Folgen.
Diplomica GmbH
http://www.diplom.de, Hamburg 2005
Printed in Germany
Erklärung
Hiermit erkläre ich, dass ich die Arbeit selbstständig und nur unter Verwendung der an-
gegebenen Quellen und Hilfsmittel verfasst habe.
Darmstadt, 31. Juli 2004
______________________
(Frank Dangelmayer)
Inhaltsverzeichnis
1 Einleitung
1
1.1
Motivation
1
1.2
Problemstellung
4
1.3
Übersicht
4
2 Grundlagen
5
2.1
Geographische Informationssysteme
5
2.1.1
GIS-Datenbanken
5
2.1.2
Anfragen an Geoinformationssysteme
6
2.1.3
Datenbankmanagementsysteme für räumliche Daten
8
2.2
Oracle Spatial
9
2.2.1
Räumliche Objekte
9
2.2.2
Abfragen
10
2.2.3
Spatial Joins
11
2.2.4
Funktionen
13
2.2.5
Bewertung
15
2.3
SketchQuery Ein Programm für skizzenbasierte GIS-Anfragen
19
2.3.1
Übersicht
19
2.3.2
Skizzen in SketchQuery
20
2.3.3
Benutzerschnittstelle
22
2.3.4
Schnittstelle für Datenbankabfragen
24
3 Räumliche Datenstrukturen und Algorithmen
25
3.1
Indexstrukturen zur Verwaltung räumlicher Objekte
25
3.1.1
Grid File
26
3.1.2
QuadTree
27
3.1.3
R-Baum
29
3.1.4
R
+
-Baum
32
3.1.5
R
*
-Baum
33
3.1.6
Bewertung
34
3.2
Spatial Join-Algorithmen beim R-Baum
36
3.2.1
Algorithmen ohne Indexstrukturen
36
3.2.2
Index nested loops join
37
3.2.3
Paralleles Durchlaufen zweier R-Bäume
37
3.2.4
Distance Join-Algorithmus
39
3.2.5
Seeded Tree
40
3.2.6
Zusammenfassung und Bewertung
41
3.3
Einsatz in Oracle Spatial
42
4 Entwurf
43
4.1
Stand der Technik
43
4.2
Anforderungen
44
4.2.1
Verschiedene Anfrageformen
44
4.2.2
Fehlerbewertung
44
4.2.3
Effizienz
45
4.3
Architektur
46
4.4
Module des Systems
48
4.4.1
Übernahme der Daten von SketchQuery
48
4.4.2
Umwandlung und Ausführung der Anfrage
48
4.4.3
Abweichungen von der Eingabe-Skizze
49
4.4.4
Darstellung der Ergebnisse
50
4.5
Ablauf
52
5 Implementierung
53
5.1
Rahmenbedingungen
53
5.1.1
Datensätze für die Erprobung des Verfahrens
53
5.2
Übernahme der Daten von SketchQuery
55
5.3
Umwandlung und Ausführung der Anfrage
58
5.3.1
Ablauf
58
5.3.2
Datenmodell für die Ergebnisse
60
5.3.3
Klasse für die Datenbankanbindung
61
5.3.4
Reihenfolge der Spatial Joins
62
5.3.5
Konfigurationsdatei
63
5.4
Abweichungen von der Eingabe-Skizze
64
5.4.1
Ermittlung der geometrischen Ähnlichkeit
66
5.5
Darstellung der Ergebnisse
68
5.6
Erweiterbarkeit
70
6 Bewertung und Ausblick
72
6.1
Ergebnisse
72
6.2
Bewertung
73
6.3
Ausblick
76
6.3.1
Kommunikation mit SketchQuery
76
6.3.2
Einsatz eigener Indexstrukturen und Join-Algorithmen
76
6.3.3
Indexstrukturen für die Fourier-Koeffizienten
78
7 Zusammenfassung
79
Anhang A - Algorithmus zur Fourier-basierten Ähnlichkeitssuche
80
Index
84
Abbildungsverzeichnis
85
Literaturverzeichnis
87
Einleitung
1
1 Einleitung
1.1 Motivation
Digitale Landkarten werden heutzutage häufig in Datenbanken gespeichert und verwal-
tet. Abfragen an eine Datenbank müssen dabei oft in Textform gestellt werden. Um
Abfragen zu formulieren muss der Benutzer eine Abfragesprache, wie z.B. SQL beherr-
schen. Zumeist versucht der Mensch seine visuelle Vorstellung in eine solche Abfrage-
sprache umzuwandeln. Es existiert eine für den Benutzer einfachere und natürlichere
Methode seine Abfragen zu definieren: das Anfertigen einer Skizze. Dabei wird das in-
nere Bild des Benutzers direkt in eine Zeichnung umgesetzt. Diese Art der Benutzerin-
teraktion wurde bisher nur sehr selten für geographische Informationssysteme eingesetzt
[BSE00].
Das Ziel dieser Arbeit ist es, aus Skizzen, welche durch Analysen ausgewertet wurden,
Anfragen für geographische Datenbanken zu erstellen und auszuführen. Diese Arbeit
baut auf eine Diplomarbeit [Huý03] auf, in welcher eine graphische Bedienoberfläche
zur Eingabe und Auswertung der Skizze entwickelt wurde.
Skizzen eignen sich besonders gut, um topologische Fragestellungen wie Nachbar-
schaft, Enthaltensein, Überschneidung und ähnlichem zu formulieren [Huý03]. Die An-
fragen können durch handschriftliche Bemerkungen weiter präzisiert werden.
Um zu verdeutlichen, welche Anfragen an ein solches System gestellt werden können,
werden zwei Beispiele für skizzenbasierte Anfragen vorgestellt:
· Eine Familie sucht für ihren Urlaub eine Ferienwohnung. In der Nähe dieser
Wohnung sollte sich ein See befinden. Da die Familie mit öffentlichen
Verkehrsmitteln anreisen möchte, sollte sich eine Bushaltestelle in der Nähe
befinden. Folgende Skizze wird dafür angefertigt:
Einleitung
2
· Ein Automobilhersteller sucht für die Anbringung von Werbeplakaten einen ge-
eigneten Standort. Er hat drei Plakate entworfen, welche der potentielle Kunde
bei der Fahrt auf einer Straße der Reihe nach sehen soll. Er sucht nach freien
Werbeflächen, die einen Abstand von etwa 500 Meter an einer Straße angren-
zen. Damit die Plakate von möglichst vielen Personen gesehen werden, sollten
sie an einer Bundesstrasse platziert werden. Außerdem sollte in maximal 10 km
Entfernung ein Autohaus seiner Marke existieren. Er könnte eine Skizze wie in
Abbildung 1.2 anfertigen:
Abbildung 1.2: Skizze für Standorte von Werbeplakaten
Abbildung 1.1: Skizze für Urlaubsplanung
Einleitung
3
In den Skizzen werden also mehrere Objekte (z.B. Ferienwohnung, See, Bushaltestelle)
und deren topologischen Beziehungen (z.B. der Abstand) angegeben. Nach dieser An-
ordnung der verschiedenen Objekte soll in einer geographischen Datenbank gesucht
werden. Es soll außerdem berücksichtigt werden, welche geometrische Form die Objek-
te haben (z.B. der See in Abbildung 1.1), um möglichst ähnliche Objekte in der Daten-
bank zu identifizieren. Der Schwerpunkt bei den Anfragen liegt jedoch auf der Suche
nach den Beziehungen der Objekte untereinander.
Eine Skizze besteht aus einer Menge von Strichen, welche zu verschiedenen Objekten
gruppiert werden. Die Objekte können beschriftet werden. Außerdem ist es möglich,
den Abstand zwischen zwei Objekten anzugeben.
Der Ablauf eines Systems, mit dem skizzierte Anfragen an eine Datenbank gestellt
werden, wird in Abbildung 1.3 erläutert. Der Benutzer zeichnet eine Skizze (1), welche
aus einer Menge von Strichen besteht. Diese Skizze wird durch eine Analyse in Objekte
und deren Beziehungen untereinander umgewandelt (2) und daraus eine formale Be-
schreibung (3) erzeugt. Anschließend wird eine Datenbank-Abfrage generiert (4), wel-
che nach dieser Objekt-Anordnung sucht. Die Ergebnisse der Abfrage müssen interpre-
tiert, bewertet und nach ihrer Qualität sortiert werden (5). Danach sind weitere Akti-
onen, wie beispielsweise die Beschaffung von zusätzlichen Informationen zu den ge-
fundenen Objekten möglich (6). Nachdem die Ergebnisse ermittelt und aufbereitet wur-
den, werden sie dem Benutzer in Form eines Kartenausschnitts dargestellt (7). In dieser
Arbeit werden die Schritte (4) und (5) bearbeitet.
Abbildung 1.3: Schema einer skizzenbasierten Anfrage an ein geographisches System [Huý03]
Bei den Anfragen an die Datenbank sollen mehrere Ergebnisse gefunden, bewertet und
ihrer Relevanz nach geordnet werden. Dabei wird eine Auflistung der einzelnen Objekte
in der Skizze und ihre topologischen Beziehungen vorausgesetzt. Der Schwerpunkt
dieser Arbeit beschäftigt sich mit der Umsetzung der Anfrage aus der Skizze in eine
geeignete Datenbank-Abfrage. Diese sollte möglichst effizient ausgeführt werden kön-
nen. Dabei wird auch die Verwendung eines geeigneten Datenbankschemas diskutiert.
Einleitung
4
1.2 Problemstellung
In [Huý03] wurde ein System zur Eingabe und Erkennung von Skizzen entwickelt.
Dieses System ermittelt alle vom Benutzer gezeichneten Objekte und deren Beziehung-
en untereinander. Die erkannten Informationen werden in einer XML-Datei abgelegt. In
der vorliegenden Arbeit soll ein Verfahren konzipiert und prototypisch umgesetzt
werden, welches basierend auf dieser XML-Datei eine Anfrage an eine geographische
Datenbank generiert. Dabei gilt es effizient Ausschnitte aus der Datenbank zu identifi-
zieren, welche der vom Benutzer gezeichneten Skizze ähneln. Eine Bewertung der
identifizierten Ergebnisse ist zudem erforderlich. Daneben ist eine Integration des ent-
wickelten Verfahrens in das System von [Huý03] bzw. in die Erweiterungen des Sys-
tems notwendig. Eine dort enthaltene Schnittstelle zur Darstellung der Resultate sollte
ebenfalls angesprochen werden.
1.3 Übersicht
In dieser Arbeit wurden folgende Punkte bearbeitet:
· Stand der Technik bei der Durchführung räumliche Anfragen
· Konzeption eines Verfahrens
· Implementierung dieses Konzepts in Java
· Bewertung des daraus entstandenen Systems
Diese Punkte sind wie folgt auf die Arbeit verteilt: Kapitel 2 definiert grundlegende Be-
griffe und stellt Programme vor, die bei dieser Arbeit verwendet wurden. Die Algorith-
men und Datenstrukturen für Abfragen von räumlichen Daten werden in Kapitel 3 er-
klärt. Kapitel 4 präsentiert den Entwurf des Systems und Kapitel 5 beschreibt dessen
Umsetzung ausführlich. Im Kapitel 6 wird das entwickelte System bewertet und mög-
liche, zukünftige Erweiterungen vorgeschlagen. Eine abschließende Zusammenfassung
findet sich in Kapitel 7.
Grundlagen
5
2 Grundlagen
2.1 Geographische Informationssysteme
Ein geographisches Informationssystem wird in [Bar89] wie folgt definiert:
Ein Geoinformationssystem (GIS) dient der Erfassung, Speicherung, Analyse
und Darstellung aller Daten, die einen Teil der Erdoberfläche und die darauf
befindlichen technischen und administrativen Einrichtungen sowie geowissen-
schaftliche, ökonomische und ökologische Gegebenheiten beschreiben [Bar89].
Die Daten eines GIS werden häufig in einer Datenbank abgelegt. Eine solche Daten-
bank unterscheidet sich von einer gewöhnlichen Datenbank im wesentlichen dadurch,
dass sie räumliche (d.h. zwei- oder dreidimensionale) Objekte enthält. Diese enthalten
die geometrische Repräsentation der geographischen Objekte. Beispiele für solche Ob-
jekte sind Straßen, Gebäude oder Parkplätze. Geoinformationssysteme haben unter an-
derem folgende Einsatzfelder:
· Kartendarstellung: Darstellung einer Teilmenge der Daten
· Routenplanung:
Suche nach der kürzesten Route zwischen zwei Orten/
Punkten
· Umgebungssuche: Was befindet sich in einem bestimmen Umkreis eines
Objekts
· Geomarketing:
Suche nach optimalem Standort für neue Geschäfte
· Stadtplanung:
Ausweisung neuer Baugebiete/Naturschutzgebiete/
Parkplätze
Aus dem Bereich Geomarketing könnte eine Anfrage an eine GIS-Datenbank z.B. wie
folgt aussehen:
Suche nach einem Standort bzw. Gebäude für ein Reisebüro. Dieses sollte nicht
mehr als 500 Meter von einem Bahnhof entfernt sein. Außerdem sollte sich im
Umkreis von 20 km ein Flughafen befinden.
2.1.1 GIS-Datenbanken
In einer zweidimensionalen GIS-Datenbank wird grundsätzlich zwischen drei Arten von
Geo-Objekten unterschieden:
· Punktobjekte
· Linienzüge
· Polygone
Grundlagen
6
Punktobjekte werden durch ihre x- und y-Koordinate beschrieben und stellen Objekte
dar, welche keine oder nur kleine Flächen enthalten (z.B. Straßenlampen). Ein Linien-
zug besteht aus einer Menge von Geraden und wird beispielsweise für Straßen oder
Flüsse benötigt. Die Geraden werden durch ihre Anfangs- und Endpunkte beschrieben.
Falls das geographische Objekt eine Fläche enthält, gehört es der dritten Kategorie, den
Polygonen an. Solche Polygone können auch Löcher enthalten. Polygone sind die
häufigsten Objekte in einer geographischen Datenbank, da viele Geo-Objekte eine Flä-
che haben. Hier sind Objekte wie Seen oder auch Gebäude zu finden. Polygone werden
in der Regel durch ihre Eckpunkte und die Eckpunkte ihrer Löcher beschrieben.
Neben den geometrischen Beschreibungen der Objekte werden weitere Informationen
wie der Objekttyp und die Bezeichnung (z.B. Straßennamen) in einer GIS-Datenbank
gespeichert. Diese zusätzlichen Informationen werden auch thematische Daten genannt.
2.1.2 Anfragen an Geoinformationssysteme
An eine GIS-Datenbank können verschiedene Abfragen gestellt werden. Drei grund-
legende Abfragen, welche auf gegebenen Koordinaten basieren, sind:
· Punktabfragen (Point Query)
· Bereichsabfragen (Region Query)
· Fensterabfrage (Window Query)
Bei Punktabfragen werden alle Objekte gesucht, in denen ein bestimmter Punkt P ent-
halten ist. Bei Bereichsabfragen wird nach allen Objekten gesucht, die ein bestimmtes
Gebiet überschneiden. Dieses Gebiet kann z.B. durch ein Polygon definiert sein. Stellt
das Suchgebiet ein achsenparalleles Rechteck dar, dann wird diese Bereichsabfrage
auch Window Query genannt. Ein Beispiel für diese Abfragen ist in Abbildung 2.1 zu
finden.
Abbildung 2.1: Auf gegebenen Koordinaten basierende Abfragen in GIS-Datenbanken
Point Query
Region Query
Window Query
Grundlagen
7
Neben diesen Abfragen, welche als Eingabe eine Koordinate oder eine Menge von Ko-
ordinaten erwarten, gibt es auch Abfragen, welche nach einer bestimmten Anordnung
der Objekte sucht. Folgende Abfragen werden hier häufig benutzt:
· Nearest Neighbor: Suche nach Objekte, die sich in der Nähe eines bestimmten
Objekts oder Punkts befinden
· Spatial Joins
1
: Suche nach zwei oder mehreren Objekten, die in bestimmter
Relation zueinander stehen (z.B. sich überschneiden)
Folgende Spatial Joins spielen dabei eine besondere Rolle:
o
Closest Pair Join: Suche nach zwei Objekten, bei denen der Abstand der
beiden Objekte untereinander am geringsten ist
o
Distance Join: Suche nach zwei Objekten, deren Abstand in einem vor-
gegebenen Bereich (gegeben als minimaler und maximaler Abstand)
liegt
Der Abstand von zwei Objekten ist dabei die kleinstmögliche Entfernung eines Punkts
aus dem ersten Objekt mit einem Punkt aus dem zweiten Objekt.
1
Statt Spatial Join findet in der Literatur auch dessen Übersetzung (räumlicher Join oder räumlicher
Verbund) Verwendung.
Grundlagen
8
2.1.3 Datenbankmanagementsysteme für räumliche Daten
Einige Hersteller von Datenbankmanagementsystemen (DBMS) bieten Erweiterungen
für die Verwaltung von räumlichen Daten an. Der Einsatz als geographische Informati-
onssysteme ist möglich. Folgende DBMS sind in der Praxis von GIS häufig anzutreffen:
· Oracle Spatial
· DB2 Spatial Extender
· Informix 2D-Spatial Datablade
Dabei sind Oracle Spatial und der DB2 Spatial Extender direkt in das DBMS integriert,
während das Informix 2D-Spatial Datablade auf einem erweiterbaren DBMS basiert
[Zie01]. Das DBMS von Informix ermöglicht generell eigene Erweiterungen des Daten-
bank-Kerns. Die darin enthaltenen Funktionen sind zum Teil noch nicht ganz ausgereift
[Zie01]. Dieses DBMS eignet sich besonders wenn ein direkter Zugriff auf die Ver-
waltung und Speicherung der geographischen Objekte benötigt wird.
Informix und der DB2 Spatial Extender unterstützen objektorientierte Datenhaltung
während Oracle Spatial als objektrelational einzustufen ist. Oracle Spatial und der DB2
Spatial Extender haben nach außen einen sehr ähnlichen Aufbau. Im nächsten Abschnitt
folgt eine Vorstellung und Bewertung von Oracle Spatial, da Oracle Spatial für die Um-
setzung dieser Arbeit Verwendung fand. Die Daten des Geoinformationssystems, wel-
ches in dieser Arbeit eingesetzt wird, liegen bereits in einer Oracle Spatial-Datenbank
vor und erlauben eine Verwendung ohne zusätzlichen Konvertierungsaufwand.
Grundlagen
9
2.2 Oracle Spatial
Oracle Spatial (kurz Spatial) ist ein Datenbank-Schema der Firma Oracle Corporation
[Ora03], mit dem zwei- oder höherdimensionale Objekte gespeichert und verwaltet
werden können. Hauptsächlich werden solche Datenbanken von GIS-Systemen verwen-
det, sie sind aber durchaus auch für andere Anwendungsgebiete wie z.B. CAD nützlich.
Spatial stellt neben den räumlichen Datentypen auch eine Indizierung dieser Daten mit
räumlichen Indexstrukturen (dem R-Baum oder QuadTree) zur Verfügung. Eine
Beschreibung von räumlichen Indexstrukturen ist in Kapitel 3 zu finden. Außerdem be-
inhaltet Spatial Funktionen und Operatoren, mit denen räumliche Abfragen unter Ver-
wendung der Indexstrukturen effizient bearbeitet werden. Diese Funktionen und Operat-
oren können als Erweiterung zu SQL eingesetzt werden.
In diesem Abschnitt wird Spatial kurz vorgestellt. Dabei wird erläutert, welche Daten-
typen für die Verwaltung von räumlichen Objekten verwendet werden. Außerdem wird
ein Überblick über die Operatoren und Funktionen von Spatial und deren Verwendung
für räumliche Joins gegeben. Danach wird untersucht, wie sehr sich Spatial für die Be-
arbeitung der in Kapitel 1.2 beschriebenen Problemstellung eignet.
2.2.1 Räumliche Objekte
Spatial unterstützt das objektrelationale Datenbankmodell. Soll ein räumliches Objekt,
wie z.B. ein durch x- und y-Koordinaten beschriebenes Gebäude, in die Datenbank ein-
gefügt werden, dann werden alle räumlichen Eigenschaften dieses Gebäudes in einem
Objekt vom Typ SDO_GEOMETRY abgelegt. Es ist eine Tabelle denkbar, in der eine
Spalte den Typ SDO_GEOMETRY hat und z.B. die Geometrie von Gebäuden be-
schreibt, während andere Spalten die ,,nicht räumlichen" Eigenschaften der Gebäude
(wie z.B. den Eigentümer) repräsentieren. Tabelle 2.1 zeigt eine mögliche Tabel-
lenstruktur mit den Feldnamen und Datentypen der Spalten
ID
Eigentümer
Anschrift
Kontur
NUMBER
VARCHAR2(40)
VARCHAR2(80)
SDO_GEOMETRY
Tabelle 2.1: Verwendung des Datentyps SDO_GEOMETRY in einer Tabellenstruktur
In Spatial können die in Abschnitt 2.1.1 aufgeführten zweidimensionalen Objektarten
(Punkte, Linienzüge und Polygone) genutzt werden. Linienzüge oder Polygone sind da-
bei durch die Koordinaten der Eckpunkte definiert, zwischen denen die Kanten verlau-
fen. Dabei können die Kanten aus Geraden, Kreisbögen oder aus einer Mischung von
Geraden und Kreisbögen bestehen. Polygone können ,,Löcher" haben, d.h. wenn sich
auf einem See eine Insel befindet, dann kann dies in dem Objekt, welches den See re-
präsentiert, berücksichtigt werden. Selbstschneidende Polygone sind in Spatial nicht
erlaubt.
Grundlagen
10
Zu jeder Tabelle die den abstrakten Datentyp SDO_GEOMETRY verwendet, werden in
einer weiteren Tabelle Metadaten gespeichert. Diese Tabelle heißt in Spatial
USERS_SDO_ GEOM_METADATA. Dort ist für jede Tabelle, welche räumliche Da-
ten enthält, ein Datensatz vorhanden. In einem solchen Datensatz werden unter anderem
die Namen der Dimensionen (z.B. 'x' und 'y') und der kleinst-/größtmöglichste Wert
der Dimension erfasst. Außerdem steht in der Tabelle eine ID, die beschreibt zu wel-
chem Koordinatensystem die Objekte gehören. Falls diese ID bei zwei Tabellen gleich
ist, dann benützen sie die gleiche Maßeinheit (z.B. Meter) und haben den Nullpunkt an
der selben Stelle. In diesem Fall ist ein Vergleich deren Inhalte sinnvoll möglich.
2.2.2 Abfragen
Zur Indizierung der räumlichen Daten kann der Anwender zwischen den
Indexstrukturen R-Baum und QuadTree wählen. Um einen räumlichen Index zu einer
Tabelle zu erstellen, müssen zuvor die Metadaten dieser Tabelle gespeichert werden.
Die Indexstrukturen werden von Spatial verwendet, um die Ausführung von Abfragen
zu beschleunigen. Eine ausführliche Beschreibung dieser räumlichen Indexstrukturen ist
in Kapitel 3 zu finden.
Spatial stellt mehrere Operatoren für Abfragen oder Veränderungen der räumlichen
Daten zur Verfügung. Diese können in SQL-Statements eingesetzt werden. Eine
mögliche Anfrage ist die Fensteranfrage. Mit ihr wird nach allen Objekten gesucht, die
sich in einem vorgegebenen Rechteck befinden (siehe Abschnitt 2.1.2). Solche An-
fragen werden mit dem Operator SDO_RELATE beantwortet. Beim Ausführen der An-
frage werden zwei Schritten abgearbeitet:
· Primärfilter
· Sekundärfilter
Im Primärfilter werden nur die kleinsten umschließende Rechtecke (minimum bounding
rectangle, MBR) der Objekte/Anfrage betrachtet. Falls sich die MBRs überschneiden
liefert der Primärfilter diese Objekte zurück. Die Überprüfung, ob sich diese Objekte
tatsächlich überschneiden, wird vom Sekundärfilter durchgeführt. Der Primärfilter
liefert also Kandidaten für Überschneidungen, während der Sekundärfilter die genaue
Geometrie der Objekte betrachtet und daraus das exakte Ergebnis berechnet. Der
Primärfilter führt eine Grobfilterung durch in welcher relativ schnell viele Objekte
ausgeschlossen werden können. Indexstrukturen wie der R-Baum werden nur beim
Primärfilter eingesetzt.
In Abbildung 2.2 ist ein Beispieldatensatz mit vier räumlichen Objekten (a,b,c und d)
und den dazugehörigen kleinsten umschließenden Rechtecken (MBR's) dargestellt. Eine
Fensteranfrage wird durch das gestrichelte Rechteck symbolisiert. Der Primärfilter
liefert bei dieser Abfrage die Kandidatenobjekte a und c zurück. Der Sekundärfilter
vergleicht diese beiden Objekte mit dem Anfragefenster und liefert als Ergebnis das
Objekt c. Neben dem Operator SDO_RELATE, welcher sowohl den Primär- als auch
den Sekundärfilter ausführt, gibt es auch noch den Operator SDO_FILTER. Bei
Grundlagen
11
SDO_FILTER werden die Daten nur mit dem Primärfilter bearbeitet. Er ermittelt also
nur die potentiellen Kandidaten, für eine Überschneidung mit dem Anfragefenster.
Mit Hilfe des SDO_RELATE- bzw. SDO_FILTER-Operator kann nicht nur ein
Datensatz mit einem Anfragefenster verglichen werden, sondern auch zwei Datensätze
untereinander. Es kann also überprüft werden, welche Objekte aus einer Tabelle, sich
mit Objekten aus einer anderen Tabelle überschneiden. Somit kann dieser Operator
einen räumlichen Join (Spatial Join) für Überschneidungen ausführen.
Um Nearest Neighbor-Anfragen bearbeiten zu können, gibt es einen Operator
SDO_NN, welcher die n Objekte ermittelt, deren Abstand zu einem vorgegebenen Ob-
jekt oder Punkt am geringsten ist. Diesem Operator wird eine Tabellenspalte (mit den
räumlichen Objekten) und ein Referenzpunkt/-objekt übergeben. Des Weiteren muss
festgelegt werden, wie viele Objekte von diesem Operator zurückgeliefert werden
sollen.
Mit dem Operator SDO_WITHIN_DISTANCE können alle Objekte ermittelt werden,
deren Abstand zu einem Punkt oder Referenzobjekt kleiner oder gleich einem vorgege-
benen Wert ist. Wenn z.B. nach allen Objekten einer Tabelle gesucht wird, die sich im
Umkreis von 10 Längeneinheiten vom Punkt P(100,100) befinden, dann kann nach
dieser Eigenschaft mit dem Operator SDO_WITHIN_DISTANCE gesucht werden.
2.2.3 Spatial Joins
Spatial Joins, d.h. Anfragen, bei denen in zwei oder mehreren Tabellen nach Paaren von
Datensätzen gesucht werden, die in einer bestimmten Relation zueinander stehen sind
mit den Operatoren SDO_NN und SDO_WITHIN_DISTANCE gar nicht bzw. nur sehr
eingeschränkt möglich. Ein Spatial Join, in Verbindung mit einer Nearest Neighbor-
Operator würde nach Paaren von Datensätzen suchen, deren Abstand zueinander am
geringsten ist, also eine Closest-Pair-Analyse durchführen. Diese Abfrage kann mit
SDO_NN nicht durchgeführt werden.
Abbildung 2.2: Fensterabfrage
a
b
c
d
Grundlagen
12
Für die Ausführung von Spatial Joins stellt die Datenbank von Oracle Corporation seit
der Version 10g den Operator SDO_JOIN zur Verfügung. Mit diesem Operator kann
neben der Suche nach Überschneidungen von zwei Objektmengen, wie sie mit dem
Operator SDO_RELATE durchgeführt werden können, auch nach anderen topologisch-
en Beziehungen zweier Objekte gesucht werden. Abbildung 2.3 zeigt, welche topolo-
gischen Beziehungen es zwischen zwei Objekten geben kann.
Die Umhüllung unter-
scheidet sich von der Überdeckung darin, dass die Ränder der Objekte sich überdecken
.
Nach den in der Abbildung gezeigten Beziehungen kann durch die Verwendung des
SDO_JOIN-Operators gesucht werden. Außerdem sind logische Kombinationen aus den
Beziehungen möglich (z.B. A überschneidet oder berührt B).
SDO_JOIN ist eine Tabellenfunktion, d.h. eine Funktion, die als Rückgabewert eine Ta-
belle hat. In dieser Tabelle sind alle Join-Resultate enthalten. Da die Anwendung dieser
Tabellenfunktion der Anwendung von Operatoren gleicht, kann SDO_JOIN durchaus
auch als Operator betrachtet werden. Zur Veranschaulichung des SDO_JOIN-Operators
ein SQL-Beispiel, in dem nach Objektpaaren gesucht wird, welche sich berühren:
SELECT tab1.ID, tab2.ID
FROM tab1, tab2,
TABLE(SDO_JOIN(`tab1', `geom', `tab2', `geom',
`mask=TOUCH')) tabjoin
WHERE tab1.rowid=tabjoin.rowid1 AND
tab2.rowid=tabjoin.rowid2;
Die Tabellen tab1 und tab2 bestehen (mindestens) aus den Spalten ID und geom, wobei
geom ein geometrisches Objekt vom Typ SDO_GEOMETRY sein muss. SDO_JOIN
werden als Aufrufparameter der Name und die zu betrachtende Spalte der ersten Tabelle
Abbildung 2.3: Beziehungen zwischen zwei Flächen
A überschneidet B
A berührt B
A entspricht B
A überdeckt B
A umhüllt B
A ist disjunkt zu B
B ist überdeckt von A
B ist umhüllt von A
A
B
A B
A
B
A
B
A
B
A
B
Grundlagen
13
(' tab1' , ' geom' ) und der zweiten Tabelle übergeben. Des Weiteren wird die Art der
Beziehung zwischen den Tabellen angegeben, nach der gesucht werden soll
(' mask=TOUCH' ). Die Ausführung von SDO_JOIN liefert die Tabelle tabjoin zurück.
Zu jeder Tabelle, die in einer Oracle-Datenbank vorkommt, gibt es eine versteckte
Spalte mit dem Namen rowid. Diese Spalte enthält eine Zahl, welche für jeden Daten-
satz eindeutig ist. Sie ist somit eine Art interner, versteckter Primärschlüssel. In der
Tabelle tabjoin wird mit Hilfe dieses Feldes auf die beiden Ausgangstabellen verwiesen.
Um sicherzustellen, dass nur die Datensatzpaare ausgegeben werden, die in der Join-
Tabelle tabjoin ermittelt wurden, müssen die rowid' s der Tabellen tab1 und tab2 mit
denen der Tabelle tabjoin in der Where-Klausel verglichen werden.
Neben den in der obigen Abbildung aufgeführten Beziehungen von Objekten kann mit
SDO_JOIN auch nach Objektpaaren gesucht werden, deren Abstand kleiner als ein vor-
gegebener Wert ist. Ein Beispiel für eine solche Abfrage ist die Suche nach Paaren von
Bahnhöfen und Seen, deren Abstand weniger als 300 Meter beträgt. Somit kann mit die-
sem Operator auch ein Distance Join durchgeführt werden. Allerdings wird in diesem
Distance Join nur nach Paaren von Objekten gesucht, deren Abstand kleiner als ein vor-
gegebener Wert ist. Die Angabe einer Mindest-Entfernung der Objektpaare ist mit die-
sem Operator nicht direkt möglich. Es kann mit diesem Operator allein beispielsweise
nicht nach Paaren von Objekten gesucht werden, deren Abstand zwischen 290 und 310
Metern beträgt. Um diesen Distance Join dennoch ausführen zu können geht man fol-
genderweise vor:
1. Man ermittelt mit dem SDO_JOIN-Operator alle Objektpaare, deren Abstand
geringer als 310 Meter ist
2. Man berechnet bei diesen Objektpaaren den jeweiligen Abstand und
berücksichtigt nur die Paare, bei denen der Abstand mehr als 290 Meter beträgt
Man könnte alternativ zu diesem Verfahren auch nach allen Objektpaaren suchen, deren
Abstand weniger als 310 Meter beträgt. Danach werden alle Objektpaare ermitteln, bei
denen die Entfernung der Objekte weniger als 290 Meter beträgt und aus diesen beiden
Mengen die Differenzmenge bilden. Jedoch ist dieses Verfahren in den meisten Fällen
aufwendiger als das oben aufgeführte.
Um den zweiten Schritt des Distance Joins auszuführen, muss der Abstand eines
Objektpaars (also der Abstand zweier Objekte) ermittelt werden. Diese kann unter der
Verwendung einer Spatial-Funktion berechnet werden. Im folgenden Abschnitt wird
eine Übersicht über die Funktionen von Spatial gegeben.
2.2.4 Funktionen
In Spatial gibt es verschiedene Funktionen, mit denen bestimmte Eigenschaften von
räumlichen (geometrischen) Objekten oder Objektpaaren berechnet werden können. Um
einen groben Überblick über diese Funktionen zu erhalten, werden im Folgenden einige
Beispiele gegeben, welche Informationen mit Spatial-Funktionen berechnet werden
können:
Grundlagen
14
· Funktionen für ein einzelnes Objekt: berechnen des
o
Flächeninhalts
o
Mittelpunkt eines Polygons
o
Kleinste umschließende Rechteck (MBR)
o
Umfangs
· Funktionen für mehrere Objekte
o
berechnen des Abstand zweier Objekte
o
Mengenoperationen (Berechnung von Vereinigung, Schnittmenge, ...)
Grundlagen
15
2.2.5 Bewertung
In diesem Abschnitt wird die Eignung von Spatial für die Ausführung von skizzenba-
sierten Anfragen untersucht. Die Speicherung geographischer Daten lässt sich in Spatial
sehr gut durchführen. Dabei wird für jedes Objekt (z.B. Haus) ein Datensatz angelegt.
In diesem Datensatz existiert eine Spalte vom Typ SDO_GEOMETRY, in welcher die
geographischen Eigenschaften dieses Objekts (wie z.B. die Koordinaten) abgelegt sind.
Die thematischen Daten, wie beispielsweise die Bezeichnung oder Anschrift dieses
Objekts werden in den weiteren Tabellen-Spalten gespeichert. Deshalb ist Spatial für
die Speicherung eines Geoinformationssystems geeignet.
Da Geoinformationssysteme in der Regel aus sehr großen Datenmengen bestehen und
oft in anderen Formaten vorliegen, kann die Migration
2
der Daten durch SQL-Befehle
aufwendig werden. Mit dem SQL*Loader [Ora03b] der Firma Oracle Corporation las-
sen sich diese aus ASCII-Dateien auslesen und in Tabellen ablegen. Das Format der
ASCII-Dateien kann dabei vom Benutzer definiert werden.
Die Generierung einer Abfrage wird am Beispiel folgender Skizze (Abbildung 2.4)
untersucht. In dieser Skizze sind alle wesentlichen wichtigen Elemente, welche bei einer
Abfrage berücksichtigt werden könnten, enthalten. Eine Beschreibung, woraus eine für
diese Arbeit relevante Skizze bestehen kann, findet sich in Abschnitt 2.3. Es wird im
Weiteren davon ausgegangen, dass für jede Objektkategorie (Gebäude, Straßen, Flüsse,
etc.) eine eigene Tabelle in der Datenbank vorhanden ist.
2
Unter Migration im Zusammenhang mit Datenbanken versteht man die Übertragung der Daten von
einem Informationssystem in ein anderes.
Abbildung 2.4: Beispiel-Skizze für die Untersuchung von
Spatial
Grundlagen
16
In der Skizze ist folgendes dargestellt: Es wird nach einem Parkplatz gesucht, der sich
in der Nähe eines Bahnhofs befindet. 50 und 100 Meter vom Bahnhof entfernt befindet
sich jeweils ein Baum. Die beiden Bäume sollen sich im 90°-Winkel zueinander stehen,
d.h. wenn sich der eine Baum im Westen des Bahnhofs befindet, dann muss der andere
im Süden oder Norden des Bahnhofs liegen. Die Skizze besteht also aus vier Geo-
Objekten und drei Beziehungen (Topologien):
Geo-Objekte
Topologien mit Metrik
· Parkplatz
· Bahnhof
· 1.Baum
· 2.Baum
· Parkplatz ist neben Bahnhof
· 1.Baum ist 50 m und Winkel von
Bahnhof entfernt (
kann beliebig
gewählt werden)
· 2.Baum ist 100 m und Winkel ± 90°
von Bahnhof entfernt
Tabelle 2.2: Geo-Objekte und Topologien der Beispiel-Skizze
In Spatial kann die gesamte Anfrage nicht auf einmal ausgeführt werden. Sie muss
deshalb in mehrere Teilabfragen zerlegt werden. Da davon ausgegangen wird, dass für
jede Objektart (Parkplätze, Bäume, Gebäude oder Bahnhöfe) eine eigene Tabelle exis-
tiert, muss nur noch nach den topologischen Beziehungen dieser Objekte gesucht wer-
den.
Es bietet sich in Spatial an, für jede Topologie eine Abfrage auszuführen. Das Ergebnis
dieser Abfrage wird in einer Tabelle zwischengespeichert und für die folgenden Topolo-
gien weiterverwendet. Wird z.B. nach der Beziehung ,, Parkplatz neben Bahnhof" ge-
sucht, dann wird mit Hilfe des SDO_JOIN-Operators eine Tabelle erzeugt, die Paare
von Parkplätzen und Bahnhöfen enthält, für welche diese Beziehung erfüllt ist. Aus
dieser Tabelle und der Tabelle mit den Bäumen wird eine weitere Tabelle erzeugt, in
der die zweite Topologie erfüllt ist, usw.
Wie in Abschnitt 2.2.3 erwähnt, kann mit dem SDO_JOIN-Operator nicht in einem
Schritt nach Objektpaare mit einer vorgegebenen Entfernung von z.B. 50 Metern ge-
sucht werden. Es müssen also zuerst alle Objektpaare ermittelt werden, deren Abstand
kleiner oder gleich 50 Meter ist. Danach müssen im zweiten Schritt die Paare, die zu
nahe beieinander liegen entfernt werden. Falls große Entfernungen angegeben werden,
liefert der erste Schritt viele Ergebnisse, von denen die meisten im zweiten Schritt
wieder entfernt werden müssen. Diese Vorgehensweise, welche nicht umgangen werden
kann, wirkt sich dann negativ auf die Performance aus.
Auch Winkelbeziehungen, wie sie im Beispiel zwischen den beiden Bäumen und dem
Bahnhof bestehen können nicht direkt mit Spatial abgefragt werden. Jedoch lassen sich
diese durch eine zusätzliche Entfernungs-Beziehung realisieren: Wenn die Bäume und
der Bahnhof wie in der Skizze angeordnet sind, dann ergibt sich aus der Trigonometrie,
dass der Abstand zwischen den Bäumen
m
m
m
112
)
100
(
)
50
(
2
2
+
beträgt. Es muss
Ende der Leseprobe aus 96 Seiten
- nach oben
Details
- Arbeit zitieren
- , 2004, Konzeption und Implementierung eines Verfahrens für effiziente, nicht präzise Datenbankabfragen im Kontext eines skizzenbasierten GIS, Hamburg, Bedey Media GmbH, https://www.diplom.de/document/219700
Ähnliche Arbeiten
Deutschlands größter Sharing Community
Jetzt Zusammenfassungen, Skripte und Klausuren kostenlos downloaden!
Uniturm.de
Ihre Vorteile als Autor
Geld verdienen Für jedes verkaufte Exemplar erhalten Sie Autorenhonorar - bis zu 40%.Kostenlose Buchveröffentlichung
Als eBook-Studie im Original und / oder auf Wunsch zusätzlich als hochwertiges Fachbuch in unserem renommierten Buchverlag.
Renommee als Fachbuchautor
Präsentieren Sie sich als Fachfrau oder Fachmann in Ihrem Fachgebiet und machen Sie sich bekannt.
Persönliche Betreuung
Unser Lektorat wird Sie persönlich betreuen und ist auch telefonisch unter 040-655992-14 erreichbar.
Weltweit im Buchhandel
Ihr Buch ist weltweit im Buchhandel und Online-Buchhandel wie z.B. amazon erhältlich.
Jetzt Autor werden!
Kommentare