Einsatz von NoSQL-Datenbanksystemen fr G ? 1 Einfhrung in die Welt der NoSQL-Datenbanken 2 ...

  • Published on
    17-Sep-2018

  • View
    212

  • Download
    0

Transcript

  • Hochschule fr Technik und Wirtschaft Dresden

    Fakultt Geoinformation

    Bachelorstudiengang Geoinformation und Vermessungswesen

    Bachelorarbeit

    Einsatz von NoSQL-Datenbanksystemen fr Geodaten

    Eingereicht von

    Benjamin Thurm

    Seminargruppe: 08/061/61

    Matrikelnummer: 27021

    1. Gutachter: Prof. Dr.-Ing. F. Schwarzbach

    2. Gutachter: Prof. Dr. oec. G. Grfe

    Eingereicht am: 23.02.2012

  • Inhaltsverzeichnis II

    Inhaltsverzeichnis

    Inhaltsverzeichnis ....................................................................................................... II

    Einleitung ..................................................................................................................... 1

    1 Einfhrung in die Welt der NoSQL-Datenbanken ........................................... 2

    1.1 Historischer Abriss ............................................................................................. 2

    1.2 NoSQL ............................................................................................................. 3

    1.3 Scaling Up/Out ................................................................................................... 4

    1.4 CAP-Theorem .................................................................................................... 4

    1.5 ACID & BASE ..................................................................................................... 5

    1.6 MapReduce ........................................................................................................ 6

    1.7 Schemalosigkeit von Daten ................................................................................ 7

    2 Allgemeiner berblick ...................................................................................... 8

    2.1 Kategorisierung .................................................................................................. 8

    2.2 Key/Value Stores ................................................................................................ 8

    2.2.1 Datenhaltung ...................................................................................................... 9

    2.2.2 Redis .................................................................................................................. 9

    2.2.3 Spatial Extension .............................................................................................. 10

    2.3 Wide Column Stores ........................................................................................ 10

    2.3.1 Datenhaltung .................................................................................................... 11

    2.3.2 Apache Cassandra ........................................................................................... 12

    2.3.3 Spatial Extensions ............................................................................................ 13

    2.4 Document Stores .............................................................................................. 13

    2.4.1 Datenhaltung .................................................................................................... 14

    2.4.2 CouchDB .......................................................................................................... 14

    2.4.3 Spatial Extensions ............................................................................................ 15

    2.5 Graphdatenbanken ........................................................................................... 16

    2.5.1 Datenhaltung .................................................................................................... 17

    2.5.2 Neo4j ................................................................................................................ 19

    2.5.3 Spatial Extensions ............................................................................................ 19

    3 Anwendungspotential fr Geodaten ............................................................. 21

    3.1 Definition Geodaten .......................................................................................... 21

    3.2 Die Haltung von Geodaten in SQL-Datenbanken ............................................. 22

    3.3 Skalierbarkeit vs. Komplexitt ........................................................................... 23

    3.4 Positionsdaten in NoSQL-Datenbanksystemen ................................................ 24

    3.5 Komplexe Geodaten in NoSQL-Datenbanksystemen ....................................... 26

    3.6 Rasterdaten ...................................................................................................... 30

    3.7 Zuknftige Entwicklungen ................................................................................. 30

  • Inhaltsverzeichnis III

    4 Implementierung einer Webprsenz fr Geodaten mit CouchDB und GeoCouch ....................................................................................................... 32

    4.1 Vorbereitung der Daten fr CouchDB ............................................................... 33

    4.2 Abfrage der Datenstze aus CouchDB ............................................................. 34

    4.3 Abfrage von Datenstzen als FeatureCollection ............................................... 36

    4.4 Integration der GeoCouch-Daten in eine Website ............................................. 37

    4.5 Fazit ................................................................................................................. 39

    5 Navigationsanwendung mit Neo4j Spatial .................................................... 41

    5.1 Vorbereitungen ................................................................................................. 41

    5.2 Datengrundlage ................................................................................................ 42

    5.3 Auffinden des nchsten Knoten zu einer beliebigen Koordinate ....................... 44

    5.4 Berechnung des krzesten, befahrbaren Weges .............................................. 46

    5.5 Ergebnis ........................................................................................................... 47

    5.6 Fazit ................................................................................................................. 48

    6 Zusammenfassung und Ausblick .................................................................. 50

    Literaturverzeichnis .................................................................................................. VI

    Abbildungsverzeichnis .............................................................................................. X

    Tabellenverzeichnis ................................................................................................... X

    Anlagenverzeichnis ................................................................................................... XI

    Anhang 1 .................................................................................................................. XIII

    Anhang 2 .................................................................................................................. XIV

    Erklrung ber die eigenstndige Erstellung der Arbeit ....................................... XV

  • Einleitung 1

    Einleitung

    Google, Amazon und Facebook teilen sich nicht nur den Status, eine der zehn am bes-

    ten verdienenden Webseiten der Welt zu sein (Bellon 2012), sie haben auch etwas

    anderes gemeinsam: Alle drei Grokonzerne haben NoSQL-Datenbanken und die

    Nutzung von Geodaten fr sich entdeckt. Gerade solche Dienste, die sich Geodaten in

    direkter oder indirekter Art zunutze machen haben in letzter Zeit groe Aufmerksamkeit

    erlangt. So ermglicht beispielweise mittlerweile jedes Social Network, allen voran Fa-

    cebook, seinen Nutzern, ihre Position anderen mitzuteilen. Anwendungen wie Fours-

    quare bauen sogar in erster Linie auf die Verknpfung von sozialer Interaktion und

    Geodaten und die W3C Implementierung der Geolocation API mit HTML5 macht es

    mittlerweile fast jedem internetfhigem Gert mglich, ebenfalls seine aktuelle Position

    mitzuteilen. Damit steht diese Entwicklung klar im Trend und verursacht dadurch ein

    immenses Daten- und Nutzeraufkommen. NoSQL-Datenbanken stellen in diesem Zu-

    sammenhang mglicherweise eine Option dar, bisher verwendete SQL-Datenbanken

    abzulsen und die so entstandenen Big Data besser zu verwalten.

    Das Ziel dieser Arbeit soll darum sein, den aktuellen Entwicklungsstand von FOSS-

    NoSQL-Datenbanksystemen darzustellen und deren Anwendungsmglichkeiten fr

    Geodaten zu untersuchen. Dazu soll im ersten Kapitel eine zweckmige Zusammen-

    fassung der Historie der NoSQL-Bewegung gegeben werden. Nach einer Erluterung

    des Begriffs NoSQL werden dann grundlegende Konzepte nichtrelationaler Daten-

    banken eingefhrt. Das zweite Kapitel schliet mit einem allgemeinen berblick zu den

    heute frei verfgbaren NoSQL-Datenbanken an. Die aktuell dafr gebruchlichste Ka-

    tegorisierung soll darin vorgestellt und jeweils ein Vertreter dieser Kategorien nher

    betrachtet werden. Insbesondere soll hier auf die fr Geodaten interessante Eigen-

    schaften und Standards eingegangen werden, um davon ausgehend eine Einscht-

    zung zum aktuellen Entwicklungsstand zu treffen. Eventuell verfgbare Spatial Exten-

    sions werden in die Betrachtungen entsprechend mit einbezogen und in ihrem Funkti-

    onsumfang beleuchtet. Daran anschlieend soll eine Diskussion des Anwendungspo-

    tentials von NoSQL-Datenbanken vorgenommen werden, bei der die in Kapitel zwei

    vorgestellten Systeme wieder aufgegriffen und exemplarisch auf ihre Tauglichkeit fr

    Geodaten untersucht werden. Davon abgeleitet soll es mglich sein, eine Einschtzung

    ber das theoretische Anwendungspotential der verschiedenen NoSQL-Datenbanken

    geben zu knnen. Kapitel fnf und sechs stellen zwei unterschiedliche exemplarische

    Implementierungen vor, die jeweils mit einem fr sie geeigneten Vertreter der NoSQL-

    Datenbanken verwirklicht wurden. Insbesondere geht es hier darum, die Eignung der

    Datenbank zur Haltung geografischer und topologischer Daten auch praktisch unter

    Beweis zu stellen und eine begrndete abschlieende Aussage zu deren Eignung tref-

    fen zu knnen.

  • 1 Einfhrung in die Welt der NoSQL-Datenbanken 2

    1 Einfhrung in die Welt der NoSQL-Datenbanken

    Um in die Welt der NoSQL-Datenbanken einsteigen und ihren Wert fr Geodaten

    schlssig beurteilen zu knnen, ist es ntig, sich einen kurzen berblick ber die wich-

    tigsten Konzepte zu verschaffen. Im folgenden Kapitel soll dazu zunchst ein histori-

    scher Abriss zur Entstehung der NoSQL-Bewegung gegeben werden. Anschlieend

    folgt eine kurze Auseinandersetzung mit Konzepten, die fr viele der NoSQL-

    Datenbanken eine wichtige Rolle spielen und auerdem die Grundgedanken hinter den

    Entwicklungen nachvollziehbar machen.

    1.1 Historischer Abriss

    Der Begriff NoSQL wurde in Zusammenhang mit Datenbanken zum ersten Mal 1998

    von Carlo Strozzi genutzt (Edlich 2011: 1). Es handelte sich dabei um ein System, das

    zwar auf einem relationalen Datenmodell basierte, aber ganz bewusst kein SQL als

    Abfragesprache zur Verfgung stellte. Auf seiner Website betont Strozzi, dass sein

    System mit der aktuellen NoSQL-Bewegung nichts zu tun hat und dass sie eher die

    Bezeichnung NoRel verdient htte, womit er auf die Abkehr vom relationalen Daten-

    modell anspielt (Strozzi 2010).

    Erste wirklich als NoSQL-Datenbanken zu bezeichnende Systeme entstanden mit Ein-

    zug der Web 2.0 Welle und der damit verbundenen Datenflut. Um den exponentiellen

    Wachstumsraten digitaler Informationen Herr zu werden, begann der Suchmaschinen-

    riese Google 2004 mit der Arbeit an BigTable (Hitchcock 2005), einer nichtrelationa-

    len Datenbank, optimiert zur verteilten Haltung exzessiver Datenmengen im Petabyte-

    Bereich. BigTable nutzt eine Kombination aus Reihen/Zellen-Schlsseln und Zeitstem-

    peln, um Daten lose zu strukturieren, und baut auf das hauseigene Dateisystem

    Google File System (GFS) auf (Chang 2006: 1). Seit der ffentlichen Prsentation der

    Ergebnisse 2006 im BigTable Whitepaper und dessen Prsentation auf der OSDI '06

    erfuhr die Entwicklung von nichtrelationalen Systemen einen sprunghaften Anstieg. So

    finden sich heute beispielsweise Eigenschaften von BigTable in Apache HBase oder

    Apache Cassandra. Die Qualitt dieses neuen Konzepts ist dabei nicht allein die F-

    higkeit, groe Datenmengen zu verwalten, sondern auch die Ausrichtung auf ein ver-

    teiltes System aus kostengnstigen Standardservern (commodity server), die zu leis-

    tungsfhigen und fehlertoleranten Clustern zusammengeschlossen werden knnen.

    Damit war es nun auch mglich, dynamisch auf wachsende Datenmengen und stei-

    gende Nutzerzahlen einzugehen und die Kapazitten entsprechend anzupassen. (Ed-

    lich 2011: 2)

    Auch andere Unternehmen, deren Geschft primr auf der Hochverfgbarkeit ihrer

    Dienste beruht, haben hnliche Anwendungsflle fr nichtrelationale Datenbanken ge-

  • 1 Einfhrung in die Welt der NoSQL-Datenbanken 3

    funden. Aufgrund der Tatsache, dass der Versandkonzern Amazon zur Weihnachtszeit

    ein stark erhhtes Nutzeraufkommen zu verzeichnen hatte, die technologischen Gren-

    zen der eingesetzten Datenbanksysteme nach eigenen Aussagen 2004 aber ausge-

    reizt waren, kam es zu Einbrchen in der Verfgbarkeit der Dienste. Daraufhin setzte

    Amazon mit der Entwicklung von Dynamo ebenfalls auf ein skalierendes, nichtrelatio-

    nales System aus der Eigenentwicklung (Vogels 2012).

    Obwohl von Google so nicht propagiert, steht das proprietre BigTable heute als Be-

    griffspate fr eine ganze Kategorie der NoSQL-Datenbanken die sogenannten Wide

    Column Stores. Vermutlich setzte sich der Begriff im Juni 2009 durch, nachdem eine

    mit NoSQL betitelte Konferenz in San Francisco auf der Plattform Eventbride.com

    angekndigt wurde. Sie umfasste Prsentationen zu mehreren Datenbankenkategorien

    wie Voldemort, Cassandra, Dynomite, HBase, Hypertable und CouchDB (Evan 2009).

    Seitdem ist NoSQL zu einer Art Sammelbegriff fr diese verschiedenen Datenbanken-

    geworden und wird gerade aus Marketinggrnden gern genutzt (Edlich 2011: XV).

    1.2 NoSQL

    Whrend der Wiedererkennungswert des Wortes NoSQL unumstritten hoch ist, ist

    der Begriff selbst eher irrefhrend. Es hat den Anschein, dass SQL als Datenbankab-

    fragesprache kategorisch abgelehnt wird, was jedoch nicht der Fall ist. Es gibt zum

    einen Systeme, die SQL in verschiedenen Qualitten selbst implementieren, wie z.B.

    OrientDB und GenieDB. Auerdem haben die neuen Datenmodelle zu einer ganzen

    Reihe von Abfragesprachen gefhrt, die sich an der Semantik von SQL, und nicht zu-

    letzt an der englischen Sprache, orientieren. Die Cassandra Query Language (CQL)

    ist einer dieser Vertreter. SQL wird vielmehr als Synonym fr (objekt-)relationale Da-

    tenbanksysteme verstanden. Dies ist damit auch die vielleicht wichtigste und einende

    Eigenschaft der als NoSQL proklamierten Datenbanksysteme. Sie brechen mit dem

    Status Quo der relationalen Datenhaltung in vordefinierten, zeilenorientierten Tabellen.

    Carlo Strozzi hat in diesem Sinne also Recht, wenn er behauptet, NoRel wre unter

    Umstnden die treffendere Bezeichnung gewesen. Dementsprechend wird NoSQL

    mittlerweile mit Not-only-SQL gedeutet, was auch in dem gemeinschaftlich entworfe-

    nen Definitionsvorschlag fr NoSQL-Datenbanken von Prof. Stefan Edlich deutlich

    wird:

    Unter NoSQL wird eine neue Generation von Datenbanksystemen verstanden, die meistens einige der nachfolgenden Punkte bercksichtigen:

    1. Das zugrundeliegende Datenmodell ist nicht relational. 2. Die Systeme sind von Anbeginn an auf eine verteilte und horizontale Ska-

    lierbarkeit ausgelegt. 3. Das NoSQL-System ist Open Source. 4. Das System ist schemafrei oder hat nur schwchere Schemarestriktionen. 5. Aufgrund der verteilten Architektur untersttzt das System eine einfache

    Datenreplikation.

  • 1 Einfhrung in die Welt der NoSQL-Datenbanken 4

    6. Das System bietet eine einfache API. 7. Dem System liegt meistens auch ein anderes Konsistenzmodell zugrunde:

    Eventually Consistant und BASE, aber nicht ACID []. (Edlich 2011: 2).

    Der Begriff NoSQL bezieht sich also nicht nur auf die Abfragesprache der relationalen

    Datenbanken. Gerade die Skalierbarkeit und der Aufbau als verteiltes System scheint

    eine groe Bedeutung im Umfeld der NoSQL-Systeme zu spielen und soll

    anschlieend Gegenstand dieser Betrachtungen sein.

    1.3 Scaling Up/Out

    Technisch gesehen wird den Anforderungen unserer vernetzten Welt bisher mit der

    unter Scaling Up oder vertikaler Skalierung bekannten Vorgehensweise begegnet.

    Server, deren Kapazitten erreicht sind und die Clientanfragen nicht mehr ausreichend

    bedienen knnen, werden durch neue Technik ersetzt oder aufgerstet. Die entspre-

    chend leistungsstarke Hardware ist teuer. Trotzdem ist dies fr die meisten Anwen-

    dungen ein ausreichendes Mittel (Edlich 2011: 377).

    Eine Alternative zu einer Vertikalen Skalierung stellt die sogenannte Horizontale Ska-

    lierung oder Scaling Out dar. Darunter versteht man das Erweitern des Systems

    durch Einfgen zustzlicher Computerressourcen (ebd.). Der Vorteil dabei liegt in der

    Mglichkeit, aus einem Verband aus Mittelklasse-Hardware einen leistungsfhigen

    Cluster zu bilden. Dies ist in der Regel kostengnstiger und ermglicht eine dynami-

    sche Einflussnahme auf die Leistung des Systems durch Hinzufgen weiterer Rechner.

    Den aktuellen Gipfel der Horizontalen Skalierung stellt das sogenannte Cloud Compu-

    ting dar (ebd.). Der Versanddienstleister Amazon etwa bietet auf Grundlage seiner

    eigenen Datencenter die Amazon Web Services an und erlaubt so eine Nutzung sei-

    ner Rechenkapazitten. Der gewillte Kunde kann Rechenzeit kaufen und eigene virtu-

    elle Server betreiben, deren Rechenleistung vom Cluster bereitgestellt wird.

    (Amazon.com 2012)

    Im Zusammenhang mit der Horizontalen Skalierung spielt das in Brewers CAP-

    Theorem erfasste Problem der Unvereinbarkeit von Verfgbarkeit und Konsistenz eine

    wichtige Rolle. Darauf soll im nchsten Abschnitt eingegangen werden.

    1.4 CAP-Theorem

    Allgemein beruhen alle relationalen Datenbanksysteme, die im Einsatz sind, auf Ent-

    wicklungen, die in ihren Paradigmen ber 25 Jahre alt sind (Stonebraker 2007: 1). Im

    Vergleich zu damals, hat sich das Spektrum fr den Einsatz von Datenbanken jedoch

    vergrert. Zumeist bedeutet dies die Integration in Web Services als verteilte Syste-

    me, die einer viel greren Zugriffslast unterliegen und dabei Hochverfgbarkeit bieten

    sollen. Eric A. Brewer stellte in diesem Zusammenhang eine gemeinhin als CAP-

  • 1 Einfhrung in die Welt der NoSQL-Datenbanken 5

    Theorem bekannte Theorie auf, welche besagt, dass die gewollten Eigenschaften

    Konsistenz, Verfgbarkeit und Partitionstoleranz fr solche Dienste nicht gleichzeitig zu

    gewhrleisten sind (Brewer 2000). Zwei Jahre spter wurde dieses Theorem durch

    Seth Gilbert und Nancy Lynch fr verteilte Web Services formal besttigt (Gilbert

    2002).

    Ein praktisches Beispiel dafr ist ein verteiltes System bestehend aus drei Servern. Da

    Netzwerkpartitionen eine Voraussetzung fr ein solches System sind, gelingt es nicht,

    gleichzeitig Verfgbarkeit und Konsistenz aller drei Server zu wahren. In einem

    Konsistenz vernachlssigenden System wrde zwar hohe Verfgbarkeit erreicht

    werden knnen, whrend eines Lesevorgangs jedoch knnte eventuell nicht der

    aktuellste Stand reflektiert werden. Soll andererseits Konsistenz garantiert werden,

    kann ein nicht verfgbarer Datenbankserver einen Schreibvorgang unterbinden, da er

    z.B. durch Transaktionierung gesperrt ist (Vogels 2009: 41).

    Ein nicht partitioniertes System hingegen bestehend aus Client und Speichereinheit

    knnte Verfgbarkeit und Konsistenz durch Transaktionierungsmechanismen garantie-

    ren. In dieser Umgebung wrde der Ausfall einer Komponente jedoch zum Totalausfall

    fhren, was bedeutet, dass fr ein solches System das CAP-Theorem nicht gilt (ebd.).

    1.5 ACID & BASE

    Aus dem CAP-Theorem lsst sich schlieen, dass aufgrund des hohen Datenzugriffs-

    bedarfs durch steigende Nutzerzahlen das ursprnglich verwendete sogenannte A-

    CID-Paradigma nicht mehr uneingeschrnkt anwendbar ist. Unter dem Begriff ACID

    sind die vier Eigenschaften Atomicity, Consistency, Isolation und Durability zusam-

    mengefasst, welche durch Transaktionierung in RDBMS durchgesetzt werden (Kemper

    2011: 289).

    Viele NoSQL-Datenbanken setzen daher auf ein alternatives Modell, welches gemein-

    hin als BASE bezeichnet wird und auf Transaktionierung verzichtet. BASE ist ein Ak-

    ronym fr:

    Basically Available

    Soft-State

    Eventually Consistent

    Der Grundgedanke beruht darauf, Hochverfgbarkeit fr gelockerte Konsistenzbedin-

    gungen einzutauschen. Bei Eventual Consistency handelt sich also um einen optimis-

    tischen Ansatz, bei dem darauf verzichtet wird, alle im Cluster beteiligten Knoten durch

    Transaktionierung vor Inkonsistenzen zu sichern. Konsistenz der Daten wird so zu ei-

    nem flieenden, sich ber ein Zeitfenster ausbreitenden Zustand (Edlich 2011: 33).

    Zwar besteht so die Gefahr, dass fr einen kurzen Zeitpunkt auf einigen Servern

  • 1 Einfhrung in die Welt der NoSQL-Datenbanken 6

    veraltete Daten zur Verfgung stehen, jedoch kann der hohe Bedarf an Zugriffen auf

    dieselben Datenstze eher gedeckt werden.

    Es ist offensichtlich, dass dieses Vorgehen nicht fr jeden Einsatzzweck geeignet ist.

    Eine finanziellen Transaktion liee ein solches Konzept nicht zu, da der richitge

    Kontostand nicht zu jedem Zeitpunkt garantiert wre. Da die

    Konfigurationsmglichkeiten zwischen ACID und BASE mittlerweile flieend sind und

    manche Datenbanken sogar eine Kombination der Paradigmen untersttzen, ist es

    sinnvoll, Vor- und Nachteile fr die jeweilige Anwendung im Voraus abzuwgen (Edlich

    2011: 34).

    1.6 MapReduce

    Mit der starken Orientierung der nichtrelationalen Datenbanken nach verteilten Syste-

    men und neuen Datenmodellen mussten auch neue Algorithmen erdacht werden, wel-

    che diese Anforderungen untersttzen. Einer der bekanntesten Algorithmen dieser Art

    ist MapReduce, welcher durch die Google-Ingenieure Jeffrey Dean und Sanjay Ghe-

    mawat fr Google BigTable umgesetzt wurden (Edlich 2011: 12). Es handelt es sich

    dabei um ein Verfahren zur massiv parallelen Datenverarbeitung auf groen, verteilten

    Systemen. Die Parallelisierung beruht dabei auf den aus der funktionalen Programmie-

    rung abgeleiteten Methoden map() und reduce(), welche Abbildungsvorschriften dar-

    stellen, die auf Grundlage einer Kopie der Originaldaten in eine neue Datenstruktur

    berfhren (Dean 2004: 1). Bei der Anwendung durch NoSQL-Datenbanken wie

    HBase, Cassandra oder BigTable erfolgt die Abarbeitung von Map und Reduce dabei

    in zwei Phasen. Die erste Phase ist die Map-Phase, bei der aus einer Liste von Werten

    in eine neue Liste von Werten berfhrt wird (ebd.: 2). Die Ausgangsliste stellt dabei

    den kompletten Datenbestand in der Datenbank dar. Da die Funktion auf Kopien der

    Originaldaten angewendet wird bzw. das Ergebnis eine neue Datenstruktur darstellt,

    beeinflussen sich mehrere gleichzeitige Aufrufe der Funktion nicht gegenseitig. Dies

    ermglicht eine parallele Abarbeitung (s. Abbildung 1). Die optionale Reduce-Phase

    kann das Ergebnis der Map-Phase anschlieend aggregieren. Die Funktion setzt vo-

    raus, dass sie rekursiv definiert ist, was sie so ebenfalls parallel ausfhrbar macht

    (Edlich 2011: 13).

  • 1 Einfhrung in die Welt der NoSQL-Datenbanken 7

    Abbildung 1: Datenfluss des MapReduce-Verfahrens (Edlich 2011: 17).

    Auf einem Computercluster, der die vielen Einzelprozesse der beiden Phasen auf die

    einzelnen Knoten verteilt, entsteht so ein enormes Potenzial fr beschleunigte Berech-

    nungen, die aufgrund der groen Datenmenge auf einem einzelnen Computer unter

    Umstnden gar nicht mglich wren (Edlich 2011: 13).

    1.7 Schemalosigkeit von Daten

    Neben den unterschiedlichen Herangehensweisen bei Konsistenz und Skalierung ist

    ein weiterer wesentlicher Unterschied zwischen den SQL- und NoSQL-Datenbanken,

    dass das Datenbankmodell selbst nicht vor dem Einfgen der ersten Datenstze defi-

    niert sein muss. Whrend vor dem Anlegen eines Datenbankmodells fr SQL-

    Datenbanksystems eine genaue Kenntnis ber die zu erwartenden Daten vorliegen

    muss, um davon ein Datenbankschema abzuleiten, ist dies mit NoSQL allgemein nicht

    ntig. Dadurch fllt auch ein eventuelles Umstrukturieren der Tabellen weg, wie es bei

    relationalen Datenbanken vonnten sein kann, sobald sich die Ansprche an die Da-

    tenhaltung ndern oder Informationen mit aufgenommen werden sollen, die beim Anle-

    gen der Tabellen so nicht vorgesehen waren.

  • 2 Allgemeiner berblick 8

    2 Allgemeiner berblick

    In der kurzen Zeit seit der Verffentlichung des BigTable Whitepapers 2006 sind viele

    NoSQL-Datenbanksysteme entstanden. Darber hinaus qualifizieren sich auch beste-

    hende Systeme, wie beispielsweis Lotus Notes oder Oracle Berkeley DB, als nichtrela-

    tionale Systeme und sind zusammen mit derzeit mehr als 122 weiteren Datenbanken

    auf http://nosql-database.org/ gelistet (Edlich 2012). Neben wenigen kommerziellen

    Anbietern handelt es sich dabei meist um Free and Open Source Projekte (FOSS) un-

    terschiedlicher Gre. Aufgrund der schieren Gre des Angebots, kann hier nicht auf

    jede dieser Datenbanken eingegangen werden. Im Folgenden sollen deshalb die vier

    wichtigsten Kategorien nichtrelationaler Datenbanken vorgestellt werden und je ein

    typischer Vertreter genauer betrachtet werden, der diese reprsentiert.

    2.1 Kategorisierung

    Eine Kategorisierung der Datenbanken erscheint zunchst schwierig, da die Eigen-

    schaften der Systeme einerseits drastisch variieren, sich andererseits aber auch nur in

    Detailfragen unterscheiden. Der beste Weg, sich dem Angebot zu nhern, ist es, die

    Datenbanken nach Art der Datenhaltung zu unterscheiden. Die Website NOSQL

    Databases schlgt hier seit 2009 eine durch die Open Source Gemeinde diskutierte

    Ordnung vor, die sich weitgehend durchgesetzt hat. (Edlich 2012). Die Kategorisierung

    der nichtrelationalen Datenbanken basiert auf den ihnen zugrundeliegenden Datenmo-

    dellen und umfasst folgende Hauptkategorien:

    Key/Value Stores

    Wide Column Stores

    Document Stores und

    Graphdatenbanken.

    Die Einordnung der Systeme in die einzelnen Kategorien kann sich mitunter als

    schwierig erweisen, da hybride Lsungen beispielsweise Eigenschaften aus

    Key/Value-Stores und Document Stores mischen (z.B. Riak) (Edlich 2011: 179) oder

    Features mehrerer Kategorien implementieren (z.B. OrientDB). (Garulli 2011).

    2.2 Key/Value Stores

    Die erste Gruppe der Key/Value Stores ist in den letzten Jahren sehr gewachsen. Seit

    den 70er Jahren bekannt, hat sich ihre Anzahl mit dem Erscheinen des Amazon Dy-

    namo Whitepapers 2007 vervielfacht. Sie sind prdestiniert fr Daten, die keine Relati-

    on zueinander aufweisen, da es sich um ein sehr einfaches Datenmodell handelt

    (Edlich 2011: 151).

    http://nosql-database.org/

  • 2 Allgemeiner berblick 9

    2.2.1 Datenhaltung

    Das Prinzip der Datenhaltung in einem Key/Value Store hnelt einer Hash Table, also

    einer Zuordnungstabelle der objektorientierten Programmierung bestehend aus zwei

    Spalten. Eine Spalte enthlt dabei den ber eine Hash-Funktion abgebildeten Schls-

    sel (Key) ber den der Zugriff erfolgt (s. Abbildung 2). Die zweite Spalte fhrt den

    assoziierten Wert, genannt Value, welcher als einzige Bedingung den Datentypen

    entsprechen muss, die durch die Datenbank untersttzt werden. Die einzelnen Eintr-

    ge in die Zeilen der Tabelle sind dabei ohne weitere Relation zueinander (Edlich 2011:

    36). Die Verantwortung der Beziehungen zwischen den Eintrgen obliegt damit voll der

    Clientanwendung.

    Abbildung 2: Hashfunktion. Eingangswerte werden ber eine bestimmte Funktion auf einen Werteraum abgebildet (Edlich 2011: 36).

    2.2.2 Redis

    Ein beliebter Vertreter der Key/Value Stores ist das Datenbanksystem Redis. Es star-

    tete 2009 als Entwicklung von Salvatore Sanfillippo und ist in ANSI-C programmiert

    (Edlich 2011: 152). Es steht fr POSIX-kompatible Plattformen in einer New-BSD-

    Lizenz zur Verfgung und kann direkt aus dem Quellcode kompiliert werden. (Edlich

    2011: 152).

    Im Gegensatz zur weit verbreiteten Caching-Lsung Memchached, bietet Redis drei

    Persistenz-Modi, aus denen frei gewhlt werden kann. Der erste Modus besteht darin,

    in fest definierten Intervallen Snapshots des Datensatzes abzulegen (RDB Modus).

    Alternativ kann auch jeder Schreibzugriff geloggt und bei Bedarf wieder in die Daten-

    bank eingespielt werden (AOF Modus). Es ist ebenfalls mglich RDB und AOF-Modi

    zweckmig zu kombinieren oder komplett auf die nachhaltige Speicherung zu verzich-

    ten. Daten, die bei einem Ausfall ausschlielich im flchtigen Arbeitsspeicher vorhan-

    den waren, wren in einem solchen Fall jedoch verloren (Edlich 2011: 152f).

    Redis bietet die Mglichkeit, Operationen in einer Transaktion zusammenzufassen.

    Dies spart Verbindungszeit bei der Abarbeitung und schtzt durch die atomare Rei-

    henabarbeitung des Operationssatzes vor Inkonsistenz gegenber weiteren Zugriffen

    (Edlich 2011: 156f.). Auf Konsolenebene geschieht dies mit dem Befehl MULTI. Zu

    beachten ist dabei, dass das Scheitern einer der Operationen, nicht das Scheitern der

  • 2 Allgemeiner berblick 10

    restlichen durch MULTI zusammengefassten Operationen bedingt. Dies muss in der

    Anwendungsebene entsprechend bercksichtigt werden (VMWare 2011d).

    Um Redis zu skaliert, kann in einer Master-Slave-Schaltung ber mehrere Knoten re-

    pliziert werden. Dies kann dazu dienen, die Leseleistung zu erhhen oder Daten re-

    dundant vorzuhalten (ebd.). Zu beachten ist, dass zum gegenwrtigen Zeitpunkt (Ver-

    sion 2.4.7) kein Sharding mit Bordmitteln mglich ist. Der dazu notwendige Redis Clus-

    ter steht bisher nur als Developer Preview zur Verfgung und wird mit Version 2.6. er-

    wartet (Sanfilippo 2011). Das bedeutet, dass der gesamte Datenbestand in den Ar-

    beitsspeicher passen muss. Davon Daten in den virtuellen Speicher auszulagern wird

    abgeraten (VMWare 2011e).

    Auch wenn alle Datentypen die durch Redis untersttzt werden auf Strings basieren,

    werden komplexe Strukturen wie Listen, unsortierte und sortierte Sets und Hashes

    bereitgestellt (Edlich 2011: 153). Darber hinaus werden Interaktionen, wie beispiels-

    weise UNION und DIFF bei Sets, oder links- oder rechtsseitige PUSH und POP-

    Befehle bei Lists geboten, die einer Clientanwendung weitreichende Optimierungsmg-

    lichkeiten bieten. Der Zugriff auf die Datenbank erfolgt dabei ber die mitgelieferte

    Konsole oder ber eine entsprechende Client-API. Die Auswahl ist sehr gro und um-

    fasst alle verbreiteten hohen Programmiersprachen (VMWare 2011a).

    2.2.3 Spatial Extension

    Zum gegenwrtigen Zeitpunkt ist fr keinen Key/Value Store eine Spatial Extension

    verfgbar (s. Anhang 2). Dies trifft auch fr Redis zu. Da durch Redis binrsichere

    Strings untersttzt werden, ist es jedoch mglich, jede Art von Daten binrcodiert abzu-

    legen und auszulesen.

    2.3 Wide Column Stores

    Bei der zweiten groen Gruppe der NoSQL-Datenbanken, den Wide Column Stores

    (auch Column Family Store), handelt es sich um spaltenorientierte, nichtrelationale

    Datenbanken. Sie knnten als Nachkommen des proprietren Google BigTable ge-

    sehen werden, da die Open-Source-Community vielfach begonnen hat, auf Basis der

    von Google verffentlichten Forschungsunterlagen Eigenschaften von BigTable zu

    klonen und gewnschte hinzuzufgen. Ein sehr erfolgreiches Beispiel dafr ist die Da-

    tenbank HBase, die Teil des Apache Frameworks Hadoop ist (The Apache Software

    Foundation 2012). Auch der Social Network Riese Facebook hat einen Wide Column

    Store entwickelt. Dieser wurde unter dem Namen Cassandra 2008 der Open-Source-

    Community bergeben (Cassandra Wiki 2012c).

    Entsprechend des proprietren Vorreiters Google stellt auch das Open Source Frame-

    work Apache Hadoop das verteilte Dateisystem Hadoop Distributed File System

  • 2 Allgemeiner berblick 11

    (HDFS) zur Verfgung und setzt als Apache Hadoop MapReduce eine quelloffenes

    Variante des Programmier-Paradigmas um auf das Cassandra und HBase zurckgrei-

    fen knnen (The Apache Software Foundation 2011).

    2.3.1 Datenhaltung

    Google selbst beschreibt das Datenmodell der Wide Column Stores als [] sparse,

    distributed, persistent multidimensional sorted map (Chang 2006: 1). Dabei handelt es

    sich um eine sehr eng gepackte Definition, die zusammengefasst Folgendes be-

    schreibt:

    Die oberste Ordnungseinheit ist, so wie in einem Key/Value Store, der Zeilenschlssel.

    Der Value ist in diesem Fall eine Map, wie sie aus der objektorientierten Programmie-

    rung bekannt ist. Diese zeigt wiederrum auf eine Zuordnungstabelle von Spaltenfami-

    lien, daher auch der alternativer Name Column Family Store. Diese Verschachtelung

    von Zuordnungstabellen kann als multidimensional bezeichnet werden. Die Column

    Family verweist letztendlich auf Spalten, also columns, die versionierte Werte enthal-

    ten, welche wiederum ein nicht interpretiertes Byte-Array darstellen (Wilson 2008).

    Abbildung 3: Konzeptuelles Schema eines Wide Column Stores nach BigTable White Paper (Chang 2006: 2).

    {

    ...

    "com.cnn.www": { //Row Key

    "anchor" : { //Column Family

    "cnnsi.com" : { //Column

    T9 : "CNN" //Version & Value

    },

    "my.look.ca" : {

    T8 : "CNN.com"

    },

    "contents" : {

    "" : { //Column mit leerem Bez. ""

    T6 : "...",

    T5 : "...",

    T3 : "..."

    }

    }

    }

    ...

    }

    Abbildung 4: Konzeptuelles Schema eines Wide Column Stores in JavaScript-naher Notation (Wilson 2008).

  • 2 Allgemeiner berblick 12

    Das Konzept der spaltenorientierten Datenhaltung der Wide Column Stores hat Vortei-

    le bei der Kompression und Analyse der Daten gegenber den zeilenorientierten

    RDBMS. Andererseits ist das Lesen und Schreiben von Objektstrukturen aufwndiger

    (Edlich 2011: 63). Durch die sortierte Speicherung von Row Keys, Column Families

    und Columns (vgl. multidimensional sorted map bzw. Abbildung 4 ist es auerdem

    leichter, eine horizontale Partitionierung der Daten einzurichten und so Zugriffe auf

    mehr als einen Datenbankserver pro Abfrage zu reduzieren (ebd.).

    2.3.2 Apache Cassandra

    Das von Facebook entwickelte und mittlerweile als Apache Top Level Project geliste-

    te Cassandra leitet seine Eigenschaften sowohl von BigTable als auch Amazon Dyna-

    mo ab. Cassandra ist damit auch ein gutes Beispiel fr die eingangs erwhnte Vielfalt

    der NoSQL-Datenbanken, die durch Kombination von Konzepten entsteht. In erster

    Linie handelt es sich um einen BigTable-Klon der um eine weitere Organisationsebene,

    die Super-Column, erweitert ist (Edlich 2011: 83). Vorbild fr die Skalierung ist das

    Amazon Dynamo Whitepaper welches unter anderem das Consistent Hashing be-

    schreibt. Es ermglicht, per horizontaler Fragmentierung (Sharding) den Datenbe-

    stand ber eine groe Menge von Datenbankservern zu verteilen. Das Grundprinzip

    besteht darin, den Hash-Wertebereich der Schlssel ber alle beteiligten Knoten zu

    verteilen und in einem Ring zu schlieen. Jeder Rechner bernimmt die Schreibver-

    antwortung fr je eine dieser Partitionen. Auerdem wird diese Partition auf weitere

    Server repliziert, um so die Fehlertoleranz zu erhhen. Sie ist dort als Schattenkopie

    vorgehalten und kann bei einem Ausfall neu im Ring verteilt werden. (Vogels 2007).

    Abbildung 5: Consistant Hashing-Ring. (Vogels 2007).

  • 2 Allgemeiner berblick 13

    Die im Cluster verbundenen Knoten befinden sich also in einer Master-Master-

    Konfiguration, wodurch einem Single-Point-of-Failure vorgebeugt werden soll. Um

    dies umzusetzen, basiert die Kommunikation der beteiligten Datenbankserver auf dem

    Peer-to-Peer Protokoll Gossip, mit dem die Instanzen ihren Status periodisch mittei-

    len und empfangen (ebd.).

    Als Schnittstelle steht Cassandra Thrift zur Verfgung, ein Framework, welches den

    plattformunabhngigen Austausch von Objekten ermglicht (Slee 2007). Auf Grundla-

    ge der reinen Thrift API sind viele High Level-Clients verfgbar, der Zugriff auf ein

    Cassandra-Cluster ist also nativ in vielen Programmiersprachen wie Java, C++ und

    Ruby mglich (Cassandra Wiki 2012a).

    2.3.3 Spatial Extensions

    Derzeit steht, wie fr Key/Value Stores, fr keinen Wide Column Store eine Spatial

    Extension zur Verfgung (Stand Februar 2012). Die Schachtelung von Column Familys

    und Columns erlaubt strukturiertere Daten als dies bei einem reinen Key/Value Store

    mglich ist. Dass die Haltung von Geodaten in einem Wide Column Store nicht grund-

    legend unmglich ist, zeigt Google durch die Nutzung von BigTable fr den Groteil

    seiner Dienstleistungen, wozu auch die Bereitstellung der Google Earth Satellitenbil-

    dern per Desktop- und Webinterface gehrt. (Chang 2006: 11f) Die gleichen

    technischen Grundlagen werden auerdem eingesetzt, um mit Google Earth Builder

    Geodaten fr Unternehmen in der Cloud bereitzustellen (Google 2012).

    Apache Cassandra kommt auerdem bei der Firma SimpleGeo zum Einsatz, welche

    auf dem Wide Column Store aufbauende Point-of-Interest-Services und einen Storage-

    Service anbietet. Der Zugang erfolgt dabei ber eine Web-API. SimpleGeo bietet

    grundlegende rumliche Abfragen auf Punktmengen durch Implementierung eines ei-

    genen Zugriffsmechanismus (Finley 2011 und Malone 2010).

    2.4 Document Stores

    Wie der Name bereits andeutet, handelt es sich bei den Document Stores, um in ers-

    ter Linie dokumentenbasierte Datenbanken. Ein konzeptueller Vater der Document

    Stores ist Lotus Notes, das neben der Integration des relationalen IBM RB2 ebenfalls

    eine dokumentenzentrische Datenhaltung anbietet. Die Entwicklung ist also nicht

    grundlegend neu, hat aber durch CouchDB und dessen Begrnder Damien Katz eine

    Wiederbelebung erfahren. Da sich die schemalose Dokumentenstruktur gerade fr

    agile Webanwendungen eignet, wird CouchDB und auch die grte Konkurenz, das

    Document Store MongoDB, von der Entwicklergemeinschaft sehr gut angenommen

    (Edlich 2011: 117).

  • 2 Allgemeiner berblick 14

    2.4.1 Datenhaltung

    Das zugrundeliegende Datenmodell eines Document Stores wird als dokumentenzent-

    risch oder dokumentenorientiert bezeichnet. Unter Dokumenten verstehen sich dabei

    Daten im JSON-Format (JavaScript Object Notation) oder in der binrenkodierten Vari-

    ante BSON. Um die Typen von Dokumenten zu unterscheiden, werden entsprechen-

    de Eigenschaften in ihnen definiert, die sie implizit unterscheiden (Scheliga 2010: 81).

    JSON ist ein Austauschformat, das auf einer Untermenge der JavaScript-

    Programmiersprache basiert und der textlichen Reprsentation von Objekten dient.

    Gegenber der Auszeichnungssprache XML (Extensible Markup Language) ergibt sich

    damit eine einfachere Lesbarkeit. Auerdem ist JSON in fast allen Programmierspra-

    chen leicht zu verarbeiten (Scheliga 2010: 45.f).

    {

    "_id": "5633855b3772c8426e77a4e2c7000de8",

    "_rev": "4-17aaa5b24954e6c6245381670fda8b88",

    "name": "Ruby",

    "implementations": [

    "Ruby",

    "JRuby"

    ]

    }

    Abbildung 6: Beispiel eines einfachen JSON-Dokuments.

    2.4.2 CouchDB

    CouchDB ist eine schemafreie, dokumentenorientierte Datenbank in der die Daten in

    Form von JSON-Datenstrukturen abgelegt werden. Der Zugriff auf CouchDB per

    HTTP-Protokoll orientiert sich eng an den durch Roy Fielding zusammengestellten Kri-

    terien des Representational State Transfer, womit es sich bei CouchDB wohl um die

    am besten ans Web angepasste Datenbank handeln drfte (Tiwari 2011).

    RESTful bedeutet, dass CouchDB alle REST Operationen (GET/HEAD, PUT, DELE-

    TE, POST) untersttzt und dabei die Konzepte der Sicherheit und Idempotenz einhlt.

    Zu verstehen ist darunter, dass beispielsweise eine simple GET-Operation keine Daten

    in der Datenbank ndert. Die Operation ist also sicher. Idempotent bedeutet, dass bei

    der Nutzung des PUT-Befehls das mehrfache Schreiben des gleichen Dokuments im-

    mer zum gleichen Ausgang fhrt. So kann verhindert werden, dass die gleiche Opera-

    tion unwillentlich zu doppelten Dokumenten fhrt (Fielding 1999). Datenbank und Do-

    kumente stellen die Ressourcen dar, auf die die Operationen angewandt werden kn-

    nen. Sie besitzen eine eindeutig zu identifizierende Uniform Ressource Identifier (URI).

    Auerdem setzt CouchDB eine zustandslose Anfrage durch den Client voraus. Jede

    Anfrage muss also alle Informationen zur Abarbeitung enthalten und kann nicht auf

    Kontextinformationen in der Datenbank vertrauen. Die Integration in Web Services ist

    so besonders einfach (Fielding 2000 und Edlich 2011: 51ff.).

  • 2 Allgemeiner berblick 15

    Neben der Funktion als Dokumentdatenbank integriert CouchDB so einen vollwertigen

    HTTP-Server, deren Ressourcen per HTTP-REST-API aufrufbar sind. Dazu gehrt

    auch eine Administrationskonsole, die per Browser aufgerufen werden kann und ber

    die, neben der Verwaltung von Datenbanken und Dokumenten auch Konfigurationen

    vorgenommen und Zugriffsrechte geregelt werden knnen.

    In der Arbeit Roy Fieldings ist die Zustandslosigkeit der Ressourcen des HTTP-

    Protokolls als einer der Hauptgrnde fr den Erfolg des World Wide Web beschrieben

    (Fielding 2000). Einerseits ist es mglich, Informationen einer Ressource einfach aus-

    zulesen, andererseits kann die Ressource auch in verschiedensten Ausprgungen

    dargestellt werden. Diesem Konzept folgt auch CouchDB und implementiert bestimmte

    Sonderdokumente, die durch einen fhrenden Unterstrich auszumachen sind. Das

    wichtigste Dokument stellt dabei _design dar. Hier lassen sich neben anderen folgen-

    de Funktionen als JSON-Objekte definieren:

    Views

    Lists

    Validierungsfunktionen (Scheliga 2010)

    Views stellen dabei die Abfragemglichkeit auf CouchDB-Dokumente dar, welche per

    Map- und Reduce-Funktionen in JavaScript formuliert wird. Der Grundgedanke ist da-

    bei analog zu dem des MapReduce-Verfahrens, welches in 2.6 beschrieben ist. Es

    werden also alle Datenstze der Datenbank durchlaufen und geprft. Die Antwortmen-

    ge wird anschlieend indexiert und ist unter der URI des Views verfgbar. List-

    Funktionen dienen als Render-Funktionen fr Views (ebd.: 140) und verarbeiten die

    Ergebnismenge eines Views weiter (ebd.). Sie eignen sich beispielsweise zum Umfor-

    men des JSON-Objekts in ein anderes Format. ber die Validierungsfunktion lassen

    sich die Benutzerrechte fr verschiedene Nutzergruppen steuern (ebd.: 149f.).

    CouchDB setzt statt auf pessimistische Transaktionierung auf die Versionierung von

    Schreibzugriffen durch Multi Version Concurrency Control (MVCC). Das heit, dass

    mehrere unvernderliche Versionen eines Datensatzes (Edlich 2011:41) vorgehalten

    werden. Jeder Schreibzugriff erstellt eine neue Version die eine eindeutig

    identifizierbare Revisionsnummer trgt. Treffen konkurrierende Schreibzugriffe auf

    einem Datensatz zusammen, wird durch vergleichen der Revisionsnummern bestimmt,

    ob die Schreiboperation zu diesem Zeitpunkt zulssig war. Im Konfliktfall muss diese

    optimistische Transaktion zurckgerollt und unter Umstnden von vorn begonnen

    werden. (ebd.)

    2.4.3 Spatial Extensions

    Fr CouchDB steht die Spatial Extension GeoCouch zur Verfgung. Sie wird durch den

    Couchbase-Entwickler Volker Mische koordiniert und gepflegt. Im Februar 2012 war

  • 2 Allgemeiner berblick 16

    ausschlielich eine Bounding Box Abfrage auf geometrische Objekte mglich, welche

    sich auf den zweiten Entwurf der OpenSearch-Spezifikation fr Geodaten sttzt. Nach

    eigenen Aussagen sollen zuknftige Implementierungen ebenfalls diesen Standard

    bedienen (s. Anhang 1).

    Fr die Strukturierung der Daten bietet sich die GeoJSON-Spezifikation an, die mit

    dem 16. Juni 2008 in die Version 1.0 berfhrt wurde. Es handelt sich dabei um ein

    Schnittstellenformat fr geographische Datenstrukturen, das ebenfalls auf der Ja-

    vaScript Object Notation beruht. Die geometrischen Objekte der Spezifikation orientie-

    ren sich an der Simple Feature Specification und umfassen neben simpler Geometrie

    auch die Definition eines FeatureObject und einer FeatureCollection. Auerdem ist es

    mglich, direkt oder indirekt ein CRS, bevorzugt notiert nach den Empfehlungen fr

    OGC Universal Ressource Names fr Koordinatenreferenzsysteme, als Attribut zu de-

    finieren (Butler 2008).

    { "type": "MultiLineString",

    "coordinates": [

    [ [100.0, 0.0], [101.0, 1.0] ],

    [ [102.0, 2.0], [103.0, 3.0] ]

    ]

    }

    Abbildung 7: Beispiel eines GeoJSON GeometryObjects des Typs MultiLineString.

    Durch die Aufnahme von GeoJSON und CouchDB als Schnittstellenformate in die

    Geospatial Data Abstraction Library (GDAL) bzw. in die Sub-Bibliothek OGR Simple

    Features Library der OGC ab Version 1.9 aufwrts, knnen alle durch die Simple

    Feature Specification definierten Geometrien in CouchDB importiert und durch

    GeoCouch indexiert werden (GDAL 2011).

    Neben CouchDB bietet auch der Document Store MongoDB, entwickelt durch die Fir-

    ma 10gen, eine native rumliche Indexierung, welche allerdings auf die Abfrage von

    Punktgeometrie beschrnkt ist (10gen 2011). Trotz dieser Einschrnkungen listet

    10gen auf seiner Website mindestens zwlf Anbieter die MongoDB primr fr

    webbasierende Geolocation Services nutzen, darunter auch FourSquare mit nach

    eigenen Aussagen 15 Millionen Nutzern im Dezember 2011 (Heine 2011).

    2.5 Graphdatenbanken

    Die letzte hier vorgestellte Gruppe der NoSQL-Datenbanken unterscheidet sich deut-

    lich von den vorherigen. Whrend Key/Value Stores, Wide Column Stores und

    Document Stores unstrukturierte Datenstze speichern und diese fr Suchanfragen zur

    Verfgung stellen, beschreibt eine Graphdatenbank die Art und Weise der Verknp-

    fungen dieser Datenstze untereinander (Edlich 2011: 207). Das Grundkonzept der

    Graphdatenbanken basiert auf der Graphentheorie der Mathematik, welche das

  • 2 Allgemeiner berblick 17

    allgemeine Graphenmodell bestehend aus einer Knoten- und einer Kantenmenge

    definiert. Eine Kante stellt eine Beziehung zwischen zwei Knoten dar und kann sowohl

    gerichtet als auch ungerichtet sein (Edlich 2011: 209f.).

    Abbildung 8: Einfacher Graph bestehend aus drei Knoten und ungerichteten Kanten.

    Auch im Hinblick auf das Schlagwort Semantic Web spielen Graphdatenbanken eine

    bedeutende Rolle. Um den Datenaustausch im Web zu standardisieren, baut man hier

    auf das Ressource Description Framework (RDF), das das Konzept des einfachen

    Verlinkens von Informationen per URI zu einer benannten Kante mit Anfangs- und

    Endpunkt ausbaut. Das resultierende Triple entspricht einem gerichteten und

    benannten Graphen (RDF Working Group 2012). Graphdatenbanken, die zu diesem

    Zweck die Abfragesprache SPARQL implementieren, werden gemeinhin als RDF-

    Stores bezeichnet und knnen als Untermenge der Graphdatenbanken angesehen

    werden (Edlich 2011: 228).

    2.5.1 Datenhaltung

    Das wichtigste Konzept der NoSQL-Graphdatenbanken stellt das Property-Graph-

    Modell dar (Rodriguez 2012a). Es handelt sich dabei um eine Erweiterung des

    allgemeinen Graphmodells, in dem jede Kante ein Label trgt, die den Typen der

    Relation zwischen den Knoten beschreibt. Auerdem erhalten sowohl Knoten als auch

    Kanten einen eindeutigen Identifikator und knnen Eigenschaften (properties) tragen,

    welche durch eine Zuordnungstabelle des Typs verkrpert werden. Je

    nach Implementierung knnen Knoten und Kanten streng typisiert werden, sodass der

    Typ des Knotens oder der Kante explizit erfasst oder implizit aus seinen Eigenschaften

    bestimmt werden kann. Wie sich Abbildung 8 entnehmen lsst, kann einer Kante auch

    ein Gewicht zugeordnet werden, weshalb man auch von einem gewichteten Graph

    spricht (Edlich 2011: 211f.).

  • 2 Allgemeiner berblick 18

    Abbildung 9: Gewichteter Property Graph zwischen Personen und Programmen (Rodriguez 2012a).

    Gegenber den relationalen Datenbanken ergeben sich einige Parallelen. Whrend

    alle anderen hier vorgestellten NoSQL-Vertreter keine Beziehungen zwischen den Da-

    tenstzen modellieren, gehrt dies zur natrlichen Struktur eines Graphen. Auch in

    einer relationalen Datenbank lassen sich diese Vernetzungen abbilden. Whrend es

    bei einer SQL-Datenbank mit einigem Aufwand verbunden sein kann, die einzelnen

    Tabellen per (rekursivem) JOIN zu durchlaufen, um komplexe Beziehungen herzustel-

    len, gestaltet sich die Traversierung eines Graphen schon bedeutend intuitiver (Edlich

    2011: 225f.).

    Aufgrund der Komplexitt des Datenmodells, mssen hnlich wie bei den SQL-

    Datenbanken, Abstriche bei der Skalierbarkeit des Systems gemacht werden. Um die

    Leistung eines Graphdatenbankservers zu erhhen, bietet sich die Replikation der

    Datenbank ber mehrere als Slave-Server konfigurierte Rechner an. Schreibzugriffe

    werden dabei ausschlielich auf dem Master-Server zugelassen und auf die

    hierachisch niederen Rechnerknoten bertragen. Mssen die Daten allerdings

    partitioniert werden, weil der Umfang fr einen Rechner zu gro geworden ist,

    entstehen ganz hnliche Probleme wie in einer relationalen Datenbank. Auch hier stellt

    sich die Frage, an welchem Punkt der Datensatz getrennt werden soll. Traversierungen

    der Datenstze ber den lokalen Datenbestand hinaus mssen dabei minimiert

    werden, um die Abfragekomplexitt ber das Netzwerk nicht unntig zu erhhen. Das

    Finden der passenden Partitionierungsregel ist damit nicht trivial (Edlich 2011: 222).

  • 2 Allgemeiner berblick 19

    2.5.2 Neo4j

    Neo4j ist seit 2007 als Java Open-Source-Datenbank nutzbar und wird auch in einer

    kommerziellen Lizenz angeboten.

    Wie die meisten NoSQL-Graphdatenbanken implementiert Neo4j die Bausteine des

    De-facto Standards Tinkerpop Graph Processing Stack, ein Java-Framework, welches

    in erster Linie eine einheitliche Schnittstelle namens Tinkerpop Blueprints zwischen

    Graphdatenbanken bietet (Edlich 2011: 230). Blueprints fungiert hier analog zu der

    JDBC-API der relationalen Datenbanken (Rodriguez 2012b). Hinzu kommt die

    Untersttzung von Tinkerpop Gremlin, einer Graph-Traversierungssprache, die auch

    eine Manipulation des Graphen zulsst. Neben Gremlin steht auerdem die

    Traversierungssprache Cypher zur Verfgung, die fr Neo4j entwickelt wurde. Sie

    zeichnet sich durch eine einfache Syntax aus, die das durchlaufen des Graphen gut

    nachvollziehbar macht. (Neo Technology 2012b) Neben dem Auffinden von Knoten

    und Kanten via Traversierung, findet auerdem die Suchengine Apache Lucene

    Anwendung, ber die Indexierungen ber die Attribute der Kanten und Knoten

    eingerichtet werden knnen.

    Neo4j kann sowohl als EmbeddedGraphDatabase in ein Programm eingebettet, als

    auch im Servermodus hnlich CouchDB ber eine REST-Schnittstelle angesprochen

    werden. Wird der Datenbankserver gestartet, ist er ebenfalls ber den Port 7474 ber

    eine Webkonsole zugnglich, welche neben Statusinformationen auch eine eigene

    Shell bietet, ber die der Graph manipuliert bzw. traversiert werden kann.

    gremlin> node = g.addVertex("name":"Gremlin")

    ==> v[2093]

    gremlin> g.addEdge(g.v(500), node, 'TEST', [:])

    ==> e[3114][500-TEST->2093]

    Abbildung 10: Hinzufgen eines Knotens und einer Kante mit Gremlin.

    Eine weitere Besonderheit im Umfeld Neo4js unter den NoSQL-Datenbanken ist die

    Untersttzung von Transaktionen. Neo4j arbeitet nach dem ACID-Paradigma. Das

    sperren der Daten geschieht dabei auf Level der Knoten und Kanten.

    2.5.3 Spatial Extensions

    Aus der Graphentheorie geht hervor, dass Topologie gut durch Graphen modelliert

    werden kann. ndern sich nmlich in einem solchen Graphen die Koordinaten, also

    eine metrische Eigenschaft eines Knotens, so ist die Topologie davon nicht betroffen.

    Im Grunde lsst sich schon mit den Bordmitteln einer Graphdatenbank komplexe To-

    pologie einpflegen. Darber hinaus bietet Neo4j die Spatial Extension Neo4j Spatial.

    Dieser steht bisher lediglich als Development Version zur Verfgung, kann aber in sei-

    nem tagesaktuellen Stand vom ffentlichen Git-Repository geladen werden (Neo

  • 2 Allgemeiner berblick 20

    Technology 2012a). Neo4j Spatial stellt auf Grundlage des GeoTools GIS Toolkits der

    Open Source Geospatial Foundation (OSGeo) fr die Graphdatenbank optimierte GIS

    Funktionalitt bereit die als Java-Bibliothek in Projekte eingebunden werden kann. Au-

    erdem steht eine Erweiterung fr die Neo4j Server Variante zur Verfgung, die Abfra-

    gen auf Geodaten per REST-Schnittstelle erlaubt.

    Durch den Aufbau auf das GeoTools Framework ist es mglich, Neo4j als Datenhal-

    tungskomponente fr OpenGIS-Produkte zu nutzen. Interessant ist dies speziell fr

    GeoServer, dem es damit mglich ist WFS und WMS auf Grundlage der Graphdaten-

    bank bereitzustellen. Darber hinaus implementiert die Erweiterung die WKT bzw.

    OSM und ESRI Shapefiles Encoder zum Im- und Export von Daten. Neo4j Spatial kann

    mit allen Geometrietypen umgehen, die durch die OGC Simple Feature Specification

    definiert sind und bietet weitreichende Operationen auf die Geometrien, die durch die

    Spezifikation vorgegeben sind.

  • 3 Anwendungspotential fr Geodaten 21

    3 Anwendungspotential fr Geodaten

    In summary, one can leverage at least the following ideas to get superior perfor-mance:

    A non-relational data model. If the users data is naturally something other than ta-bles and if simulating his natural data model on top of tables is awkward, then chances are that a native implementation of the natural data model will significantly outperform a conventional RDBMS. (Stonebraker 2009).

    Das obige Zitat einer der Gallionsfiguren der relationalen Datenbanken, Michael

    Stonebraker, hat mit seinem Erscheinen fr einige Aufmerksamkeit gesorgt. Mittlerwei-

    le steht Stonebraker eher fr eine defensive Haltung gegenber der NoSQL-Bewegung

    und kritisiert die vollkommene Abkehr von bewhrten Konzepten. Nichtsdestotrotz

    spricht er einen Punkt an, der gerade auch fr Geodaten diskutiert werden muss. Die

    Haltung von Geodaten in Tabellen ist nicht intuitiv oder natrlich und erfordert weitrei-

    chende Kenntnisse zur Strukturierung der Daten. Dieses Kapitel soll zeigen, ob sich in

    den NoSQL-Datenbanksystemen Alternativen dazu finden lassen.

    3.1 Definition Geodaten

    Um die Komplexitt von Geodaten selbst zu erfassen, ist es hilfreich eine genaue Defi-

    nition zu betrachten. Ralf Bill gibt dafr folgenden Vorschlag:

    Geodaten sind Daten ber Gegenstnde, Gelndeformen und Infrastrukturen an der

    Erdoberflche, wobei als wesentliches Element ein Raumbezug vorliegen muss. []

    Geodaten lassen sich ber den Raumbezug miteinander verknpfen, woraus insbe-

    sondere unter Nutzung von GIS-Funktionalitten wiederum neue Informationen abge-

    leitet werden knnen [] (Bill 1999: 167). Besonders im Zusammenhang mit

    Datenbanken spricht man auch von Geoobjekten - elementaren oder auch

    zusammengesetzten Einheiten mit sowohl quantitativen (geometrischen und

    topologischen) als auch qualitativen (thematischen) Komponenten. Ein Objekt ist

    dabei eine konkrete, physisch, geometrisch oder begrifflich begrenzte Einheit der Natur

    und besitzt eine individuelle Identitt. (ebd.: 10f.) Die Geometrie eines Objekts kann

    dabei sowohl in Vektor- als auch Rasterdarstellung vorliegen, ihr Raumbezug indirekt

    oder direkt hergestellt sein. (ebd.: 11)

    Durch die weitreichende Definition von Geodaten unterscheidet sich auch die

    Komplexitt der unter Geodaten verstanden Informationen. Insbesondere Geoobjekte

    in Vektordarstellung stellen eine Herrausforderung fr die Wahl eines passenden

    Datenmodells dar. Das verbreitetste ist dabei das (objekt-)relationale Datenmodell.

  • 3 Anwendungspotential fr Geodaten 22

    3.2 Die Haltung von Geodaten in SQL-Datenbanken

    Fr die Verwaltung von Geodaten in einer relationalen Datenbank bestehen zwei

    grundlegende Lsungen. Zum einen ist eine Speicherung der Geometrie in der un-

    strukturierten Form eines Binary Large Objects (BLOB) mglich, zum anderen kann sie

    strukturiert unter Nutzung der numerischen Datentypen, die durch die Datenbank an-

    geboten werden gespeichert werden. Beide Methoden haben dabei Vor- und Nachteile:

    Die Speicherung als BLOB ist zwar einfach, der Zugriff muss aber in diesem Fall ber

    eine externe Anwendung sichergestellt werden und kann nur ber eine eigene API

    erfolgen. Es handelt sich um solche Anwendungsdaten, die vom Datenbanksystem

    gar nicht interpretiert, sondern nur gespeichert bzw. archiviert werden sollen (Kemper

    2011: 421). Auerdem muss die Sicherung der Konsistenten zwischen der Geometrie

    und den Sachdaten geregelt sein.

    Die Speicherung der Geometrie in strukturierter Form stellt die zweite Mglichkeit dar,

    bei der Topologie und Metrik mittels Normalisierung in Tabellenform abgebildet wird.

    Durch einen hohen Grad an Normalisierung ist es mglich Anomalien im Datenbestand

    Grtenteils vorzubeugen (ebd.: 179f.). Ein Nachteil ist jedoch, dass das Datenmodell

    damit sehr umfangreich wird und das Antwortverhalten auf komplexe rumliche Abfra-

    gen nicht optimal ist (Bill 1999: 318). Mchte man Geodaten in einer relationalen

    Datenbank in Abfragen zustzlich mit Sachdaten verknpfen fhrt dies je nach

    Anwendungsfall zu komplizierten Statements.

    Mit dem zunehmenden Erfolg objektorientierter Programmiersprachen haben Konzepte

    der Objektorientierung auch Einzug in die relationalen Datenbanken gehalten. Durch

    Typendeklaration und die Mglichkeit, Operationen auf diese Typen zu definieren,

    ergaben sich damit auch fr die Geodatenhaltung Vorteile, die in objektrelationelen und

    objektorientierten Datenbanken umgesetzt werden konnten. Als Standard hat sich in

    der GIS-Welt seit dem die OGC Simple Features Specification for SQL durchgesetzt

    welche von den verbreiteten Geodatenbanken wie Oracle Spatial oder PostGIS umge-

    setzt wird. Zunehmend wird dieses um Bestandteile des bedeutend umfangreicheren

    konzeptuellen Schema ISO 19107 erweitert.

    Der Entwicklungsstand dieser Geodatenbanken ist sehr hoch und stellt den aktuellen

    Stand der Technik dar, wozu insbesondere die weitreichenden

    Standardisierungbemhungen der OGC und der International Organisation for

    Standardisation (ISO) mit beigetragen haben. Soll die Eignung von NoSQL-

    Datenbanken fr Geodaten eingeschtzt werden, muss also an den Qualitten der

    aktuellen objektrelationalen Datenbanken Ma genommen werden, das heit, sie

    sollten zumindest diesen Stand erreichen oder andere Qualitten aufweisen, die sie fr

    die Nutzung interessant machen.

  • 3 Anwendungspotential fr Geodaten 23

    3.3 Skalierbarkeit vs. Komplexitt

    In Hinblick auf die der NoSQL-Datenbanken zugrundeliegenden Datenmodelle fllt die

    zunehmende Komplexitt auf, mit der Daten strukturiert abgelegt werden knnen. Die

    Ordnung in der die Datenbanken in Kapitel 2 vorgestellt wurden, ist dabei kein Zufall.

    Emil Eifrem, ebenfalls beteiligt am Dialog zur Kategorisierung der NoSQL-

    Datenbanken (s. Anhang 2), stellte dazu in einem Blog-Eintrag fest, dass die Komplexi-

    tt des Datenmodells der NoSQL-Datenbanken beginnend bei den Key/Value und Wi-

    de Column Stores, ber die Document Stores und schlielich bis hin zu den Graphda-

    tenbanken zunimmt. Daraus ergibt sich eine Wechselwirkung mit der Skalierbarkeit der

    Datenbank. Da Key/Value Stores und Wide Column Stores auf ein einfaches Daten-

    modell bauen, in denen die Datenstze keine bzw. geringe Beziehungen zueinander

    haben, ist es besser mglich, die Daten horizontal zu Partitionieren und auf mehrere

    Datenbankserver auszubreiten. Wie auch bei den SQL-Datenbanken ist dies bei-

    spielsweise fr Graphdatenbanken schwieriger, da engere Verknpfungen zwischen

    den Daten bestehen (Eifrem 2009). Um Leseleistung zu erhhen, bietet sich hier eher

    eine Replikation auf mehrere Server an, womit jedoch die Gre der Datenbank auf die

    Gre des kleinsten Servers beschrnkt bleibt.

    Abbildung 11: Die Komplexitt des untersetzten Datenmodells der NoSQL-Datenbanken un-terscheidet sich stark und steht in Wechselbeziehung mit der zu erwartenden Skalierbarkeit. (veranschaulichende Darstellung aus der Prsentation Emil Eifrems. (Eifrem 2009)

    Es muss allerding betont werden, dass diese berlegungen in vielerlei Hinsicht theore-

    tischer Natur sind, da die Anforderungen sehr hoch sein mssen, um die Kapazitt

    eines Servers zu berschreiten (Edlich 2011: 377). Auerdem verschiebt ein einfaches

  • 3 Anwendungspotential fr Geodaten 24

    Datenmodell die Komplexitt eine Stufe hher in die Anwendungsebene und er-

    schwert so die Implementierung. Dementsprechend sollte die Wahl der richtigen Da-

    tenbank nach dem Zweck ihrer Anwendung erfolgen. (Eifrem 2009). Dies gilt insbe-

    sondere auch fr die Verwaltung von Geodaten, denn der Nutzen, der aus Geodaten

    gezogen werden soll, ist jeweils sehr unterschiedlich.

    Wenn Web Services wie FourSquare oder Twitter Positionsdaten speichern und

    diese mit Beitrgen und Fotos koppeln, dann dient dies in erster Linie zur reinen Pr-

    sentation des Ortes. Die weitreichendste Analyse, die auf diese Daten angewandt wird,

    ist eine einfache Umkreissuche. Die Fragestellung Wer hlt sich in meiner Umgebung

    auf? oder Wo wurde dieses Foto aufgenommen? ist dabei keine zeitkritische, die

    immer korrekt beantwortet werden muss. Viel wichtiger ist es fr einen solchen Dienst-

    leister, alle zur Verfgung gestellten Informationen zu speichern und dabei auch zu

    Spitzenzugriffszeiten eine angenehme Nutzererfahrung zu gewhrleisten. Die quantita-

    tive Komponente des Geoobjekts Position beschrnkt sich in diesem Fall lediglich auf

    Punkte auf der Erde von denen anzunehmen ist, dass sie immer im gleichen Referenz-

    system vorliegen werden, also keine weitere Informationen gesammelt werden muss.

    In vielen Fllen ist die Positionsangabe auch nur optional und stellt so nur ein weiteres

    Attribut der eigentlichen Informationseinheit Statusmitteilung dar. Die Struktur der

    Daten ist hier also wenig komplex.

    Soll die Datenbank hingegen als Datenhaltungskomponente eines wertigen Geoinfor-

    mationssystems eingesetzt werden, stellen sich andere Anforderungen, denn allge-

    mein haben Geodaten eine viel komplexere Struktur. Auerdem ist hier der Anspruch

    an standardisierte Schnittstellen viel grer.

    Es soll gezeigt werden, wie diesen Ansprchen gerecht zu werden ist. Dazu wird im

    Folgenden in drei Ausprgungen von raumbezogenen Objekten unterschieden. Zum

    einen ist unter Positionsdaten eine Basisklasse von Objekten gemeint, dessen Geo-

    metrie lediglich aus einem Punkt besteht. Im speziellen bezieht sich dies auf eine Posi-

    tion, analog der Definition einer direkten Position in der Simple Feature Specification

    (OGC 2011: 9). Des Weiteren sollen komplexe Geodaten raumbezogene Daten nach

    dem Vektormodell beschreiben. Dies sind Daten, die im eigentlichen Sinne komplexe,

    auf punkt- und linienhaften Beschreibungen beruhende Datenstrukturen (Bill 1999: 21)

    darstellen. Abschlieend sollen Geodaten in einer Rasterdarstellung gesondert be-

    trachtet werden.

    3.4 Positionsdaten in NoSQL-Datenbanksystemen

    Lsst man in einem Vektormodell lediglich Punkte, also die Trger der geometrischen

    Information, zu, beschrnkt also die topologische Dimension auf 0-Zellen (Nullzellen),

    so liegen in diesem Modell keine topologischen Beziehungen zwischen Objekten vor.

  • 3 Anwendungspotential fr Geodaten 25

    Die Kante, als Trger der topologischen Information, fehlt (Bill 1999: 15,18). Nach Ralf

    Bill kann erst die Vereinigung von metrischen und topologischen Daten [] zu []

    umfassenden rumlichen Datenmodellen fhren, die in der Lage sind, auf einen

    breitgefcherten Abfrageraum zu antworten (edb.: 255). Das im vorherigen Kapitel

    gezeigte Beispiel zur Anwendung in Web Services hat aber gezeigt, dass solch ein

    breitgefcherter Abfrageraum nicht unbedingt ntig ist, um Anforderungen bestimmter

    Anwendungen zu befriedigen. Ist ein Modell ausschlielich bestehend aus

    Punktobjekten ausreichend, so erleichtert dies die Organisation in einer Datenbank

    enorm. Es handelt sich im Grunde genommen um ungeordnete raumbezogene Daten

    ohne die logische Zuordnung der Nachbarschaft wie sie durch Ralf Bill beschrieben

    sind (edb.: 241).

    Zu beachten ist, dass sich die Beschreibung fr ungeordneten raumbezogene Daten

    eigentlich auf Geometrieinformationen aus verschiedenen Quellen, wie beispielsweise

    Koordinatenlisten, bezieht. Deren Attribute bzw. Sachdaten knnten in

    unterschiedlicher Ausdehnung vorliegen. Dies ist durchaus ein Fall, der fr dynamische

    Webanwendungen eine Rolle spielen kann, beispielsweise um in einem neuen

    Konzept auch Bilder mit einer Georeferenz zu versehen. Sollen diese Daten in eine

    objektrelationale Geodatenbank gefhrt werden, so muss diese Ausdehnung der

    Attribute durch Normierung in eine einheitliche Dimension bzgl. der Tabellengre

    gebracht werden. (edb.: 241f.) Dabei bestehen zwei grundlegende Probleme, die

    bereits in Kapitel 1.7 angesprochen wurden:

    Neue Attribute machen eine Schemanderung der Relationen ntig, knnen

    aber zu vielen leeren Zellen im Datenbestand fhren.

    Referenzierungen fhren zu mehr Relationen und erschweren die Abfrage.

    Hier kann sich also ein Vorteil ergeben, wenn von Seiten der Datenbank kein Schema

    fr die Struktur der Daten vorrausgesetzt wird. In jener Hinsicht kommen NoSQL-

    Datenbanksysteme fr die Lsung der Aufgabe in Frage.

    Ein wesentlicher Nachteil der dabei jedoch bercksichtigt werden muss, ist, dass es fr

    Key/Value Stores und Wide Column Stores bis dato keine Spatial Extension gibt und

    das keiner der Vertreter dieser Kategorien eine native multidimensionale Indexierung

    untersttzt. (s. Anhang 2) Aus Kapitel 2 wissen wir allerdings, dass Document Stores

    wie CouchDB/GeoCouch oder MongoDB einen zweidimensionalen Index fr

    Punktgeometrien bieten.

    Die Implementierung ist bei beiden sehr unterschiedlich. Die CouchDB-Erweiterung

    berechnet einen persistenten R-Tree-Index auf Grundlage der Bounding Box der

    Geometrie (s. Anhang 1 und Katz 2012), MongoDB hingegen setzt auf einen

    Algorithmus namens GeoHash (Chodorow 2011). Das Grundprinzip beruht dabei auf

    einer hierachischen Teilung der Eroberflche in zunehmend kleinere Quadranten,

  • 3 Anwendungspotential fr Geodaten 26

    indem Lngen- und Breitengrad immer durch die Zahl 2 geteilt und so sukzessive

    einem Binrcode zugewiesen werden. Die Besonderheit des entstehenden Hashcodes

    ist dabei, dass die Auflsung der Quadranten durch die Anzahl der Stellen des

    Hashwerts beeinflusst werden kann und dass nah beeinander liegende Punkte meist

    den gleichen Prefix tragen. Wird die hinterste Stelle des Hashs gestrichen, vergrert

    sich so der durch den Wert dargestellte Quadrant (edb.). Der Geohash-Index ist bei

    einer Umkreissuche in den Grenzbereichen eines Quadranten nicht schlssig. Es kann

    also nicht immer angenommen werden, dass die ersten Stellen zwei sich nahe

    liegender Punkte den gleichen Prefix teilen. Dieses Problem kann allerdings

    weitestgehend ausgeglichen werden, indem die acht umliegenden Quadranten

    ebenfalls fr den Test genutzt werden.

    MongoDB nutzt dieses Prinzip sehr erfolgreich und konnte in der Vergangenheit viele

    Kunden gewinnen, die die Datenbank fr Geolocation Services einsetzen.

    Abbildung 12: Visualisierung der "Geohash Quadranten". (Troy 2008)

    3.5 Komplexe Geodaten in NoSQL-Datenbanksystemen

    Unter komplexen Geodaten sollen hier rumliche Objekte verstanden werden, deren

    Geometrie in Vektordaten beschrieben ist. Ihre Grundelemente sind der Punkt, die

    Linie und die Flche [] (Bill 1999: 21), wobei die graphische Grundstruktur aus

    Punkten und Linien besteht durch welche Flchen als geschlossener Linienzug darge-

  • 3 Anwendungspotential fr Geodaten 27

    stellt werden (ebd.). Ohne die im vorherigen Kapitel vorgestellten Beschrnkungen

    besteht die Geometrie von raumbezogenen Objekten nicht nur aus der metrischen In-

    formation des Punktes, sondern ist um topologische Beziehungen zwischen den Punk-

    ten bereichert.

    Die Haltung von solch komplexen raumbezogenen Daten in Datenbanken ist bekann-

    termaen nicht trivial. Diese Aufgabe wird allgemein zu den Nichtstandardanwendun-

    gen (NSA) von Datenbankmanagementsystemen (DBMS) gezhlt (Bill 1999: 327). Die

    Nichtstandardanwendung fr Geodaten hat dabei unter anderem die folgenden

    Charakteristiken:

    Die Daten sind typischerweise mehrdimensional und

    sollen durch rumliche Bereichsabfragen aufrufbar sein.

    Die Geometrien der Objekte knnen dabei aus einer Vielzahl logischer

    Verknpfungen bestehen, sie besitzen eine komplexe Struktur.

    Auerdem werden fr die Analyse raumbezogener Daten komplexer

    Operationen vorrausgesetzt.

    Aufgrund der Struktur und Gre der Objekte knnen Operationen auf

    raumbezogene Daten deshalb zu langen Transaktionen fhren (ebd.: 330).

    Um eine grobe Einschtzung treffen zu knnen, inwiefern diesen Anforderungen

    entsprochen werden kann, ist es hilfreich, einen kurzen Vergleich anzustellen.

    Mehrdimensionalitt: Das offensichtlichste Problem, das fr Geodaten geklrt werden

    muss, ist die Indexierung des multidimensionalen Raums. Die bereichsbezogene

    Abfrage stellt hier mehr die Regel als die Ausnahme dar, also sollte die Indexierung

    mindestens in X- und Y-Richtung mglich sein (Bill 1999: 330). Dieses Kriterium

    beschrnkt die Anzahl der Vertreter der NoSQL-Datenbanken auf sehr wenige die

    entsprechende Erweiterungen anbieten. In der hier getroffenen Auswahl bieten nur

    CouchDB mit den Spatial Extensions GeoCouch und Neo4j Spatial einen

    mehrdimensionalen Index, der rumliche Abfragen ber ihre API ermglicht. Alternativ

    knnen auch eigene Zugriffsmechanismen fr die Datenbank der Wahl konstruiert

    werden, allerdings ist dies auch mit einem gehrigem Mehraufwand fr die Umsetzung

    verbunden.

    Komplexe Strukturen: Der Umsetzung einer Vielzahl logischer Verknpfungen von

    Geodaten steht auerdem das zugrundeliegende Datenmodell der meisten NoSQL-

    Datenbanken entgegen, das auf Relationen zwischen den Datenstzen betont

    verzichtet. Das gilt insbesondere fr Key/Value und Wide Column Stores.

    Konsequenter ist hier die Speicherung im Binrformat oder in einer textlichen

    Reprsentation. Dies impliziert aber auch die gleichen Nachteile, wie sie bereits in

    Kapitel 3.2 fr SQL-Datenbanken in Bezug auf die Speicherung als BLOB beschrieben

  • 3 Anwendungspotential fr Geodaten 28

    worden sind. Wieder ist es die der Datenbank bergeordnete Ebene, die diese Daten

    interpretieren muss. Wie bereits durch Emil Eifrem festgestellt, verlagert sich die

    Komplexitt damit in die Anwendungsebene (Eifrem 2009). Es gilt die Entscheidung zu

    treffen, ob die damit verbundenen Nachteile fr die jeweilige Anwendung Sinn machen.

    Die Nutzung des MapReduce-Paradigmas fr exzessiv groe Datenmengen kann

    beispielsweise von Interesse sein und so die Nachteile aufwiegen. Document Stores

    bieten hingegen die Mglichkeit, Daten denormalisiert in einem Dokument abzulegen.

    Das macht die Datenverwaltung bersichtlicher und durch die Implementierung des

    MapReduce-Paradigmas knnen diese effektiv auf Sachdaten durchsucht werden.

    Graphdatenbanken beiten die weitreichste Mglichkeit Daten logisch zu Verknpfen

    und knnen durch Traversierungsalgorithmik auftrumpfen. Das macht sie fr komplexe

    Strukturen interessant.

    Komplexe Operationen: Neben den einfachen den CRUD-Operationen (Create,

    Read, Update, Delete) versteht man unter komplexen Operationen fr Geodaten

    bespielsweise das Verschneiden, die Ein- und Ausschlussberechnung oder das

    Clipping von raumbezogenen Objekten (Bill 1999: 330). Nach der Definition der

    NoSQL-Datenbank bieten diese aber ganz bewusst nur eine sehr einfache API an, um

    so den Zugang fr die Programmierung zu erleichtern (Edlich 2011: 2). Auf Grundlage

    dieser APIs kann es mglich sein, Operationen auf die in der

    Datenhaltungskomponente abgelegten Objekte zu implementieren, aber auch das ist

    mit dem ntigen Aufwand verbunden. Die Spatial Extension Neo4j Spatial bietet hier

    weitreichende Funktionalitt, um raumbezogene Analysen durchzufhren und kann

    diesen Punkt als einzige bedienen.

    Lange Transaktionen: Das Thema der langen Transaktionen spielt auch fr NoSQL-

    Datenbanken eine entscheidene Rolle. Es findet eher der optimistische Ansatz per

    Versionierung der Datenstze Anwendung. Dadurch ist der Zugriff auf den

    Datenbestand nicht fr weitere Nutzer gesperrt. Andererseits muss auch hier von der

    Anwendungsebene bestimmt werden, wie mit Konflikten umgegangen wird. Aber auch

    pessimistische Transaktionen werden durch NoSQL-Datenbanken bedient. Neo4j

    erlaubt beispielsweise sowohl eine Lese- als auch Schreibsperre auf die betreffenden

    Knoten und Kanten. Das entspricht weitesgehend der Umsetzung durch die meisten

    SQL-Datenbanken. Eine optimale Lsung ist hier nicht zu erreichen.

  • 3 Anwendungspotential fr Geodaten 29

    Tabelle 1: Eigenschaften von NoSQL-Datenbanken in Relation zu Charakteristiken von Nicht-standardanwendungen.

    Key/Value Store Redis (VMWare 2011b und 2011d)

    Wide Column Store Cassandra

    Document Store CouchDB mit GeoCouch (Katz und Mische 2012)

    Graphdatenbank Neo4j mit Neo4j Spatial (NeoTechnology 2012 und Edlich 2011: 291)

    Mehrdimensionaler Index

    Nein Nein Ja Ja

    Bereichsabfragen Nur in Listen & Sets

    Ja, Columns und Column Families sortiert

    Ja Ja

    Vielfache logische Verknpfung

    Nein, binrsichere Speicherung von Objekten

    Nein, einfache Strukturierung und binrsichere Speicherung von Objekten

    Nein, schemafreie Dokumente

    Ja, durch Traversierung

    Komplexe Operationen

    Nein Nein Nein Ja

    Transaktionen Ja Nein Ja, MVCC ACID und Bulk

    Betrachtet man die Eigenschaften der NoSQL-Datenbanken bzw. hier spezieller der

    vorgestellten Vertreter der Datenbankkategorien, sieht man sich besttigt, dass das

    Datenmodell einen erheblichen Einfluss auf die Eignung fr die

    Datenhaltungskomponente in einem Geodatenbanksystem hat. Mangels

    entsprechender Erweiterungen kommen Key/Value und Wide Column Stores leider nur

    in Frage, wenn die zu erwartende Datenmenge wirklich dem Vielfachen entspricht, das

    mit einer herkmmlichen Geodatenbank verarbeitet werden kann. Zugegebener Maen

    ist der Aufwand, die Datenstze in ihnen zu pflegen bedeutend hher, als der Nutzen

    fr ein mittelgroes GIS sein kann.

    Fr Document Stores sieht das schon anders aus. Sie bieten durch das Konzept

    schemaloser Dokumente zusammen mit einer multidimensionalen Abfragemglichkeit

    via Spatial Extension und der Implementierung von MapReduce eine interessante

    Alternative zur Haltung von Geodaten in einer SQL-Datenbank. Um sich dem

    umfassender zu widmen, soll die Implementierung einer Anwendung mit CouchDB und

    GeoCouch in Kapitel 4 gesondert betrachtet werden.

    Auch Graphdatenbanken nehmen in diesem Vergleich eine gewisse Sonderstellung

    ein. Sie ermglichen eine ebenso komplexe Strukturierung von Daten wie dies die

    relationalen Datenbanken tun. Darber hinaus bieten sie ein Datenmodell das diese

    besser nachvollziehbar macht. Gerade fr die Geodatenhaltung ist das Modellieren von

    Topologie eine bedeutende Herrausforderung. Deshalb soll die Implementierung einer

    Anwendung zur Analyse von Geodaten in Kapitel 5 eine weitere Rolle spielen.

  • 3 Anwendungspotential fr Geodaten 30

    3.6 Rasterdaten

    Neben den bereits besprochenen Vektordaten nimmt die Verwaltung von Rasterdaten

    in Geoinformationssystemen eine wichtige Rolle ein. Die graphische Grundstruktur von

    Rasterdaten ist das Pixel welches zeilen- und spaltenweise in einer Matrix

    gleichfrmiger, quadratischer oder rechteckiger Elemente angeordnet ist (Bill 1999:

    22). Es gibt keine Unterscheidung nach Punkt, Linie oder Flche, das heit, es

    existieren keine logischen Verbindungen zwischen den einzelnen Bildelementen

    (ebd.). Die Datenstruktur ist also bedeutend einfacher als die der strukturierten

    Vektordaten und Analysen basieren auf simpleren Algorithmen. Da der Speicherbedarf

    von Rasterdaten den von Vektordaten aber typischerweise bei weitem bertrifft, ist die

    Ausfhrung von Berechnungen deshalb nicht schneller (Schneider 1993: 7). Die Daten

    knnen beispielsweise als Satellitenaufnahmen der Fernerkundung vorliegen oder als

    Scans bestehender Kartenwerke.

    Ein interessantes Beispiel fr die Handhabe von Rasterdaten in einer NoSQL-

    Datenbank gibt Google durch sein Produkt Google Earth. Die Haltung und Aufberei-

    tung wird nach eigner Aussage in Google BigTable verwirklicht. 2006 ist die Tabellen-

    gre allein mit 70 Terrabyte angegeben. Whrend allein das Speichern einer solchen

    Datenmenge auf einem Rechner unmglich ist, sind Berechnungen auf eine solch

    enorme Menge von Daten nur durch massive Parallelisierung mglich. Um die Satelli-

    tenbilder letztendlich fr die Darstellung im Browser oder der Clientanwendung Google

    Earth aufzubereiten, wird das MapReduce Framework eingesetzt, welches die Daten

    bereinigt und letztendlich in geographische Segmente teilt. Eine weitere, bedeutend

    kleinere Tabelle von 500GB hlt auerdem die Indexierung des Bildmaterials im ver-

    teilten Dateisystem GFS vor und dient zur Interaktion mit dem Nutzer. Allein diese Ta-

    belle ist ber hunderte von Server gehostet, um zehntausende Anfragen pro Sekunde

    zu befriedigen (Chang 2006: 10f.). Whrend die Haltung von solchen Datenmengen

    eher die Ausnahme ist, verdeutlicht Google damit aber das enorme Leistungspotential

    das von verteilten Systemen ausgeht.

    3.7 Zuknftige Entwicklungen

    Neben der eigentlichen Datenhaltung spielt gerade auch die Interoperabilitt von geo-

    referenzierten Daten zwischen verschiedenen Systemen eine wichtige Rolle und stellt

    ein altes Problem dar (de Souza Baptista 2011). Durch die Entwicklung der NoSQL-

    Datenbanken ist denkbar, dass etwa CouchDB, Neo4j oder MongoDB zu einer hetero-

    generen Landschaft im Umfeld der Geoinformation fhren knnen. Darber hinaus ist

    es auch fr die Nutzer klassischer SQL-Geodatenbanken interessant, Informationen

    aus dem Umfeld der Social Networks in Analysen einzubeziehen, denn hier hat NoSQL

    bereits viel Anwendung gefunden. Es wird also in Zukunft unumgnglich sein, sich um

  • 3 Anwendungspotential fr Geodaten 31

    Schnittstellen zwischen den Welten zu bemhen, um so den Informationsfluss zu fr-

    dern.

    Der wohl berzeugendste Weg, ist es auf bereits bestehende Standards zurckzugrei-

    fen. Neben dem Im- und Export ber bekannte Formate, ist die Implementierung von

    Web Services wie dem OGC Web Map Service (WMS) und dem Web Feature Service

    (WFS) die lohnenswerteste, da so jeder Client mit Untersttzung dieser Services Zu-

    griff auf die Daten erhalten kann. Cludio de Souza Baptista et al. haben mit dieser

    Begrndung einen ersten erfolgreichen Vorschlag geleistet, wie eine solche Schnittstel-

    le fr GeoCouch aussehen kann. Sie nutzten den modularen Aufbau CouchDBs, um

    einen Service Layer fr die NoSQL-Datenbank zu integrieren.

    Nicht zuletzt zeigt auch die Integration des CouchDB-Treibers in die GDAL-Bibliothek

    ab Version 1.9 (GDAL 2011), dass gerade von Seiten der OpenGIS-Bewegung reges

    Interesse an solchen Speziallsungen bestehen muss. GDAL dient vielen O-

    penSource-Projekten wie QGIS und uDIG als abstraktes Datenmodell fr den Zugriff

    auf Geodaten. So kann erwartet werden, dass ber kurz oder lang auch CouchDB in

    diese Lsungen integriert werden wird. Wnschenswert ist, dass auch andere NoSQL-

    Datenbanken sich diesem Trend in Zukunft anschlieen.

    Interessant ist in diesem Zusammenhang auch, dass am 1. November 2011 das Open

    Geospatial Consortium die Grndung einer Arbeitsgruppe zur Ausarbeitung eines OGC

    Standards fr RESTful Web Services verkndet hat. Das erwartete Ergebnis dieser

    Arbeitsgruppe ist eine formalisierte Regelung fr die standardisierte Implementierung

    von REST-Services fr geographische Abfragen (Open Geospatial Consortium 2011)

    Whrend auch kommerzielle Anbieter wie ESRI Interesse an einer solchen

    Standardisierung haben drften, kann dies auch fr Vertreter der NoSQL-Datenbanken

    von Interesse sein.

  • 4 Implementierung einer Webprsenz fr Geodaten mit CouchDB und GeoCouch 32

    4 Implementierung einer Webprsenz fr Geodaten

    mit CouchDB und GeoCouch

    Geodaten dienen vielen verschiedenen Zwecken. Neben der Pflege komplexer Daten

    in den Vermessungsverwaltungen und der Analyse von Raumdaten durch Spezialisten

    dienen sie hufig zur anschaulichen Prsentation von Sachverhalten unserer Umwelt.

    Eine typische Lsung einer solchen Prsentation besteht in der Bereitstellung einer

    Website, die einen WFS oder WMS-Service via Geoserver abruft. Dieser liest Daten

    aus einer objektrelationalen Geodatenbank wie PostGIS.

    Da CouchDB einen HTTP-Server integriert und GeoCouch grundlegende rumliche

    Abfragen erlaubt, soll diese Pilotanwendung zeigen, wie die Umsetzung einer solchen

    Prsentation stark vereinfacht ablaufen kann. Zweck der Aufgabe ist es, auf einen

    WFS oder WMS-Server zu verzichten und sowohl Webseite als auch Geodaten ber

    eine CouchDB-Instanz zur Verfgung zu stellen. Die einzelnen Schritte umfassen da-

    bei:

    Geodaten in CouchDB einlesen

    Mit der Erweiterung GeoCouch vertraut machen und einen Abfragemechanis-

    mus definieren

    Webseite ber CouchDB hosten

    Datengrundlage sollen dabei ffentlich verfgbare Geodaten sein, wie sie von ffentli-

    chen Trgern angeboten werden. Dies umfasst insbesondere Informationen zu Lan-

    despflege und Naturschutz, wie sie beispielsweise auch in den Bestnden des Landes

    Brandenburg zu finden sind. Sie knnen unter der Website

    http://www.mugv.brandenburg.de/cms/detail.php/bb2.c.515599.de (Lukas 2012) abge-

    rufen werden und sollen in diesem Entwurf als Datengrundlage fr eine digitale ber-

    sichtskarte dienen, die es Interessierten ermglicht, sich ber Naturschutz im Land

    Brandenburg zu erkundigen.

    Zur Umsetzung kommt CouchBase Single Server Version 1.2 als vorkompiliertes Pa-

    cket aus CouchDB 1.1.0 und GeoCouch zum Einsatz. Auerdem findet die Folgende

    Software Anwendung:

    GDAL Library 1.9

    jQuery 1.7.1

    Leaflet.js 0.3.1

  • 4 Implementierung einer Webprsenz fr Geodaten mit CouchDB und GeoCouch 33

    4.1 Vorbereitung der Daten fr CouchDB

    Wie bereits in Kapitel 2.4.2 vorgestellt, erwartet CouchDB Daten im JSON-Format. Die

    vom Brandenburger Ministerium bereitgestellten Daten liegen allerdings als Shapefiles

    vor und mssen zunchst entsprechend umgewandelt werden. Auerdem ist es sinn-

    voll, vom durch das Land Brandenburg genutzten Koordinatenreferenzsystem ETRS89

    BB in WGS84 zu transformieren. Dies erleichtert spter die Integration in bestehende

    Mapping-Frameworks, ist aber ein optionaler Schritt. Beide Operationen sind mit dem

    durch die Open Source Geospatial Foundation (OSGEO) befrderten Framework

    GDAL (Geospatial Data Abstraction Library) bzw. der enthaltenen Sub-Library OGR

    mglich. Mit Version 1.9 wurde die OGR Simple Feature Library um eine Schnittstelle

    fr CouchDB erweitert, die die bereits bestehende GeoJSON Untersttzung nutzt, um

    Geodaten so per HTTP-PUT auf eine CouchDB zu bertragen.

    Die Transformation mit dem Konsolentool OGR2OGR sieht dabei folgendermaen aus:

    $ ogr2ogr -t_srs EPSG:4326 output_4326.shp input.shp

    Beim bertragen der Daten auf eine CouchDB-Instanz kann auerdem ein Admin-

    Zugang spezifiziert werden:

    $ ogr2ogr -f couchdb "couchdb:http://user:pwd@host:port" output_4326.shp

    OGR2OGR legt pro Feature je ein JSON-Dokument in die Datenbank, welches die

    Geometrie als GeoJSON-Objekt enthlt. Im Beispiel wird dieses Dokument in die Da-

    tenbank output_4326 hinterlegt. Bestehende Attribute und Metadaten werden im

    JSON-Objekt properties abgelegt, wodurch das Dokument nun ber die URI

    http://host:pwd/output_4326/_id verfgbar ist. Mit dem erstmaligen Speichern des

    JSON-Dokuments wird durch CouchDB ebenfalls eine Revisionsnummer _rev ange-

    legt, die fr die MVCC-Versionierung genutzt wird.

  • 4 Implementierung einer Webprsenz fr Geodaten mit CouchDB und GeoCouch 34

    {

    "_id": "000000202",

    "_rev": "1-57b1dffc6a3c47d428252db519fad50f",

    "type": "Feature",

    "properties": {

    "AST__NR": "1068456000",

    "NAME": "Global Wind Power A/S",

    "ANL__NR": "4016",

    "BEZEICHNUN": "WKA NEG Micon NM 82/1500",

    []

    "ROTORDURCH": "82",

    "NABENHOEHE": "108"

    },

    "geometry": {

    "type": "Point",

    "coordinates": [

    12.271748312990185,

    52.895952732225524

    ]

    }

    }

    Abbildung 13: JSON-Dokument eines Features des Typs Point. (gekrzt)

    4.2 Abfrage der Datenstze aus CouchDB

    Die einfachste Abfragemglichkeit ist der direkte Zugriff auf ein Dokument ber den

    Namen der Datenbank und den Identifikator in der Form:

    http://host:port/db/_id

    Die Antwort erfolgt als HTTP-Response, dessen Krper das Dokument als JSON-

    Objekt enthlt.

    Um umfangreichere Abfragen auf Grundlage der Dokumente zu verwirklichen, kann ein

    View eingesetzt werden. Sie werden in Design-Dokumenten als JavaScript-

    Funktionen definiert und unter dem Attribut views gespeichert. Dadurch sind sie unter

    der URI des Designdokuments und dem Zusatz _view/viewname identifizierbar. So ist

    es mglich, per MapReduce-Verfahren nach Untermengen des Datenbestands zu fil-

    tern und die Ergebnismenge als Ressource des HTTP-Servers abzufragen.

    function(doc) {

    if(doc.properties) {

    emit(doc.properties.BEZEICHNUN, doc.properties.LEISTUNG)

    }

    }

    Abbildung 14: Eine einfache Map-Funktion. Sie durchluft jedes Dokument der Datenbank, testet, ob das JSON-Objekt properties vorhanden ist und emittiert das Attribut BEZEICHNUN als Key bzw. LEISTUNG als Value. ber eine optionale Reduce-Funktion liee sich das Er-gebnis der Map-Funktion aggregieren.

  • 4 Implementierung einer Webprsenz fr Geodaten mit CouchDB und GeoCouch 35

    Die Ergebnismenge einer MapReduce-Funktion wird durch CouchDB mit der ersten

    Abfrage indexiert. Spter hinzugefgte Datenstze werden mit jeder weiteren Abfrage

    sukzessive im Index eingepflegt.

    function(doc) {

    if(doc.geometry) {

    emit(doc.geometry, doc.properties);

    }

    }

    Abbildung 15: Geometrie emittierende Map-Funktion. Sofern vorhanden, wird das (GeoJSON) Objekt "geometry" als Schlssel emittiert. Die Eigenschaften properties schlieen als Values der Ausgabeliste an.

    Diese Map-Funktion allein untersttzt noch keine rumlichen Suchanfragen. Wrde sie

    in einem Designdokument einfach als View gespeichert werden, wre mit dem ersten

    Abrufen ein B-Tree-Index angelegt, wie er auch fr jeden anderen eindimensionalen

    View eingesetzt wird. Die Spatial Extension GeoCouch erweitert hier die Indexierungs-

    fhigkeiten um einen R-Tree-Index. Um diesen zu nutzen, wird die Mapping-Funktion

    im Designdokument unter dem Attribut spatial gespeichert.

    {

    "_id": "_design/technik",

    "_rev": "1-b5319680744d68d3a7ab145623fc18a9",

    "spatial": {

    "pos":

    "function(doc) {

    if (doc.geometry){

    emit(doc.geometry, doc.properties);

    }

    }"

    }

    }

    Abbildung 16: Design-Dokument. Das Dokument "technik" umfasst nur den Spatial-View "pos".

    Um anschlieend eine rumliche Abfrage durchzufhren, wird die URI, welche auf das

    definierte Design-Dokument zeigt, um den Parameter _spatial, den Namen des Spa-

    tial Views sowie die gesuchte Bounding Box ergnzt. Eine rumliche Abfrage der ent-

    haltenen Features im umschlieenden Rechteck mit den Koordinaten [(52,13),

    (53,14)] auf das Designdokument technik und dessen Spatial-View pos wrde wie

    folgt lauten:

    http://host:port/wka_4326/_design/technik/_spatial/pos?bbox=13,52,14,53

    Zu beachten ist, dass die Implementierung dem Entwurf der OpenSearch Spezifikation

    fr Geodaten folgt. Auch dieser empfiehlt die Nutzung des EPSG:4326 und setzt die

  • 4 Implementierung einer Webprsenz fr Geodaten mit CouchDB und GeoCouch 36

    Konstruktion des umschlieenden Rechtecks in der Form minX, minY, maxX, maxY

    voraus. Achtung muss hier beim berspannen der Datumsgrenzen geboten sein. In

    der aktuellen Version von GeoCouch fr CouchDB 1.2.x steht die Bounding Box Suche

    als einzige rumliche Funktion zur Verfgung.

    Die nachfolgende Antwort der CouchDB-Instanz entspricht einem JSON-Dokument,

    das die ermittelten Datenstze im Objekt rows als Array von JSON Objekten enthlt:

    {

    "update_seq":3475,

    "rows":[{

    "id":"000000989",

    "geometry":{

    "type":"Point",

    "coordinates":[13.53925025567202,52.60986928248099]

    },

    "value":{

    "AST__NR":"2060379000",

    "NAME":"Phase 5 GmbH & Co Lindenberg 4 KG",

    "ANL__NR":"0001",

    []

    "GEN_NIB":"ja",

    "GEPLANT":null,

    "ROTORDURCH":"92",

    "NABENHOEHE":"100"

    }},

    []

    ]

    }

    Abbildung 17: Antwortdokument eines Bounding Box Querys. (Gekrzt)

    4.3 Abfrage von Datenstzen als FeatureCollection

    Bei dem im HTTP-Body erhaltenen JSON-Dokument einer CouchDB-Abfrage handelt

    es sich nicht um ein GeoJSON-Objekt, sondern um ein valides JSON. Das heit, dass

    die gewonnen Datenstze in dieser Form nicht weiter fr Mapping-Aufgaben genutzt

    werden knnen, ohne dass GeoJSON-Objekt (geometry) zu extrahieren und die ge-

    wnschten Attribute mit anzufhren.

    CouchDB bietet hier mit der Funktion List ein mchtiges Werkzeug. Sie verarbeitet

    die Zeilen der Ergebnisliste einer Mapping-Funktion und formatiert sie nach einer ge-

    whlten Vorschrift in eine Liste von Objekten. Abbildung 18 zeigt hierfr eine Ja-

    vaScript-Funktion, welche eine Ergebnisliste mit den Spalten geometry und value in

    eine GeoJSON-FeatureCollection wandelt.

  • 4 Implementierung einer Webprsenz fr Geodaten mit CouchDB und GeoCouch 37

    function(head, req) {

    var row, out, sep = '\\n';

    if (typeof(req.headers.Accept) != "undefined"

    && req.headers.Accept.indexOf('application/json')!=-1)

    start({"headers":{"Content-Type" : "application/json"}});

    else

    start({"headers":{"Content-Type" : "text/plain"}});

    if ('callback' in req.query)

    send(req.query['callback'] + "(");

    send('{"type": "FeatureCollection", "features":[');

    while (row = getRow()) {

    out = '{"type": "Feature", "id": ' + JSON.stringify(row.id);

    out += ', "geometry": ' + JSON.stringify(row.geometry);

    delete row.geometry;

    out += ', "properties": ' + JSON.stringify(row.value) + '}';

    send(sep + out);

    sep = ',\n';

    }

    send("]}");

    if ('callback' in req.query) send(")");

    };

    Abbildung 18: List-Funktion. Sie wandelt die Ergebnisse eines GeoCouch Spatial-Views in eine GeoJSON-FeatureCollection. (Ogden 2011)

    4.4 Integration der GeoCouch-Daten in eine Website

    Um die Geodaten verfgbar zu machen, sollen sie als ein Vektorlayer auf einer Karte

    dargestellt werden. Die Implementierung erfolgte in HTML und JavaScript, wobei die

    Leaflet-Karte in einen div-Block eines einfachen *.html-Dokuments eingebunden wur-

    de. Das Abrufen der Kartenwerke und weitere Zusatzfunktionen sind ebenfalls mit

    Leaflet implementiert und hier nicht weiter beschrieben.

    Um den Datenfluss auf ein Minimum zu reduzieren und so den Kartenaufbau zu be-

    schleunigen, ist es mglich, ber die Methode getBounds() der Leaflet-Karte die aktuel-

    le Ausbreitung der Karte abzufragen. Diese knnen als Parameter im AJAX-Request

    an die CouchDB bergeben werden, wie es in 5.3.3 bereits beschrieben wurde. Die in

    der aktuellen Ausbreitung befindlichen Features knnen auf diese Weise bestimmt und

    durch die in Abbildung 19 gezeigte Map-Funktion pos als Ergebnisliste emittiert wer-

    den. Die Liste wird anschlieend durch die in Abbildung 18 vorgestellte List-Funktion in

    eine GeoJSON-FeatureCollection gewandelt und so als Antwort bertragen.

  • 4 Implementierung einer Webprsenz fr Geodaten mit CouchDB und GeoCouch 38

    function loadPlacesWka(bounds) {

    $.ajax( {

    type: 'GET',

    url: 'http://localhost:5984/wka_4326/' +

    '_design/simplegeo/_spatial/_list/geojson/pos?bbox='

    + bounds._southWest.lng + ','

    + bounds._southWest.lat + ','

    + bounds._northEast.lng + ','

    + bounds._northEast.lat,

    dataType: 'json',

    success: function (data) {

    []

    wkaGeoJSON.on("featureparse", function (e) {

    var popupContent = '

    ';

    if (e.properties && e.properties.NAME){

    popupContent+='Name: ' + e.properties.NAME + '
    '

    }

    []

    popupContent+='

    ';

    if (popupContent!='

    ') {

    e.layer.bindPopup(popupContent);

    }

    });

    wkaGeoJSON.addGeoJSON(data);

    map.addLayer(wkaGeoJSON);

    layersControl.addOverlay(wkaGeoJSON, "Windkraftwerke");

    },

    error: function (req, status, error) {

    alert('Unable to get data:' + error);

    }

    });

    Abbildung 19: AJAX-Request an eine CouchDB. Hier wird das Design-Dokument simplegeo in der Datenbank wka_4326 angefragt. Die darin gespeicherte List-Funktion geojson wandelt dann das Ergebnis des Spatial-View pos, der mit den Parametern einer Bounding Box aufge-rufen wurde, um. Die nachfolgenden Methoden im Krper der success-Funktion sind Bestand-teil des Leaflet.js-Frameworks und parsen die gewonnene FeatureCollection fr die Darstellung.

    Da neben der eigentlichen Geometrie auch die Sachdaten im JSON-Objekt properties

    bermittelt werden, knnen diese als interaktive Marker auf der Karte eingebunden und

    dem Nutzer verfgbar gemacht werden. Mit einem Mausklick auf das zu untersuchen-

    de Feature lassen sich so weitere Informationen abrufen (s. Abbildung 19).

    Die Webseite und alle referenzierten JavaScript-Dateien wurden anschlieend als At-

    tachement an ein Design-Dokument angehangen. So ist der Zugriff per URI der Web-

    seite als Anhang des Designdokuments in der Form

    http://host:port/db/_design/technik/index.html mglich.

  • 4 Implementierung einer Webprsenz fr Geodaten mit CouchDB und GeoCouch 39

    Abbildung 20: Screenshot der Konzeptanwendung "Brandenburger Schutzgebiete". Durch Klicken auf eines der Features wurden hier Zusatzinformationen zu einem Wasserschutzgebiet aufgerufen. Auerdem sind Windkraftwerke (blaue Marker) und ein Schutzgebiet (grnes Poly-gon) in der nheren Umgebung eingeblendet.

    4.5 Fazit

    Das Aufsetzen einer Webprsentation von Geodaten hat sich als sehr einfach und

    praktikabel erwiesen. Der Verwaltungsaufwand ist gering, da fr die zu verwaltenden

    Dokumente kein Schema angelegt werden muss. Im Ergebnis sind alle Komponenten

    dieser Anwendung ber einen einzige Server verfgbar die beginnend mit der Websei-

    te aus der CouchDB-Instanz geladen werden. Die Reihenfolge sieht dabei folgender-

    maen aus:

    Anfrage des index.html-Dokuments ber die URI

    Referenzierte JavaScript-Bibliotheken werden nachgeladen

    Interaktive Karte wird initialisiert und Features werden asynchron abgefragt und

    als Vektorlayer auf die Karte gemappt

    Durch die Formatierungsmglichkeiten der List-Funktion bieten sich vielfltige Schnitt-

    stellen, da Geodaten, wenn auch mit einem hheren ersten Aufwand, an das ge-

    wnschte Mapping-Framework angepasst werden knnen.

    Zu beachten ist, dass die erste Indexierung als R-Tree fr groe Datenbestnde zeit-

    aufwndig ausfallen kann. Dies sollte beim Erstellen einer Webprsens bercksichtigt

    werden, um Nutzern die Wartezeit zu ersparen. Nachdem der Index bereitsteht, wer-

    den neue Features mit dem ersten Aufruf in den Index eingepflegt, er muss also nicht

    komplett neu generiert werden. Des Weiteren fiel im Testbetrieb und speziell beim Tes-

    ten verschiedener Spatial Views auf, dass der Index eines Views sehr schnell viel

  • 4 Implementierung einer Webprsenz fr Geodaten mit CouchDB und GeoCouch 40

    Speicherplatz in Anspruch nehmen kann. Um Speicherplatz zu sparen, ist es sinnvoll,

    alte Views durch den Compaction-Befehl zu entfernen, der durch CouchDB bereitge-

    stellt wird.

    Die Abfragemglichkeiten beschrnken sich im Moment auf einfache Bounding Box

    Queries. In Kombination mit dem angewandten MapReduce-Verfahren und den Forma-

    tierungsmglichkeiten lsst sich dies fr mchtige Sachabfragen mit geographischem

    Bezug einsetzen. Fr umfangreiche Analysen ist GeoCouch aber zum gegenwrtigen

    Zeitpunkt nicht einsetzbar. Es ist auch fraglich, ob dies ein erklrtes Ziel fr das Ge-

    oCouch-Team sein wird. Nichtsdestotrotz sind nach eigenen Aussagen des Ge-

    oCouch-Programmierers Volker Mische weitere Funktionen in Arbeit (s. Anhang 1).

  • 5 Navigationsanwendung mit Neo4j Spatial 41

    5 Navigationsanwendung mit Neo4j Spatial

    Die Suche nach einem Weg zwischen zwei Punkten ist eine der grundlegenden Fra-

    gen, die durch Geodaten beantwortet werden knnen. Die Suche lsst sich durch Be-

    dingungen, wie das Finden des krzesten oder schnellsten Weges, beliebig erweitern.

    Die Beschreibung eines solchen Weges wird sich allgemein auf die einzelnen Weg-

    punkte und die Folgerichtung beziehen die dabei passiert werden mssen. Im Grunde

    lsst sich dieses Problem also auf einen Graphen reduzieren, dessen Knoten die

    Wegpunkte und dessen Kanten die Wege zwischen diesen Punkten beschreibt. Ent-

    scheidend fr das Traversieren eines solchen Graphen ist in erster Linie nicht die Met-

    rik der Punkte, sondern ihre Topologie. Diese sollte sich in einer Graphdatenbank wie-

    dergeben lassen.

    Im Folgenden soll ein Beispiel fr eine solche Problemlsung gegeben werden, bei

    dem topologisch strukturierte Geodaten in die Graphdatenbank Neo4j importiert wer-

    den und anschlieend zwischen gegebenen Start- und Zielkoordinaten der krzeste

    befahrbare Weg ermittelt wird.

    Fr die Implementierung in Java kommt Neo4j Community Edition in der Version 1.6

    und die Spatial Extension Neo4j Spatial als Development Snapshot Version 0.8 zum

    Einsatz. Beide stehen unter der GPL. Neo4j Spatial baut auf das OpenGIS GeoTools

    Toolkit auf, welches in Version 8.0 Milestone 4 bereitsteht.

    5.1 Vorbereitungen

    Neo4j implementiert beruhend auf der Graphentheorie bereits umfassende Algorith-

    men, um die Datenstze im Graphen zu traversieren. Am einfachsten ist dies in der

    Webkonsole des Datenbankservers zu testen (s. Kapitel 2.5.2). Die Abfrage erfolgt mit

    der Traversierungssprache Cypher.

    neo4j-sh (0)$ START a=node(2093), x=node(6)

    MATCH p = shortestPath( a-[*..15]-x ) RETURN p

    ==> +----------------------------------------------------+

    ==> | p |

    ==> +----------------------------------------------------+

    ==> | (2093)(6) |

    ==> +----------------------------------------------------+

    ==> 1 rows, 1 ms

    Abbildung 21: Abfrage des krzesten Pfads der Lnge 2 zwischen den Knoten mit der ID 2093 und 6. Das MATCH-Statement gibt hier Bedingungen fr die Traversierung der Kanten im Graph. Da nicht explizit ein Label in der Form [:LABEL] angegeben ist, werden alle in Frage kommenden Beziehungen durchlaufen. Der Parameter *..15 beschrnkt die Suche dabei auf maximal 15 Schritte.

    Die in Abbildung 21 gezeigte Berechnung des krzesten Pfades bezieht sich auf einen

    ungewichteten Graphen und zhlt lediglich die zurckgelegten Schritte. Soll sich die

  • 5 Navigationsanwendung mit Neo4j Spatial 42

    Auswertung auf die tatschliche geometrische Lnge beziehen, wie es von einer Navi-

    gationsanwendung erwartet werden wrde, so msste das Gewicht der Kante also

    entweder implizit aus den Eigenschaften der Knoten berechnet werden oder explizit als

    Gewicht der Kante verfgbar sein.

    5.2 Datengrundlage

    Als Datengrundlage fr den Prototypen einer Navigationsanwendung sollen die Vek-

    tordaten des OpenStreetMap-Projekts dienen. Sie knnen direkt auf der Website

    http://www.openstreetmap.org/ im OpenStreetMap-XML-Format exportiert werden.

    Alternativ bieten andere Webseiten Datenstze, an die das Downloadlimit des OpenSt-

    reetMap-Projekts berschreiten. Unter http://download.geofabrik.de/osm/ sind tagesak-

    tuelle Datenstze ganzer Kontinente und Staatsgebiete sowohl als OSM (OpenStreet-

    Map-XML) als auch Shapefiles verfgbar (Geofabrik GmbH 2012). Das Standardformat

    fr Geo-Vektordaten ESRI Shapefile bietet allerdings keine persistente Speicherung

    von Topologien. Das bedeutet, dass sie durch die verarbeitende Anwendung erzeugt

    werden muss. Fr diese Pilotanwendung kommt deshalb das semi-strukturierte OSM-

    Format in Frage, welches die von Nutzern gesammelten Informationen in folgender

    Gestalt aufbereitet darstellt:

    ...

    ...

    ...

    ...

    Abbildung 22: Gekrztes Beispiel einer OSM-XML-Datei. (OpenStreetMap Wiki 2011).

    Neo4j Spatial implementiert in der aktuellen Version mehrere Mglichkeiten, Geodaten

    einzupflegen. Neben dem Einlesen der Geometrie als Well-known Text oder Well-

    known Binary steht die Mglichkeit des Imports von Shapefiles und OSM-Dateien be-

    reit.

  • 5 Navigationsanwendung mit Neo4j Spatial 43

    GraphDatabaseService databaseService = new EmbeddedGraphDatabase(storeDir);

    OSMImporter importer = new OSMImporter(layerName);

    importer.importFile(db, osmPath);

    importer.reIndex(db, 1000);

    Abbildung 23: Import einer OSM-Datei in eine eingebettete Graphdatenbank.

    Der entstandene Graph lsst sich mit dem Programm Neoeclipse visualisieren und auf

    seine Struktur untersuchen. Besonders interessant ist es hier zu erkennen, wie die

    Topologie der Pfade in der Datenbank reprsentiert ist. In Abbildung 24 ist der Sub-

    Graph eines OSM-Weges des Typs highway: residential zu sehen. Die Kante mit dem

    Label FIRST_NODE ist auf den ersten Knoten gerichtet, welcher selbst keine Eigen-

    schaften trgt. Jeder dieser Sttzpunkte eines Weges besitzt genau eine Kante des

    Typs NODE, dessen Endpunkt Trger der Informationen des Wegpunktes, wie

    Rechts- und Hochwert, sowie der node_osm_id ist. Um dem Weg zu folgen, kann

    entlang der Kanten mit dem Label NEXT traversiert werden. Neben dem eigentlichen

    Label zeichnet sich diese Kante durch die Eigenschaft lenght aus, welche beim Im-

    portieren aus den gegebenen Koordinaten berechnet wird. Es handelt sich also um

    einen gewichteten Sub-Graphen.

    Abbildung 24: Visualisierung in Neoclipse.

  • 5 Navigationsanwendung mit Neo4j Spatial 44

    Die Nachbarschaftsbeziehungen zu angrenzenden Pfaden lassen sich ber die NO-

    DE-Relationen herstellen. Punkte, an denen sich die Wege kreuzen, zeigen auf den

    gleichen Knoten. Die Beziehung wird hier ber die node_osm_id hergestellt, welche

    in der OSM-XML enthalten ist. Die Kanten sind gerichtet, so dass neben dem eigentli-

    chen Label NEXT bzw. NODE und der Eigenschaft length auch die Richtung der

    Kante genutzt werden kann, um den gesuchten Pfad ber mehrere OSM-Wege hinweg

    zu identifizieren. Eine Kreuzung zwischen zwei OSM-Wegen ist in Cypher-

    Schreibweise also immer von der Form:

    a-[:NODE]->()

  • 5 Navigationsanwendung mit Neo4j Spatial 45

    Layer layer = db.getSpatialService().getLayer(layerName);

    Coordinate point = new Coordinate(13.84, 51.03);

    GeoPipeline pipeline = GeoPipeline

    .startNearestNeighborLatLonSearch(layer, point, 0.5)

    .sort("Distance");

    List foundGeometries = pipeline.toNodeList();

    Abbildung 26: Nearest Neighbor-Suche mit Hilfe einer GeoPipeline. Die Methode startNea-restNeighborLatLonSearch() nimmt den zu durchsuchenden Layer, die Koordinate und einen Grenzwert entgegen. Die Suche ist hier auf einen Umkreis von 500m begrenzt. Das Ergebnis wird sortiert in eine Liste von Knoten bergeben.

    Die Suche mit der GeoPipeline beruht dabei auf dem R-Tree-Index, der durch den

    SpatialService (s. Abbildung 26, Zeile 1) mit dem Layer bergeben wurde. Das beson-

    dere an einer Graphdatenbank ist, dass die Indexierung Teil des eigentlichen Graphen

    sein kann, welcher zur Suche traversiert wird (s. Abbildung 27).

    Abbildung 27: R-Tree-Index in Neo4j. Der importierte Datensatz bestand lediglich aus zwei kurzen Wegen, deren umschlieendes Rechteck hier indexiert ist.

  • 5 Navigationsanwendung mit Neo4j Spatial 46

    Ein OSM-Datensatz ist nicht auf einen Geometrietyp beschrnkt. Um dies in der Suche

    zu bercksichtigen, muss nach befahrbaren Geometrien gefiltert werden. Aus Abbil-

    dung 27 lsst sich entnehmen, dass das Ergebnis einer Suche mit GeoPipeline auf die

    RTREE_REFERENCE einer Geometrie zeigt. Dieser Knoten enthlt das Attribut

    gtype, dass Auskunft ber den referenzierten Geometrietypen gibt. Die Konstante

    Integer 2 entspricht dabei dem OpenGIS GeometryType GTYPE_LINESTRING, wel-

    cher potentiell eine Strae darstellen kann.

    Um die Suche weiter zu verfeinern, wird ausgehend vom Referenzknoten ber die

    Kante GEOM traversiert und dieser somit auf den OSM-Parameter highway getes-

    tet. Fr diese Anwendung wurde vereinfachend angenommen, dass folgende Attribute

    eine befahrbare Strae beschreiben: motorway, trunk, primary, secondary, tertiary,

    motorway_link, primary_link, road, residential und unclassified.

    Um nun auf die Graphentheorie zurckgreifen zu knnen, muss das aus 6.2 gewonne-

    ne Wissen auf die Konfiguration der zur Traversierung des Graphen genutzten Klasse

    angewandt werden. Hier ergab sich ein grundlegendes Problem bei der aktuellen Im-

    plementierung fr OSM-Daten: Die NearestNeighbor-Suche erwidert den Referenzkno-

    ten der gesamten Geometrie und nicht den Sttzpunkt des Pfades, der der gegebenen

    Koordinate am nchsten ist. Deshalb muss im Sub-Graphen der Geometrie gesondert

    nach dem gesuchten Sttzpunkt gesucht werden. Dazu entstand das folgende Cypher-

    Skript, das eine Liste aller Knoten die auf die gerichtete Kante NODE folgen erstellt.

    Diese Knoten entsprechend dabei den Trgern der metrischen Information der Geo-

    metrie (vgl. Abbildung 28):

    START a=node(" + /*ID Referenzknoten*/ + ")

    MATCH a()-[:NEXT*0..]->()-[:NODE]->b

    RETURN b

    Abbildung 28: Sammeln aller Sttzpunkte mit Cypher.

    Die so entstandene Liste kann durch einfaches Vergleichen der Raumstrecke zum ge-

    suchten Punkt auf den nchsten Sttzpunkt untersucht werden.

    5.4 Berechnung des krzesten, befahrbaren Weges

    Nachdem nun die Knoten der Geometrie gefunden wurden, welche am ehesten der

    gesuchten Koordinate entsprechen, kann der krzeste Weg zwischen diesen berech-

    net werden. Zum Einsatz kommt hier der Dijkstra-Algorithmus, der, neben anderen

    Traversierungsalgorithmen fr gerichtete und ungerichtete Graphen, durch die Neo4j-

    Bibliothek bereits integriert ist. Wie schon vorher festgestellt, besteht der Graph nicht

    nur aus der Topologie der Geoobjekte, sondern enthlt weitere Daten des Layers, wie

    beispielsweise den R-Tree-Index selbst. Um also nur entlang der Knoten und Kanten

  • 5 Navigationsanwendung mit Neo4j Spatial 47

    zu traversieren, die fr diese Aufgabe von Bedeutung sind, mssen bestimmte Krite-

    rien erstellt werden. Dafr dient die Klasse des Expander:

    Expander expander = Traversal.emptyExpander();

    expander = expander.add(RelTypes.NODE);

    expander = expander.add(RelTypes.NEXT);

    expander = expander.addRelationshipFilter(relFilter);

    Abbildung 29: Konfiguration des Expanders. Relationen des Typs NODE und NEXT werden zum Expander hinzugefgt. Alle anderen Kanten, deren Label nicht den gegeben entspricht, werden ignoriert. Der hinzugefgte Relationship Filter ist gesondert definiert und testet auf weitere Bedingungen. Hier speziell, ob es sich beim Wechsel von einem OSM-Weg auf den angrenzenden um eine fr PKW befahrbare Strae handelt.

    Um den gesuchten Dijkstra-Pfad letztendlich zu berechnen, dient die Klasse des Path-

    Finder, welche mit Hilfe des zuvor definierten Expanders und einer Vorschrift zur Inter-

    pretation des Kantengewichts instanziiert wird.

    CostEvaluator costEvaluator =

    CommonEvaluators.doubleCostEvaluator("length", 0);

    PathFinder finder = GraphAlgoFactory.dijkstra(expander,

    costEvaluator);

    WeightedPath path = finder.findSinglePath(node1, node2);

    Abbildung 30: Berechnung des krzesten Wegs nach Dijkstra. Die Gewichtung des Graphs basiert hier auf der Eigenschaft "length" und wird fr eine Kante 0 gesetzt, wenn diese Eigenschaft nicht vorhanden ist. Dies ist genau dann der Fall, wenn eine Kreuzung zweier Wege ber die Kanten des Typs NODE traversiert wird (vgl. Abbildung 24).

    5.5 Ergebnis

    Abschlieend wurde die Anwendung NeoGIS konstruiert, um das Ergebnis zu visuali-

    sieren. Es besitzt die grundlegenden Fhigkeiten, OSM-Dateien zu importieren und auf

    einer interaktiven Karte darzustellen. Die Darstellung der OSM-Daten beschrnkt sich

    auf Straen, da nur diese fr die Navigation in Frage kommen. Da auch das verwende-

    te Framework GeoTools typenreine Layer zur korrekten Darstellung voraussetzt, kam

    hier eine Funktion Neo4j Spatials zum Einsatz, mit dessen Hilfe sich eine dynamische

    Layerkonfiguration anlegen lsst, welche GeoTools nur einen FeatureType pro Layer

    offenbart. Dies ist die gleiche Herangehensweise durch die Neo4j als DataStore fr

    andere GeoTools-Produkte fungieren kann.

  • 5 Navigationsanwendung mit Neo4j Spatial 48

    Abbildung 31: Die Programmoberflche von NeoGIS mit einem importierten OSM-Layer des Verkehrsnetz der Innenstadt Dresdens.

    Abbildung 32: Ergebnis der Berechnung einer krzesten Route. Die Auswahl des Start- und Zielpunkts erfolgt per Mausklick auf die Karte. Die Wegberechnung kann manuell gestartet wer-den.

    5.6 Fazit

    Dieser Prototyp demonstriert die Eignung von Graphdatenbanken zur Analyse von To-

    pologie. Durch die implizite Identifikation von Kanten und Knoten ber deren Eigen-

    schaften bietet das Property-Graph-Modell eine groe Vielseitigkeit. Fr die Berech-

  • 5 Navigationsanwendung mit Neo4j Spatial 49

    nung von gewichteten und ungewichteten Pfaden stehen neben Dijkstra weitere Algo-

    rithmen zur Verfgung, die sehr frei und beliebig komplex konfiguriert werden knnen.

    Darber hinaus knnen aus der Traversierung des Graphen weitere Fragestellungen

    ber Nachbarschaft und Erreichbarkeit beantwortet werden.

    Da der Index Teil des Graphen selbst ist, kann dieser beliebig angepasst werden. Au-

    erdem besteht so die Mglichkeit, den Zugriffsmechanismus auf die Abfrage zu per-

    fektionieren. Beispielsweise wre es denkbar, einen Sub-Graphen wie den einer Geo-

    metrie durch einen eigenen Zugriffsmechanismus zu ergnzen. Das in Kapitel 5.3 vor-

    gestellte Problem der Sttzpunktsuche liee sich so eventuell effektiver lsen.

    Bei der Konzeption fiel auf, dass speziell die Implementierung des OSM-Modells in

    Neo4j ist zum gegenwrtigen Zeitpunkt nicht optimal ist, da das Gewicht der Kanten

    zwischen Sttzpunkten beim Import aus den Koordinaten berechnet wird. ndern sich

    die Koordinaten der Sttzpunkte, kann dies zu Updateanomalien fhren. Wnschens-

    wert wre auerdem eine topologische Dekodierung bekannter Schnittstellenformate,

    so dass diese in einen Graph eingefgt werden knnen. Im Moment beschrnken sich

    die Mglichkeiten hier auf die Dekodierung von OSM-Daten. Der Import von Geomet-

    rien im WKT oder WKB-Format fhrt lediglich zu einem Knoten, der die Geometrie als

    Array enthlt. An dieser Stelle bietet sich spannendes Potential fr die zuknftige Ent-

    wicklung.

    Im direkten Vergleich mit den bestehenden Lsungen zur Geodatenhaltung muss ein

    evolutionrer Vorteil fr Systeme wie PostGIS oder Oracle Spatial besttigt werden.

    Neben dem greren Feature Set an Operationen und einer wohlbekannten, standar-

    disierten Abfragesprache steht fr diese etablierten Systeme auch eine zentrale Do-

    kumentation zur Verfgung, auf die bei der Arbeit zurckgegriffen werden kann. Das

    modellieren von Topologie ist hier aber schwieriger. Das proprietre Oracle Spatial

    bietet hierfr umfangreiche Funktionen und integriert eigene Datentypen (Oracle 2006).

    PostGIS wird hnliche Funktionalitt voraussichtlich mit dem Erscheinen in Version 2.0

    beinhalten (PostGIS Tracker and Wiki o.J.). Durch diese Lsungen entsteht aber ein

    Mehraufwand, der bei der Haltung von Geodaten in einer Graphdatenbank nicht

    vorliegt.

  • 6 Zusammenfassung und Ausblick 50

    6 Zusammenfassung und Ausblick

    Der Inhalt dieser Arbeit sollte es sein, den Entwicklungsstand der NoSQL-Datenbanken

    aufzuzeigen und ihr Anwendungspotential fr Geodaten zu werten. Dazu wurde zuerst

    ein berblick ber die Geschichte, grundlegende Konzepte und die vier wichtigsten

    Kategorien der NoSQL-Datenbanksysteme gegeben. Einzelne Vertreter dieser Katego-

    rien wurden mit ihren Spatial Extensions und Anwendungen vorgestellt. Danach wur-

    den zunchst Geodaten definiert, um deren Komplexitt darzulegen und davon ausge-

    hend die konventionelle Verarbeitung in SQL-Datenbanken mit ihren Vor- und Nachtei-

    len grob zu umreien. Anschlieend wurde gezeigt, wie die Komplexitt des Datenmo-

    dells in Wechselwirkung mit der Skalierbarkeit der Datenbank steht. Es ging hervor,

    dass, da Geodaten sich als unterschiedlich komplex erwiesen haben, es viel wichtiger

    ist, Datenbanken nach dem Zweck ihrer Anwendung zu whlen als ausschlielich auf

    die Skalierbarkeit des Systems zu achten. Es wurde nmlich ersichtlich, dass das

    Datenmodell einen erheblichen Einfluss auf die Eignung fr die

    Datenhaltungskomponente in einem raumbezogenen Informationssystem hat. Im wei-

    teren Verlauf zeigte eine Unterteilung in einfache Positionsdaten, komplexe Geodaten

    und Rasterdaten exemplarisch, wie diese Anwendungsfelder aussehen knnen und

    wie ihre Struktur Einfluss auf die Wahl der Datenbank haben muss. Dabei fiel auf, dass

    der Aufwand fr das Einpflegen von White Column und Key/Value Stores fr komplexe

    Daten zu gro ist, als dass es Sinn macht, sie fr kleine bis mittelgroe Projekte zu

    benutzen. Document Stores hingegen, welche eine denormalisierte Dokumentenstruk-

    tur untersttzen, bieten eine interessante Alternative zu SQL-Datenbanken mit ihrer

    Kombination aus Schemalosigkeit, 2D-Indexierung und MapReduce an. Auch Graph-

    datenbanken haben sich im Laufe der Arbeit als interessant erwiesen, da sie eine

    ebenso komplexe Strukturierung der Daten wie SQL-Datenbanken erlauben, intuitive

    Traversierungsalgorithmik anbieten und Topologie so direkt und intuitiv in einem Graph

    modellieren knnen. Aufbauend auf diesen Erkenntnissen wurden zwei Prototypen

    erstellt, die die theoretische Eignung dieser Datenbanken fr Geodaten praktisch ber-

    prfen sollten. Das Ergebnis untersttze letztendlich die theoretische Vorberlegung,

    dass der Nutzen einer NoSQL-Datenbank auch schlicht die Vereinfachung bekannter

    Vorgnge sein kann, die es auch Interessierten aus GIS-fremden Fachgebieten er-

    laubt, einen Geodienst nicht nur zu konsumieren, sondern selbst zu pflegen. Die Be-

    rechnung des krzesten zwischen zwei Wegpunkten bestehenden Pfads anhand eines

    intuitiv erfassbaren Graphen zeigte, dass es natrlichere Wege gibt, topologische

    Sachverhalte schon im Datenbankschema abzubilden.

    Allgemein kann gesagt werden, dass die Haltung von Geodaten in allen Datenbankty-

    pen mglich ist. Durch die hohe Komplexitt, die Geodaten im Allgemeinen jedoch

    aufweisen, ist genau abzuwgen, welche Datenbank zum Einsatz kommen soll. Auf-

    grund des berlegenen Entwicklungsstands der objektrelationalen Geodatenbanken,

  • 6 Zusammenfassung und Ausblick 51

    wie PostGIS oder Oracle Spatial, sind diese jedoch bei komplexen Projekten vorzuzie-

    hen.

    Zu beachten ist, dass es sich bei dieser Arbeit lediglich um eine momentane Einscht-

    zung der NoSQL-Systeme und ihrer Eignung fr Geodaten handelt. Die Bewegung ist

    vergleichsweise jung und gerade die hier vorgestellten Lsungen fr Geodaten entwi-

    ckeln sich erst seit kurzem. Trotzdem haben NoSQL- Systeme innerhalb ihrer kurzen

    Bestehenszeit bereits so viel Raum in Gebieten der Datenanalyse, der verteilten Web

    Services und der Biotechnologie gut gemacht, dass sich auch in Zukunft die Frage

    stellen wird, ob die Geoinformation von den neuen Entwicklungen profitieren kann.

  • Literaturverzeichnis VI

    Literaturverzeichnis

    Monographien, Zeitschriftenaufstze

    ANDRAE, C. (2009): Spatial Schema. Heidelberg.

    BILL, R. (1999): Grundlagen der Geoinformationssysteme. Heidelberg.

    DE SOUZA BAPTISTA, C. ET AL. (2011): Using OGC Services to Interoperate Spatial Data Stored in SQL and NoSQL Databases. Proceedings XII GEOINFO: 61-72.

    EDLICH, S. ET AL. (2011): NoSQL. Mnchen.

    GILBERT, S., UND N. LYNCH. (2002): Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services. ACM SIGACT News 33 (2): 51-59.

    KEMPER, A., UND A. EICKLER (2011): Datenbanksysteme. Mnchen.

    KOCH, T. (2008): Verwaltung von Geodaten in Oracle. Saarbrcken.

    SCHELIGA, M. (2010): CouchDB. kurz & gut. Kln.

    SCHNEIDER, R. (1993): Geo-Datenbanksysteme. Mannheim.

    STONEBRAKER, M. ET AL. (2007): The End of an Architectural Era (Its Time for a Complete Rewrite). Proceedings of the 33rd International Conference on Very Large Data Bases: 1150-1160.

    TIWARI, S. (2011): Professional NoSQL. Indianapolis.

    VOGELS, W. (2009): Eventually Consistent. Communications of the ACM 52 (1): 40-44.

    Internetquellen

    10gen (2011): Geospatial Indexing - MongoDB. Internet: http://www.mongodb.org/display/DOCS/Geospatial+Indexing (15.02.2012)

    Amazon (2012): Amazon Elastic Compute Cloud (Amazon EC2) . Internet: http://aws.amazon.com/de/ec2/ (20.2.2012)

    BELLON, A. (2012): Die 20 bestverdienenden Internetseiten der Welt. Internet: http://www.alexbellon.de/die-20-bestverdienenden-internetseiten-der-welt/ (22.02.2012)

    BREWER, E. A. (2000): Towards Robust Distributed Systems. Internet: http://www.eecs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf (20.02.2012)

    BUTLER, H. ET AL. (2008): The GeoJSON Format Specification. Internet: http://geojson.org/geojson-spec.html (14.02.2012)

    Cassandra Wiki (2012a): ClientOptions. Internet: http://wiki.apache.org/cassandra/ClientOptions (14.02.2012)

    Cassandra Wiki (2012b): DataModel. Internet: http://wiki.apache.org/cassandra/DataModel (14.02.2012)

    Cassandra Wiki (2012c): Datamodel. Internet: http://wiki.apache.org/cassandra/FrontPage (14.02.2012)

    http://www.mongodb.org/display/DOCS/Geospatial+Indexinghttp://aws.amazon.com/de/ec2/http://www.alexbellon.de/die-20-bestverdienenden-internetseiten-der-welt/http://www.alexbellon.de/die-20-bestverdienenden-internetseiten-der-welt/http://www.eecs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdfhttp://geojson.org/geojson-spec.htmlhttp://wiki.apache.org/cassandra/ClientOptionshttp://wiki.apache.org/cassandra/DataModelhttp://wiki.apache.org/cassandra/FrontPage

  • Literaturverzeichnis VII

    CHANG, F. ET AL. (2006): Bigtable: A Distributed Storage System for Structurated Data. Internet: http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/de//archive/bigtable-osdi06.pdf (21.02.2012)

    CHODROW, K. (2011): Mongo in Flatland. Internet: http://www.snailinaturtleneck.com/blog/2011/06/08/mongo-in-flatland/ (05.02.2012)

    CouchDB (o.J.): CouchDB/GeoCouch. Internet: http://www.gdal.org/ogr/drv_couchdb.html (09.01.2012)

    DataStax. (2012): Cassandra Users. Internet: http://www.datastax.com/cassandrausers (08.01.2012)

    DEAN, J. UND S. GHEMAWAT (2004): MapReduce: Simplified Data Processing on Large Clusters. Internet: http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//archive/mapreduce-osdi04.pdf (10.01.2012)

    EDLICH, S. (2012): Your Ultimate Guide to the Non-Relational Universe! Internet: http://nosql-database.org/ (30.01.2012)

    EIFREM, E. (2009): NOSQL: scaling to size and scaling to complexity. Internet: http://blogs.neotechnology.com/emil/2009/11/nosql-scaling-to-size-and-scaling-to-complexity.html (18.02.2012)

    EVAN, E. (2009): NOSQL 2009. Internet: http://blog.sym-link.com/2009/05/12/nosql_2009.html (08.01.2012)

    FIELDING, R. T. (2000): Representational State Transfer (REST). Internet: http://www.ics.uci.edu/~fielding/pubs/dissertation/rest_arch_style.htm (05.02.2012)

    FIELDING, R. T. ET AL. (1999): Hypertext Transfer Protocol -- HTTP/1.1. Internet: http://www.w3.org/Protocols/rfc2616/rfc2616-sec9.html (02.02.2012)

    FINLEY, K. (2011): Video: How SimpleGeo Built a Scalable Geospatial Database with Apache Cassandra. Internet: http://www.readwriteweb.com/cloud/2011/02/video-simplegeo-cassandra.php (05.02.2012)

    GARULLI, L. (2011): OrientDB. Internet: http://www.orientechnologies.com/orient-db.htm (14.02.2012)

    Geofabrik GmbH (2012): Geofabrik Download-Bereich. Internet: http://download.geofabrik.de/osm (21.02.2012)

    GDAL (2012): OGR Vector Formats. Internet: http://www.gdal.org/ogr/drv_couchdb.html (21.02.2012)

    GONALVES, B. L. (2012): FrontPage. Internet: http://wiki.apache.org/cassandra/ (07.01.2012)

    Google (2012): Google Earth Builder. Internet: http://www.google.com/enterprise/earthmaps/builder.html (19.02.2012)

    GREHAN, R. UND D. BARRY (2012): Introduction to ODBMS. Short History. Internet: http://www.odbms.org/Introduction/history.aspx (06.01.2012)

    HEINE, C. (2011): Foursquare Reaches 15M Users, Triples Audience on a Year. Internet: http://www.clickz.com/clickz/news/2130251/foursquare-reaches-15m-users-triples-audience (22.02.2012)

    http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/de/archive/bigtable-osdi06.pdfhttp://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/de/archive/bigtable-osdi06.pdfhttp://www.snailinaturtleneck.com/blog/2011/06/08/mongo-in-flatland/http://www.gdal.org/ogr/drv_couchdb.htmlhttp://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/archive/mapreduce-osdi04.pdfhttp://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/archive/mapreduce-osdi04.pdfhttp://blogs.neotechnology.com/emil/2009/11/nosql-scaling-to-size-and-scaling-to-complexity.htmlhttp://blogs.neotechnology.com/emil/2009/11/nosql-scaling-to-size-and-scaling-to-complexity.htmlhttp://blog.sym-link.com/2009/05/12/nosql_2009.htmlhttp://blog.sym-link.com/2009/05/12/nosql_2009.htmlhttp://www.ics.uci.edu/~fielding/pubs/dissertation/rest_arch_style.htmhttp://www.w3.org/Protocols/rfc2616/rfc2616-sec9.htmlhttp://www.readwriteweb.com/cloud/2011/02/video-simplegeo-cassandra.phphttp://www.orientechnologies.com/orient-db.htmhttp://download.geofabrik.de/osmhttp://www.gdal.org/ogr/drv_couchdb.htmlhttp://wiki.apache.org/cassandra/http://www.google.com/enterprise/earthmaps/builder.htmlhttp://www.odbms.org/Introduction/history.aspxhttp://www.clickz.com/clickz/news/2130251/foursquare-reaches-15m-users-triples-audiencehttp://www.clickz.com/clickz/news/2130251/foursquare-reaches-15m-users-triples-audience

  • Literaturverzeichnis VIII

    HITCHCOCK, A. (2005): Google's BigTable. Internet: http://andrewhitchcock.org/?post=214 (05.01.2012)

    KATZ, D. UND V. MISCHE (2012): geocouch. Internet: https://github.com/couchbase/geocouch (10.02.2012)

    LUKAS, B. (2012): Geoinformationen Download von Daten. Internet: http://www.mugv.brandenburg.de/cms/detail.php/bb2.c.515599.de (21.02.2012)

    MALONE, M. (2010): Working with Dimensional Data in a Distributed Hash Table. Internet: http://strangeloop2010.com/talks/14495 (06.01.2012)

    Neo Technology (2012a): Chapter 15. Cypher Query Language. Internet: http://docs.neo4j.org/chunked/1.6.1/cypher-query-lang.html (28.01.2012)

    Neo Technology (2012b): neo4j/spatial. Internet: https://github.com/neo4j/spatial (18.02.2012)

    NEUMANN, A. (2008): PostGIS-Einfhrung. Internet: http://gis.hsr.ch/wiki/images/f/fd/Postgis_einfuehrung_2008.pdf (10.02.2012)

    OGDEN, M. (2011): geocouch-utils. Internet: https://github.com/maxogden/geocouch-utils (15.01.2012)

    Open Geospatial Consortium (2011): OpenGIS Implementation Standard for Geo-graphic information - Simple feature access - Part 1: Common architecture. In-ternet: https://portal.opengeospatial.org/modules/admin/license_agreement.php?suppressHea-ders=0&access_license_id=3&target=http://portal.opengeospatial.org/files/%3fartifact_id=25355 (21.02.2012)

    Open Geospatial Consortium (2012a): The OGC Forms REST and WFS/FE Standards Working Groups. Internet: http://www.opengeospatial.org/pressroom/pressreleases/1497 (04.01.2012)

    Open Geospatial Consortium (2012b): OGC History (detailed). Internet: http://www.opengeospatial.org/ogc/historylong (01.02.2012)

    OpenStreetMap Wiki (2011): OSM XML. Internet: http://wiki.openstreetmap.org/wiki/OSM_XML (08.02.2012)

    Oracle (2006): Topology Data Model Overview. Internet: http://docs.oracle.com/cd/B19306_01/appdev.102/b14256/sdo_topo_concepts.htm#CIHFGFIA (20.02.2012)

    PostGIS Tracker and Wiki (o.J.): PostGIS Topology. Internet: http://trac.osgeo.org/postgis/wiki/UsersWikiPostgisTopology (20.02.2012)

    RDF Working Group (2012): Ressource Description Framework (RDF). Internet: http://www.w3.org/RDF/ (16.02.2012)

    RODRIGUEZ, M. (2012a): Defining a Property Graph. Internet: https://github.com/tinkerpop/gremlin/wiki/Defining-a-Property-Graph (20.02.2012)

    RODRIGUEZ, M. (2012b): Blueprints. Internet: https://github.com/tinkerpop/blueprints/wiki (20.02.2012)

    SANFILIPPO, S. (2011): Short term Redis plans. Internet: http://antirez.com/post/short-term-redis-plans.html (10.01.2012)

    SLEE, M., AGARWAL, A., UND M. KWIATKOWSKI (2007): Thrift: Scalable Cross-Language Services Implementation. Internet: http://www.scribd.com/doc/20232450/Thrift-Scalable-Cross-Language-Services-Implementation (21.02.2012)

    http://andrewhitchcock.org/?post=214https://github.com/couchbase/geocouchhttp://www.mugv.brandenburg.de/cms/detail.php/bb2.c.515599.dehttp://strangeloop2010.com/talks/14495http://docs.neo4j.org/chunked/1.6.1/cypher-query-lang.htmlhttps://github.com/neo4j/spatialhttp://gis.hsr.ch/wiki/images/f/fd/Postgis_einfuehrung_2008.pdfhttps://github.com/maxogden/geocouch-utilshttps://github.com/maxogden/geocouch-utilshttps://portal.opengeospatial.org/modules/admin/license_agreement.php?suppressHeaders=0&access_license_id=3&target=http://portal.opengeospatial.org/files/%3fartifact_id=25355https://portal.opengeospatial.org/modules/admin/license_agreement.php?suppressHeaders=0&access_license_id=3&target=http://portal.opengeospatial.org/files/%3fartifact_id=25355https://portal.opengeospatial.org/modules/admin/license_agreement.php?suppressHeaders=0&access_license_id=3&target=http://portal.opengeospatial.org/files/%3fartifact_id=25355https://portal.opengeospatial.org/modules/admin/license_agreement.php?suppressHeaders=0&access_license_id=3&target=http://portal.opengeospatial.org/files/%3fartifact_id=25355http://www.opengeospatial.org/pressroom/pressreleases/1497http://www.opengeospatial.org/ogc/historylonghttp://wiki.openstreetmap.org/wiki/OSM_XMLhttp://docs.oracle.com/cd/B19306_01/appdev.102/b14256/sdo_topo_concepts.htm#CIHFGFIAhttp://docs.oracle.com/cd/B19306_01/appdev.102/b14256/sdo_topo_concepts.htm#CIHFGFIAhttp://trac.osgeo.org/postgis/wiki/UsersWikiPostgisTopologyhttp://www.w3.org/RDF/https://github.com/tinkerpop/gremlin/wiki/Defining-a-Property-Graphhttps://github.com/tinkerpop/blueprints/wikihttp://antirez.com/post/short-term-redis-plans.htmlhttp://antirez.com/post/short-term-redis-plans.htmlhttp://www.scribd.com/doc/20232450/Thrift-Scalable-Cross-Language-Services-Implementationhttp://www.scribd.com/doc/20232450/Thrift-Scalable-Cross-Language-Services-Implementation

  • Literaturverzeichnis IX

    STONEBRAKER, M. (2009): The End of a DBMS Era (Might be Upon Us). Internet: http://cacm.acm.org/blogs/blog-cacm/32212-the-end-of-a-dbms-era-might-be-upon-us/fulltext (10.01.2012)

    STROZZI, C. (2010): NoSQL. A Relational Database Management System. Internet: http://www.strozzi.it/cgi-bin/CSA/tw7/I/en_US/nosql/Home%20Page (21.02.2012)

    The Apache Software Foundation (2011): Hadoop HDFS. Internet: http://hadoop.apache.org/hdfs/ (15.01.2012)

    The Apache Software Foundation (2012): Apache HBase. Internet: http://hbase.apache.org/ (31.01.2012)

    TROY, D. (2008): geoshash demonstrator. Internet: http://openlocation.org/geohash/geohash-js/ (02.02.2012)

    VMWare (2011a): Clients. Internet: http://redis.io/clients (20.02.2012)

    VMWare (2011b): Commands. Internet: http://redis.io/commands (20.02.2012)

    VMWare (2011c): Replication. Internet: http://redis.io/topics/replication (20.01.2012)

    VMWare (2011d): Transactions. Internet: http://redis.io/topics/transactions (05.01.2012)

    VMWare (2011e): Virtual Memory. Internet: http://redis.io/topics/virtual-memory (02.01.2012)

    VOGELS, W. ET AL. (2007): Dynamo: Amazon's Highly Available Key-value Store. Inter-net: http://www.allthingsdistributed.com/2007/10/amazons_dynamo.html (10.01.2012)

    VOGELS, W. (2012): Amazon DynamoDB a Fast and Scalable NoSQL Database Service Designed for Internet Scale Applications. Internet: http://www.allthingsdistributed.com/2012/01/amazon-dynamodb.html (20.01.2012)

    WILSON, J. R. (2008): Understanding HBase and BigTable. Internet: http://jimbojw.com/wiki/index.php?title=Understanding_Hbase_and_BigTable (23.01.2012)

    http://cacm.acm.org/blogs/blog-cacm/32212-the-end-of-a-dbms-era-might-be-upon-us/fulltexthttp://cacm.acm.org/blogs/blog-cacm/32212-the-end-of-a-dbms-era-might-be-upon-us/fulltexthttp://www.strozzi.it/cgi-bin/CSA/tw7/I/en_US/nosql/Home%20Pagehttp://hbase.apache.org/http://openlocation.org/geohash/geohash-js/http://redis.io/clientshttp://redis.io/commandshttp://redis.io/topics/replicationhttp://redis.io/topics/transactionshttp://redis.io/topics/virtual-memoryhttp://www.allthingsdistributed.com/2012/01/amazon-dynamodb.htmlhttp://jimbojw.com/wiki/index.php?title=Understanding_Hbase_and_BigTable

  • Abbildungsverzeichnis X

    Abbildungsverzeichnis

    Abbildung 1: Datenfluss des MapReduce-Verfahrens. ................................................. 7

    Abbildung 2: Hashfunktion.. ......................................................................................... 9

    Abbildung 3: Konzeptuelles Schema eines Wide Column Stores nach BigTable White Paper. .................................................................................................... 11

    Abbildung 4: Konzeptuelles Schema eines Wide Column Stores in JavaScript-naher Notation. ................................................................................................ 11

    Abbildung 5: Consistant Hashing-Ring ...................................................................... 12

    Abbildung 6: Beispiel eines einfachen JSON-Dokuments. ......................................... 14

    Abbildung 7: Beispiel eines GeoJSON GeometryObjects des Typs MultiLineString. ................................................................................................ 16

    Abbildung 8: Einfacher Graph bestehend aus drei Knoten und ungerichteten Kanten. ............................................................................................................ 17

    Abbildung 9: Gewichteter Property Graph zwischen Personen und Programmen ...... 18

    Abbildung 10: Hinzufgen eines Knotens und einer Kante mit Gremlin. .................... 19

    Abbildung 11: Komplexitt vs. Skalierbarkeit ............................................................... 23

    Abbildung 12: Visualisierung der "Geohash Quadranten" .......................................... 26

    Abbildung 13: JSON-Dokument eines Features des Typs Point. ............................... 34

    Abbildung 14: Eine einfache Map-Funktion. ............................................................... 34

    Abbildung 15: Geometrie emittierende Map-Funktion.. ............................................ 35

    Abbildung 16: Design-Dokument. .............................................................................. 35

    Abbildung 17: Antwortdokument eines Bounding Box Querys. .................................. 36

    Abbildung 18: List-Funktion. ...................................................................................... 37

    bbildung 19: AJAX-Request an eine CouchDB. ......................................................... 38

    Abbildung 20: Screenshot der Konzeptanwendung "Brandenburger Schutzgebiete". ................................................................................................ 39

    Abbildung 21: Abfrage des krzesten Pfads .............................................................. 41

    Abbildung 22: Gekrztes Beispiel einer OSM-XML-Datei. ......................................... 42

    Abbildung 23: Import einer OSM-Datei in eine eingebettete Graphdatenbank. .......... 43

    Abbildung 24: Visualisierung in Neoclipse. ................................................................ 43

    Abbildung 25: Cypher MATCH-Statement. ................................................................ 44

    Abbildung 26: Nearest Neighbor-Suche mit Hilfe einer GeoPipeline. ......................... 45

    Abbildung 27: R-Tree-Index in Neo4j. ........................................................................ 45

    Abbildung 28: Sammeln aller Sttzpunkte mit Cypher. .............................................. 46

    Abbildung 29: Konfiguration des Expanders. ............................................................. 47

    Abbildung 30: Berechnung des krzesten Wegs nach Dijkstra. ................................. 47

    Abbildung 31: Die Programmoberflche von NeoGIS ................................................ 48

    Abbildung 32: Ergebnis der Berechnung einer krzesten Route. ............................... 48

    Tabellenverzeichnis

    Tabelle 1: Eigenschaften von NoSQL-Datenbanken in Relation zu Charakteristiken von Nichtstandardanwendungen. .......................................... 29

  • Anlagenverzeichnis XI

    Anlagenverzeichnis

    Anhang 1

    Anhang 2

    CD-Inhalt

    Bachelorarbeit Benjamin Thurm Einsatz von NoSQL-Datenbanken fr Geodaten.doc BrandenburgerSchutzgebiete\

    ._index.html

    ._script

    .DS_Store script\ style\ index.html

    NeoGIS\

    NeoGIS Runnable\ NeoGIS Source\ Hinweis.txt

    Webseiten\

    10gen (2011) Geospatial Indexing - MongoDB.htm Amazon (2012) Amazon Elastic Compute Cloud (Amazon EC2).htm Bellon, A. (2012) Die 20 bestverdienenden Internetseiten der Welt.htm Brewer, E. A. (2000) Towards Robust Distributed Systems.pdf Butler, H. et al. (2008) The GeoJSON Format Specification.htm Cassandra Wiki (2012a) ClientOptions.htm Cassandra Wiki (2012b) Datamodel.htm Chang, F. et al. (2006) Bigtable - A Distributed Storage System for Structurated Da-ta.pdf Chodrow, K. (2011) Mongo in Flatland.htm CouchDB (o.J.) CouchDB GeoCouch.htm DataStax (o.J.) Cassandra Users.htm Dean, J. und S. Ghemawat (2004) MapReduce - Simplified Data Processing on Large Clusters.pdf Edlich, S. (2012) Your Ultimate Guide to the Non-Relational Universe!.htm Eifrem, E. (2009) NOSQL - scaling to size and scaling to complexity.htm Evan, E. (2009) NOSQL 2009.htm Fielding, R. T. (2000) Representational State Transfer (REST).htm Fielding, R. T. et al. (1999) Hypertext Transfer Protocol -- HTTP 1.1.htm Finley, K. (2011) Video - How SimpleGeo Built a Scalable Geospatial Database with Apache Cassandra.htm Garulli, L. (2011) OrientDB.htm Geofabrik GmbH (2012) Geofabrik Download-Bereich.htm Gonalves, B. L. (2012) FrontPage.htm Google (2012) Google Earth Builder.htm Grehan, R. und D. Barry (2012) Introduction to ODBMS.htm Heine, C. (2011) Foursquare Reaches 15M Users, Triples Audience on a Year.htm Hitchcock, A. (2005) Google's BigTable.htm Katz, D. und V. Mische (2012) geocouch.htm Lukas, B. (2012) Geoinformationen - Download von Daten.htm Malone, M. (2010) Working with Dimensional Data in a Distributed Hash Table In-ternet.htm

  • Anlagenverzeichnis XII

    Neo Technology (2012a) Chapter 15. Cypher Query Language.htm Neo Technology (2012b) neo4j spatial.htm Neumann, A. (2008) PostGIS-Einfhrung.pdf Ogden, M. (2011) geocouch-utils.htm Open Geospatial Consortium (2011) OpenGIS Implementation Standard for Geo-graphic information - Simple feature access - Part 1 Common architecture..pdf Open Geospatial Consortium (2012a) The OGC Forms REST and WFS FE Stand-ards Working Groups.htm Open Geospatial Consortium (2012b) OGC History (detailed).htm OpenStreetMap Wiki (2011) OSM XML.htm Oracle (2006) Topology Data Model Overview.htm PostGIS Tracker and Wiki (o.J.) PostGIS Topology.htm RDF Working Group (2012) Resource Description Framework (RDF).htm Rodriguez, M. (2012a) Defining a Property Graph.htm Rodriguez, M. (2012b) Blueprints.htm Sanfilippo, S. (2011) Short term Redis plans.htm Slee, M., Agarwal, A. und M. Kwiatkowski (2007) Thrift Scalable Cross-Language Services Implementation.htm Stonebraker, M. (2009) The End of a DBMS Era (Might be Upon Us).htm Strozzi, C. (2010) NoSQL Relational Database Management System.htm The Apache Software Foundation (2011) Hadoop HDFS.htm The Apache Software Foundation (2012) Apache HBase.htm Troy, D. (2008) geoshash demonstrator..htm VMWare (2011a) Clients.htm VMWare (2011b) Commands.htm VMWare (2011c) Replication.htm VMWare (2011d) Transactions.htm VMWare (2011e) Virtual Memory.htm Vogels, W. (2012) Amazon DynamoDB a Fast and Scalable NoSQL Database Service Designed for Internet Scale Applications.htm Vogels, W. et al. (2007) Dynamo - Amazon's Highly Available Key-value Store.htm Wilson, J. R. (2008) Understanding HBase and BigTable.htm

  • Anhang 1 XIII

    Anhang 1

    Von: Volker Mische

    Betreff: Re: Geocouch Spatial Queries

    Datum: 11. Januar 2012 12:36:20 MEZ

    An: Benjamin Thurm

    >Ich kann aber nicht

    >rausfinden, ob komplexere Abfragen nach Nearest-Neighbor, Polygon

    >berhrt-Polygon etc. nativ untersttzt werden? Sollen dergleichen

    >Abfragen auch ber die Views integriert werden?

    Momentan gibt es nut bounding box abfragen. Polygon suche (bzw. ist es

    mit jeder Geometry mglich, also auch mit Linien) funktioniert schon,

    ist momentan aber im Code Review der Firma steckengeblieben. Wird aber

    bald verfgbar sein.

    An Nearest-Neighbour-Suche (knn) arbeitet momentan Tobias Sauerwein, ein

    Master Student der Universitt Marburg.

    Die Abfragen werden einfach wie die Bounding-Box-Abfrage funktionieren.

    Ich versuche dabei die OpenSearch Geo Spezifikation [1] zu implementieren.

    [1]http://www.opensearch.org/Specifications/ _

    OpenSearch/Extensions/Geo/1.0/Draft_2

    ___

    Von: Volker Mische

    Betreff: Re: Geocouch Spatial Queries

    Datum: 11. Januar 2012 14:13:40 MEZ

    An: Benjamin Thurm

    >Meinst du damit die Suche nach eingeschlossenen Features in einem Polygon

    >etc.? Aggregationen wie das umschlieende Feature mehrerer Geometrien

    >liee sich ja eventuell jetzt schon ber entsprechendes Map/Reduce

    >durchfhren?

    Alle Features die ein Polygon schneiden oder darin liegen.

    Der Spatial-Index von GeoCouch hat nichts mit dem MapReduce-Index

    (Views) zu tun. Er ist komplett unabhnig davon. Man kann sich das so

    vorstellen. Die Daten sind in CouchDB gespeichert. Nun kann man einen

    Index darauf aufbauen. Dabei gibt es die Wahl zwischen einem auf

    MapReduce basierendem und einem rumlichen Index.

    An Nearest-Neighbour-Suche (knn) arbeitet momentan Tobias Sauerwein, ein

    Master Student der Universitt Marburg.

    >Hast du Informationen wann knn implementiert sein knnte?

    Ein Prototyp funktioniert schon [1].

    Die Abfragen werden einfach wie die Bounding-Box-Abfrage funktionieren.

    Ich versuche dabei die OpenSearch Geo Spezifikation [1] zu implementieren.

    >Wie schaut es dann aus mit der Ausgabe in anderen Formaten als JSON?

    >"?format" wird dann als standardisierter View fr WKT etc. implementiert?

    >Gibt es darber hinaus Standards die bei der Umsetzung eine Rolle gespielt

    >haben? (Soweit man das so fr eine schemafreie Datenbank sagen kann.)

    Momentan kann man verschiedene Formate per _list Funktion ausgeben (es

    gibt ein Beispiel in der README von GeoCouch). Daher plane ich nicht

    dass direkt in GeoCouch zu implementieren. Das ist eher was fr kleine

    Helfer fr GeoCouch wie geocouch-utils [2].

    [1] https://github.com/tsauerwein/geocouch/tree/knn_prototyp_1.1.x

    [2] https://github.com/vmx/geocouch-utils/

  • Anhang 2 XIV

    Anhang 2

    Von: Stefan Edlich

    Betreff: Re: Kategorisierung von NoSQL/Spatial Lsungen

    Datum: 11. Januar 2012 12:38:50 MEZ

    An: Benjamin Thurm

    Sehr geehrter Herr Thurm,

    vielen Dank fr Ihre Email.

    >Die Kategorisierung der NoSQL Datenbanken in die vier Hauptgruppen

    >(Key/Value, Document Stores,...) hat sich in ziemlich allen

    >Artikeln zum Thema durchgesetzt. Mir ist klar, dass sie auf der

    >logischen Struktur der Datenverwaltung beruht und deshalb nicht

    >weit hergeholt ist. Interessieren wrde mich dennoch, ob sie fr

    >ihre NoSQL-Liste schon auf diese bestehende Einordnung

    >zurckgegriffen haben oder ob sie sich bei der Recherche fr sie

    >ergeben hat?

    Die erste Einordnung habe ich selbst auf der webseite http://nosql-

    database.org vorgenommen. Das war 2009.

    Und dafr hatte ich mit allen NoSQL Gurus diskutiert. Ursprnglich

    wollte ich witzigerweise sogar Graph-Datenbanken nicht mit

    aufnehmen. Hatte hier aber z.B. heftige Diskussionen mit Emil Efrem

    und vielen anderen. Auch daher kam die Aufteilung auf der Webseite

    in Core-NoSQL und Soft-NoSQL.

    >Sehen sie in der Hinsicht auf Geodaten eine Zukunft fr NoSQL?

    Eine sehr groe.

    >GeoCouch wurde zB. gerade als Schnittstelle fr das GDAL Tool der

    >OGC aufgenommen, MongoDB bietet eine zweidimensionale Indexierung,

    >Neo4j mittlerweile auch eine eigene Spatial Extension. Key/Value

    >Stores und Wide Column Stores scheinen mir in dieser Entwicklung im

    >Open Source Bereich unterprsentiert. (Sicherlich auch wegen der

    >schwierigen Datenhaltung fr nicht-Standard Daten.)

    >Sind ihnen andere Projekte bekannt?

    Nicht wirklich. Die Geo Features von Couch und Mongo kenne ich

    natrlich.

    Aus diesem Grunde haben ich mit Kollegin Frau Prof. Sauer eine

    Abschlussarbeit am laufen, die diese

    Features untersucht und vergleicht. Wenn sie mich in 4 Monaten

    nochmal erinnern, kann ich ihnen das PDF dazu senden.

    Viele Gre

    Stefan Edlich

  • Erklrung ber die eigenstndige Erstellung der Arbeit XV

    Erklrung ber die eigenstndige Erstellung der Arbeit

    Hiermit erklre ich, dass ich die vorgelegte mit dem Titel

    __Einsatz von NoSQL-Datenbanksystemen fr Geodaten____

    selbstndig verfasst, keine anderen als die angegebenen Quellen und Hilfsmittel be-

    nutzt sowie alle wrtlich oder sinngem bernommenen Stellen in der Arbeit als sol-

    che und durch Angabe der Quelle gekennzeichnet habe. Dies gilt auch fr Zeichnun-

    gen, Skizzen, bildliche Darstellungen sowie fr Quellen aus dem Internet.

    Mir ist bewusst, dass die Hochschule fr Technik und Wirtschaft Dresden Prfungsar-

    beiten stichprobenartig mittels der Verwendung von Software zur Erkennung von Pla-

    giaten berprft.

    ___Dresden, den 23.02.2012____ ____________________________

    Ort, Datum Unterschrift Student

Recommended

View more >