Maximal matching of tree in SPARQL

[Aidan Delaney <ai...@phoric.eu>]

Dear all,
Using SPARQL 1.1 it is straightforward to do a path query to match a long chain
in a graph, for example:

?leaf  (rdfs:subClassOf)+ ?root

In my case I'm trying to match trees within an RDF graph.  The internal nodes of
the trees are either unary or binary.  This could be described by the (nearly) BNF
grammar

root ::= root bOp root | uOp root | leaf
leaf ::= (?leaf rdf:type my:leaf) 

where bOp stands for a binary operation and uOp for a unary operation.  In
practice, bOp would be
:bOp rdf:type    rdf:Property
:bOp rdfs:domain rdfs:Class .
:bOp rdfs:range  rdf:List .
and the rdf:List contains only two items.

Is it possible to formulate a SPARQL query to match this kind of recursive
structure?  If, as I suspect, it is not possible, what stratgy is commonly used
when trying to find such recursive structures in an RDF graph?

-- 
Dr Aidan Delaney

web     : http://www.phoric.eu/aidan
twitter : @aidandelaney

Re: Maximal matching of tree in SPARQL

[Joshua TAYLOR <jo...@gmail.com>]

On Thu, Dec 12, 2013 at 5:55 AM, Aidan Delaney <ai...@phoric.eu> wrote:
> ?leaf  (rdfs:subClassOf)+ ?root
>
> In my case I'm trying to match trees within an RDF graph.  The internal nodes of
> the trees are either unary or binary.  This could be described by the (nearly) BNF
> grammar
>
> root ::= root bOp root | uOp root | leaf
> leaf ::= (?leaf rdf:type my:leaf)

Since your query variable is ?leaf, I assume you don't want the
intermediate nodes.  If you have data like this:

@prefix : <http://example.org/> .

#       a
#      / \
#     /   \
#    b     c
#   / \
#  d   e

:b :sub :a .
:c :sub :a .
:d :sub :b .
:e :sub :b .

then you can use a query like this:

prefix : <http://example.org/>

select ?leaf where {
  ?leaf :sub* :a .
  filter not exists { ?subLeaf :sub ?leaf }
}

to get results like this:

--------
| leaf |
========
| :c   |
| :e   |
| :d   |
--------





-- 
Joshua Taylor, http://www.cs.rpi.edu/~tayloj/