Corese News Corese

Graph Path in SPARQL

Olivier Corby, INRIA, March 2008.
See also: Corese Demo on insee RDF base.

A path expression enables to find a path of length greater than one between two resources by means of linked properties. Our syntactic convention consists in writing a variable prefixed by $ in property position to use path match.

select * where {
  ?x $path ?y
  filter(?x = c:Charybde && ?y = c:Scylla)
}

It is possible to specify the greatest type of the properties involved in the path.

select * where {
  ?x c:step::$path ?y
  filter(?x = c:Charybde && ?y = c:Scylla)
}

Can restrict path to direct edges.

select * where {
  ?x direct::c:step::$path ?y
  filter(?x = c:Charybde && ?y = c:Scylla)
}

Regular expression

It is possible that the list of properties of the path match a regular expression.

select * where {
  ?x $path ?y
  filter(?x = c:Charybde && ?y = c:Scylla)
  filter(match($path, star(c:back | c:forth)))
}

Reg exp syntax

Reg exp must be written directly in functional abstract syntax:

EXP ::= 
QNAME      |
(EXP)      |
star(EXP)  |  
plus(EXP   |  
opt(EXP)   |  
EXP && EXP |  
EXP || EXP |  
! EXP

QNAME is the QNAME of a property. The negation operator (!) only makes sense with QNAME or with an OR on QNAMES, e.g. !(p1 || p2). Matching any property can be done using the meta property cos:Property.

Options

It is possible to parameterize the graph path search algorithm by means of options.

match($path, regex, option)

option ::=  
'd'  depth first
'b'  breadth first
's'  shortest path (eliminate new path with length greater (or equal)
     than already known path) 
'a'  keep all path of given length between two resources (when 'ds')
'p'  property only (no subproperties, default is with subproperties)
'i'  consider properties also with arguments in reverse order 
     (aka inverse of itself)

Path Length

By default, Corese considers path with length at most 5. This can be changed using the pathLength function.

filter(pathLength($path) >= 2 && pathLength($path) <= 4)

Enumerate Path Relations

Using a graph pattern on a path variable, it is possible to enumerate the triples of the path. In the example below, the triples ?a ?r ?b are the triples that link ?x and ?y in the path.

?x $path ?y
graph $path {?a ?r ?b}

Check constraints

Hence, it is possible to check constraints on the path such as: Verify that the path matches a specific pattern:

graph $path {?a p ?b . ?b q ?c . ?b rdf:type c:BlackHole}

Verify that the path goes through a specific resource:

graph $path {?a ?p c:Roma}

Verify that all resources of the path match a constraint:

optional {
  graph $path {
    ?a ?p ?b 
    filter(! my:constraint(?b))
  }
}
filter(! bound(?b))

Recursive graph pattern

Paths are computed between first and second arguments of relations: (a, b, c, d).

a R b . b R c . c R d

However, it is possible to consider generalized paths that are computed between graph name and first argument: (g1, g2, g4, g6).

g1 { g2 R g3 } . g2 { g4 R g5 } . g4 { g6 R g7 }

Generalized paths implement walking through nested named graphs by means of contextual relations: g2 and g3 are linked within g1, g4 and g5 are linked within g2. Hence we can say that g4 and g5 are linked recursively within g1. We have designed an extension of SPARQL to query recursively nested named graph using generalized paths:

rec graph g1 { ?x R ?y }

The answer to the query above is the relations that are linked recursively within g1.
In the example above we consider the generalized path from graph name to first argument only. We may want to consider generalized paths from graph name to first and/or second argument. In this case, we use the 'i' argument of the match function for regular expressions that apply to the properties:

rec graph g1 { ?x ?p ?y . filter(match(?p, star(R), 'i')) }

References

Faisal Alkhateeb and Jean-François Baget and Jérôme Euzenat RDF with Regular Expressions INRIA RR-6191, http://hal.inria.fr/inria-00144922/en

Olivier Corby, Web, Graphs & Semantics, Proc. of the 16th International Conference on Conceptual Structures (ICCS'2008), July 2008 Toulouse.

Krys J. Kochut and Maciej Janik, SPARQLeR: Extended SPARQL for Semantic Association Discovery Proc. European Semantic Web Conference, ESWC'2007 Innsbruck, Austria 2007