Formale Grundlagen von XML-Anfragen unter besonderer Berücksichtigung von XQuery
Final Report Abstract
Im Mittelpunkt des Projektes standen die formalen und algorithmischen Grundlagen von Anfragesprachen für XML-Daten. Frühere Forschungen hatten bereits Logiken und Automaten als formale Modelle für die Spezifikation und Auswertung von Anfragen in XPath und für Schemasprachen untersucht. Dabei wurden allerdings fast ausschließlich die strukturellen Merkmale von XML-Dokumenten berücksichtigt, von vorhandenen Datenwerten wurde weitgehend abstrahiert. Ziel dieses Projektes waren Grundlagen für mächtigere Anfragesprachen wie XQuery, die strukturelle und Datenwert-bezogene Aspekte in Anfragen verbinden. Dabei ergaben sich die folgenden drei Arbeitsschwerpunkte. Logiken mit Datenwerten. Anfragen des strukturorientierten Fragments von XPath lassen sich genau in der Prädikatenlogik mit zwei Variablen formulieren. Im Rahmen des Projektes wurden Erweiterungen dieser Logik um Vergleiche von Datenwerten untersucht und für einige dieser Erweiterungen die Entscheidbarkeit des Erfüllbarkeitsproblems gezeigt. Dies ist ein erster wichtiger Schritt für die Entwicklung von Algorithmen zur statischen Analyse von Anfragen. Die Betrachtung von Strings und Bäumen mit Datenwerten hat sich nicht zuletzt durch diese Untersuchungen zu einem neuen sehr aktiven Forschungsbereich entwickelt. Automaten mit Datenwerten. Während Logiken zur Spezifikation von Anfragen geeignet sind, sind Automaten ein Instrument zur algorithmischen Umsetzung solcher Anfragen. In der Automatentheorie für herkömmliche Strings haben die meisten Modelle dieselbe Ausdruckskraft und beschreiben die robuste Klasse der regulären Sprachen. Für Datenstrings scheint eine gleichermaßen robuste Klasse nicht zu existieren. Im Rahmen des Projektes wurden neue, robustere Modelle entwickelt und ihr Verhältnis zu existierenden Automatenmodellen untersucht. Das Verständnis von Automatenmodellen für Datenstrings wurde durch die Arbeiten des Projektes insgesamt erheblich verbessert. Und-Anfragen. Der dritte Schwerpunkt war die statische Analyse von Und-Anfragen auf XML-Dokumenten sowohl ohne als auch mit Berücksichtigung von Datenwerten, Der prinzipielle Aufwand des Er füllbarkeits- und des Enthaltenseins-Problems für Und-Anfragen, die beiden grundlegenden algorithmischen Probleme der statischen Analyse von Anfragen, sind nunmehr im Wesentlichen verstanden. Auch wenn das Projekt einen erheblichen Erkenntnisfortschritt gebracht hat, ist die Untersuchung der formalen und algorithmischen Grundlagen von Anfragesprachen für XML-Daten noch längst nicht abgeschlossen. Die Resultate des Projektes bilden ein ausgezeichnetes Fundament für Folgeprojekte. In einem weiteren DFG-Projekt werden nichtklassische Logiken für Strukturen mit Datenwerten untersucht werden (unter Berücksichtigung von Anwendungen in der Verifikation). Weitere umfangreiche Arbeiten sind im EU-geförderten Verbundprojekt FOX - Foundations of XML - Safe Processing of Dynamic Data over the Intemet, mit sechs weiteren europäischen Partnern geplant.
Publications
-
Expressive power of pebble automata. ICALP'06 pp. 157-168
Bojanczyk, Samuelides, Schwentick, Segoufin
-
Two-variable logic on data trees and XML reasoning. PODS'06, pp. 10-19, 2006
Bojanczyk, David, Muscholl, Schwentick, Segoufin
-
Two-variable logic on words with data. LICS'06, pp. 7-16, 2006
Bojanczyk, David, Muscholl, Schwentick, Segoufin
-
Bounded depth data trees. ICALP'07, pp. 862-874, 2007
Björklund, Bojanczyk
-
Conjunctive query containment over trees. DBPL'07, pp. 66-80, 2007
Björklund, Martens, Schwentick
-
On notions of regularity for data languages. FCT'07. pp. 88-99, 2007
Björklund, Schwentick
-
Shuffle expressions and words with nested data. MFCS'07, pp 750-761, 2007
Björklund, Bojanczyk
-
Optimizing conjunctive queries over trees using schema information. MFCS'08. pp. 132-143
Björklund, Martens, Schwentick
