HXQ-0.9.0: 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>
<h3>Download <a href="/HXQ-0.9.0.tar.gz">HXQ-0.9.0.tar.gz</a></h3>
</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 <a href="Test2.hs">XQuery given below</a>, 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>
Finally, HXQ can store XML documents in a relational database
(currently SQLite), by shredding XML into relational tuples, and by
translating XQueries over the shredded documents into optimized SQL
queries.
<p>
<h2>Installation Instructions</h2>
<p>
HXQ can be installed on most platforms but I have only tested it on
Linux and Windows XP. The simplest installation is without database
connectivity (ie, it can only process XQueries against XML text
documents).
<p>
First, you need to install the Glasgow Haskell
Compiler, <a href="http://www.haskell.org/ghc/">ghc</a>. Optionally,
if you want to modify the XQuery parser, you need to install the
parser generator for Haskell,
<a href="http://www.haskell.org/happy/">happy</a>. Then,
download <a href="/HXQ-0.9.0.tar.gz">HXQ version 0.9.0</a> and untar
it (using <tt>tar xfz</tt> on Linux
or <a href="http://www.7-zip.org/">7z x</a> on Windows). Then
configure cabal without or with database connectivity:
<dl>
<dt><b>Without database connectivity:</b></dt>
<dd>
To configure HXQ, do:
<pre>
runhaskell Setup.lhs configure
</pre>
</dd>
<p>
<dt><b>With database connectivity:</b></dt>
<dd>
For database connectivity, you need to install <a href="http://sqlite.org/">SQLite</a>.
(On Linux, you can install it using <tt>yum install sqlite</tt>.)
Then you need to install the Haskell packages:
<a href="http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HDBC-1.1.4">HDBC 1.1.4</a> (but not version 1.1.5)
and the
<a href="http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HDBC-sqlite3-1.1.4.0">HDBC-sqlite3 1.1.4</a> driver
to connect to SQLite relational databases.
Then you configure HXQ:
<pre>
runhaskell Setup.lhs configure -fdb
</pre>
</dd>
Finally, you do:
<pre>
runhaskell Setup.lhs build
runhaskell Setup.lhs install
</pre>
On Linux, the last command must be run as root. This will create the
executable <tt>xquery</tt>, which is the XQuery interpreter, and the
HXQ library. To use the HXQ library in a Haskell program,
simply <tt>import Text.XML.HXQ.XQuery</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. In
addition, 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 is not currently
supported by HXQ but will be addressed in the future (needs a static
analysis to determine when duplicate elimination is necessary). For
example, <tt>e//*//*</tt> may return duplicate elements in HXQ.
<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.
<p>
HXQ has two parsers: one that generates simple rose trees from XML
documents, which can be processed by forward queries without space
leaks, and another parser where each tree node has a reference to its
parent. Some, but not all, backward axis steps (such as the parent
axis /..) are removed from a query using optimization rules. If there
are backward axis steps left in the query, then HXQ uses the latter
parser, which may result to a performance penalty due to space leaks.
<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>. You compile it using
<tt>ghc --make Test1.hs -o a.out</tt>.
<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 script <tt>compile</tt> (on either Unix or Windows) to compile the XQuery file
to an executable. For example:
<pre>
compile data/q1.xq
</pre>
will compile the XQuery file <a href="data/q1.xq">data/q1.xq</a> into the executable <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>
<h2>Database Connectivity</h2>
<p>
HXQ provides an interface to <a href="http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HDBC">HDBC</a>
to query relational data inside an XQuery.
For the HXQ compiler, the main function that allows database connectivity is:
<pre>
$(xqdb query) :: (IConnection conn) => conn -> IO XSeq
</pre>
For example, if the database name is "myDB", then
<pre>
do db <- connect "myDB"
result <- $(xqdb xquery) db
</pre>
For the HXQ interpreter, the function is:
<pre>
xqueryDB :: (IConnection conn) => String -> conn -> IO XSeq
</pre>
The xquery executable can also run XQueries that use a database by
specifying the database name using the -db option.
<p>
Currently, HXQ works with <a href="http://sqlite.org/">SQLite</a> only, but is very easy to make it work
with any relational database that supports ODBC: simply install
<a href="http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HDBC-odbc">HDBC-odbc</a>
and change the file <a href="src/withDB/Text/XML/HXQ/DBConnect.hs">src/withDB/Text/XML/HXQ/DBConnect.hs</a> accordingly.
<p>
<h3>Querying an Existing Database</h3>
<p>
An XQuery may contain multiple SQL queries in the
form <tt>sql(query,args)</tt>, where <tt>query</tt> is the sql query
that may contain parameters (denoted by ?), which are bound to the
values in <tt>args</tt> (an XSeq). An example can be found
in <a href="TestDB.hs">TestDB.hs</a>. To run this example, you need to
install the <a href="data/company.sql">company</a> database. For
example, using the sqlite3 interpreter, you do:
<pre>
sqlite3 myDB
.read data/company.sql
.quit
</pre>
and then compile and run <tt>TestDB.hs</tt>.
<p>
<h3>Shredding</h3>
<p>
To store an XML document into a relational database, use the following Haskell function:
<pre>
shred :: (IConnection conn) => conn -> String -> String -> IO ()
shred db file name
</pre>
that shreds and stores the XML document located at the file pathname
in the database db under a unique name. HXQ will find a good
relational schema (using hybrid inlining) to store the XML data by
first scanning the document to extract its structural summary, then
deriving a good relational schema, and finally scanning the document
for a second time to store its data into the relational tables. For
example,
<pre>
do db <- connect "myDB"
shred db "data/cs.xml" "c"
</pre>
<p>
The Haskell function
<pre>
printSchema db name
</pre>
displays the relational schema for the shredded document under the given name, while
<pre>
createIndex db name tagname
</pre>
creates a secondary index on tagname for the shredded document.
<p>
<h3>Publishing</h3>
<p>
You can query a shredded XML document using the XQuery function:
<pre>
publish(dbame,name)
</pre>
where dbname is the database file name and name is the unique name
assigned to the XML document when was shredded. The translation from
XQuery to SQL is done at compile-time, so both dbname and name must be
constant strings. HXQ will do its best to push relevant predicates to
the generated SQL query (using partial evaluation and code folding),
thus deriving an efficient execution. One example
is <a href="TestDB2.hs">TestDB2.hs</a>.
<p>
<hr>
<p>
<address>Last modified: 08/23/08 by <a href="http://lambda.uta.edu/">Leonidas Fegaras</a></address>