rdf - 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…