IOException.de

An der Uni Ulm muss jeder Bachelorstudent in einem Informatik / Informatik verwandten Studiengang das Sopra absolvieren. Das ist ein umfangreiches Softwareprojekt, das sich über zwei Semester erstreckt. Im ersten Semester steht dabei die Erfassung von Anforderungen, die Planung und das Pflichtenheft im Vordergrund. Das passiert in einem Team aus drei Studenten. Im zweiten Semester werden zwei Teams zusammengelegt, so dass fortan sechs Leute an der Implementierung arbeiten.

Alle Teams, die am Sopra teilnehmen, müssen dasselbe Projekt implementieren, wobei die Projekte jedes Jahr wechseln. Dieses Jahr war die Aufgabe von Grund auf einen Routenplaner für die Universität zur erstellen. Die Ausgangsbasis waren die Baupläne der Uni, die vom Bauamt zur Verfügung gestellt wurden.

Einige Problemstellungen des Projekts waren eine besondere Herausforderungen. Beispielsweise müssen handelsübliche Straßen-Routenplaner nicht mit fünf Stockwerken die übereinander liegen zurecht kommen.

Zum Routing: Algorithmen für Routingprobleme (Dijkstra, Bellman-Ford, etc.) verwenden üblicherweise einen gewichteten Graphen. Unser Team hat sich dafür entschieden eine graphenbasierte NoSQL-Datenbank zu verwenden: Neo4J. Da wir vorhatten einen Routeplaner zu entwickeln bot es sich einfach an eine Datenbank zu verwenden die inhärent schon auf einer Graphenstruktur aufbaut und somit viele Probleme — wie das Routing zwischen Knoten — schon im Vornherein löst.

Routingalgorithmen auf relationalen Datenbanken können recht hässlich werden. Für einige andere Teams war das eines der Kernprobleme.

Man sollte Technologien nie deswegen auswählen, weil es eben die einzige Technologie ist die man kennt.
Stattdessen sollte eine Technologie, ein Werkzeug, gewählt werden, weil es sich am Besten für die Aufgabe eignet.

Der Routenplaner sollte webbasiert realisiert werden. Wir haben uns für Vaadin als Web-Framework entschieden. Vaadin setzt auf GWT auf und ermöglicht es Web-Applikationen in Java zu schreiben, als würde man eine Swing-Applikation entwickeln. Java Code wird durch einen Cross-Compiler in JavaScript, HTML & CSS übersetzt. Die Arbeit mit dem Framework hat ziemlich gut funktioniert, es lassen sich sehr schnell vorzeigbare Ergebnisse erstellen.

Wir haben außerdem eine Desktop-Applikation für das Bearbeiten und Hochladen von Kartenmaterial geschrieben. Da wir die Aufgaben im Vornherein aufgeteilt hatten war ich hier aber nur beteiligt als es um die Synchronisation mit der Webapp ging. Dafür haben wir Git verwendet (siehe auch den Blogbeitrag “Git als Update-Mechanismus“).

Weitere erwähnenswerte Technologien: Für den PDF-Druck haben wir LaTeX verwendet. Aus einer generierten *.tex Datei wird eine PDF erstellt und an den Browser zurückgegeben. Wir haben mittels node.js das Uni-Adressbuch gescraped um so vernünftig einen vollständigen Datensatz in die Datenbank zu bekommen.

Die erstellen Projekte werden nicht produktiv eingesetzt werden, es wird aber an einer Musterimplementierung gearbeitet. Diese wird später eventuell auch auf den Terminals, die auf dem Unigelände verteilt sind, laufen.
Allgemein war es ziemlich interessant mal in einem größeren Team an einem umfrangreicheren Projekt zu arbeiten. Man lernt einige Dinge über die Arbeit im Team und verschiedene Technologien. Insbesondere lernet man aber wo die eigenen Stärken liegen.

Im vorherigen Teil haben wir gesehen, wie man Geodaten mithilfe von CouchDB abspeichern kann. Da diese Datenbank zugleich ein Webserver ist und die Daten im JSON-Format gespeichert werden, eignet sie CouchDB auch gut für AJAX-Abfragen. Hierfür gibt es eine auf jQuery aufbauende Library namens jquery.couch.js, die von den AJAX-Requests abstrahiert und direkt browser-seitige Interaktionen mit der Datenbank ermöglicht.

Im diesem Beitrag soll gezeigt werden, wie man mit der offenen Karten-Library Leaflet und jquery.couch.js geographische Daten aus CouchDB heraus auf einer Karten anzeigen kann.

Beispiel-Visualisierung von ulmapi.de, ebenfalls basierend auf CouchDB und Leaflet.

Wir verwenden die CouchApp aus dem ersten Teil weiter, und fügen zu den bisherigen Map/Reduce Views noch statische HTML- und Javascript-Dateien hinzu (im _attachments Ordner), die dann im Browser abgerufen werden können. Beim Aufruf dieser Webseite wird ein HTML-Grundgerüst übertragen, sowie eine JavaScript-Datei, die beim Aufruf die eigentlichen Datensätze via jquery.couch.js aus der CouchDB nachlädt.

Als Mapping-Library verwenden wir Leaflet, eine Open-Source Bibliothek für Kartendarstellungen im Browser. Leaflet abstrahiert von verschiedenen Kartenprovidern und erlaubt es somit, unterschiedliche Datenquellen zu verwenden, wie zum Beispiel auch Bing Maps oder Cloudmade. Letzteres ist ein Service, der auf Basis der Open Street Map Daten Kartenkacheln mit individuellen Stilen rendert und hostet – für Visualisierungen oft sehr hilfreich, da reguläre Karten meist zu viele Karteninformationen enthalten oder farblich überladen sind. In unserem Fall haben wir einen einfach Graustufenkarte gewählt. Leaflet selbst lässt sich relativ leicht verwenden, es muss eine CSS-Datei sowie eine JavaScript-Datei importiert werden, und ein div-Block im HTML enthalten sein, worin später die Karte gerendert werden soll. Somit sieht unser HTML-Gerüst zu Beginn so aus:

<!doctype html>
<html>
<head>
	<link rel="stylesheet" href="style/leaflet.css" />
	<script type="text/javascript" src="js/jquery.min.js"></script>
	<script type="text/javascript" src="js/jquery.couch.js"></script>
	<script type="text/javascript" src="js/leaflet.js"></script>
	<script type="text/javascript" src="js/maploader.js"></script>
</head>
<body>
	<div id="map"></div>
</body>
</html>

Es werden jQuery, jquery.couch.js und die Leaflet-Libs geladen, und die letzte importierte JavaScript-Datei soll nun unseren Code zum initialisieren der Karte und dem Laden der Daten aus der CouchDB enthalten. Zunächst erstellen wir eine Karte und rendern sie, sobald die Seite vollständig geladen wurde (jQuery Callback für document.ready):

$(document).ready(function(){

		var cloudmadeUrl = 'http://{s}.tile.cloudmade.com/[YOUR_API_KEY]/33481/256/{z}/{x}/{y}.png';
		var cloudmadeAttribution = 'UlmApi.de / Shape Files: Stadt Ulm (cc-by-sa), Map data © 2011 OpenStreetMap contributors, Imagery © 2011 CloudMade';
		var cloudmade = new L.TileLayer(
			cloudmadeUrl, {
				maxZoom : 18,
				attribution : cloudmadeAttribution
		});

		var map = new L.Map('map', {
			center : new L.LatLng(48.399976,9.995399),
			zoom : 12,
			layers : [ cloudmade ],
			zoomControl : false
		});
});

In der cloudmadeUrl muss für Cloudmade Karte ein korrekter API-Key angegeben werden, der nächste Parameter im Pfad identifiziert den Kartentyp. Beim Initialisieren der Karte wird dann die ID des divs angeben, bei uns ‘map’. Nun sollte unsere Karte bereits dargestellt werden, nachdem wir die CouchApp neu deployen (außerhalb des Fokus dieses Artikels, mehr dazu auf couchapp.org).

Was nun noch fehlt, ist das Nachladen der Geodaten aus der CouchDB und die Anzeige auf der Karte. Hierfür verwenden wir jquery.couch.js als Wrapper für die AJAX-Requests gegen CouchDB und die GeoJSON-Funktionalität von Leaflet:

$.couch.db('database_name').view('design_doc_name/view_name', {

	success: function(data){
		if(data && data.rows && data.rows.length){

			var geoJsonLayer = new L.GeoJSON();

			for(var i = 0;i<data.rows.length;i++){
				geoJsonLayer.addGeoJSON(data.rows[i].value.geometry);
			}

			map.addLayer(geoJsonLayer);
		}
	}
});

Das obige Snippet sollte im vorherigen Code hinter der Erzeugung der Karte eingefügt werden. Es ruft von der Datenbank ‘database_name’ den View ‘view_name’ des Design-Dokuments ‘design_doc_name’ auf, und iteriert bei erfolgreicher Abfrage über alle Zeilen. Von jeder Zeile wird dabei die geometry-Property zu einem GeoJSON-Layer hinzugefügt, der am Ende an die Karte übergeben wird. Da unser View aus Teil 1 bereits GeoJSON generiert, und Leaflet nativ GeoJSON lesen und darstellen kann, ist das Hinzufügen von Geodaten auf die Karte sehr einfach.

Hier noch ein paar weiterführende Links mit vertiefenden Inhalten zu den einzelnen Themen:

• Leaflet Reference
• CouchApp
• Diplomarbeit von Lena Herrmann über Webanwendungen mit CouchDB und CouchApp

Die Hochschulgruppe Open Data Ulm hat es sich zur Aufgabe gemacht, offene und öffentliche Daten rund um die Region Ulm zu aggregieren, aufzuarbeiten und zu visualisieren. Näheres zu diesem Projekt sowie bereits gesammelte Datensätze gibt es unter UlmApi.de

Für unser Vorhaben habe ich als Persistenzlösung die dokumentenorientierte Datenbank CouchDB gewählt, da sie für uns mehrere interessante Features bietet:

• schemalos: Anders als relationale Datenbanken benötigen schemalose Datenbanken keine im Voraus fest definierte Struktur der Einträge. Für unsere Geodaten ist dies sehr hilfreich, da außer einer ID und den Geodaten noch beliebige zusätzliche Daten pro Eintrag mitgespeichert werden können.
• JSON: Für die Speicherung strukturierter Daten stellt dieses Format eine leichtgewichtige Alternative zu XML dar.
• webbasiert: Die Datenbank ist zugleich ein Webserver und der Zugriff auf die Daten läuft somit über HTTP.
• verteilt/replizierend: Ein wichtiges Konzept von CouchDB ist die einfache aber mächtige Replikation zwischen verschiedenen Instanzen. Im Kontext unserer offenen Datensammlungen ermöglicht dies, dezentralte Kopien der Daten anzulegen, diese lokal zu editieren oder erweitern und wieder auf unsere Hauptdatenbank zu laden.
• Attachments: Neben strukturierten Daten lassen sich auch ganze Dateien speichern. Dies ist vor allem für archivierte Rohdaten in proprietären Formaten interessant.
• CouchApps: Neben der Speicherung der Daten sind vor allem einfache Anwendungen interessant, die diese visualisieren oder aufbereiten. Das Konzept der CouchApps ermöglicht es uns, simple Webanwendungen direkt auf der Datenbank zu deployen und verfügbar zu machen.
• räumliche Indizes: Dank Volker Mische besitzt CouchDB einen zusätzlichen Index (GeoCouch), der statt eindimensionaler B-Bäume zweidimensionale R-Bäume benutzt. Damit lassen sich Dokumente mit räumlichen Daten abspeichern, indizieren und effizient abfragen.

Von der Stadt Ulm haben wir als ersten Datensatz Shapefiles der Ulmer Stadtteile und Stadtviertel bekommen. Diese wurden zunächst vom Ausgangsformat (Gauss-Krueger-Shapefiles) in das GeoJSON-Format mit WGS84-Koordinaten konvertiert. Mithilfe eines kleinen node.js Skriptes wurden die einzelnen Shapes dann als Dokumente auf die Couch geladen.

Ein Dokument hat hierbei folgende Form (Originaldokument):

{
   "_id": "ul-st14",
   "_rev": "1-797187e292d93b6d661ca8f7fec3f6c9",
   "type": "stadtteil",
   "name": "Weststadt"
   "geometry": {
       "type": "Feature",
       "properties": {
           "identifier": "ST 14",
           "name": "Weststadt"
       },
       "geometry": {
           "type": "Polygon",
           "coordinates": [
               [
                   [
                       9.981459,
                       48.395751
                   ],
                   …
              ]
           ]
       }
   },
   "creator": "Stadt Ulm",
   "license": {
       "name": "Creative Commons - Namensnennung-Weitergabe unter gleichen Bedingungen 3.0 Deutschland (CC BY-SA 3.0)",
       "link": "http://creativecommons.org/licenses/by-sa/3.0/de/"
   },
}

Die _id bestimmt das Dokument eindeutig, das _rev Feld ist für die Versionskontrolle verantwortlich. Als ID haben wir einen internen Identifier der Stadt genommen und noch mit einem “ul” Präfix versehen. Der Rest des Dokuments kann frei strukturiert werden. In unserem Fall verwenden wir noch ein type Feld, durch das wir später Dokumente unterschiedlichen Typs unterscheiden können (z.B. stadtteil oder stadtviertel). Das geometry Feld (hier gekürzt) enthält die geografischen Daten im GeoJSON-Format. Die sonstigen Felder beschreiben noch den Urheber und die Lizenz der Daten sowie den Namen des Eintrags.

Nun ist die Datenbank gefüllt, später sollen aber die Daten auch wieder abgefragt werden können. Als “NoSQL” Datenbank bietet CouchDB hierfür aber keine SQL-Statements an, stattdessen muss man mithilfe von MapReduce beschreiben, wie aus den Daten Indizes gebildet werden sollen:

function(doc) {
	if (doc.type) {
		if(doc.type === 'stadtviertel'){
		    emit(['stadtviertel', doc._id], {
		    	'geometry' : doc.geometry,
		    	'label' : "<b>Stadtviertel "+doc.name+"</b><br/>ID: "+doc._id+"<br/>(Stadteil "+doc.stadtteil+")"
		    });
		}
		else if(doc.type === 'stadtteil'){
		    emit(['stadtteil', doc._id], {
		    	'geometry' : doc.geometry,
		    	'label' : "<b>Stadtteil "+doc.name+"</b><br/>ID: "+doc._id
		    });
		}
	}
};

Damit erzeugen wir eine sortiere Liste von Schlüssel-Wert-Paaren. Der Schlüssel ist selbst wieder komplex und besteht aus zwei Teilen. Der erste Teil ist der Typ, der zweite Teil die ID des Dokuments. Damit kann man später durch die sogenannte View Collation Abfragen durchführen, die sich auf einen bestimmtem Typ beschränken (zur Wiederholung: ohne SQL gibt es hier auch kein WHERE Statement). In diesem Fall werden bisher nur Dokumente des Typs stadtteil oder stadtviertel eingetragen, und als Wert eines Eintrages wird bereits die spätere Nutzung auf einer Karte vorbereitet – es werden die Geodaten sowie ein Label indiziert. Damit lassen sich nun schon Stadtteile/Stadtviertel abfragen.

Ergänzt man dies noch um einen räumlichen Index, so werden auch räumliche Abfragen ermöglicht. Hierfür werden in den Index als Schlüssel die Geodaten (unverändert im GeoJSON Format) eingetragen, den Wert selbst bliebt leer, da das Feld _id sowieso eingetragen wird und vorest keine weiteren Daten mehr benötigt werden:

function(doc){
	if(doc.geometry && doc.geometry.geometry){
		emit(doc.geometry.geometry, null);
	}
};

(Das etwas merkwürdig anmutende doc.geometry.geometry entstand einerseits dadruch, dass unser Feld mit dem GeoJSON-Objekt geometry heißt, das GeoJSON-Objekt selbst aber komplex ist und nur in einem Teil davon die eigentlichen Geodaten hinterlegt sind.)

Mithilfe dieses Index lässt sich nun bei einem gegebenen geografischen Raum überprüfen, welche Objekte darin enthalten sind. Also zum Beispiel ausgehend von einer Koordinate, ob sie sich in Ulm befindet und wenn ja, in welchem Stadtteil/Stadtviertel.

Im nächsten Teil wird näher betrachtet, wie die nun abgespeicherten und indizierten Geodaten im Browser auf einer Karte dargestellt werden können, und zwar direkt aus CouchDB heraus.

Im Vergleich zu klassischen SQL-Datenbank erfordern NoSQL-Datenbank vor allem bei der Datenabfrage ein Umdenken. Im Falle von CouchDB lässt sich zwar mit View Collation schon einiges erreichen, allerdings bei weitem nicht alles. Auf eine solche Grenze bin ich gestoßen, als ich Zeiträume speichern und abfragen wollte, also Einträge die ein Start- und Enddatum besitzen. Anfragen auf diese Daten könnten nun zu einem fixen Zeitpunkt alle darin ablaufenden Einträge erfragen, oder ausgeweitet auf einen Zeitraum auflisten, welche Einträge innerhalb eines Zeitfensters liegen. All dies ist mit CouchDB nicht wirklich lösbar.

Einen kleinen Workaround bietet die Idee, die Zeitleiste zu segmentieren und immer dann für einen Eintrag einen Key zu emitten, wenn der Zeitraum des Eintrages innerhalb dieses Bereichs liegt. Eine solche Map-Funktion könnte wie folgt aussehen. Hierbei wird für einen Eintrag jeweils ab dem Beginn für alle 5 Minuten ein Schlüssel in den Index emittiert.

Dokumentaufbau:

{
   "_id": "s-ffc0b6b0-59d4-4a3b-ad36-7ec05e7db1de",
   "begin": "2010-08-05T09:11:52.156Z",
   "end": "2010-08-05T09:23:13.457Z"
}

Map-Funktion:

//length of time segment (here 5 min)
var periodLength = (60*5);

function(doc) 
{
        if(doc.begin && doc.end)        
        {
                //start and end time as UNIX timestamps (seconds, not milliseconds)
                var begin =  Math.round(new Date(doc.begin).getTime()/1000);
                var end =  Math.round(new Date(doc.end).getTime()/1000);

                //calculate first matching segment of period
                var p = (begin - (begin%periodLength));

                //emit key for each matching period
                while(p<=end)
                {
                        emit([p, doc._id], null);
                        p = p + periodLength;
                }
        }
}

Der resultierende View sieht dann in etwa so aus:

Oder als Abfrage:
http://localhost:5984/entries/_design/entries/_view/docsByPeriodList?startkey=[1280998800]&endkey=[1281000193,{}]

{"total_rows":3,"update_seq":2,"offset":0,"rows":[
{"id":"s-ffc0b6b0-59d4-4a3b-ad36-7ec05e7db1de","key":[1280999400,"s-ffc0b6b0-59d4-4a3b-ad36-7ec05e7db1de"]15,"value":null},
{"id":"s-ffc0b6b0-59d4-4a3b-ad36-7ec05e7db1de","key":[1280999700,"s-ffc0b6b0-59d4-4a3b-ad36-7ec05e7db1de"],"value":null},
{"id":"s-ffc0b6b0-59d4-4a3b-ad36-7ec05e7db1de","key":[1281000000,"s-ffc0b6b0-59d4-4a3b-ad36-7ec05e7db1de"],"value":null}
]}

Eine viel bessere Lösung bietet jedoch die CouchDB-Erweiterung GeoCouch. Dank des R-Trees lassen sich Bereichtsabfragen effizient durchführen. Da GeoCouch eigentlich für zweidimensionale Geokoordinaten gedacht, muss sie und die GeoJSON-Syntax etwas missbraucht werden. Anstatt einer WGS84-Koordinate emittieren wir einfach einen UNIX-Zeitstempel und lassen den anderen Grad leer:

function(doc) 
{
        if(doc.begin && doc.end)        
        {
                //start and end time as UNIX timestamps (seconds, not milliseconds)
                var begin =  Math.round(new Date(doc.begin).getTime()/1000);
                var end =  Math.round(new Date(doc.end).getTime()/1000);

                emit(
                        {
                                type: "Point",
                                bbox : [0,start,0,end]                              
                        }, null
                );
        }
}

So lassen sich nun effiziente Bereichsabfragen durchführen:
http://localhost:5984/entries/_design/entries/_spatial/entriesByPeriod?bbox=0,1280998800,0,1281000600

{"update_seq":16,"rows":[
{"id":"s-ffc0b6b0-59d4-4a3b-ad36-7ec05e7db1de","bbox":[0,1280999512,0,1281000193],"value":null}
]}