Efficient XML Processing with Tree Automata
Alexandru Berlea · 2005
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.