LDScript Linked Data Script Language

2017, September 1st

Authors

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

Abstract

This document defines a function definition language on top of SPARQL filter language. 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.

Table of contents

1 Introduction
  1.1 Relationship to W3C Recommendations
2 Function Definition
  2.1 Function
  2.2 Lambda Expression
  2.3 Annotation
3 Statement
  3.1 SPARQL
  3.2 Let
  3.3 For
  3.4 Pattern Matching
  3.5 If Then Else
  3.6 Return
  3.7 Error
4 Second Order Function
  4.1 Funcall
  4.2 Apply
  4.3 Map
  4.4 Reduce
5 Predefined Extension Function
6 Datatype
  6.1 List
  6.2 RDF Datatype
  6.3 SPARQL Datatype
  6.4 Extension Datatype
7 Language Syntax
8 SPARQL Extension
  8.1 LDScript in SPARQL
  8.2 Aggregate
  8.3 Values Unnest
  8.4 Named Graph Pattern
9 Use Case
  9.1 Functional Property
  9.2 Functional Service
  9.3 Approximate Match
  9.4 Recursive Match
  9.5 Event Driven Function
  9.6 Predefined Query
10 Implementation
11 Conclusion

 

1 Introduction

In addition to the existing standards dedicated to representation or querying, Semantic Web programmers could really benefit from a dedicated programming language enabling them to directly define functions on RDF terms, RDF graphs or SPARQL results. This is especially the case, for instance, when defining SPARQL extension functions. We propose a function definition 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.

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

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

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

1.1 Relationship to W3C Recommendations

This proposition is strongly related to SPARQL 1.1 Query Language and to RDF 1.1 Concepts and Abstract Syntax.

 

2 Function Definition

The language is built on top of SPARQL filter language extended with the statements defined in this proposition. The objects of the language are SPARQL variables and RDF terms: URI, literal, blank node. The language objects can also be RDF triple and graph as well as SPARQL query solution (mapping) and solution sequence (mappings). A list datatype is also introduced whose elements can be any of the objects listed above, including lists. List elements do not need to be of the same kind or of the same datatype. Triple, graph, mapping, mappings and list are managed as RDF literals with extension datatypes: dt:triple, dt:graph, dt:mapping, dt:mappings and dt:list. Their content is accessed by pattern matching and they are iterable. We call LDScript terms the union of RDF terms and LDScript literals with extension datatype in the dt: namespace.

In the document, we use prefix and namespaces shown below:

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

2.1 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 that are variables in SPARQL syntax. Function overloading is provided: several functions can be defined with the same name and different number of arguments. Functions can call other LDScript functions including themselves, SPARQL functions or extension functions. The body is a sequence of expressions. The result of the function is the result of the last expression of the body, or the result of the return function if any.

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

2.2 Lambda Expression

This statement defines an anonymous function that can be used with second order functions such as: apply, funcall, map and reduce. As it is an expression of the language, it can be bound to a variable, passed to a function call as parameter, it can be an element of a list, etc. At compile time, compiling a lambda expression generates a function definition with a generated URI. At runtime, a lambda expression definition evaluates to the URI of the generated function, hence lambda expression definition is transparent for the interpreter as it resumes to its URI.

lambda(?x) { 1 / (?x * ?x) }
maplist(lambda(?x) { 1 / (?x * ?x) } , xt:iota(5))

2.3 Annotation

Public

This @public annotation exports function definitions in the SPARQL interpreter in such a way that future SPARQL queries can use them within current runtime session.

@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
  }
}

 

3 Statement

This section details LDScript statements.

3.1 SPARQL

LSDcript inherits SPARQL Filter language statements, including the exists clause, and SPARQL select and construct queries. The exists, select-where and construct-where statements are evaluated with the Dataset of the embedding SPARQL query that runs the LDScript function. For syntactic reasons, SPARQL queries are embedded in a query statement, except in the let and for statements where it can be avoided.

query(select ?x ?y where { ?x foaf:knows ?y })

It is possible to specify a graph on which the query must be evaluated. The datatype of the result of the expression representing the graph must be dt:graph.

query(select ?x ?y where { ?x foaf:knows ?y }, ?g)

The result of a select (resp. construct) query is a dt:mappings (resp. dt:graph) datatype extension literal. These datatypes act as "pointers" to the underlying data structure that implements the result of the query.

datatype(query(select ?x ?y where {?x foaf:knows ?y})) = dt:mappings
datatype(query(construct    where {?x foaf:knows ?y})) = dt:graph

At runtime, variables projected in the select clause of a query that are bound in LDScript stack are bound in the where clause. They are bound using an extended values clause that is generated dynamically. It is extended because it accepts blank node values in addition to URI and literals. The query above is evaluated as shown below if the value of ?x is v in the stack.

function us:foo(?x) {
  query(select ?x ?y where { values ?x { v }  ?x foaf:knows ?y })
}

For construct queries, variables that are in-scope in the where clause and that are bound in LDScript stack are bound in the where clause using an extended values clause.

For the exists { BGP } clause, variables that are in-scope in the BGP and that are bound in LDScript stack are bound in the BGP using an extended values clause.

Statements such as if, bound, coalesce are also available. SPARQL functions are also available with the rq: prefix.

Query and Lambda

It is worth nopicine dhat, as any statement, a SPARQL query can be embedded in a lambda expression.

let (?query = lambda() { query(select .. where ..) }) {
    datatype(funcall(?query)) = dt:mappings
}

3.2 Let

This statement defines local variables whose scope is the body of the let statement. The result of the statement is the result of the last expression of the body, or the result of the return statement if any.

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

Let List

The let statement enables users to map list elements to 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 left argument can be a list of lists of variables.

let (((?a, ?b), (?c, ?d)) = @((1 2)(3 4)) {
  us:foo(?a, ?b) ;
  us:foo(?c, ?d)
}

Let Select Query

The let statement can have a select-where query as argument. In this case, the variables in the select clause are defined and bound, in the body of the let clause, with the values of the first query solution. If a variable has no value in the first solution (e.g. due to an optional), the body is executed with the variable left unbound. If there is no solution, the body is still executed. These cases can be trapped in the body by the bound or coalesce functions.

let (select ?x ?y where { ?x foaf:knows ?y }) {
    us:bar(?x, ?y)
}

If the left argument is a list of variables, each variable is bound to the corresponding query solution (a mapping) in order.

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

If the left argument is a list of list of variables, each variable is bound to the value of the corresponding variable (with same name) in the first query solution.

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

Let Construct Query

The let statement can take as second argument a construct-where query. The value of the variable is the RDF result graph.

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

Variables in-scope in the where clause that are bound in LDScript stack are bound in the where clause using an extended values clause generated at runtime. The query above is evaluated as shown below if the value of ?x is v in the stack.

function us:foo(?x) {
    let (?g = construct where { values ?x { v }  ?x foaf:knows ?y}) {
        ?g
    }
}

3.3 For

This statement defines a loop on LDScript terms that are iterable datatypes. The list below specifies the kind of the term iterated in the for statement.

  1. for(dt:list) : LDScript term
  2. for(dt:graph) : dt:triple
  3. for(dt:triple) : RDF term
  4. for(dt:mappings) : dt:mapping
  5. for(dt:mapping) : dt:list(xsd:string, RDF term) where first element is the variable name and second is the variable value

The result returned by the for statement is the boolean value true. A specific result can be returned using the return statement.

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

For Select Query

The for statement can take as argument a select-where query. In this case, the loop iterates on the solutions of the query and the variables projected in the select clause are bound to their value of the current solution in the body of the loop.

for (select ?x ?y where {?x foaf:knows ?y}) {
    us:foo(?x, ?y)
}

It is possible to specify explicitly the variable(s) to be bound in the loop.

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

For Construct Query

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) = ?t) {
    ...
  }
}

3.4 Pattern Matching

In order to avoid cumbersome APIs, the access to the content of extension datatypes can be done by declarative pattern matching.

Let Pattern Matching

Iterable datatypes can be mapped by to a list of variables, by pattern matching, using the let statement.

let ((?e1, ?e2, ?e3) = ?list)
let ((?t1, ?t2, ?t3) = ?graph)
let ((?s, ?p, ?o)    = ?triple)
let ((?m1, ?m2, ?m3) = ?mappings)

Pattern matching with dt:mapping datatype is done by variable name and not by position. In the example below, variable ?x is bound to the value of variable ?x in current mapping.

let ((?x, ?y) = ?mapping) 

For Pattern Matching

LDScript extension datatypes can be iterated and mapped to a list of variables using the for statement.

for (?elem in ?list)
for (?triple in ?graph)
for ((?s, ?p, ?o) in ?graph)
for (?term in ?triple)
for (?mapping in ?mappings)
for ((?var, ?val) in ?mapping) 

A mappings datatype is iterated as mapping elements. Pattern matching with mapping element is done by variable name and not by position. In the example below, variable ?x and ?y are bound to the values of variable ?x and ?y in current mapping.

for ((?x, ?y) in ?mappings)

Lambda Pattern Matching

A syntax for lambda expression arguments is available for pattern matching on query solutions as shown below.

maplist(lambda((?x, ?y)) { us:foo(?x, ?y) }, 
  query(select ?x ?y where { .. }))  
::=
maplist(lambda(?m) { let ((?x, ?y) = ?m) { us:foo(?x, ?y) } }, 
  query(select ?x ?y where { .. }))
maplist(lambda((?s, ?p, ?o)) { us:bar(?s, ?p, ?o) }, 
  query(construct { .. } where { .. }))  
::=
maplist(lambda(?t) { let ((?s, ?p, ?o) = ?t) { us:bar(?s, ?p, ?o) } }, 
  query(construct { .. } where { .. } ))

3.5 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) 
}

3.6 Return

This statement resumes the execution of a function and returns its result.

function us:test(?a, ?b)
  for (?x in xt:iota(?a, ?b)) {
     if (us:prime(?x)) { return(?x) }
  }
}

3.7 Error

This statement returns an error. The execution of the LDScript expression resumes and returns an error. It can be trapped by the coalesce statement as in SPARQL.

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

4 Second Order Function

A second order function is a function whose first argument evaluation returns a function (a function URI or a lambda expression) and which calls this function with the other arguments. Second order functions are funcall, apply, map and reduce. The are useful in the context of Linked Data because the name of a function to be applied on resources can be determined by a SPARQL query.

4.1 Funcall

This statement applies a function which is the result of the evaluation of an expression. The first argument of the statement is an expression that must return either the URI of a function or a lambda expression.

funcall (us:getMethod(us:surface, ?x), ?x)

4.2 Apply

This statement applies a function to a list of arguments. The first argument of the statement is an expression that must return the URI of a function or a lambda expression.

apply (rq:regex, xt:list("test", "e", "i"))

4.3 Map

The map statement applies a function iteratively on the elements of an iterable datatype: dt:list, dt:graph, dt:mappings, etc. The first argument of the statement is an expression that must return the URI of a function or a lambda expression. SPARQL filter functions, as well as second order functions, are available as URI with the rq: prefix.

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

The map functions described here can operate on two (or several) iterable datatypes. In this case, the function to be applied must have the same number of arguments as the number of iterable, and each iterable datatype is iterated at the same pace with the same index.

map (us:test, xt:list(1, 2, 3), xt:list(4, 5, 6))

The map functions described here can also have arguments that are not iterable datatypes. In this case, the same value of the argument is considered at each step of the iteration of the iterable datatypes.

map (us:fun, xt:list(1, 2, 3), 4)

The map functions described here can operate on iterable datatypes such as graph (iterate triple) or mappings (iterate mapping).

map (us:foo, query(select * where { ?x ?p ?y }))

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

maplist (lambda(?x) { 1 / (?x * ?x) }, xt:list(1, 2, 3))

The mapmerge statement applies a function on the elements of an iterable datatype and returns the merge of the lists of results

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

The mapfind statement search elements for which the function returns true. Function mapfind returns first of such elements.

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

The mapfindlist statement finds the elements of an iterable datatype for which the function returns true, retutn the list of such elements.

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

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

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

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

mapany (lambda(?y) { exists { ?x ?p ?y } }, xt:list(1, 2, 3))

4.4 Reduce

This statement applies a binary function iteratively to a list of arguments and produces one final result. The first argument of the statement is an expression that must return the URI of a function or a lambda expression.

reduce (rq:plus, xt:iota(5)) = 15

Combining second order functions

Second order functions are available with the rq: prefix and can be combined.

reduce(rq:concat, maplist(rq:funcall, 
  xt:list(rq:year, rq:month, rq:day, rq:hours, rq:minutes, rq:seconds), 
  now()))

 

5 Predefined Extension Function

LDScript introduces general purpose extension functions.

Display

Display RDF terms in Turtle syntax.

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

Print

Display RDF terms string value.

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

Turtle

Return a xsd:string Turtle representation of an RDF term.

xsd:string xt:turtle(RDF term)

Content

Return a xsd:string representation of the content of an extension datatype in the dt:namespace.

xsd:string xt:content(?g)

Self

Return the result of the evaluation of its argument.

RDF term xt:self(RDF term)

Graph

Return the current focus graph.

dt:graph xt:graph()

Load

The xt:load function implements URI dereferencing, it returns the graph resulting from the parsing of an RDF document.

dt:graph xt:load(URI)

Focus Statement

The first argument MUST returns a graph with datatype dt:graph. The focus statement evaluates the second argument with the graph as current dataset.

xt:focus(graph, exp)
xt:focus(
    xt:load(<http://example.org/test>),
    exists { ?x rdf:value 2.718 })

Transformation

LDScript inherits STTL transformation language API that enables users to apply transformations to RDF entities such as Turtle, RDF/XML or JSON transformations to RDF graphs and resources or the functional syntax transformation of OWL ontologies. Note that these functions belong to the st: namespace. In the example below, st-uri is the name of a transformation: st:turtle, st:rdfxml, st:json, st:owl.

st:apply-templates-with(st-uri)
st:apply-templates-with(st-uri, term)

st:apply-templates-all(term)
st:apply-templates-with-all(st-uri, term)

st:apply-templates-graph(graph-uri)
st:apply-templates-with-graph(st-uri, graph-uri)

st:call-template(uri, term_1, .., term_n)
st:call-template-with(st-uri, uri, term_1, .., term_n)

 

6 Datatype

Conceptually, LDScript objects are RDF terms as well as RDF, SPARQL and LDScript entities. RDF terms are URI, literal with XSD datatype and blank node. RDF entities are graph and triple. SPARQL entities are query solution sequence (called mappings) and query solution (called mapping). LDScript entities are lists whose elements are LDScript objects.

At the implementation level, LDScript objects other than RDF terms are implemented by means of literals with specific extension datatypes in the dt: namespace: dt:list, dt:graph, dt:triple, dt:mappings, dt:mapping. Hence they are also implemented as RDF terms (i.e. RDF literals with extension datatypes) and their content can be accessed by specific statements as shown below. These datatypes are iterable by means of the for and map statements (see section Pattern Matching). We call such LDScript object LDScript terms.

6.1 List

The dt:list extension datatype implements list of LDScript terms, including lists. Although similar, it is distinct from RDF list (rdf:List class with rdf:first, rdf:rest and rdf:nil). List elements need to be neither of the same kind nor of the same datatype. The dt:list datatype is provided with a set of functions.

The xt:list function is the list constructor.

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

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

xt:iota(5)        = xt:list(1, 2, 3, 4, 5)
xt:iota(5, 7)     = xt:list(5, 6, 7)
xt:iota('a', 'c') = xt:list('a', 'b', 'c')

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

xt:size(?list)

The xt:first function returns the first element of a list.

xt:first(?list)

The xt:rest function returns the rest of a list.

xt:rest(xt:list(1, 2, 3)) = xt:list(2, 3)

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

xt:get(?list, 2)

The xt:set function sets the value of the nth element of a list. Error if there is no nth element.

xt:set(?list, 2, us:John)

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

xt:add(?list, us:John)

The xt:add function inserts/adds element to a list at nth place. List is modified.

xt:add(?list, us:John, 10)

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

xt:cons(1, ?list)

The xt:append function appends two lists, keep duplicates.

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

The xt:merge function merges two lists and removes duplicates.

xt:merge(xt:list(1, 2), xt:list(2, 3)) = xt:list(1, 2, 3)

The xt:reverse function reverses a list.

xt:reverse(?list)

The xt:sort function sorts a list.

xt:sort(?list)

Mapping rdf:List with dt:list

select ?x (us:list(?l) as ?list) where {
    ?x rdf:value ?l .
}

function us:list(?l) {
  let (
    select ?l 
      (aggregate(if (?b, us:list(?e), if (?e = rdf:nil, xt:list(), ?e))) as ?list) 
    where {
        ?l rdf:rest*/rdf:first ?e
        bind (exists { ?e rdf:rest ?a } as ?b)
    }) {
    ?list
  }
}

6.2 RDF Datatype

There are two datatypes for RDF entities, dt:graph for RDF graph and dt:triple for RDF triple. They are iterable as shown below.

let (?g = construct where { ?x ?p ?y }) {
    for (?t in ?g) {
        for (?x in ?t) {
        
        }
    }
}

datatype(?g) = dt:graph 
datatype(?t) = dt:triple
?x : RDF term 

Graph Datatype

The dt:graph datatype is provided with functions. Function xt:size returns the number of triples of a graph.

xt:size(?g)

Function xt:union computes a graph that is the union of two graphs. The arguments are literals with dt:graph datatype and the result is returned as a literal with dt:graph datatype.

xt:union(?g1, ?g2)

Triple Datatype

The dt:triple datatype is provided with functions to access the subject, the property and the object. Implementations MAY provide a function to access the named graph when triples are quads.

xt:subject(?t)
xt:property(?t)
xt:object(?t)
xt:graph(?t)

6.3 SPARQL Datatype

There are two datatypes for SPARQL entities, dt:mappings for SPARQL Query solution sequence and dt:mapping for SPARQL Query solution. They are iterable as shown below.

let (?s = select * where { ?x ?p ?y }) {
    for (?m in ?s) {
        for ((?var, ?val) in ?m) {
        
        }
    }
}

datatype(?s)   = dt:mappings 
datatype(?m)   = dt:mapping
datatype(?var) = xsd:string
?val :  RDF term

Mappings

The dt:mappings datatype is provided with a function xt:size that returns the number of solutions.

xt:size(?m)

The dt:mappings datatype is provided with functions that perform SPARQL algebra operations on SPARQL query solutions of select-where queries. The results are returned as literals with dt:mappings datatype.

let (?m1 = select where, ?m2 = select where) {
  xt:join(?m1, ?m2) ;
  xt:union(?m1, ?m2) ;
  xt:minus(?m1, ?m2)
  xt:optional(?m1, ?m2) ;
}

6.4 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 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)
}

Example of ls:equal for dt:list recursive equality.

prefix ls: <http://ns.inria.fr/sparql-datatype/list#>

function ls:equal(?l1, ?l2) {
  xt:size(?l1) = xt:size(?l2) && 
  mapevery(lambda(?x, ?y) { ?x = ?y }, ?l1, ?l2)
}

Example of tr:equal for dt:triple equality.

prefix tr: <http://ns.inria.fr/sparql-datatype/triple#>

function tr:equal(?t1, ?t2) {
   mapevery(lambda(?x, ?y) { ?x = ?y }, ?t1, ?t2)
}

 

7 Language Syntax

The syntax is given in EBNF and relies on SPARQL syntax.

LDScript   ::= SPARQL_QueryUnit Fun
Fun        ::= (Annotation Function | Annotation Package)*
Function   ::= 'function' Uri FunVarList  Body 
Package    ::= 'package' '{' Function+ '}'
Annotation ::= ( '@public' | '@debug' )*

Body ::= '{' Exp? (';' Exp)* '}'
Exp  ::= SPARQL_Constraint -- with BuiltInCall extended below

BuiltInCall ::= SPARQL_BuiltInCall 
| Let | For | If | Return | Error | SecondOrder | Lambda | Query

SecondOrder ::= Funcall | Apply | MapFun | Reduce |  
  
Query ::= 'query' '('  (SelectQuery | ConstructQuery) (',' Exp)?  ')'

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

Let ::=
'let' '(' Var       '=' ExpQuery ')'  Body  |
'let' '(' VarList   '=' ExpQuery ')'  Body  |
'let' '(' '(' VarList (',' VarList)* ')' ')' '=' ExpQuery ')'  Body  |
'let' '(' SelectQuery ')'  Body  

VarList    ::= '(' Var  (',' Var)* ')'
FunVarList ::= '(' Var? (',' Var)* ')'

For ::=
'for' '(' Var     'in' ExpQuery ')'  Body |
'for' '(' VarList 'in' ExpQuery ')'  Body |
'for' '(' SelectQuery ')'  Body  

If ::= 'if'  '(' Exp ')'  Body  ('else' (  Body | If )) ?

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

Lambda ::= 'lambda' LambdaVarList  Body 
LambdaVarList ::= FunVarList | '(' VarList ')'

Error ::= 'error' '(' ')'

Return ::= 'return' '(' Exp ')'

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

 

8 SPARQL Extension

LDScript enables us to propose and implement natural SPARQL extensions.

8.1 LDScript in SPARQL

LDScript statements MAY be available within extended SPARQL.

SPARQL Query

LDScript statements MAY be available within extended SPARQL Query Filter Constraints.

select * where {
    ?x us:method [ us:name us:validate ; us:function ?fun ]
    filter funcall(?fun, ?x) 
}

SPARQL Update

LDScript statements and datatypes MAY be available within extended SPARQL Update. An RDF graph MAY manage LDScript extension datatypes.

insert { [] us:knows ?g }
where {
  bind (query(construct { ?x foaf:knows ?y } 
              where     { ?x foaf:knows+ ?y }) 
  as ?g)
}

8.2 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
}

8.3 Values Unnest

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

values ?n { (unnest(xt:list(1, 2, 3)) }

It is equivalent to the values clause below.

values ?n { 1 2 3 }

Values unnest can be used on: list, mappings, graph.

LDScript SPARQL Extension

Aggregate ::= SPARQL_Aggregate |
'aggregate' '(' 'distinct'? Exp ')' |
'aggregate' '(' ')'

ValuesClause ::= SPARQL_ValuesClause |
'values' Var     '{' 'unnest' '(' Exp ')' '}' |
'values' VarList '{' 'unnest' '(' Exp ')' '}'

8.4 Named Graph Pattern

When a variable has for value an RDF graph, the variable can be used in a named graph pattern and the named graph pattern is evaluated on the content of the graph. The example below shows this case with variable ?g.

let (?g = construct { .. } where { .. }) {
     query(select * where { graph ?g { .. }}) 
} 

 

9 Use Case

9.1 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
  }
}

9.2 Functional Service

Implement a function as a service.

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

9.3 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 }
  }    
}

9.4 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) }
  }    
}

9.5 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)

9.6 Predefined Query

LDScript can be use to manage predefined queries by means of lambda expressions.

function us:foo() {
    let (?list = xt:list(
        lambda() { query(select .. where ..) },
        lambda() { query(select .. where ..) }
    )) {
        maplist(rq:funcall, ?list)
    }
}

 

10 Implementation

LDScript is implemented and available in the Corese Semantic Web Factory.

Examples

 

11 Conclusion

Dedicated programming language enabling Semantic Web programmers to define functions on RDF terms, triples and graphs or SPARQL query results can facilitate the development and improve the reuse and maintenance of the code produced for Linked Data. We propose to extend SPARQL with LDScript, a script language that enables users to define extension functions. Its main characteristics are:

  1. Design on top of SPARQL Filter language
  2. Provide SPARQL queries
  3. Function definition
  4. Lambda expression
  5. Second order functions: funcall, apply, map, reduce
  6. Statements: let, for, if then else, return
  7. Pattern matching, recursion
  8. Entities: RDF term, list, triple, graph and SPARQL query solution(s)
  9. Type system: RDF term kind, XSD and extension datatype
  10. User defined extension datatype with operator definitions

In the future we wish to provide a second implementation on top of another Semantic Web Factory. We wish to provide a compiler to Java language and work on performance. We would like to design a type checker and investigate Linked Functions.

 

Bibliography

Olivier Corby, Catherine Faron-Zucker and Fabien Gandon, LDScript: a Linked Data Script Language, International Semantic Web Conference, ISWC, 2017 October, Vienna, Austria.

RDF 1.1 Concepts and Abstract Syntax, Graham Klyne, Jeremy J. Carroll, Brian McBride. W3C Recommendation, February 2014

SPARQL 1.1 Query Language, Steve Harris, Andy Seaborne. W3C Recommendation, March 2013