:: XPC: A XPath Compiler (version 1.0)

Overview: Abstract :: Documentation :: Web-Interface :: Downloads:: Publications:: Contact

Abstract

The efficient processing of XML data hinges on fast evaluation techniques for XPath expressions because XPath is an essential part of widely used XML processing languages like XSLT and XQuery.

Within the publications below we present translation rules to translate any XPath version 1.0 expression into algebraic expressions and some optimization techniques to efficiently evaluate them.

Such a translation of XPath expressions into algebraic expressions (1) renders possible algebraic optimization approaches as found in most modern query optimizers, and (2) facilitates the application of iterator-based, pipelining query execution engines that scale well to large data volumes and have proven their performance e.g. in relational systems. For the same reasons, algebra-based XQuery evaluation is attractive, requiring algebra-based XPath evaluation as an essential ingredient.

Our XPath compiler has been developed for our native XML database management system Natix. As Natix is not available for download yet, we offer a standalone version of our query compiler. It allows to parse any XPath 1.0 expression and to translate it into logical algebra expressions. The full translation process is described in "Full-fledged Algebraic XPath Processing in Natix".

Documentation

Our query compiler is easy to use. Just download the executable and the XSL Stylesheet provided below.

At first, you have to write the path expression you want to translate into a file. Then call the query compiler xpc using the following syntax:


Usage: xpc -x "filename"

Options:

  -expression | -translate

  -o "filename"

  -memox

  -pushprojd

  -xschedule

  -xscan

The -o option specifies an explicit output filename
The -expression option tells the compiler not to translate the path expression into algebraic expressions, but to show the internal representation of the query after some normalization steps.
The -translate option tells the compiler to translate the path expressions into the algebraic representation. This is the default option.
All other options offer the possibility to specify some translation hints the query compiler should use. All hints are described in the papers below. The first two are described in "Full-fledged Algebraic XPath Processing in Natix. The last two are specified in "Cost-Sensitive Reordering of Navigational Primitives"

At the end, you can use the generated XML-output file to visualize the internal representation of the query. For this purpose you can transform the XML-file using the p2d.xsl stylesheet into input for dot.

The transformed .dot file acts as input for dot, which is a preprocessor for drawing directed graphs. It can be downloaded from http://www.graphviz.org/, but is usually provided with any current Linux distribution. It can be used as follows: dot -Tps output.dot -o output.ps The output.ps file now contains a visualization of the internal representation using postscript.

The above steps are all combined within the bash script (nixplain.sh)offered below. This script translates and illustrates all .xp files within a directory using xpc, Xalan and dot.

Web-Interface

As a second alternative, besides downloading our Linux binaries, you can also use the Web-Interface to visualize XPC query plans or take a look at the resulting Natix Virtual Machine (NVM) code which can be executed in our run time system.

Downloads

WARRANTY

BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION.

IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF THE PRO GRAM TO OPERATE WITH ANY OTHER PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.

Copyright (C) Chair of Practical Computer Science III
(Please note: this is not free software. We give the permission to download and use it for research purposes only.)

File	Description
xpc	The XPath query compiler version 0.9. Compiled for Linux.
p2d.xsl	A stylesheet to transform the output of xpc into an input file for dot.
nixplain.sh	A bash-script to translate and visualize all .xp files within the current directory using xpc, Xalan and dot.

Examples

Here are some examples:

File	Path Expression
p000.xp.png	`/a/b/c`
p001.xp.png	`/child::doc/child::chapter[position()=5]/child::section[position()=2]`
p014.xp.png	`child::a[position() = last() or position() = last() - 1]`

Publications

A list of publications that deal with XPath can be found here.

Contact

Please report bugs or any other suggestions concerning xpc to Matthias Brantner.