Foundations of Regular Languages for Processing RDF and XML

Die vorliegende Arbeit befasst sich mit der Komplexität und Optimierung von Problemen, die bei der Verwendung von regulären Sprachen für die web-basierte Datenverarbeitung entstehen. Die betrachteten Problemstellungen sind insbesondere durch Anwendungen motiviert die eines der folgenden zwei Datenformate benutzen: die Extensible Markup Language (XML) und das Resource Description Framework (RDF). Wir werden uns zunächst mit der Komplexität von regulären Sprachen in dem Kontext XML und RDF beschäftigen. Danach untersuchen wir die Auswertung von dynamischen Daten, die aus heutiger Sicht immer relevanter für die web-basiere Datenverarbeitung wird. In dem ersten Teil dieser Arbeit liegt unser Fokus auf regulären Ausdrücken (kurz RAs) zur Repräsentation von regulären Sprachen. Reguläre Ausdrücke haben sich in praktischen Anwendungen für die XML- und RDF-Datenverarbeitung weitestgehend gegenüber anderen Repräsentationen für reguläre Sprachen, wie zum Beispiel endlichen Automaten oder logischen Charakterisierungen, als effizient wie auch nutzerfreundlich durchgesetzt. Um den einzelnen Anforderungen in den verschiedenen praktischen Anwendungen gerecht zu werden, sind außerdem mit der Zeit mehrere Varianten regulärer Ausdrücke entstanden. Eben diese Varianten und deren Komplexität sind Betrachtungsgegenstand unserer Forschung in dem ersten Teil dieser Dissertation. Zu diesem Zweck werden wir verschiedene Varianten regulärer Ausdrücke, die im Kontext der XML- und RDF-Datenverarbeitung benutzt werden, formal definieren und untersuchen, ob diese eine ihrem Verwendungszweck entsprechend effiziente Nutzung zulassen oder eventuell sogar verhindern. Wir beschäftigen uns dabei im Detail mit Schemasprachen für XML und Anfragesprachen für RDF, in denen durch semantische und syntaktische Zusatzbedingungen einige interessante Varianten regulärer Ausdrücke entstanden sind. Anschließend werden wir in dem Kontext von Anfragesprachen die Komplexität regulärer Sprachen aus einer etwas allgemeineren Perspektive untersuchen. Dafür lösen wir unsere Betrachtungen sowohl von konkreten Datenformaten als auch von regulären Ausdrücken. Stattdessen untersuchen wir die web-basierte Datenverarbeitung mit dem Fokus auf das Verhalten moderner Datenbanken. In diesen sind heutzutage zwei Tendenzen deutlich zu erkennen: Erstens, die in den Datenbanken gespeicherten Datensätze werden immer größer; sie nehmen dabei Dimensionen an die mit klassischen Methoden nicht mehr effizient beherrschbar sind. Aus diesem Grund ist zu erwarten, dass die Ergebnisse von Datenbankanfragen immer komplexer werden und dem Nutzer eine (möglicherweise sehr große) Menge an korrekten Ergebnissen zurückgegeben wird. Zweitens, unterliegen die in den Datenbanken enthaltenen Daten ständigen Änderungen, so dass eine gerade abgeschlossene Analyse der Daten im nächsten Moment schon wieder veraltet sein kann. Wir stellen uns die Frage, ob reguläre Datenbankanfragen in diesem Kontext effizient ausgewertet werden können. Um große Antwortmengen effizient verarbeiten zu können, untersuchen wir sogenannte Enumerationsalgorithmen, die das Ergebnis einer Anfrage nicht direkt in einem Schritt berechnen, sondern vielmehr Stück für Stück an den Nutzer zurückgeben. Da wir außerdem dynamische Daten betrachten, sollen diese Algorithmen zudem auf eintreffende Datenupdates schnell reagieren können. Dabei betrachten wir Anfragen, die in ihrem Kern regulär sind, und durch ein spezielles endliches Automatenmodell dargestellt werden können. Obwohl für ähnliche Anfragen bereits effiziente Enumerationsalgorithmen bekannt und gut untersucht sind, können diese Algorithmen nicht dafür genutzt werden Anfragen über dynamischen Datenbanken effizient auszuwerten.

Level thesis:degree_level

thesis.doctoral

Grantor dc:publisher

Universität Bayreuth

Year

2015

Author dc:creator

• Losemann, Katja

Contributors dc:contributor

• Martens, Wim

Repository record source_url

https://epub.uni-bayreuth.de/id/eprint/2536/

OAI identifier oai:identifier

oai:epub.uni-bayreuth.de:2536