[Back]


Doctor's Theses (authored and supervised):

S. Skritek:
"Foundational Aspects of Semantic Web Optimization: New Algorithms and Complexity Results";
Supervisor, Reviewer: R. Pichler, M. Arenas; 184-2, 2013; oral examination: 2013-04-30.



English abstract:
The goal of the Semantic Web is to make the information available on the web easier accessible. Its idea is to provide machine readable meta-data to enable the development of tools that support users in finding the relevant data. The aim of this thesis is to shed some light onto different foundational aspects of optimization tasks occurring in the field of the Semantic Web.
Two basic building blocks of the Semantic Web are the Resource Description Framework (RDF) and SPARQL, with RDF being the data model proposed for this purpose and SPARQL the corresponding query language. As the popularity of RDF increases, so does the need for storing, querying and processing this data efficiently. However, the progress made towards a deeper understanding of the foundational properties of these technologies and the problems related to their optimization can only be considered as first steps towards this goal, since many questions have remained still open. Extending the current knowledge on these topics by exploring several fundamental problems related to SPARQL query optimization and the efficient storage of RDF data is the main goal of this thesis.
Towards SPARQL query optimization, concentrating on SPARQL´s optionality feature, we initialize the study of static query analysis for the class of well-designed SPARQL queries. In particular, we investigate the central problems of subsumption (being arguably the right notion of containment for SPARQL) and equivalence. Further, we study the complexity of the evaluation, enumeration, and counting problem for well-designed SPARQL queries, with a focus on identifying tractable fragments. We especially investigate to what extend tractable fragments from conjunctive query (CQ) evaluation carry over to this SPARQL fragment. Finally, we present several equivalence preserving transformation rules for these queries. While being essential for establishing the above mentioned results, they also represent an important step towards an algebra for SPARQL query plans.
Concerning the efficient storage of RDF data, we observe that inference is an essential aspect of the Semantic Web. We therefore study the problem of detecting redundancy in RDF graphs caused by rule-based inference. To this end, we examine a setting including rules andconstraints, and also consider redundancy with respect to a set of queries. The result is a fine grained complexity analysis of how the different problem parameters influence the complexity of this problem.
While a central goal of this thesis is to extend results from corresponding research on relational data to RDF and SPARQL, we encounter some problems unanswered even in the relational case. With two of them being of broader interest, we investigate them in the relational setting. That is, we study the complexity of the model checking problem for several classes of tuple generating dependencies. Moreover, we initialize the systematic search of tractable fragments of the counting problem for CQs by studying this problem for acyclic CQs.

German abstract:
Ziel des "Semantic Web" ist es, im Web verfügbare Informationen leichter zugänglich zu machen. Das Auffinden relevanter Informationen soll durch das zur Verfügung stellen maschinen lesbarer Metadaten erleichtert werden, welche die Entwicklung von Software ermöglichen die den Benutzer bei der Suche unterstützt. Zweck dieser Dissertation ist es, die theoretischen Grundlagen einiger Optimierungsaufgaben zu untersuchen, die sich im Zusammenhang mit dem Semantic Web ergeben.
Zwei zentrale Bausteine des Semantic Web sind das "Resource Description Framework" (RDF) und SPARQL. Sie stellen das vorgeschlagene Datenmodell und die dazugehörige Ab-
fragesprache dar. Gemeinsam mit der Popularität von RDF steigt auch die Notwendigkeit diese Daten effizient zu speichern, zu verarbeiten und abzufragen. Der momentane Wissenstand über die grundlegenden Eigenschaften dieser Technologien, und mit ihrer Optimierung verbundenen Probleme, kann jedoch nur als ein erster Schritt in Richtung eines tieferen Verständnisses der Problematik betrachtet werden, da viele Fragen bislang unbeantwortet geblieben sind. Mit Hilfe der vorliegenden Arbeit soll, durch die Untersuchung unterschiedlicher grundlegender Probleme im Zusammenhang mit der Optimierung von SPARQL-Abfragen und dem effizienten Speichern von RDF Daten, das aktuelle Wissen auf diesem Gebiet erweitert werden.
Im Fall der SPARQL-Abfrageoptimierung konzentrieren wir uns auf die Möglichkeit, optionale Bedingungen in einer Abfrage zu definieren, und beginnen eine systematische Unter-
suchung der Klasse der "wohlgestalteten" (well-designed) SPARQL-Abfragen. Im Speziellen untersuchen wir die zentralen Probleme der Subsumierung und Äquivalenz solcher Abfragen. Weiters betrachten wir das Entscheidungs-, Aufzählungs- und Abzählproblem für diese Abfragen, wobei wir besonderes Augenmerk auf das Aufspüren effizient lösbarer Fragmente legen. Wir überprüfen insbesondere, inwieweit entsprechende Ergebnisse von konjunktiven Abfragen (Conjunctive Queries, CQs) auf unseren Fall übertragbar sind. Darüber hinaus präsentieren wir Äquivalenz erhaltende Transformationsregeln für wohlgestaltete Abfragen, welche nicht nur essenziell für die Analyse der oben genannten Probleme sind, sondern auch einen wichtigen Schritt Richtung einer Algebra für SPARQL-Abfragepläne darstellen.
Hinsichtlich der effizienten Speicherung von RDF Daten behandeln wir das Problem, Informationen in RDF Daten zu identifizieren, welche auf Grund von regelbasierter Inferenz redundant sind. Wir betrachten ein Szenario, welches sowohl Regeln, als auch Integritätsbedingungen beinhaltet, und erweitern unsere Untersuchungen auf Redundanzen bezüglich einer Menge von Abfragen. Das Ergebnis ist eine detaillierte Analyse des Einflusses der verschiedenen Parameter auf die Komplexität des Problems.
Der Schwerpunkt der vorliegenden Arbeit ist es, entsprechende Ergebnisse von relationalen Daten auf RDF und SPARQL zu erweitern, wobei wir einigen Fragestellungen begegnen, welche selbst im relationalen Fall noch ungeklärt sind. Da zwei dieser Probleme von allgemeinem Interesse sind, betrachten wir sie im relationalen Modell. Konkret untersuchen wir dabei das "model-checking" Problem für verschiedene Klassen von Tupel erzeugenden Abhängigkeiten (tuple generating dependencies). Weiters starten wir die systematische Suche nach Klassen von CQs, für welche das Abzählproblem effizient gelöst werden kann, beginnend mit der Klasse der azyklischen konjunktiven Abfragen (acyclic CQs).


Related Projects:
Project Head Reinhard Pichler:
Service-orientierte Datenintegration


Created from the Publication Database of the Vienna University of Technology.