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

Skizzen werden angefertigt, um mit sich selbst oder mit anderen zu kommunizieren. Häufig werden in Skizzen Karten gezeichnet [Tve02]. Solche Skizzen können mit einer Sprache verglichen werden. Sie bestehen aus mehreren Elementen (Objekte bzw. Worte), welche abhängig von ihrer Anordnung verschiedene Interpretationen zulassen. Architekten benutzen Skizzen, um aus einer kleinen Menge von Objekten große, komplexe Strukturen aufzubauen. In SketchQuery besteht eine Skizze aus einer Mengen von Linien und Punkten. Dabei werden mehrere Linien zu Objekten gruppiert. Häuser, Bäume und Straßen sind Beispiele für solche Objekte. Neben der Erkennung der Objekte, werden auch die topologischen Beziehungen der Objekte untereinander erkannt. Der Benutzer kann außer den Skizzenelementen, welche geographische Objekte repräsentieren, auch Meta-Informationen in der Skizze unterbringen. In SketchQuery gibt es zwei Arten von Metainformationen: • • Handschrift Richtungs-/Entfernungsangaben [...]

Grundlagen also zusätzlich neben den drei oben erwähnten Topologien noch eine weitere Beziehung berücksichtigt werden, in welcher die beiden Bäume 112 Meter voneinander entfernt sind. In einer Skizze kann auch eine Himmelsrichtung vorgegeben werden. Nach dieser Himmelsrichtung richtet sich die Anordnung der Objekte. Auch diese kann nicht direkt in die Abfrage eingebaut werden und muss für jeden gefundenen Ergebnis-Datensatz einzeln berechnet und überprüft werden. Dies ist etwas aufwendiger. Eine Bewertung der Algorithmen, welche Spatial für die Suche nach topologischen Beziehungen verwendet, findet sich in Kapitel 3.3. Sehr gut lässt sich mit Spatial nach anderen Beziehungen suchen, die nicht auf Entfernungen oder der „ in der Nähe von“ -Beziehung basieren. Es kann z.B. nach Überschneidungen der Objektgrenzen oder Enthaltensein gesucht werden. Die von Spatial unterstützten Beziehungen wurden in Abbildung 2.3 dargestellt. Auch dafür gibt es praktische Abfragen wie beispielsweise die Suche nach Gebäuden, welche sich in einem Wald befinden oder die Suche nach Straßen, die sich mit Flüssen kreuzen. In einer Skizze kann die Bezeichnung eines Objekts, wie z.B. der Name einer Straße vorgegeben werden. Da ein Datensatz immer aus den thematischen Daten und den dazugehörigen Koordinaten besteht, können solche Objekte problemlos in der Datenbank identifiziert werden. Da bei einer vorgegeben Entfernung von z.B. 100 Metern, i.d.R. keine Objektpaare gefunden werden, deren Abstand exakt 100 Meter beträgt, muss in den Abfragen eine Toleranz verwendet werden. Dadurch gibt es Ergebnisse mit unterschiedlicher Qualität. Um die Genauigkeit eines gefundenen Ergebnisses bewerten zu können muss u.a. die Entfernung zweier Objekt ermittelt werden. Des Weiteren kann es für die Darstellung, oder für weitere Berechungen wichtig sein, wo sich der Mittelpunkt eines Objekts befindet, oder welche Fläche ein Objekt beinhaltet. Diese Aufgaben lassen sich alle durch die in Abschnitt 2.2.4 erwähnten Funktion erledigen, wodurch keine zusätzliche Implementierung dieser Berechungsfunktionen erforderlich ist. Die Vorteile und Probleme von Spatial für die Beantwortung skizzenbasierter Anfragen werden in Tabelle 2.1 zusammengefasst. Insgesamt lässt sich feststellen, dass Spatial für die in dieser Arbeit geforderten Anfragen gut geeignet ist. Die Effizienz könnte in einigen Fällen zwar noch gesteigert werden, ist aber trotzdem zufrieden stellend und kann deshalb im Rahmen dieser Arbeit berücksichtigt werden. Eine eigene, zeitaufwendige Implementierung der Algorithmen zur Anfrage-Beantwortung ist deshalb nicht erforderlich. [...]

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 existiert, muss nur noch nach den topologischen Beziehungen dieser Objekte gesucht werden. 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 Topologien weiterverwendet. Wird z.B. nach der Beziehung „ Parkplatz neben Bahnhof“ gesucht, 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 gesucht 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 [...]