Evaluation of XPath queries against XML streams [Elektronische Ressource] / vorgelegt von Dan Olteanu

Olteanu, Turèll Dan

Sujets

• Informatik

Informations

• Publié par: ludwig-maximilians-universitat_munchen
• Publié le: 01 janvier 2004
• Nombre de lectures: 30
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Evaluation of XPath Queries against
XML Streams
Dan Olteanu
Dissertation
zur Erlangung des akademischen Grades des
Doktors der Naturwissenschaften
an der Fakult at fur Mathematik, Informatik und Statistik
der Ludwig{Maximilians{Universit at Munc hen
vorgelegt von
Dan Olteanu
Munc hen, Dezember 2004Erstgutachter: Fran cois Bry
Zweitgutachter: Dan Suciu (University of Washington)
Tag der mundlic hen Prufung: 11. Februar 2005To my wife Floriivv
Abstract
XML is nowadays the de facto standard for electronic data interchange on the Web.
Available XML data ranges from small Web pages to ever-growing repositories of, e.g.,
biological and astronomical data, and even to rapidly changing and possibly unbounded
streams, as used in Web data integration and publish-subscribe systems.
Animated by the ubiquity of XML data, the basic task of XML querying is becoming
of great theoretical and practical importance. The last years witnessed e orts as well
from practitioners, as also from theoreticians towards de ning an appropriate XML query
language. At the core of this common e ort has been identi ed a navigational approach for
information localization in XML data, comprised in a practical and simple query language
called XPath [46].
This work brings together the two aforementioned \worlds", i.e., the XPath query eval-
uation and the XML data streams, and shows as well theoretical as also practical relevance
of this fusion. Its relevance can not be subsumed by traditional database management
systems, because the latter are not designed for rapid and continuous loading of individual
data items, and do not directly support the continuous queries that are typical for stream
applications [17].
The rst central contribution of this work consists in the de nition and the theoretical
investigation of three term rewriting systems to rewrite queries with reverse predicates, like
parent or ancestor, into equivalent forward queries, i.e., without reverse predicates.
Our rewriting approach is vital to the evaluation of queries with reverse predicates against
unbounded XML streams, because neither the storage of past fragments of the stream, nor
several stream traversals, as required by the evaluation of reverse predicates, are a ordable.
Beyond their declared main purpose of providing equivalences between queries with
reverse predicates and forward queries, the applications of our rewriting systems shed light
on other query language properties, like the expressivity of some of its fragments, the
query minimization, or even the complexity of query evaluation. For example, using these
systems, one can rewrite any graph query into an equivalent forward forest query.
The second main contribution consists in a streamed and progressive evaluation strategy
of forward queries against XML streams. The evaluation is speci ed using compositions of
so-called stream processing functions, and is implemented using networks of deterministic
pushdown transducers. The complexity of this evaluation strategy is polynomial in both
the query and the data sizes for forward forest queries and even for a large fragment of
graph queries.
The third central contribution consists in two real monitoring applications that use
directly the results of this work: the monitoring of processes running on UNIX comput-
ers, and a system for providing graphically real-time tra c and travel information, as
broadcasted within ubiquitous radio signals.vi
Zusammenfassung
Heutzutage ist XML der de facto Standard fur den Datenaustausch im Web. Dabei
reicht die Spanne an verfugbaren XML Daten von kleinen Webseiten bis hin zu immer
gr o er werdenden Sammlungen, beispielsweise an biologischen oder anstronomischen Daten
und sogar, m oglicherweise unbegrenzte, Datenstr ome mit schnellem Datenaufkommen, wie
sie in publish-subscribe Systemen verwendet werden.
Getrieben durch die weite Verbreitung von XML Daten, bekommt die Anfragebear-
beitung an XML Daten zunehmend gr o ere theoretische und praktische Bedeutung. In
den letzten Jahren konnten Initiativen sowohl von Seiten der Industrie als auch aus der
Forschung beobachtet werden, die darauf abziehen eine angemessene XML Anfragesprache
zu de nieren. Das Kernergebnis dieser Initiativen ist die Identi k ation eines navigationalen
Ansatzes zur Lokalisierung von Informationen in XML Daten in der benutzer-orientierten
Anfragesprache XPath.
Diese Arbeit bringt die zwei oben genannten Welten, die XPath Anfragebearbeitung
und XML Str ome, zusammen und zeigt die sowohl praktische als auch theoretische Rele-
vanz dieser Verbindung.
Der erste Hauptbeitrag dieser Arbeit besteht in der De nition und der theoretischen
Untersuchung von drei Termersetzungssystemen, um Anfragen mit sogenannten \reverse"
Predikaten, wie beispielsweise parent oder ancestor, in equivalente Anfragen, die keine
solche Predikate enthalten, umzuschreiben. Unser Ansatz ist essentiell fuer die Auswertung
von Anfragen mit \reverse" Predikaten gegen unbegrenzte XML Str ome, da weder die
Speicherung von bereits verarbeiteten Stromfragmenten noch mehrere Durchl aufe ub er
den XML Strom erforderlich sind.
Neben diesem Hauptziel, die Anwendungen unserer Umschreibungssysteme werfen ein
neues Licht auf andere Eigenschaften der Anfragesprache, wie die Ausdruckskraft einiger
Fragmente, die Minimierung von Anfragen, und sogar die Komplexit at der Anfrageauswer-
tung. Man kann beispielsweise unter Nutzung dieser Umsc beliebige
Graphanfragen in equivalente Waldanfragen ohne \reverse" Predikate umschreiben.
Der zweite Hauptbeitrag besteht in einer strom-basierten, progressiven Auswertungsstrate-
gie fur Waldanfragen ohne \reverse" Predikate gegen XML Str ome. Die Auswertung wird
spezi ziert durch die Komposition von sogenannten Stromverarbeitungsfunktionen und
implementiert unter Verwendung von Netzwerken aus deterministischen Kellerautomaten.
Die Komplexit at dieser Auswertungsstrategie ist polynomiell sowohl in der Gr osse der An-
frage als auch der Daten fuer Waldanfragen ohne \reverse" Predikate und sogar fur viele
Graphanfragen.
Der letzte Hauptbeitrag besteht aus zwei praktisch verwendbaren Uberwachungssystemen,
die direkt auf den Resultaten dieser Arbeit aufsetzen: die Uberwachung von auf einem
UNIX System laufenden Prozessen und ein System, das Verkehrsinformationen aus Ra-
diosignalen in Echtzeit ub erwacht und graphisch aufbereitet.vii
Acknowledgments
During the last three years, many people have contributed directly or indirectly to the
development of this dissertation. I would like to express my gratitude to them.
First of all I am deeply indebted to my advisor Fran cois Bry, for his continuing trust
and support during the evolution of this thesis. Further, I am grateful to Dan Suciu, whose
work on XML query processing in uenced constantly my research directions. This thesis
and its author further bene tted from long and very useful discussions with two of my best
supporters Tim Furche and Holger Meuss. Without their active commitment, this disser-
tation would not have been possible. I thank the students, whose theses I co-supervised,
for their interest in my work and for bringing new relevant ideas to surface: Fatih Coskun,
Serap Durmaz, Tim Furche, Tobias Kiesling, Sebastian Scha ert, Dominik Schwald, and
Markus Spannagel. I thank also the members of our teaching and research group for creat-
ing a stimulating environment at the o ce and a pleasant stay in Munich: among others,
Slim Abdennadher, Sacha Berger, Tim Geisler, Martin Josko, Michael Kraus, Ellen Lilge,
Bernhard Lorenz, Hans Jurgen Ohlbach, Paula P atr^ anjan, Stephanie Spranger, and Felix
Weigel. I especially want to mention Norbert Eisinger for his always competent advises on
various subjects ranging from easy ones, like con uence of rewriting systems, to complex
ones, like teaching computer science topics.
Last, but de nitely not least, I thank my wife, Flori, for her love and non-interrupting
support, my parents and my brother for enduring the physical distance that separated
us for such a long time, and all my friends for the weekends we spent together doing no
research.viiiContents
1 Introduction 1
1.1 Data Streams: Use, Concepts, and Research Issues . . . . . . . . . . . . . 2
1.2 Thesis Contributions and Overview . . . . . . . . . . . . . . . . . . . . . . 6
2 Preliminaries 9
2.1 XML Essentials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Example Scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3 LGQ (Logic Graph Query): An Abstraction of XPath 15
3.1 Data Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.3 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.4 Digraph Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.5 Path, Tree, DAG, Graph Formulas and Queries . . . . . . . . . . . . . . . 26
3.6 Forward Formulas and their Specializations . . . . . . . . . . . . . . . . . . 28
3.7 Measures for Formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.8 LGQ versus XPath . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.8.1 XPath . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31