SPARQL Algebra for RDF.rb

This is a Ruby implementation of the SPARQL algebra for RDF.rb.

Features

  • Implements all SPARQL 1.0 algebra operators generating RDF::Query compatible solution sequences.
  • Implements FILTER expression optimizations such as constant folding, strength reduction, and memoization.
  • Compatible with Ruby 1.8.7+, Ruby 1.9.x, and JRuby 1.4/1.5.
  • 100% free and unencumbered public domain software.

Examples

require 'sparql/algebra'

include SPARQL::Algebra

Example Queries

Basic Query

BASE <http://example.org/x/> 
PREFIX : <>

SELECT * WHERE { :x ?p ?v }

is equivalent to

(prefix ((: <http://example.org/x/>))
  (bgp (triple :x ?p ?v)))

Prefixes

PREFIX ns: <http://example.org/ns#>
PREFIX x:  <http://example.org/x/>

SELECT * WHERE { x:x ns:p ?v }

is equivalent to

(prefix ((ns: <http://example.org/ns#>)
         (x: <http://example.org/x/>))
  (bgp (triple x:x ns:p ?v)))

Ask

(prefix ((: <http://example/>))
  (ask
    (bgp (triple :x :p ?x))))

Datasets

PREFIX : <http://example/> 

SELECT * 
FROM <data-g1.ttl>
FROM NAMED <data-g2.ttl>
{ ?s ?p ?o }

is equivalent to

(prefix ((: <http://example/>))
  (dataset (<data-g1.ttl> (named <data-g2.ttl>))
    (bgp (triple ?s ?p ?o))))

Join

PREFIX : <http://example/> 

SELECT * 
{ 
   ?s ?p ?o
   GRAPH ?g { ?s ?q ?v }
}

is equivalent to

(prefix ((: <http://example/>))
  (join
    (bgp (triple ?s ?p ?o))
    (graph ?g
      (bgp (triple ?s ?q ?v)))))

Union

PREFIX : <http://example/> 

SELECT * 
{ 
   { ?s ?p ?o }
  UNION
   { GRAPH ?g { ?s ?p ?o } }
}

is equivalent to

(prefix ((: <http://example/>))
  (union
    (bgp (triple ?s ?p ?o))
    (graph ?g
      (bgp (triple ?s ?p ?o)))))

LeftJoin

PREFIX :    <http://example/>

SELECT *
{ 
  ?x :p ?v .
  OPTIONAL
  { 
    ?y :q ?w .
    FILTER(?v=2)
  }
}

is equivalent to

(prefix ((: <http://example/>))
  (leftjoin
    (bgp (triple ?x :p ?v))
    (bgp (triple ?y :q ?w))
    (= ?v 2)))

Complex

Expression Evaluation

Constructing operator expressions manually

Operator(:isBlank).new(RDF::Node(:foobar))
Operator(:isIRI).new(RDF::URI('http://rdf.rubyforge.org/'))
Operator(:isLiteral).new(RDF::Literal(3.1415))
Operator(:str).new(Operator(:datatype).new(RDF::Literal(3.1415)))

Constructing operator expressions using SSE forms

Expression[:isBlank, RDF::Node(:foobar)]
Expression[:isIRI, RDF::URI('http://rdf.rubyforge.org/')]
Expression[:isLiteral, RDF::Literal(3.1415)]
Expression[:str, [:datatype, RDF::Literal(3.1415)]]

Constructing operator expressions using SSE strings

Expression.parse('(isBlank _:foobar)')
Expression.parse('(isIRI <http://rdf.rubyforge.org/>)')
Expression.parse('(isLiteral 3.1415)')
Expression.parse('(str (datatype 3.1415))')

Evaluating operators standalone

Operator(:isBlank).evaluate(RDF::Node(:foobar))              #=> RDF::Literal::TRUE
Operator(:isIRI).evaluate(RDF::DC.title)                     #=> RDF::Literal::TRUE
Operator(:isLiteral).evaluate(RDF::Literal(3.1415))          #=> RDF::Literal::TRUE

Evaluating expressions on a solution sequence

require 'rdf/triples'

# Find all people and their names & e-mail addresses:
solutions = RDF::Query.execute(RDF::Graph.load('etc/doap.nt')) do |query|
  query.pattern [:person, RDF.type,  FOAF.Person]
  query.pattern [:person, FOAF.name, :name]
  query.pattern [:person, FOAF.mbox, :email], :optional => true
end

# Find people who have a name but don't have a known e-mail address:
expression = Expression[:not, [:bound, Variable(:email)]]    # ...or just...
expression = Expression.parse('(not (bound ?email))')
solutions.filter!(expression)

Optimizing expressions containing constant subexpressions

Expression.parse('(sameTerm ?var ?var)').optimize            #=> RDF::Literal::TRUE
Expression.parse('(* -2 (- (* (+ 1 2) (+ 3 4))))').optimize  #=> RDF::Literal(42)

Optimizations

Some very simple optimizations are currently implemented for FILTER expressions. Use the following to obtain optimized SSE forms:

Expression.parse(sse).optimize.to_sse

Constant comparison folding

(sameTerm ?x ?x)   #=> true

Constant arithmetic folding

(!= ?x (+ 123))    #=> (!= ?x 123)
(!= ?x (- -1.0))   #=> (!= ?x 1.0)
(!= ?x (+ 1 2))    #=> (!= ?x 3)
(!= ?x (- 4 5))    #=> (!= ?x -1)
(!= ?x (* 6 7))    #=> (!= ?x 42)
(!= ?x (/ 0 0.0))  #=> (!= ?x NaN)

Memoization

Expressions can optionally be memoized, which can speed up repeatedly executing the expression on a solution sequence:

Expression.parse(sse, :memoize => true)
Operator.new(*operands, :memoize => true)

Memoization is implemented using RDF.rb's RDF::Util::Cache utility library, a weak-reference cache that allows values contained in the cache to be garbage collected. This allows the cache to dynamically adjust to changing memory conditions, caching more objects when memory is plentiful, but evicting most objects if memory pressure increases to the point of scarcity.

Documentation

http://sparql.rubyforge.org/algebra/

TODO

  • Need to come up with appropriate SXP for SPARQL 1.1
  • Operator#optimize needs to be completed and tested.

Dependencies

Installation

The recommended installation method is via RubyGems. To install the latest official release of the SPARQL::Algebra gem, do:

% [sudo] gem install sparql-algebra

Download

To get a local working copy of the development repository, do:

% git clone git://github.com/bendiken/sparql-algebra.git

Alternatively, download the latest development version as a tarball as follows:

% wget http://github.com/bendiken/sparql-algebra/tarball/master

Mailing List

Authors

Contributors

Refer to the accompanying CREDITS file.

Contributing

  • Do your best to adhere to the existing coding conventions and idioms.
  • Don't use hard tabs, and don't leave trailing whitespace on any line.
  • Do document every method you add using YARD annotations. Read the tutorial or just look at the existing code for examples.
  • Don't touch the .gemspec, VERSION or AUTHORS files. If you need to change them, do so on your private branch only.
  • Do feel free to add yourself to the CREDITS file and the corresponding list in the the README. Alphabetical order applies.
  • Do note that in order for us to merge any non-trivial changes (as a rule of thumb, additions larger than about 15 lines of code), we need an explicit public domain dedication on record from you.

License

This is free and unencumbered public domain software. For more information, see http://unlicense.org/ or the accompanying UNLICENSE file.

Portions of tests are derived from W3C DAWG tests and have other licensing terms.