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/
- SPARQL::Algebra
- SPARQL::Algebra::Expression
- SPARQL::Algebra::Query
- SPARQL::Algebra::Operator
- SPARQL::Algebra::Operator::Add
- SPARQL::Algebra::Operator::And
- SPARQL::Algebra::Operator::Asc
- SPARQL::Algebra::Operator::Ask
- SPARQL::Algebra::Operator::Base
- SPARQL::Algebra::Operator::Bound
- SPARQL::Algebra::Operator::Compare
- SPARQL::Algebra::Operator::Construct
- SPARQL::Algebra::Operator::Dataset
- SPARQL::Algebra::Operator::Datatype
- SPARQL::Algebra::Operator::Desc
- SPARQL::Algebra::Operator::Describe
- SPARQL::Algebra::Operator::Distinct
- SPARQL::Algebra::Operator::Divide
- SPARQL::Algebra::Operator::Equal
- SPARQL::Algebra::Operator::Exprlist
- SPARQL::Algebra::Operator::Filter
- SPARQL::Algebra::Operator::Graph
- SPARQL::Algebra::Operator::GreaterThan
- SPARQL::Algebra::Operator::GreaterThanOrEqual
- SPARQL::Algebra::Operator::IsBlank
- SPARQL::Algebra::Operator::IsIRI
- SPARQL::Algebra::Operator::IsLiteral
- SPARQL::Algebra::Operator::Join
- SPARQL::Algebra::Operator::Lang
- SPARQL::Algebra::Operator::LangMatches
- SPARQL::Algebra::Operator::LeftJoin
- SPARQL::Algebra::Operator::LessThan
- SPARQL::Algebra::Operator::LessThanOrEqual
- SPARQL::Algebra::Operator::Minus
- SPARQL::Algebra::Operator::Multiply
- SPARQL::Algebra::Operator::Not
- SPARQL::Algebra::Operator::NotEqual
- SPARQL::Algebra::Operator::Or
- SPARQL::Algebra::Operator::Order
- SPARQL::Algebra::Operator::Plus
- SPARQL::Algebra::Operator::Prefix
- SPARQL::Algebra::Operator::Project
- SPARQL::Algebra::Operator::Reduced
- SPARQL::Algebra::Operator::Regex
- SPARQL::Algebra::Operator::SameTerm
- SPARQL::Algebra::Operator::Slice
- SPARQL::Algebra::Operator::Str
- SPARQL::Algebra::Operator::Subtract
- SPARQL::Algebra::Operator::Union
TODO
- Need to come up with appropriate SXP for SPARQL 1.1
- Operator#optimize needs to be completed and tested.
Dependencies
- Ruby (>= 1.8.7) or (>= 1.8.1 with Backports)
- RDF.rb (>= 0.3.1)
- SXP (>= 0.0.14) for SSE parsing and serialization
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
orAUTHORS
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 theREADME
. 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.