HXQ-0.7.4: index.html
<html>
<head><title>HXQ: A Compiler from XQuery to Haskell</title></head>
<body>
<center>
<h1>HXQ: A Compiler from XQuery to Haskell</h1>
</center>
<p>
<h2>Description</h2>
<p>
HXQ is a fast and space-efficient translator from <a href="http://www.w3.org/XML/Query/">XQuery</a> (the standard
query language for XML) to embedded Haskell code. The translation is
based on Haskell templates. HXQ takes full advantage of Haskell's lazy
evaluation to keep in memory only those parts of XML data needed at
each point of evaluation, thus performing stream-based evaluation for
forward queries (queries that do not contain backward steps). This
results to an implementation that is as fast and space-efficient as
any stream-based implementation based on SAX filters or finite state
machines. Furthermore, the coding is far simpler and extensible since
its based on XML trees, rather than SAX events.
<p>
For example, the XQuery given at the bottom of this page, which is
against the <a href="http://dblp.uni-trier.de/xml/">DBLP XML
database</a> (420MB), runs in 39 seconds on my laptop PC (using 18MB of max heap space).
To contrast this, <a href="http://www.gnu.org/software/qexo/">Qexo</a>, which
compiles XQueries to Java bytecode, took 1 minute 17 seconds (using no less than 1400MB of heap space).
Also <a href="http://xqilla.sourceforge.net/HomePage">XQilla</a>, which is written in C++, took 1 minute and 10 secs
(using 1150MB of heap space). (All results are taken on an Intel Core 2 Duo 2.2GHz 2GB running ghc-6.8.2 on Linux 2.6.23 kernel.)
<p>
HXQ uses the <a href="http://www.flightlab.com/~joe/hxml/">HXML parser for XML</a> (developed by Joe English),
which is included in the source.
I have also tried hexpat, tagsoup, HXT, and HaXML Xtract, but they all have space leaks.
For example, when I replaced the HXML parser with <a href="http://www-users.cs.york.ac.uk/~ndm/tagsoup/">tagsoup</a>
in HXQ, it required more than 3GB heap space for the above query
and gave partial results.
<p>
<h2>Installation Instructions</h2>
<p>
First, you need to install the Glasgow Haskell Compiler,
<a href="http://www.haskell.org/ghc/">ghc</a>,
and the parser generator for Haskell,
<a href="http://www.haskell.org/happy/">happy</a>.
For example, in Fedora Linux, you install both using:
<pre>
yum install ghc happy
</pre>
Then download <a href="/HXQ-0.7.4.tar.gz">HXQ</a> and untar it.
You can use either make or cabal to build it. To build it with cabal, you do:
<pre>
runhaskell Setup.lhs configure --prefix=$HOME
runhaskell Setup.lhs build
runhaskell Setup.lhs install
</pre>
(The last command must be run as root.)
It will create the executable <tt>xquery</tt>, which is the XQuery interepreter, and the HXQ library.
To use the library, you run ghc or ghci with <tt>-package HXQ</tt>.
<p>
<h2>Current Status</h2>
<p>
HXQ supports most essential XQuery features, although some system functions are missing (but are easy to add).
To see the list of supported system functions, run <tt>xquery -help</tt> .
HXQ does not have static typechecking; it leaves all checking to Haskell. This means that it distinguishes regular predicates
from indexing at run time: if an XPath predicate returns an integer at run time, it is taken as indexing and this index is
checked against the current node position. The most important omission is backward step axes, such as /.. (parent).
Some, but not all, parent axis steps are removed using optimization rules; all others cause a compilation error.
Finally, the XQuery semantics requires duplicate elimination and
sorting by document order for every XPath step, which is very expensive and unnecessary in most cases.
This will be addressed in the future (needs a static analysis to determine when is necessary).
<p>
<h2>Using the Compiler</h2>
<p>
The main functions for embedding XQueries in Haskell are:
<ul>
<li> <tt>$(xe query) :: XSeq</tt>
<li> <tt>$(xq query) :: IO XSeq</tt>
</ul>
where <tt>query</tt> is a string value (a Haskell expression that evaluates
to a string <b>at compile-time</b>), They both translate the query into Haskell
code, which is compiled and optimized into machine code directly.
The code that xe generates has type <tt>XSeq</tt> (a sequence of XML trees of type <tt>[XTree]</tt>)
while the code that xq generates has type <tt>(IO XSeq)</tt>. If the query reads
at least one document (using doc(...)), then you should use xq since it requires
IO. To define constant XML data or a function body, it is better to use xe.
You can use the value of a Haskell variable <tt>v</tt> inside a query using
<tt>$v</tt> as long as <tt>v</tt> has type <tt>XSeq</tt>.
To use a function in a query, it should be defined in Haskell
with type <tt>(XSeq,...,XSeq) -> XSeq</tt>.
<p>
Here is an example of a main program:
<pre>
f(x,y) = $(xe "<article><first>{$x}</first><second>{$y}</second></article>")
main = do a <- $(xq ("<result>{ "
++" for $x at $i in doc('data/dblp.xml')//inproceedings "
++" where $x/author = 'Leonidas Fegaras' "
++" order by $x/year descending "
++" return <paper>{ $i, ') ', $x/booktitle/text(), "
++" ': ', $x/title/text() "
++" }</paper> "
++" }</result> "))
putXSeq a
b <- $(xq " f( $a/paper[10], $a/paper[8] ) ")
putXSeq b
</pre>
Another example, can be found in <a href="Test1.hs">Test1.hs</a>.
<p>
You can compile an XQuery file into a Haskell program (<tt>Temp.hs</tt>) using <tt>xquery -c file</tt>. Or better, you
can use the Unix shell script <tt>compile</tt> to compile the XQuery file to an executable. For example:
<pre>
compile data/q1.xq
</pre>
will compile the XQuery file <tt>data/q1.xq</tt> into <tt>a.out</tt>.
<p>
<h2>Using the Interpreter</h2>
<p>
The HXQ interpreter is far more slower than the compiler; use it only if you need to evaluate ad-hoc XQueries read from input or from files.
The main functions are:
<ul>
<li> <tt>xquery :: String -> IO XSeq</tt> -- Evaluates an XQuery in a string
<li> <tt>xfile :: String -> IO XSeq</tt> -- Evaluates an XQuery in a file
</ul>
The HXQ interpreter doesn't recognize Haskell variables and functions
(but you may declare XQuery variables and functions using the XQuery 'declare' syntax).
The main HXQ program, called <tt>xquery</tt>,
evaluates an XQuery in a file using the interpreter. For example:
<pre>
xquery data/q1.xq
</pre>
Without an argument, it reads and evaluates XQueries and variable/function declarations from input.
With <tt>xquery -p xpath-query xml-file</tt> you evaluate an XPath query against an XML file, eg.
<tt>xquery -p "//inproceedings[100]" data/dblp.xml</tt>.
With <tt>xquery -help</tt> you get the list of system functions and usage information.
<p>
There is an experimental
program, called <tt>hxqc</tt>, that works like <tt>xquery</tt> but is faster because it uses the
HXQ compiler instead of the interpreter. It's constracted with the Unix Makefile (<tt>make hxqc</tt>).
It is unstable and the <tt>hxqc</tt> executable is 10 times larger than <tt>xquery</tt> since it
uses the ghc libraries at run-time. Also, although it is faster than the interpreter, it is slower than a
compiled xquery since it uses part of the heap for the ghc compiler to compile Haskell code on-the-fly.
<p>
</body>
<p>
<hr>
<p>
<address>Last modified: 05/03/08 by <a href="http://lambda.uta.edu/">Leonidas Fegaras</a></address>