Konzeption und Implementierung eines Verfahrens für effiziente, nicht präzise Datenbankabfragen im Kontext eines skizzenbasierten GIS

Dangelmayer, Frank

Titel: Konzeption und Implementierung eines Verfahrens für effiziente, nicht präzise Datenbankabfragen im Kontext eines skizzenbasierten GIS

Konzeption und Implementierung eines Verfahrens für effiziente, nicht präzise Datenbankabfragen im Kontext eines skizzenbasierten GIS

Zusammenfassung

Inhaltsangabe:Einleitung:
Anfragen an eine geographische Datenbank müssen häufig in Textform wie z.B. in SQL formuliert werden. Räumliche Gegebenheiten lassen sich jedoch nur schwer auf diese Weise beschreiben. Diese können durch visuelle Spezifikationen leichter beschrieben werden. Dennoch fand die Generierung von Anfragen aus Skizzen bisher wenig Beachtung.
Diese Arbeit beschäftigt sich mit der Konzeption und Umsetzung eines Systems zur Generierung von Anfragen an geographische Datenbanken aus analysierten Skizzen. Eine Skizze besteht dabei aus mehreren geographischen Objekten (z.B. Häuser, Bushaltestellen, Straßen, etc.), zwischen welchen verschiedene Beziehungen existieren (z.B. Haus ist 50 Meter entfernt von einer Straße). Nach dieser Objektanordnung wird in einer geographischen Datenbank gesucht.
Um die Anfrage effizient ausführen zu können, sind spezielle räumliche Indexstrukturen und Suchalgorithmen erforderlich. Oracle Spatial ist ein im Rahmen dieser Arbeit untersuchtes Datenbankschema, welches räumliche Objekte abspeichert und Anfragen mit Hilfe von R-Bäumen beantworten kann. Das System und die neu entwickelten Verfahren bauen auf einer solchen Datenbank auf.
Das in dieser Arbeit entwickelte System erhält die analysierten Skizzen-Daten von einem Programm mit dem Namen SketchQuery. Aus diesen Daten wird die Anfrage an eine Oracle Spatial-Datenbank generiert. Anschließend findet eine Bewertung der Ergebnisse bezügliche ihrer Ähnlichkeit zur Skizze statt. Dabei wird auf die geometrische Ähnlichkeit z.B. von Straßenverläufen verglichen. Nach der Ermittlung der Abweichungen von der Skizze erfolgt eine Aufbereitung der Ergebnisse zur Darstellung und eine Zurückgabe an SketchQuery.
Insgesamt wurden vier Module entworfen und umgesetzt. Zwei Module zur Entgegennahme/Zurückgabe der Daten von/zu SketchQurey. Ein Modul zur Generierung und Ausführung der Datenbankanfrage und ein Modul zur Berechnung der Abweichungen von der Skizze.

Inhaltsverzeichnis:Inhaltsverzeichnis:

1.Einleitung1
1.1Motivation1
1.2Problemstellung4
1.3Übersicht4
2.Grundlagen5
2.1Geographische Informationssysteme5
2.1.1GIS-Datenbanken5
2.1.2Anfragen an Geoinformationssysteme6
2.1.3Datenbankmanagementsysteme für räumliche Daten8
2.2Oracle Spatial9
2.2.1Räumliche Objekte9
2.2.2Abfragen10
2.2.3Spatial Joins11
2.2.4Funktionen13
2.2.5Bewertung15
2.3SketchQuery - Ein Programm für skizzenbasierte GIS-Anfragen19
2.3.1Übersicht19
2.3.2Skizzen in […]

Leseprobe

Inhaltsverzeichnis

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

Motivation

1.2

Problemstellung

1.3

Übersicht

2 Grundlagen

2.1

Geographische Informationssysteme

2.1.1

GIS-Datenbanken

2.1.2

Anfragen an Geoinformationssysteme

2.1.3

Datenbankmanagementsysteme für räumliche Daten

2.2

Oracle Spatial

2.2.1

Räumliche Objekte

2.2.2

Abfragen

2.2.3

Spatial Joins

2.2.4

Funktionen

2.2.5

Bewertung

2.3

SketchQuery Ein Programm für skizzenbasierte GIS-Anfragen

2.3.1

Übersicht

2.3.2

Skizzen in SketchQuery

2.3.3

Benutzerschnittstelle

2.3.4

Schnittstelle für Datenbankabfragen

3 Räumliche Datenstrukturen und Algorithmen

3.1

Indexstrukturen zur Verwaltung räumlicher Objekte

3.1.1

Grid File

3.1.2

QuadTree

3.1.3

R-Baum

3.1.4

-Baum

3.1.5

-Baum

3.1.6

Bewertung

3.2

Spatial Join-Algorithmen beim R-Baum

3.2.1

Algorithmen ohne Indexstrukturen

3.2.2

Index nested loops join

3.2.3

Paralleles Durchlaufen zweier R-Bäume

3.2.4

Distance Join-Algorithmus

3.2.5

Seeded Tree

3.2.6

Zusammenfassung und Bewertung

3.3

Einsatz in Oracle Spatial

4 Entwurf

4.1

Stand der Technik

4.2

Anforderungen

4.2.1

Verschiedene Anfrageformen

4.2.2

Fehlerbewertung

4.2.3

Effizienz

4.3

Architektur

4.4

Module des Systems

4.4.1

Übernahme der Daten von SketchQuery

4.4.2

Umwandlung und Ausführung der Anfrage

4.4.3

Abweichungen von der Eingabe-Skizze

4.4.4

Darstellung der Ergebnisse

4.5

Ablauf

5 Implementierung

5.1

Rahmenbedingungen

5.1.1

Datensätze für die Erprobung des Verfahrens

5.2

Übernahme der Daten von SketchQuery

5.3

Umwandlung und Ausführung der Anfrage

5.3.1

Ablauf

5.3.2

Datenmodell für die Ergebnisse

5.3.3

Klasse für die Datenbankanbindung

5.3.4

Reihenfolge der Spatial Joins

5.3.5

Konfigurationsdatei

5.4

Abweichungen von der Eingabe-Skizze

5.4.1

Ermittlung der geometrischen Ähnlichkeit

5.5

Darstellung der Ergebnisse

5.6

Erweiterbarkeit

6 Bewertung und Ausblick

6.1

Ergebnisse

6.2

Bewertung

6.3

Ausblick

6.3.1

Kommunikation mit SketchQuery

6.3.2

Einsatz eigener Indexstrukturen und Join-Algorithmen

6.3.3

Indexstrukturen für die Fourier-Koeffizienten

7 Zusammenfassung

Anhang A - Algorithmus zur Fourier-basierten Ähnlichkeitssuche

Index

Abbildungsverzeichnis

Literaturverzeichnis

Einleitung

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

· 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

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

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

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

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

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

: Suche nach zwei oder mehreren Objekten, die in bestimmter

Relation zueinander stehen (z.B. sich überschneiden)

Folgende Spatial Joins spielen dabei eine besondere Rolle:

Closest Pair Join: Suche nach zwei Objekten, bei denen der Abstand der

beiden Objekte untereinander am geringsten ist

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.

Statt Spatial Join findet in der Literatur auch dessen Übersetzung (räumlicher Join oder räumlicher

Verbund) Verwendung.

Grundlagen

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

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

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

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

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

Grundlagen

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

Grundlagen

(' 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

· Funktionen für ein einzelnes Objekt: berechnen des

Flächeninhalts

Mittelpunkt eines Polygons

Kleinste umschließende Rechteck (MBR)

Umfangs

· Funktionen für mehrere Objekte

berechnen des Abstand zweier Objekte

Mengenoperationen (Berechnung von Vereinigung, Schnittmenge, ...)

Grundlagen

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

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.

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

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

112

)

100

(

)

(

beträgt. Es muss

Details

Seiten
Erscheinungsform: Originalausgabe
Jahr: 2004
ISBN (eBook): 9783832440718
ISBN (Paperback): 9783838640716
DOI: 10.3239/9783832440718
Dateigröße: 1.8 MB
Sprache: Deutsch
Institution / Hochschule: Hochschule Ravensburg-Weingarten – angewandte Informatik
Erscheinungsdatum: 2005 (Februar)
Note: 1,0
Schlagworte: r-baum spatial join oracle topologie softwareentwurf

Autor

Frank Dangelmayer (Autor:in)

Konzeption und Implementierung eines Verfahrens für effiziente, nicht präzise Datenbankabfragen im Kontext eines skizzenbasierten GIS

Zusammenfassung

Leseprobe

Inhaltsverzeichnis

Details

Autor

Frank Dangelmayer (Autor:in)