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

Diplomarbeit aus dem Jahr 2004 im Fachbereich Informatik - Angewandte Informatik, Note: 1,0, Hochschule Ravensburg-Weingarten (angewandte Informatik), Sprache: Deutsch, Abstract: 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 SketchQuery20
2.3.3Benutzerschnittstelle22
2.3.4Schnittstelle für Datenbankabfragen24
3.Räumliche Datenstrukturen und Algorithmen25
3.1Indexstrukturen zur Verwaltung räumlicher Objekte25
3.1.1Grid File26
3.1.2QuadTree27
3.1.3R-Baum29
3.1.4R+-Baum32
3.1.5R -Baum33
3.1.6Bewertung34
3.2Spatial Join-Algorithmen beim R-Baum36
3.2.1Algorithmen ohne Indexstrukturen36
3.2.2Index nested loops join37
3.2.3Paralleles Durchlaufen zweier R-Bäume37
3.2.4Distance Join-Algorithmus39
3.2.5Seeded Tree40
3.2.6Zusammenfassung und Bewertung41
3.3Einsatz in Oracle Spatial42
4.Entwurf43
4.1Stand der Technik43
4.2Anforderungen44
4.2.1Verschiedene Anfrageformen44
4.2.2Fehlerbewertung44
4.2.3Effizienz45
4.3Architektur46
4.4Module des Systems48
4.4.1Übernahme der Daten von SketchQuery48
4.4.2Umwandlung und Ausführung der Anfrage48
4.4.3Abweichungen von der Eingabe-Skizze49
4.4.4Darstellung der Ergebnisse50
4.5Ablauf52
5.Implementierung53
5.1Rahmenbedingungen53
5.1.1Datensätze fü...

Klappentext

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