XML Stream Attribute Grammars (XSAGs)

(Christoph Koch and Stefanie Scherzinger)

Abstract

We introduce the new notion of XML Stream Attribute Grammars (XSAGs). XSAGs are the first scalable query language for XML streams (running strictly in linear time with bounded memory consumption independent of the size of the stream) that allows for actual data transformations rather than just document filtering. XSAGs are also relatively easy to use for humans.
Moreover, the XSAG formalism provides a strong intuition for which queries can or cannot be processed scalably on streams. We introduce XSAGs together with the necessary language-theoretic machinery, study their theoretical properties such as their expressiveness and complexity, and discuss their implementation.

Publications

• Christoph Koch, Stefanie Scherzinger: Attribute Grammars for Scalable Query Processing on XML Streams. DBPL 2003: 233-256. (209kB PDF file).

• Christoph Koch, Stefanie Scherzinger: Attribute Grammars for Scalable Query Processing on XML Streams. To appear in VLDB Journal, 2005. Journal version.

Additional Resources

• Slides from the talk at DBPL03 (PPT).
• Experiments:  Our experiments with the hybrid yXSAG engine confirm our theoretic results: The memory  consumption depends on the depth of the input document and the size of the query, while the evaluation time depends on both the size of the input document and the size of the query.
  
  
  
  Details on conducting the experiments are shown below. We use two XML databases derived from the DBLP dataset which contains 135 MB of bibliographic XML data.
  
  

• Our platform is a laptop with a 1.3 GHz processor and 256 MB of RAM running Linux. The compiler is gcc version 3.2 with the -O3 command-line option. We parse XML files with a simple SAX parser based on flex (version 2.5.4).
  

  Two values are of immediate interest in XML stream processing, namely the memory consumption during query evaluation and the throughput of the prototype implementations.

  We first study the evaluation of the following yXSAG queries:   Q1: "Validate the input", Q2: "Select all books", Q3: "Select all books published in 2003", and Q4: "Select all books".

  
  The figure above shows the memory consumption (denoted “mc”), runtime (in seconds), and the computed throughput (“tp”) for processing queries Q1, Q2, and Q3 on database D1. We further perform query Q4 on the 500 MB database D2. Query Q4 is evaluated in 112.234 seconds using 1872 KB memory, i.e. a throughput of about 4.45MB/sec is reached.This demonstrates that the query engine may very well handle file sizes which exceed the main memory capacities of the execution platform. Note that the evaluation of query Q4 requires significantly more memory than that of queries Q1 through Q3
  

• The StreamGlobe Project at TU München
• The XMLTaskForce Project at TU Wien

back to main page of Saarland University Database Group