LDScript: Linked Data Script Language

Authors

Olivier Corby <olivier.corby@inria.fr>
Catherine Faron-Zucker <faron@i3s.unice.fr>
Fabien Gandon <fabien.gandon@inria.fr>

Created: 2015, November 5th
Modified: 2017, May 1st

Introduction

We define a Function Language on top of SPARQL filter language by introducing a function clause. It enables users to define and use simple extension functions directly in (extended) SPARQL. The body of functions is written using SPARQL filter language augmented with additional statements. The language can be seen as a kind of SPARQLScript w.r.t SPARQL in the spirit of JavaScript w.r.t HTML.

In the document, we use prefix definitions shown below:

prefix xt: <http://ns.inria.fr/sparql-extension/>
prefix dt: <http://ns.inria.fr/sparql-datatype/>
prefix us: <http://ns.inria.fr/user-extension/>

The example below defines and uses the factorial function. Function definitions occur just after query.

select *
where {
  ?x rdf:value ?n
  filter (?n >= us:fac(10))
}

function us:fac(?n) {
  if (?n = 0, 1, ?n * us:fac(?n - 1))
}

Language Abstract Syntax

FunSPARQL  ::= SPARQL Fun
Fun        ::= (Annotation Function | Annotation Package)*
Function   ::= function Uri(Var*) { Body }
Package    ::= package { Function+ }
Annotation ::= (@public | @debug)*

Body ::= Exp*
Exp  ::= SPARQL Expression with BuiltInCall below

BuiltInCall ::= SPARQL BuiltInCall |
Let | Set | For | If | Funcall | Apply | MapFun | Error 

ExpQuery = Exp | @List | SelectQuery | ConstructQuery | ServiceGraphPattern

Let ::=
let (Var    = ExpQuery, ... ) { Body } |
let ((Var+) = ExpQuery) { Body }

Set ::= set (Var = Exp)

For ::=
for (Var    in ExpQuery) { Body } |
for ((Var+) in ExpQuery) { Body } |

If ::= SPARQL If |
if  (Exp) { Body } (else ( { Body }  | If ))?

Funcall::= funcall  (Exp, Exp*)
Apply  ::= apply (Uri, Exp+)
MapFun ::= Map   (Uri, Exp+) 
Map    ::= map | maplist |  mapfind | mapfindlist | mapmerge | mapany | mapevery

Error ::= error()

List ::= "(" (RDFTerm | List)* ")"

Aggregate ::= SPARQL Aggregate |
aggregate (Exp) |
aggregate ()

Values ::= SPARQL Values |
values Var { unnest(Exp) } |
values (Var+) { unnest(Exp) }
list datatype: http://ns.inria.fr/sparql-datatype/list
xt:list(1, 2, 3)
xt:iota(1, 10)
xt:cons | xt:add | xt:append | xt:reverse | xt:get | xt:sort |xt:size

xt:display(Exp*)

Function

This statement defines a function that can be used in a query, a rule, a template or another function. The name of a function is an URI, it can have zero, one or several arguments. Several functions can be defined with the same name and different number of arguments. Functions can call other functions, including themselves. The body is a sequence of expressions. The result of the function is the result of the last expression of the body.

function us:fun(?x, ?y){
  ?x + ?y
}

Public

This statement exports function definitions in the SPARQL interpreter in such a way that SPARQL queries can use them within current runtime, until triple store resumes.

@public 
function us:foo(){
  xt:display("Hello World")
}

@public 
package {

  function us:bar(?x, ?y){
    us:gee(?x * ?y)
  }
  
  function us:gee(?x){
    ?x * ?x
  }
}

Let

This statement defines local variables. The result of the statement is the result of the last expression of the body.

let (?z = ?x + ?y, ?t = 2 * ?z){
  us:foo(?t)
}

The let statement enables users to destructure list elements into variables. The number of variables may be less than the size of the list.

let ((?x, ?y, ?z) = ?list){
  us:foo(?x, ?y, ?z)
}

The let statement can have a select-where query as right argument. If the left argument is a variable, its value is the first solution of the query, if the left argument is a list of variables, the variables are bound to the values of the corresponding variables (with same name) of the first solution.

let ((?x, ?y) = select * where { ?x foaf:knows ?y }){
  us:foo(?x, ?y)
}

The let statement can take as second argument a construct-where query.

let (?g = construct where {?x foaf:knows ?y}){
  ?g
}

Set

This statement assigns a (new) value to a local variable.

set (?x = ?x + 1)

For

This statement defines a loop on elements of a list.

for (?n in xt:list(1, 2, 3)){
  if (xt:prime(?n)){
    xt:display(?n)
  }
}

The for statement can take as second argument a select-where query. In this case, the loop iterates on the solutions of the query.

for (?m in select * where {?x foaf:knows ?y}){
  let ((?x, ?y) as ?m){
    ...
  }
}

The for statement can take as second argument a construct-where query. In this case, the loop iterates on the triples of the result graph.

for (?t in construct where {?x foaf:knows ?y}){
  let ((?s, ?p, ?o) as ?t){
    ...
  }
}

Let & For

Objects that can be destructured as list of variables in let:

Objects that can be iterated in for:

If Then Else

This statement is a syntactic extension of SPARQL if then else statement.

if (?x > 0){
  us:foo(?x)
}
else if (?y > 0){
  us:bar(?y)
}
else {
  us:gee(?x, ?y)
}

Map

The map statement applies a function on the elements of a list.

map (xt:display, xt:list(1, 2, 3))

The maplist statement applies a function on the elements of a list and returns the list of results

maplist (us:double, xt:list(1, 2, 3))

The mapmerge statement applies a function on the elements of a list and returns the merge of the lists of results

mapmerge (xt:list, xt:list(1, 2, 3))

The mapfindlist statement finds the elements of a list for which the function returns true. Function mapfind returns first of such elements.

mapfindlist (xt:prime, xt:list(1, 2, 3))

The mapevery statement returns true if the function returns true on all elements.

mapevery (xt:prime, xt:list(1, 2, 3))

The mapany statement returns true if the function returns true on any element.

mapany (xt:prime, xt:list(1, 2, 3))

Apply

This statement recursively applies a binary function to a list of arguments.

apply (xt:plus, xt:list(1, 2, 3))

Error

This statement returns an error.

if (?x < 0){
  error()
}

Aggregate

This statement defines an extension aggregate. The first expression (e.g. aggregate(?n)) is the expression to aggregate. The aggregate function computes the list of values of this expression. The second expression (e.g. us:median(?list)) is the function to be applied to the list of values. In the example below, the aggregate computes the median of the values.

select (aggregate(?n) as ?list) (us:median(?list) as ?med)
where {
  ?x rdf:value ?n
}

function us:median(?list){
   xt:sort(?list); 
   xt:get(?list, xt:div(xt:size(?list), 2)) 
}

The aggregate function can also be used alone, in this case the list of values is returned. When used with no argument, it returns the list of solutions.

select (aggregate(?n) as ?list)
where {
  ?x rdf:value ?n
}

Unnest

This statement unnests a list of values in a bind statement. It is equivalent to a values clause where the values would be computed.

bind (unnest(xt:list(1, 2, 3)) as ?n)

It is equivalent to the values clause below.

values ?n { 1 2 3 }

Display

Display RDF terms.

xt:display("Hello", "World")

List datatype

The dt:list extension datatype manages lists of values. The xt:list function is the list constructor.

xt:list(1, 2, 3)

The xt:iota function generates a list of successive integers.

xt:iota(10)

xt:iota(20, 30)

The xt:size function returns the number of elements of a list.

xt:size(?list)

The xt:get function returns the nth element of a list.

xt:get(?list, 2)

The xt:cons function adds a head element to a list. Returns copy of list.

xt:cons(1, ?list)

The xt:add function adds a tail element to a list. List is modified.

xt:add(?list, 1)

The xt:append function appends two lists.

xt:append(xt:list(1, 2), xt:list(3, 4))

The xt:reverse function reverses a list.

xt:reverse(?list)

The xt:sort function sorts a list.

xt:sort(?list)

Use Cases

Functional Property

In an ontology, properties may be defined as functions of other properties. For example, the surface can be defined as the product of the length and the width.

select * where {
  ?x a us:Figure 
  bind (us:surface(?x) as ?s)
}

function us:surface(?x){
  let ((?w, ?l) = select * where { ?x us:width ?w ; us:length ?l }){
    ?w * ?l
  }
}

Functional Service

Implement a function as a service.

function us:service(?x){
  let ((?l) = 
    select ?x ?l where {
      service <http://fr.dbpedia.org/sparql> {
        ?x rdfs:label ?l}}){
    ?l
  }
}

Approximate Match

Functions can be used to program approximate match.

select * where {
  ?x a ?t
  filter us:match(foaf:Person, ?t)
}

function us:match(?q, ?t) { 
  exists { 
    { ?t rdfs:subClassOf* ?q } union 
    { ?q rdfs:subClassOf/(rdfs:subClassOf*|^rdfs:subClassOf) ?t }
  }    
}

Recursive Match

Functions can be used to program recursive match.

select * where {
  ?x a foaf:Person 
  ?y a foaf:Person 
  filter us:match(?x, ?y)
}

function us:match(?x, ?y) { 
  exists { 
    { ?x foaf:knows ?y } union 
    { ?x foaf:knows ?z . ?y a foaf:Person filter us:match(?z, ?y) }
  }    
}

Extension Datatype

The language enables users to define the binding of extension datatype operators to functions. We give below the correspondance of functions with operators. Functions have a fixed name (e.g. plus) in the namespace of the extension datatype (e.g. ex:plus). When the SPARQL interpreter applies an operator on two extended datatypes (e.g. ?x + ?y), it uses the corresponding function definition (e.g. ex:plus(?x, ?y)).

prefix ex: <http://example.org/mydatatype#>

=  ex:equal 
!= ex:diff 
<  ex:less 
<= ex:lessEqual 
>  ex:greater 
>= ex:greaterEqual 

+ ex:plus 
- ex:minus 
* ex:mult 
- ex:divis

Example of ex:plus extension function.

function ex:plus(?x, ?y){
  ex:digit(?x) + ex:digit(?y)
}

Event Driven Function

A SPARQL interpreter may define a set of Event Driven functions. If a SPARQL query provides a function definition for an event, the SPARQL interpreter calls it.

Function called when query processing starts.

xt:start(?query, ?ast)

Function return an iterator of candidate triples for query edge ?q.

xt:produce(?q)

Function called when query engine evaluate target triple ?t for query triple ?q.

xt:candidate(?q, ?t, ?b)

Function called after service execution with service solutions ?ms.

xt:service(?uri, ?query, ?ms)

Function called when a solution ?m is found.

xt:result(?query, ?m)

Function called when query processing completes with solutions ?ms.

xt:solution(?query, ?ms)

SPARQL Script

A xt:main() function in an empty query with function definitions is automatically run by query execution (as a Java main).

function xt:main(){
  us:test()
}

function us:test(){
  xt:display("Hello World")
}

Implementation

LDScript is implemented in the Corese Semantic Web Factory.

Examples

Conclusion

We propose to extend SPARQL with function definitions.