Get all nodes in a transitive relation

Question

Is it somehow possible to get the list of nodes connected through a transitive relation with SPARQL? I have elements that are connected in this way:

?a g:eastOf ?b
?b g:eastOf ?c
…

Not all nodes are connected with each other, because some are further down south. Only when nodes are vertically in the same plane there might be a g:eastOf relationship. This means there are several groups of nodes that are not connected with each other.

I'd like to get all these groups of nodes (basically a list of lists). Is there a way to do that in SPARQL? The SELECT statement requires a finite number of variables and can't somehow express "a list of" something.

I'm only interested in the lists where an xsd:integer property of all nodes is ascending when going from west to east, but that should be relatively easy after I have the solution for my first problem.

Answer 1

You can do at least some of this with SPARQL 1.1.

Getting a list of nodes

Assume you have the data in which there are two groups of points that form a row based on :eastOf:

@prefix : <http://stackoverflow.com/q/4056008/1281433/>

:a :eastOf :b .
:b :eastOf :c .
:c :eastOf :d .

:e :eastOf :f .
:f :eastOf :g .
:g :eastOf :h .

Then you can use query like this:

prefix : <http://stackoverflow.com/q/4056008/1281433/>

select (group_concat(strafter(str(?westernpoint),str(:));separator=", ") as ?colatitudinalPoints)
 where {
  ?easternmost :eastOf* ?westernpoint .
  filter not exists { ?easternmoster :eastOf ?easternmost }
}
group by ?easternmost

to get these results:

-----------------------
| colatitudinalPoints |
=======================
| "e, f, g, h"        |
| "a, b, c, d"        |
-----------------------

There's some string processing in

group_concat(strafter(str(?westernpoint),str(:));separator=", ") as ?colatitudinalPoints

that you might not need; the point is that ?westernpoint is the IRI of the points west of the east of the ?easternmost (which actually includes ?easternmost, since we used * in the property path), and then we need to concatenate those together somehow. Here I did some string processing to make the results prettier. You can just as easily do

prefix : <http://stackoverflow.com/q/4056008/1281433/>

select (group_concat(?westernpoint;separator=", ") as ?colatitudinalPoints)
 where {
  ?easternmost :eastOf* ?westernpoint .
  filter not exists { ?easternmoster :eastOf ?easternmost }
}
group by ?easternmost

and get

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
| colatitudinalPoints                                                                                                                                                                      |
============================================================================================================================================================================================
| "http://stackoverflow.com/q/4056008/1281433/e, http://stackoverflow.com/q/4056008/1281433/f, http://stackoverflow.com/q/4056008/1281433/g, http://stackoverflow.com/q/4056008/1281433/h" |
| "http://stackoverflow.com/q/4056008/1281433/a, http://stackoverflow.com/q/4056008/1281433/b, http://stackoverflow.com/q/4056008/1281433/c, http://stackoverflow.com/q/4056008/1281433/d" |
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Ensuring that the nodes are ascending

Your other requirement is a bit more of a challenge:

I'm only interested in the lists where an xsd:integer property of all nodes is ascending when going from west to east, but that should be relatively easy after I have the solution for my first problem.

That said, if you can clarify exactly what you want in the case of something like

w --eastof-> x --eastof-> y --eastof-> z
|            |            |            |
5            6            2            3

E.g., do you want to reject the whole chain because the nodes aren't all ascending, or do you want to get the two subchains w x and y z wherein the values are ascending? It might be possible to do both…

Answer 2

As far as I know, you can't get a variable list of elements as an SPARQL solution. I think the easiest way to do what you need is just to get the pairs (a,b) from ?a g:eastOf ?b and sort them.

SELECT ?a ?b WHERE {
?a g:eastOf ?b
} ORDER BY ASC(?a) ASC(?b)

It should be pretty straight forward to put some logic in place to convert the list of tuples on a list of elements.

If you use reasoning with transitivity you won't be able to trace back what's the path that connects A with C. In case you have something like (A,g:eastOf,B) and (B,g:eastOf,C). Basically in this case using reasoning will make the things more complicated because you want to construct the full list of connected elements. Transitivity in SPARQL will give you the start and end node but you'll loose traceability of all the intermediate points.

If you don't have millions of statements I think that the above SPARQL query plus some logic to transform the resultset will do the job.

Edited to give pointers to Jena + owl:TransitiveProperty

So first make sure that you load an ontology with the following axiom into your Jena Model:

g:eastOf rdf:type owl:TransitiveProperty .

Then enable the Jena OWL reasoner see documentation here : Jena OWL coverage

And connect Jena ARQ to your model so to be able to launch SPARQL queries.

Once you've done that ... if you had something like ...

:x g:eastOf :y .
:y g:eastOf :t .
:t g:eastOf :z .

and you run a query like ...

SELECT ?a ?b WHERE {
?a g:eastOf ?b
} ORDER BY ASC(?a) ASC(?b)

you'll get ...

:x g:eastOf :y .
:x g:eastOf :t .
:x g:eastOf :z .
:y g:eastOf :t .
:y g:eastOf :z .
(...)

Also with Jena consider to use Property Paths. It'll do the job as well.

Let us know if its works or if you run into any issues, cheers !!!