ARQ - SPARQL Algebra

A SPARQL query in ARQ goes through several stages of processing:

• String to Query (parsing)
• Translation from Query to a SPARQL algebra expression
• Optimization of the algebra expression
• Query plan determination
• Evaluation of the query plan

and each step is externally accessible. This page describes how to access and use expressions in the SPARQL algebra within ARQ. The definition of the SPARQL algebra is to be found in the SPARQL specification in section 12.

The classes for the datastructures for the algebra resize in the package com.hp.hpl.jena.sparql.algebra in the op subpackage.  All the classes are names "Op..."; the interface that all offer is "Op".

Viewing the algebra expression for a Query

The command line tool arq.qparse will print the algebra form of a query:

arq.qparse --print=op --query=Q.rq
arq.qparse --print=op 'SELECT * { ?s ?p ?o}'

The syntax of the output is SSE, a simple format for writing data structures involving RDF terms. It can be read back in again to produce the Java form of the algebra expression.

Turning a query into an algebra expression

Getting the algebra expression for a Query is simply a matter of passing the parsed Query object to the transaction function in the Algebra class:

Query query = QueryFactory.create(.....) ;
Op op = Algebra.compile(query) ;

And back again.

Query query = OpAsQuery.asQuery(op) ;
System.out.println(query.serialize()) ;

This reverse translation can handle any algebra expression originally from a SPARQL Query, but not any algebra expression.  It is possible to create programmatically useful algebra expressions that can not be truned into a query, especially if they involve algebra.  Also, the query produced may not be exactly the same but will yield the same results (for example, filters may be moved because the SPARQL query algebra translation in the SPARQL specification moves filter expressions around).

Directly reading and writing algebra expression

The SSE class is a collection of functions to parse SSE expressions for the SPARQ algebra but also RDF terms, filter expressions and even dataset and graphs.

Op op = SSE.parseOp("(bgp (?s ?p ?o))") ;	// Read a string

Op op = SSE.readOp("filename.sse") ;		// Read a file

The SSE class simply calls the appropriate builder operation from the com.hp.hpl.jena.sparql.sse.builder package.

To go with this, there is a collection of writers for many of the Java structures in ARQ. 

Op op = ... ;
SE.write(op) ;		// Write to stdout

Writers default to writing to System.out but support calls to any output stream (it manages the conversion to UTF-8) and ARQ own IndentedWriters form for embedding in structured output.  Again, SSE is simply passing the calls to the writer operation from the com.hp.hpl.jena.sparql.sse.writer package.

Creating an algebra expression programmatically

See the example in src-examples/ arq.examples.AlgebraExec.

To produce the complete javadoc for ARQ, downlaod an ARQ distribution and run the ant task 'javadoc-all'.

Evaluating a algebra expression

See the example in src-examples/ arq.examples.AlgebraExec.

QueryIterator qIter = Algebra.exec(op,graph) ;

QueryIterator qIter = Algebra.exec(op,datasetGraph) ;

for ( ; qIter.hasNext() ; )
{
   Binding b = qIter.nextBinding() ;
   Node n = b.get(var_x) ;
   System.out.println(var_x+" = "+FmtUtils.stringForNode(n)) ;
}
qIter.close() ;

ARQ extensions

Quads are handled by a slightly different query translation process that tracks the relevant graph for the quad and generates quad patterns, instead of triple patterns. The main query engine supports quad evaluation; there is a separate reference query engine for quad as well (QueryEngineQuad).

Algebra.compileQuad(Query query)

ARQ Documentation Page