Techtalk: Komplexe Abfragen einfach formulieren - die Entstehung einer künstlichen Sprache

Techtalk
Techtalk: Komplexe Abfragen einfach formulieren - die Entstehung einer künstlichen Sprache

Die weedu Query Language ist ein zentrales Element in weedu und erlaubt erstmals die sehr flexible Abfrage des gesamten Datenbestands durch die Benutzer. Das Dialogsystem unterstützt sowohl Einsteiger als auch erfahrene Benutzer wirkungsvoll und macht so das volle Potential von WQL für einen breiten Benutzerkreis verfügbar. Die weitgehende Automatisierung der Grammatik- und XSL-Erstellung aufgrund von Attributen im Domain Model sowie das sehr einfache, Frage-Antwort-basierte Benutzerinterface führen zudem zu sehr tiefen Kosten für weitere Datentypen und Abfragemöglichkeiten. Damit erfüllen die weedu Query Language und das weedu Dialogsystem die skizzierten Anforderungen auf innovative und langfristig sinnvolle Art und sind damit ein interessanter Enterprise-Search-Baustein.

Techtalk Serie Enterprise Search, Teil 1: Enterprise Search

Jedes Unternehmen hat zahlreiche Systeme mit vielen Daten – über seine Kunden, seine Produkte, seine Prozesses und vieles mehr. Leider sind diese Daten oft nur ungenügend zugänglich und generieren deshalb nur wenig Wert.

Enterprise Search als Komponente im GARAIO E-Business-Motor nimmt sich dieser Herausforderung an und stellt Werkzeuge zur Verfügung, um Daten durchsuchbar, auffindbar und abfragbar zu machen. In einer losen Serie von Tech Talk Beiträgen zeigen wir entsprechende Konzepte und Lösungen aus der Praxis.

Abfragen im Projekt weedu

Im Rahmen des Projekts weedu entwickelt Didacware mit der Untersützung von GARAIO eine Schulverwaltungslösung für die ganze Kalaidos Bildungsgruppe. Dabei werden erstmals die Daten aller Unternehmen in einem System vereinigt, um entsprechende Synergien zugänglich zu machen. Entsprechend sind die Datenmengen recht beachtlich: ca. 500‘000 Personen, mehrere Millionen Kommunikationsmittel, Tausende von Modulen, Anlässen etc. sollen verwaltet werden.

In dieser Datenflut sollen die Benutzer die für ihre Tätigkeit relevanten Datensätze finden können. Dazu verfügt weedu über eine leistungsfähige Volltextsuche, die anhand von bruchstückhafter Information den Zugriff auf den gesuchten Datensatz erlaubt. Dabei kommt für die Bewertung der Datensätze neben den eingegebenen Begriffen auch Kontextinformation über den Benutzer zum Einsatz, so dass jeder Benutzer die für ihn relevantesten Datensätze findet. Ähnlich wie bei einer Google-Suche wählt der Benutzer dann anhand der angezeigten Zusammenfassung den richtigen Datensatz aus.

Wenn jedoch nicht nur ein einzelner Datensatz interessiert, sondern alle Datensätze mit bestimmten Eigenschaften, dann wird es noch ein wenig anspruchsvoller. Diesen Anwendungsfall bezeichnen wir in weedu als „abfragen“ (im Unterschied zum obigen „suchen“).

Traditionelle Abfragen

Um eine Abfrage auszuführen, muss der Benutzer die Bedingungen erfassen können. Traditionellerweise erfolgt dies mit spezialisierten Eingabemasken für den jeweiligen Zweck, z.B. eine Maske „Teilnehmer pro Klasse“ mit einem Eingabefeld für die Klasse. Damit kann der Benutzer seine Kriterien erfassen und die Abfrage ausführen.

Abbildung 1: Klassische Abfragemaske mit vordefinierten Eingabemöglichkeiten, spezifisch auf bestimmte Anwendungsfälle zugeschnitten

Der Benutzer ist in der Auswahl seiner Kriterien stark eingeschränkt, so dass in recht kurzer Zeit sehr viele solche Abfragen entwickelt werden müssen, die alle ähnlich aber nicht gleich sind. Diese Inflation an vorgefertigten Abfragen wollten wir in weedu vermeiden und suchten deshalb nach einer flexibleren Lösung, mit der die Benutzer ihre Abfragen selber erfassen können.

Die ersten Gedanken orientierten sich dabei am Modell des Abfragesatzes, wie ihn z.B. FogBugz kennt, oder auch an einer Dropdown-basierten Zusammenstellung der Bedingungen wie in JIRA.

Abbildung 2: Abfragesystem von FogBugz mit einem anpassbaren Satz (Quelle: www.fogbugz.com)

Abbildung 3: „Basic“-Abfragesystem von JIRA (www.atlassian.com/jira) mit Dropdowns für die Eingabe von Kriterien

Bereits im Design wurde sichtbar, dass dies ein sehr komplexes User Interface ergibt, das somit teuer zu entwickeln und zu pflegen würde. Zudem wurde klar, dass schon mittelkomplexe Abfragen wie „Alle Personen mit einer Ausbildung an der Kalaidos Fachhochschule“ mit einer solchen Lösung kaum mehr formuliert werden können, ohne wieder zahlreiche Spezialbedingungen einzeln zu programmieren. Es war aber absehbar, dass viele der im Alltag erforderlichen Abfragen durchaus eine solche Komplexität aufweisen würden, so dass dies ermöglicht werden musste.

Anforderungen an das weedu Abfragesystem

Das Projektteam suchte deshalb nach Alternativen, welche die folgenden Anforderungen abdecken sollten:

Das Abfragesystem muss für alle in weedu verwalteten Daten nutzbar sein

Einsteiger und Gelegenheitsbenutzer müssen einfache Abfragen selber formulieren können

Poweruser müssen Abfragen schnell und effizient erfassen, verändern, kopieren etc. können

Ein Ausdruck einer Abfrage muss die zugrundeliegenden Bedingungen klar zeigen

Die in der Abfrage ausgegebenen Informationen (Spalten) sowie die Sortierung müssen vom Benutzer frei gewählt werden können

Bedingungen müssen beliebig kombiniert werden können

Abfragen müssen als Daten in weedu hinterlegt werden können (z.B. für zulässige Wahlfächer)

Inspiriert von der Abfragesprache in JIRA (JIRA Query Language) prüfte das Team auch den Einsatz einer Abfragesprache: Damit können in JIRA extrem mächtige Abfragen ausgeführt werden, zudem unterstützt von einer Art Autovervollständigung für die Eingabe von Namen und Werten – für Poweruser ein wahrer Traum.

Abbildung 4: „Advanced“-Abfragesystem in JIRA (www.atlassian.com/jira) mit der Abfragesprache JQL und Autocomplete

Unsere Erfahrung mit JIRA zeigt allerdings, dass weniger geübte Benutzer damit grosse Schwierigkeiten haben. Zudem kann in JIRA die Darstellung nicht über die Abfrage gestaltet werden.

Die weedu Query Language (WQL)

Im Team setzte sich die Erkenntnis durch, dass die geforderte Ausdruckskraft nur mit einer eigens dafür geschaffenen Sprache erreicht werden konnte. Diese Sprache sollte auch für nicht-Techniker verständlich sein, so dass jeder die formulierten Abfragen verstehen und allenfalls anpassen könnte.

Da die Benutzer nahezu ausschliesslich in Deutsch arbeiten, sollte sich die Abfragesprache an Deutsch anlehnen und somit natürlich lesbar sein. Die Verwendung echter deutscher Sätze mit allen entsprechenden grammatischen Möglichkeiten wurde aber recht schnell ausgeschlossen.

So entstand eine erste Grammatik mit den Bestandteilen „Datensatzart“, „Bedingungen“ und „Sortierung“. Die Datensatzart ist ein erster Filter und bestimmt, welche Bedingungen und Spalten/Sortierungen existieren.

Gültige einfache Abfragesätze sind z.B.:

  • Personen sortiert nach Name
  • Publikationen mit Aktiv = nein

Die Sprache wurde dann in mehreren Schritten erweitert, um weitere Möglichkeiten zu schaffen. Inzwischen hat ein WQL-Abfragesatz die folgenden Elemente:

  • Datensatzart (wie oben, zusätzlich mit dem Spezialfall „Alles“)
  • Spaltenauswahl (Spalten der gewählten Datensatzart, aber auch virtuelle Spalten wie „hat Tag testversand-mai2014“)
  • Beziehungen inkl. Subabfragen (ermöglichen die Navigation zwischen Datensätzen, z.B. „Anmeldungen an Modul X“)
  • Bedingungen (Einschränkung der Datensätze, beliebig kombinierbar, auch mit Verneinung)

Sortierung

Optionen (z.B. Darstellungsvarianten)

Eine so formulierte Abfrage ist immer noch annähernd ein deutscher Satz, der gelesen und verstanden werden kann und umfasst alle oben geforderten Möglichkeiten. Ein Poweruser, der die Sprache gut kennt, kann so nahezu alle Daten in der gewünschten Aufbereitung aus weedu herausholen. Aber was macht ein Einsteiger?

Das weedu Abfrage Dialogsystem

Die weedu Query Language erfüllt viele der genannten Anforderungen, aber sie erfordert vom Benutzer viel Vorwissen und ist für Einsteiger ungeeignet. Aufgrund der komplexen Möglichkeiten ist sie sogar für Poweruser anspruchsvoll und ohne Eingabeunterstützung kaum nutzbar.

Ausfüllhilfen gibt es inzwischen an vielen Orten: In Formularen, in Entwicklungswerkzeugen etc. unterstützen sie sowohl Einsteiger als auch geübte Benutzer wirksam. Einen solchen Ansatz versuchte das Team auch für die weedu Query Language zu schaffen, wobei vor allem auch ungeübte Benutzer wirksam unterstützt werden sollten.

Die Vision war ein Frage-Antwort-Spiel zwischen System und Benutzer:

System: Was möchtest Du abfragen?

Benutzer: Personen

System: Möchtest Du Bedingungen formulieren oder alle Personen?

Benutzer: Bedingungen formulieren

System: Welche Bedingung müssen die Personen erfüllen?

Dabei sollte der Benutzer möglichst wenig selber wissen müssen. Also müsste das System ihm die Frage stellen und Vorschläge für mögliche Antworten machen, aus denen er nur noch auswählen muss. Das Konzept des weedu Abfrage Dialogsystems war somit entstanden: Mit einer Serie von Frage-Vorschläge-Auswahl-Schritten sollte der Benutzer seine Abfrage in WQL formulieren können.

Abbildung 5: Der Start für jede Abfrage: die Auswahl der Datensatzart

Anspruchsvoll ist in diesem Zusammenhang, dass gewisse Fragen Antworten haben, die sich aus den vorhandenen Daten ergeben, so dass sie dynamisch ermittelt werden müssen. Dieser Unterschied zwischen „statischen“ und „dynamischen“ Teilen soll aber für den Benutzer möglichst wenig spürbar sein.

Abbildung 6: Abfrage nach Tags - die möglichen Antworten kommen live aus den durchsuchten Daten und zeigen auch bereits statistische Daten an.

Eine ähnliche Herausforderung besteht bei der Eingabe von Beziehungen, da dort ein einzelner Bezugsdatensatz gewählt werden muss. Dazu integriert das Dialogsystem die Volltextsuche von weedu transparent in den Dialogprozess:

Abbildung 7: Anfrage mit eingebetteter Volltextsuche für die Auswahl des Bezugsdatensatzes

In vielen Fällen interessiert allerdings nicht ein einzelner Bezugsdatensatz, sondern wiederum eine Abfrage. Auch dies ist mit der weedu Query Language dialoggestützt formulierbar:

Abbildung 8: Eingabe einer Abfrage als Quelle für die Bezugsdatensätze. Spätestens in solchen Fällen würde ein formularbasiertes Abfragesystem scheitern.

Die Darstellung der Ergebnisse kann ebenfalls über das Dialogsystem gesteuert werden, indem eine eigene Spaltenauswahl und/oder die gewünschte Sortierung angeben werden können. Entsprechende Fragen stellt das System im Dialog:

Abbildung 9: Dialoggeführte Definition der Darstellung des Ergebnisses

Abfragen als einfacher Text

Eine Abfrage in weedu Query Language ist ein simpler Text und kann somit ganz einfach kopiert und verteilt werden. Der natürliche Arbeitsfluss des Benutzers mit Cut & Paste etc. wird optimal unterstützt. Gewisse Benutzer haben immer einen Editor offen, in dem sie „Schnipsel“ ablegen – auch das geht mit Text wie WQL.

Zudem ist in weedu der aktuelle Abfragesatz immer in der Adresse der Abfrageseite enthalten, so dass eine Abfrage jederzeit mit der Browser-Funktion als Favorit gespeichert oder jemand anderem per Mail gesendet werden kann.

Die Wahl von Text als Medium für die Abfrage schafft somit viel Flexibilität, aber auch ein paar zusätzliche Herausforderungen: Bezugsdatensätze und andere Werte müssen für den Benutzer lesbar und für das System technisch eindeutig dargestellt werden. Dazu kommen ein paar CSS Tricks zum Einsatz, welche den Abfragetext anders aussehen lassen, als er eigentlich ist und so die technisch korrekten Werte im Text für die Darstellung umwandeln.

Abbildung 10: Darstellung des Texts „Anmeldungen von f42f708c-cad2-54d9-bf79-e6a6055d8ab0“ in weedu

Die Umwandlung zwischen den zwei Darstellungen erfolgt vollautomatisch und transparent: Der Benutzer gibt im Dialogsystem z.B. den Namen ein und wählt dann die Person aus der Suche aus. Damit wählt er eigentlich die technische ID der Person aus, die aber wiederum über CSS-Manipulationen mit ihrem Namen dargestellt wird. Geübte Benutzer können auch eine Bezugsentität markieren, kopieren und anderswo einsetzen, fast wie wenn es normaler Text wäre. Durch die Speicherung der ID ist die Abfrage aber dennoch resistent gegen Änderungen am Namen des Bezugsdatensatzes und kann zwischen verschiedenen Datensätzen mit dem gleichen Namen zuverlässig unterscheiden.

Erweiterungspunkte und „Expert Mode“

In der weedu Query Language sind auch einige Erweiterungspunkte umgesetzt, die im Dialogsystem nicht angeboten werden. Poweruser können sie verwenden, wenn sie sie kennen, ansonsten kommen sie vor allem in Abfragen zum Einsatz, die das System intern generiert.

Andiskutiert wurde bereits, ob das Dialogsystem verschiedene Stufen kennen sollte, damit Einsteiger mit möglichst wenigen Fragen die alltäglichen Abfragen formulieren können und Poweruser die volle Funktionsvielfalt sehen. Dies wurde bisher nicht umgesetzt, könnte aber mit der bestehenden Struktur recht einfach erfolgen; anspruchsvoll wäre dabei vor allem auch die Definition, was einem „Standardbenutzer“ gezeigt werden soll und was nicht.

Die technische Umsetzung

Die Search Engine: Apache Solr

Als Backend für Suche und Abfrage dient in weedu Apache Solr, eine sehr leistungsfähige Open Source Search Lösung. Die in weedu verwalteten Daten werden in eine geeignete Form gebracht und als Dokumente (eigentlich Feld-Wert-Paare) in Solr abgelegt. Die Aktualisierung von Solr erfolgt in einem Push-Modell laufend, so dass Solr jederzeit ein vollständiges read-only-Abbild des Datenbestands enthält.

Die Daten werden in diesem Index weitgehend denormalisiert abgelegt, so dass zu jedem Datensatz alle seine Daten direkt vorliegen. Ebenfalls vorausberechnet werden die Zusammenfassungen für die Darstellung in der Suche und weitere berechnete Felder.

Dies alles hat zum Ziel, dass jede beliebige Suche oder Abfrage in weedu als Query an Solr umgesetzt werden kann. Die SQL Datenbanken kommen somit in diesen Szenarien nicht zum Einsatz.

Die Aufbereitung von Inhalten aus den verschiedenen Datenquellen und ihre Zusammenführung in Solr wird in einem separaten Artikel der Serie Enterprise Search eingehender beleuchtet werden.

Die Grammatik

Das Herzstück der weedu Query Language ist die Grammatik, welche abschliessend beschreibt, wie ein WQL-Abfragesatz aufgebaut ist, welche Elemente in welcher Form zulässig sind etc. Diese Grammatik von WQL wird in der üblichen Backus-Naur-Form (BNF -- http://de.wikipedia.org/wiki/Backus-Naur-Form) beschrieben.

BNF beschreibt eine Sprache als Menge von kleinen Bausteinen und ihren zulässigen Kombinationen. Der folgende Ausschnitt aus der WQL-Grammatik beschreibt den Anfang aller Abfragen und definiert die möglichen Werte:

Abbildung 11: Ausschnitt aus der Grammatik: ermöglicht die Eingabe der drei Datensatztypen „Abonnemente“, „Anlässe“ und „Anmeldungen“ mit entsprechenden Strukturbezeichnungen

Dieses Beispiel ist nur ein sehr kleiner Ausschnitt aus der gesamten Grammatik für WQL, zeigt aber den grundsätzlichen Aufbau mit Regeln (die in <> verpackten Teile) und Literals (in ''). Die gesamte WQL-Grammatik umfasst derzeit ca. 5‘000 Zeilen.

Der Parser

Die Grammatik als BNF kann nicht direkt verwendet werden, sondern dient nur als Vorlage für die Erstellung eines Parsers. Parser bzw. Parsergeneratoren gibt es auf dem Markt verschiedene, darunter z.B. die Klassiker yacc oder Antlr.

In weedu kommt der GOLD Parser (www.goldparser.org) zum Einsatz, um die als BNF-Text vorliegende Grammatik in eine ausführbare Form zu bringen. Dabei untersucht der GOLD Parser alle möglichen Bausteine und erzeugt daraus eine Zustandsmaschine (deterministic finite automaton) für die Erkennung der zulässigen Token (aus dem Beispiel oben wären dies ‚Abonnemente‘, ‚Anlässe‘ und ‚Anmeldungen‘) sowie eine LALR-Tabelle, mit der aus den erkannten Token auf die entsprechenden Regeln geschlossen werden kann.

Das durch den GOLD Parser erzeugte kompilierte Grammatik-File wird dann durch die Open-Source-Komponente bsn-goldparser (https://code.google.com/p/bsn-goldparser/) in .net Code geladen und ausgeführt. Das Ergebnis dieser Ausführung ist ein Objektbaum, der die in der Grammatik definierten Regeln wiedergibt und den wir zur weiteren Verarbeitung als XML serialisieren.

Die erwarteten Token als Grundlage für das Dialogsystem

Eine nützliche Eigenschaft eines Parsers ist, dass er für jeden eingegebenen Text angeben kann, bis wo er ihn korrekt lesen (d.h. bekannten Token und Regeln zuordnen) konnte und was er anschliessend erwartet hätte.

Dies stellt die Grundlage für das Dialogsystem dar: Die Token, welche der Parser an der Stelle des Cursors akzeptieren würde, sind die möglichen Antworten im Dialogsystem. Da im GOLD Parser System keine Möglichkeit besteht, um Metadaten zu Regeln oder Token zu hinterlegen und zugänglich zu machen, haben wir einen Kniff verwendet: Die Grammatik wird um zusätzliche erwartete Token erweitert, die die Fragen und Erläuterungen des Dialogsystems transportieren.

Diese Token beginnen mit einem (frei gewählten) Unicode-Sonderzeichen und werden durch das weedu Abfragesystem aus der Menge der erwarteten Token ausgefiltert und zum Dialog aufbereitet.

Abbildung 13: Liste der erwarteten Token nach der Eingabe von „Abonnemente“

Im obigen Beispiel sieht man zuunterst die Frage (markiert mit einem einzigen ¿), die möglichen Antworten (ohne ¿) sowie die Erläuterungen zu den Antworten (mit mehreren ¿). Das Dialogsystem filtert diese Token-Liste vom Parser und erstellt daraus die benutzergerechte Ansicht.

Abbildung 14: Aus den erwarteten Token generierter Dialog

Für den bereits erwähnten Übergang zu dynamischen Inhalten (z.B. der Auswahl von existierenden Werten) kommen ebenfalls speziell formatierte Token zum Einsatz, die dann im Dialogsystem umgewandelt werden.

Umwandlung des Parser-Ergebnisses in ein Solr Query

Nachdem der Parser die Grundlage für das Dialogsystem liefert und eine XML-Darstellung des eingegebenen Texts erstellt, muss diese noch in eine Solr-Abfrage umgewandelt werden, um die gewünschten Daten auch tatsächlich aus Solr beziehen zu können.

Eine XSL-Transformation wandelt die XML-Darstellung aus dem Parser in ein Solr Query um. Da ein Solr Query aus mehreren Teilen besteht, nutzt die XSL Transformation neben dem üblichen Output als Text auch Extension-Objekte, um weitere Parameter wie z.B. die Spaltenliste für das Solr Query bereitzustellen.

Abbildung 15: Ausschnitt aus der XSL-Transformation für die Umwandlung von „Abonnemente“

Das Domain Model als Grundlage für Grammatik und XSL Transformation

Bereits der oben gezeigte kleine Ausschnitt aus der Grammatik zeigt, dass die Grammatik sehr viele repetitive Elemente aufweist und sehr gross wird. Neben der Grammatik existiert zudem auch die XSL-Transformation, welche jedes Grammatik-Element umwandeln können muss. Diese beiden Teile manuell zu erstellen und zu pflegen wäre sehr aufwändig und fehleranfällig.

bbildung 16: Ausschnitt aus der Domain-Klasse „Abonnement“ mit Attributen für die automatische Generierung von Grammatik und XSL-Transformation

Die so generierten Grammatik-Fragmente werden beim Deployment von weedu zusammengeführt zu einer grossen Grammatik, die anschliessend kompiliert und geladen wird. Entsprechend wird auch aus den XSL-Fragmenten eine grosse Transformation gebildet, die anschliessend geladen werden kann.

Erweiterbarkeit über Applikationsgrenzen hinweg

Diese Kombination von Grammatik und Transformation aus Einzelteilen bietet neben der viel einfacheren Pflege direkt im Domain Model einen weiteren entscheidenden Vorteil: Beliebige Systeme können Fragmente für die Grammatik und die Transformation beisteuern und so die Abfragesprache erweitern, ohne dass die „betroffenen“ Applikationen verändert werden müssen.

Ein interessantes Beispiel dafür ist das Tagging in weedu: Alle Datensätze wie Personen, Module, Anlässe etc. können in weedu mit Tags versehen werden. Die Implementation des Tagging ist aber losgelöst von den getaggten Entitäten in einer eigenen Applikation umgesetzt. Diese Applikation erzeugt Grammatik- und XSL-Fragmente für die Tagging-fähigen Entitäten und erweitert so ihre Grammatik.

Spannend ist z.B. die Schaffung neuer, konfigurierbarer Spalten auf beliebigen Entitäten, wie der folgende Auszug aus dem Dialogsystem zeigt:

Abbildung 17: Dialogschritt, um eine Personen-Abfrage eine Spalte für ein bestimmtes Tag hinzuzufügen

Der oben gezeigte Dialogschritt zeigt exemplarisch die Kraft von WQL: Die Entität Personen wird vollkommen dynamisch um Spalten erweitert, die der Benutzer durch die Vergabe von Tags soeben selber geschaffen hat.