Foundations of Regular Languages for Processing RDF and XML

Titelangaben

Losemann, Katja:
Foundations of Regular Languages for Processing RDF and XML.
Bayreuth , 2015 . - XIV, 175 S.
( Dissertation, 2015 , Universität Bayreuth, Fakultät für Mathematik, Physik und Informatik)

Volltext

Link zum Volltext (externe URL):

Abstract

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.

Abstract in weiterer Sprache

We investigate the complexity of regular languages for data processing on the web. More precisely, our focus is on problems arising from two particular data formats: the Extensible Markup Language (XML) and the Resource Description Framework (RDF). Regular languages can be found in a wide array of technology on the web. To process XML- or RDF-data, regular expressions (REs) became a well-established concept because of their user-friendly behavior and good complexity compared to other representations for regular languages, e.g., finite automata or logical characterizations. Thereby, different practical applications require different variants of regular expressions that are enhanced with additional operators or restrained by semantical constraints.
These variants and their computational complexity are the main object of our studies in the first part of this dissertation. We examine a wide range of distinct classes of regular expressions that are used in prevalent XML or RDF applications. In detail, we focus on the use of regular expressions in schema languages for XML and query languages for RDF where certain syntactical and semantical constraints form interesting and challenging variants of regular expressions. Although some of these constraints are very specific, it is the case that several of them are reused in different applications in another context. Therefore, our results will likely be relevant in other contexts than XML and RDF processing as well.
In the last part of this dissertation we study query languages for data processing on the web from a more general point of view. Here, our main motivation comes from two problems arising in today’s databases: First, the amount of data that is stored in databases exploded during the last decade such that classical methods from database theory are sometimes not sufficient anymore. When querying these data it is likely that queries return a huge set of rightful answers in general. Second, very often the stored data is dynamic, i.e., the data is subject to frequent updates over time. We are interested in whether efficient query evaluation is still feasible under these constraints. Towards a positive answer, we examine enumeration algorithms which, after some preprocessing phase, compute the query result step by step and output answers sequentially within a certain delay. Although enumeration algorithms for similar queries were examined in the literature before, there exist - as far as we know - no such algorithms that can efficiently handle data updates. For that matter we investigate whether it is possible to construct an enumeration algorithm for regular queries that can quickly recompute the new query result after a data update occurred.