A way to write down data structures in an RDF-centric syntax.
But not an idea for another RDF serialization format.
The SPARQL algebra defines the semantics of a SPARQL graph pattern. Every SPARQL query string (the syntax) is mapped to a SPARQL algebra expression.
It is convenient to be able to print out such algebra expressions for discussion between people and for debugging. Further, if algebra expressions can be read back in as well, testing of specific parts of an implementation is also easier.
This is an example of a general problem : how to express data structures where the basic elements of RDF are based on RDF nodes.
RDF itself is often the most appropriate way to do this, but sometimes it isn't so convenient. An algebra expression is a tree, and order matters.
When expressing a data structure, there are certain key structure that need to be expressible: arrays and maps, then sets and bags, but expression of a data structure is not the same as the high-level semantics of the data structure.
A stack can be expressed as a list. And because we want to express the structure, and not express the operations on the structures, data structures that operational meaning don't enter the picture. There are no operations, no push, pop or peek.
Note that this is to express a data structure, not encode or repressent it. By express we mean communicate it, between people or between cooperating machines. The structures are not completely self-representing. But we do discuss a way to express in RDF that does give a self-describing nature through the use of tagged structures.
Non-goals:
So desirable features are:
RDF is "map-centric" but not all data structures are conveniently expressible in maps. RDF has lists, and these lists have convenient syntax in Turtle or N3.
If your data structure fits the RDF paradigm, then RDF is a better choice that SSE. Below is a possible mapping from SSE to RDF as Turtle.
Lacks convenient syntax for the RDF terms themselves.
SSE syntax is almost valid
Scheme; literal
language tags and datatypes get split a separate list symbols but the
information is recoverable. Scheme doesn't use [] lists or
single-quoted strings.
Too verbose.
JSON provides values (strings, numbers, booleans, null), arrays and object (which are maps). SPARQL Query Results in JSON shows how JSON might be used. It describes how RDF terms are encoded into further substructures. Alternatively, we could put encoded terms in strings like "<http://w3.org/>" and have a parser-within-a-parser. But both these approaches do not make the writing of RDF terms as easy as it could be.
S-expressions using RDF terms.
The command arq.qparse --print=op --file queryFile will print the
SPARQL algebra for the query in SSE format.
Tokens are the atomic elements of the syntax.
| Example | Explaination |
|---|---|
"abc" |
string |
"abc"@en |
string with language tag. |
123 |
number, specifically an xsd;integer. |
<http://example.org/> |
IRI (or URI). |
_:abc |
blank node. |
?x |
variable |
? |
variable |
ex:thing |
prefixed name |
ex:123 |
prefixed name |
SELECT |
symbol |
+ |
symbol |
@xyz |
symbol |
For ? (no name), a unique, internal name for a fresh variable will be
allocated; every use of ? is a different variable.
??x creates a non-distinguished variable. ?? creates a fresh
non-distinguished variable.
_: creates a fresh blank node.
@xyz - this is a symbol because a language tags only follow a lexical
form.
Almost any sequence of characters which is not an RDF term or variable is a symbol that can be given special meaning by processing software.
# or ; introduce comments, which run to the end of line, including
the end-of-line characters.
\u and \U escape sequences for arbitrary Unicode codepoints. These
apply to the input character stream before parsing. They don't, for
example, permit a space in a symbol.
Strings provide \n, \t, \r, \b, \b, \f, \", \' and \\
escape sequences as in SPARQL.
(?x ns:p "abc") - list of 3 elements: a variable, a prefixed name and
a string
(bgp [?x ns:p "abc"])
A list of 2 elements: a symbol (bgp) and a list of 3 elements. Both
() and [] delimit lists; they must match but otherwise it's a free
choice. Convention is that compact lists use []; large lists use ().
The basic syntax defines tokens and lists. Higher level processing happens on this basic syntax and can be extended by interpreting the structure.
Layers on top of the basic abstract syntax produce specialised data structures. This can be a transformation into a new SSE structure or the production of programming language objects.
This is driven by tagged (data) objects in an SSE expression. The tag is a symbol and the elements of the data object are the rest of the list.
(+ 1 2)
is tagged with symbol +
(triple ?s ?p "text"@en)
is tagged with symbol triple
One such layer is IRI and prefix name resolution, using tags base and
prefix.
Basic syntax includes unresolved IRIs, (example <abc>) and prefixed
names (example foaf:name). These are turned into absolute IRIs and the
base and prefix tagged object wrappers are removed.
This is sufficiently important that the SSE library handles this in an optimized fashion where the IRI processing directly rewrites the streamed output of the parser.
base(base <http://example/> (triple <xyz> ?p "lex"^^<thing>))
becomes
(triple <http://example/xyz> ?p "lex"^^<http://example/thing>)
prefix(prefix ((: <http://example/>) (ns: <http://example/ns#>)) (triple :x ns:p "lex"^^ns:type))
becomes
(triple <http://example/x> <http://example/ns#p> "lex"^^<http://example/ns#type>)
The tagged structures can be combined and nested. The base or prefixes declared only apply to the body of the data object.
(prefix ((: <http://jena.hpl.hp.com/2007/>) (foaf: <http://xmlns.com/foaf/0.1/>)) (triple (base <http://jena.hpl.hp.com/> <afs> foaf:name "Andy")))
Combined with the triple builder, this will produce a triple:
<http://jena.hpl.hp.com/afs> <http://xmlns.com/foaf/0.1/name> "Andy" .
Not implemented
Not all data structures can be conveniently expressed as nested lists. Sub-element sharing matters. A structure with shared elements can't be serialized as a strict tree and some form of reference is needed.
Name a place in the structure: (name@ symbol X)
Link to it: (@link symbol)
The link layer will produce an SSE structure without these tags, having
replaced all name@ and @link with the shared structure X.
@ is a convention for referencing.
Builders are code classes that process the structure into Java objects. Writing builders is straight-forward because low-level parsing details have been taken care of in the basic syntax. A typical builder is a recursive-decent parser over the abstract syntax tree, coding one is primarily walking the structure, with a tagged object to Java instance mapping being applied.
Some tagged objects with builders are:
(triple S P O) where X is an RDF node (RDF term or variable).(quad G S P O)(graph triple*)(graph@ URL) — Read a URL.@@ Need to write the abstract syntax for each tagged object
Many builders have convenience syntax. Triples can be abbreviated by
omitting the tag triple because usually the fact it is a triple is
clear.
(bgp (triple ?s ?p ?o)) (bgp (?s ?p ?o))
Quads have a similar abbreviation as 4-lists. In addition, _ is a quad
on the default graph.
Elements for executing SPARQL:
(+ 1 2))The class SSE in package com.hp.hpl.jena.sparql.sse provides many
convenience functions to call builders for RDF and SPARQL structures.
Node n = SSE.parseNode("<http://example/node>") ; Triple t = SSE.parseTriple("(?s ?p ?o)") ; Op op = SSE.parseOp("(filter (> ?v 123) (bgp (?s ?p ?v)))") ;
Most of the operations have forms that allow a PrefixMapping to be
specified - this is wrapped around the parser run so prefixed names can
be used without explicit prefix declarations.
There is a default prefix mapping with a few common prefixes: rdf,
rdfs, owl, xsd and fn (the XPath/XQuery functions and operators
namespace).
The syntax of SSE is very close to Turtle lists because the syntax for IRIs and literals are the same.: to produce Turtle (outline):
@prefix directives.The result is an RDF model using only the properties rdf:first and
rdf:rest so it records the data structure, but not what hthe data
structure represents.
The file extension is .sse and all files are UTF-8.
A quick and pragmatic Emacs mode is given by:
;; ==== SSE mode (define-derived-mode sse-mode lisp-mode "SSE" nil (make-local-variable 'lisp-indent-function) (setq lisp-indent-function 'sse-indent-function) ) ;; Everything in SSE is "def" like (defun sse-indent-function (indent-point state) (lisp-indent-defform state indent-point)) (setq auto-mode-alist (cons '("\\.sse" . sse-mode) auto-mode-alist))
PREFIX foaf: <http://xmlns.com/foaf/0.1/> SELECT DISTINCT ?name ?nick { ?x foaf:mbox <mailt:person@server> . ?x foaf:name ?name OPTIONAL { ?x foaf:nick ?nick } } (prefix ((foaf: <http://xmlns.com/foaf/0.1/>)) (distinct (project (?name ?nick) (leftjoin (BGP [triple ?x foaf:mbox <mailto:person@server>] [triple ?x foaf:name ?name] ) (BGP [triple ?x foaf:nick ?nick]) ))))
The following is a complete query execution, data and query. There is an inline dataset and a query of
PREFIX : <http://example/> SELECT * { GRAPH :g1 { ?x ?p ?v } }
The tag graph is used twice, with different meanings. First, for an
RDF graph, and second in GRAPH SPARQL pattern. In a data structrure,
context sorts out the different usages.
(prefix ((: <http://example/>)) (exec (dataset (default (graph (:x :p 1) (:x :p 2))) (namedgraph :g1 (graph (:x :gp 1) (:x :gp 2))) (namedgraph :g2 (graph (:y :gp 1) (:y :gp 2))) ) (graph :g1 (bgp (?x ?p ?v))) ))
@@ insert grammar here