An essential task for XML applications is querying, i.e. identifying locations in the input data with certain specified properties. The present work considers an expressive XML query language and provides efficient algorithms for its implementation. The techniques introduced are applied in the XML querying tool Fxgrep.
Some XML documents may be too large to be built in memory. For these, special algorithms have to be provided. The same holds true for XML data which must be processed while being received, rather than being completely available in advance. In such cases XML data is seen as a stream of events to which the application has to react in order to perform the desired processing. Fxgrep provides therefore an event-based processing mode which avoids the in-memory construction of the input, and in addition recognizes matches of queries at the earliest possible moment.
Typical XML queries identify only individual locations in the input. A useful extension is to retrieve k locations which are in a specified context. Binary queries (obtained for k=2) are identified in this work as a useful case, especially in view of XML transformations. Besides for unary queries we therefore develop algorithms for the evaluation of binary queries. These techniques are at the base of our XML transformation tool Fxt.
The practical results are based on the compilation of XML queries to grammars, as used in XML schema languages, and on tree automata based constructions, tailored to our application domain.
A more detailed overview of the addressed topics and the contributions presented is given in the introductions to the first and second parts of this work.
Übersetzte Kurzfassung:
Diese Arbeit betrachtet eine ausdrucksstarke Sprache zur Suche in XML-Dokumenten, was eine grundlegende Aufgabe von XML-Anwendungen ist. Für diese Anfrage-Sprache werden effiziente Algorithmen zur Auswertung bereit gestellt und in dem Tool Fxgrep realisiert.
Sehr große XML-Dokumente können nicht als Bäume im Speicher aufgebaut werden. Dasselbe gilt für XML-Daten, die verarbeitet werden müssen, noch während sie empfangen werden. In diesen Fällen werden spezielle Algorithmen benötigt, die die XML-Eingabe statt als Baum als Strom von Ereignissen ansehen. Diese verarbeiten die Eingabe, indem sie auf Ereignisse reagieren. Deshalb verfügt Fxgrep über einen strom-basierten Bearbeitungsmodus, der es so weit wie möglich vermeidet, eine interne Repräsentation des Dokuments im Speicher aufzubauen, und zudem Treffer der Anfrage zum frühest möglichen Zeitpunkt signalisiert.
Typische XML-Anfragen suchen nur nach einzelnen Teildokumenten, die über ihre Eigenschaften sowie die Eigenschaften ihres Kontexts definiert sind. Sinnvoll sind aber auch Anfragen, die nach k-Tupeln von Teildokumenten mit gegebenen Eigenschaften suchen. Zweistellige Anfragen werden in dieser Arbeit als einen im Hinblick auf XML-Transformationen besonders nützlichen Fall identifiziert. Hier werden darum neben der Behandlung von einstelligen Anfragen insbesondere Techniken entwickelt, um zweistellige Anfragen zu beantworten. Diese Methoden bilden die Grundlage unseres effizienten Transformationstools Fxt.
Die eingeführten Algorithmen erzeugen aus Anfragen Grammatiken, wie sie auch in Schema-Sprachen eingesetzt werden, und konstruieren aus diesen maßgeschneiderten Baumautomaten.
Ein ausführlicherer Überblick über die behandelten Themen sowie die hier vorgestellten neuen Forschungsergebnisse befindet sich in den Einführungen zum ersten und zweiten Teil der Arbeit.
Veröffentlichung:
Universitätsbibliothek der Technischen Universität München
Login
BibTeX