Non-Standard Semantics for Graph Query Languages

Als effiziente Alternative zur klassischen Subgraphisomorphie haben sich Simulationen für diverse Aufgaben im Graphdatenmanagement etabliert, z. B. in Beschreibungssprachen baumstrukturierter Daten. Dieser Theorie widmen wir uns zuallererst im Hinblick auf moderne (nicht braumstrukturierte) Graphdatenbankmodelle. Nach eingehender Studie der Rolle von Wurzelknoten gelingt die Ableitung einer korrekten Semantik für Graphschemata. Außerdem erweitern wir das Modell um verpflichtende Attribute, für die wir ebenfalls eine korrekte Semantik angeben. Simulationen werden auch bzgl. ihres pragmatischen Werts für einfache Graphanfragen untersucht.
Im zweiten Teil der Arbeit komplementieren wir duale Simulationen mit klassischen Operatoren der Anfragesprache SPARQL. Leider stellt sich dies als unlösbare Aufgabe heraus, sobald man interessante Verknüpfungsoperatoren der Sprache hinzufügt. Die resultierenden Anfragesprachen sind weder korrekt noch vollständig bezüglich der Ursprungssemantik. Für Fragmente gelingt es, Vollständigkeit und sogar effiziente Lösbarkeit klassischer Anfragesprachprobleme nachzuweisen. Über mehrere Approximierungsschritte gelingt es schließlich eine vollständige SPARQL-Semantik auf Basis dualer Simulationen zu definieren. Die Semantik selbst hat die Eigenschaft, mit einem einzigen Match alle SPARQL-Resultate zusammenzufassen. Daraus entwickeln wir eine algorithmische Lösung, die als Vorverarbeitung der SPARQL-Anfragebeantwortung verwendet werden kann. Etablierte und effiziente Algorithmen zur Berechnung von Simulationen skalieren gleich schlecht mit der Datenbankgröße. Die allgemeineren Werkzeuge sind zu wenig auf übliche Annahmen über Graphdaten eingestellt. Wir analysieren solche Annahmen und entwickeln auf deren Basis einen Algorithmus, der im Vergleich zu den bestehenden Algorithmen deutlich besser skaliert. Außerdem evaluieren wir mit dem entwickelten Werkzeug unsere Pruning-Semantik für SPARQL.