XIME-P 2006

This paper proposes an extension to the XQuery language to solve the problem of positional grouping: that is, problems in which it is necessary to convert a flat sequence into a hierarchy by recognizing patterns in the sequence of items. Positional grouping is contrasted with value-based grouping, where the allocation of items to groups is based on common values rather than on the positional relationships of the items in the sequence. The approach is based on analyzing a set of use cases, derived from real-world experience.

XQuery is a declarative language for querying and updating XML data sources. Interfacing XQuery to a host programming language is difficult because of the type system mismatch, and global optimization is difficult in a mixed-language environment. In this paper, we investigate a small extension called XQueryP that enables XQuery expressions to exchange state information through variables. This extension makes it easier to develop applications in XQuery without relying on a host programming language. We draw an analogy between the proposed extension and similar extensions that have been added over the years to the SQL query language for similar reasons.

We present a high-performance, pull-based streaming processor for XQuery, called XQPull, that can handle many essential features of the language, including general predicates, recursive queries, backward axis steps, and function calls, using a very small amount of caching. Our framework is based on a new type of event streams, called retarded streams, which allow multiple and nested streams to be interleaved in the same physical stream, while postponing the caching of input events until is absolutely necessary, typically at the end of the query evaluation, just before the results are ready to print.

We discuss query evaluation for XML-based server systems where the same query is evaluated on every incoming XML message. In a typical scenario, many of the incoming messages will be highly similar to each other. Current XML query evaluators reevaluate the query from scratch on every message. We call substructures that occur in many input documents template fragments, and introduce a novel template folding method that allows to move the work of evaluating the query on recurring document substructures from the query execution engine into the query compiler. Similar to constant folding, our method avoids run-time evaluation of intermediate results whose value only depends on information that is already available at compile time. For XPath location paths, we propose a representation for such invariant intermediate results, and show how it can be incorporated into query execution plans. Such augmented execution plans improve query performance when evaluating the same query on subsequent input documents.

This is to report on a database systems course the rst author held in the summer semester of 2005 at Saarland University, Saarbrüucken, Germany. This course was an experiment in several respects. For one, we wanted to teach a systems course with a practical part in which students apply the material taught to build the core of a database management system. Such a systems building e ort seems to be quite common in top-tier US universities, but it is rare in Europe. One main reason for this is that European curricula often require students to take many small courses per term. Students then cannot be required to invest the time necessary for such a systems-building e ort into an individual course. In Saarbrücken, this fortunately does not apply and students are expected to take only about two main courses per term. (The database systems course in Saarbrucken is worth 9 points in the European course-credit transfer system ECTS, which corresponds to an estimated workload of 20 hours per week.)

XML annotations are a widely occurring phenomenon in many application fields, and XML databases should be used to store and query such data. To provide intuitive and fast querying of annotations, we make a case for extending XPath with four new axis steps, that correspond with socalled StandOff joins, introduced here. The new steps can be efficiently implemented using a region index and fast looplifted StandOff MergeJoin algorithms. These techniques were added to the open-source XML DBMS MonetDB/XQuery, and we show in our evaluation it thus becomes capable of interactively querying >GB annotation databases.

Text has a non-hierarchical structure. Not suprisingly, searching for information ion the content of a document often yields results that overlap the structure within the document. It is often of great interest to relate such results to the embedded document structure. In this work we present an extension to the XQuery language over multihierarchical document-centric XML documents. We illustrate the benefits of using multihierarchical XQuery for text-and-structure searches in document-centric XML documents. More specifically, multihierarchical XQuery allows representing relationships between text and search results and document structure even for cases where such search results overlap markup boundaries and even in cases when only one markup hierarchy is considered.