SPARQL which is the path connecting two objects?

Question

Hi all I'd like to discover if there is a relation between two nodes and if any the predicates connecting them. Let's say my graph is like following

                    [Uri1]
                 /          \
          (pred:a)          (pred:b)    
         /      \           /       \
    [Uri2]      [Uri3]  [Uri4]      [Uri5]
    /     \ 
(pred:c) (pred:d)  
  /             \
[Uri6]         [Uri7]
                  \
                  (pred:a)
                     \
                     [Uri8]

If the query is looking for the relations between Uri8 and Uri1, the expected result should be

[Uri7] = pred:a

[Uri2] = pred:d

[Uri1] = pred:a

Consider that predicates (relations) between nodes may vary and also lengths.

the two following: SPARQL: is there any path between two nodes? and Is it possible to return relationships between two objects in SPARQL? do not work

I don't think this is possible with SPARQL. It's not designed for such kind of graph traversal things. You could get the intermediate nodes by using property paths, but in that case you'll loose the predicates. The only way I think would work is to incrementally send queries with more hops between both resources. Otherwise you need to load the data into some graph database and use it's query language. — UninformedUser, Feb 15 '16 at 16:08
@AKSW This is definitely possible with SPARQL, and I've added [an answer](http://stackoverflow.com/a/35416197/1281433). The trick is to use two wildcard paths: one for the first portion of the path, and one for the last portion of the path, and then to get the values from the triple that joins them. — Joshua Taylor, Feb 15 '16 at 18:10
@RobMor The first question that you linked to has, in the comments, a link to [Finding all steps in property path](http://stackoverflow.com/q/18024413/1281433), which is very similar to this. The accepted answer says it's not possible, but [my answer](http://stackoverflow.com/a/18032019/1281433) actually shows that you can do it. — Joshua Taylor, Feb 15 '16 at 18:16
@Joshua Taylor Thanks, nice solution.See some comments below your answer. — UninformedUser, Feb 16 '16 at 01:18

score 3 · Answer 1 · edited May 23 '17 at 12:32

3

The approaches in those questions do work, although the explanations in Is it possible to get the position of an element in an RDF Collection in SPARQL? and Finding all steps in property path might help even more in understanding the solution. Here's some data to test with, if I've understood your example correctly:

@prefix : <urn:ex:>

:uri1 :a :uri2, :uri3 ;
      :b :uri4, :uri5 .

:uri2 :c :uri6 ;
      :d :uri7 .

:uri7 :a :uri8 .

Here's the query. The idea is to follow a wildcard path from the beginning (:uri1) to some point ?x. Then we take a link from ?x to its object ?o, and then find a wildcard path from ?o to the ?end (:uri8). (Note that I'm using (:|!:) as a property wildcard; it matches everything since every IRI is either : or not :.)

prefix : <urn:ex:>

select ?x ?p where {
  :uri1 (:|!:)* ?x .
  ?x ?p ?o .
  ?o (:|!:)* :uri8 .
}

The results are just like what you asked for:

--------------
| x     | p  |
==============
| :uri1 | :a |
| :uri2 | :d |
| :uri7 | :a |
--------------

edited May 23 '17 at 12:32

Community

1
1

answered Feb 15 '16 at 18:09

Joshua Taylor

84,998
9
154
353

Thanks, nice solution. I have three questions according to your solution, that maybe also the user should keep in mind. 1) scalability - do you think this will be performant enough especially compared to optimized graph databases? I cannot imagine that although I do not know how the evaluation of property paths is usually implemented. 2) the ordering of the nodes in the path is not given in your solution, right? I know that this can be extended if you sort by number of intermediate nodes. 3) What happens if there are cycles in the graph? – UninformedUser Feb 16 '16 at 01:19
@AKSW In the first question I linked to in this answer, there's some timing information in [my answer](http://stackoverflow.com/a/17530689/1281433). If the data store supports some native queries for this kind of structure, they're likely to be more performant. In this answer, the ordering isn't given, but as you say, it could be added, and I think that that's where the biggest time issue would be. By all means, if an endpoint has some kind of optimized support for this, it will probably be better. – Joshua Taylor Feb 16 '16 at 13:04
You have a bunch of semicolons in strange places. Why do you have semicolons after your URIs? – Joshua Taylor Feb 16 '16 at 13:48
@Joshua Taylor it throws an error: org.openrdf.query.algebra.ValueConstant cannot be cast to org.openrdf.query.algebra.Var My query is `code` select ?x ?p where { (skos:broader|!skos:broader)* ?x . ?x ?p ?o . ?o (skos:broader|!skos:broader)* . } `code` – RobMor Feb 16 '16 at 13:51
@Joshua Taylor there are no ; in my query, it's the editor that adds them – RobMor Feb 16 '16 at 13:54
@RobMor Why do you have a semicolon between the `` and `(skos:broader||!skos:broader)*`? And **please** use backticks for code in comments. Otherwise it's virtually unreadable. (And even with backticks, it's very hard to read code in comments.) – Joshua Taylor Feb 16 '16 at 13:56
1

@RobMor I see that you posted your code as a separate answer. Please don't post more question as an answer. Use the **edit** link under your question to add the addition information to your question. Does your query also have the `prefix skos: <...>` at the top to declare that prefix? But just showing us one little bit of the error message doesn't really help. You need to show the whole error message. – Joshua Taylor Feb 16 '16 at 14:24
@Joshua Taylor Sorry I had to insert it as a new post, as you see the "add a comment" box doesn't output the code as expected. Yes the prefix is correctly listed in my declaration. **PREFIX skos:** The only error that the endpoint prints out is: **"org.openrdf.query.algebra.ValueConstant cannot be cast to org.openrdf.query.algebra.Var"** – RobMor Feb 16 '16 at 14:37
@RobMor **What endpoint?** You haven't said anything about where you're sending this. Does it support SPARQL 1.1? And **please** use code formatting in the comments. Just put the code within backticks (``) to get results like `var x = 42`. – Joshua Taylor Feb 16 '16 at 14:40
1

@RobMor Immediately underneath yoru question, there should be a list of links: "share edit close delete flag protect" (you might not have all of those). Use the **edit** link to edit more information into your question if there are additional questions about it. This answer shows a complete working example, and it sounds like you're encountering a different problem. – Joshua Taylor Feb 16 '16 at 14:42
@Joshua Taylor Ok I got it! the Endpoint is: http://digitale.bncf.firenze.sbn.it/openrdf-workbench/repositories/NS/query – RobMor Feb 16 '16 at 14:43
@RobMor It looks like your endpoint doesn't support SPARQL 1.1. You'd need to check to be sure though. Property paths were introduced with version 1.1 of the SPARQL language. – Joshua Taylor Feb 16 '16 at 14:47
@Joshua Taylor another query like following works fine : `SELECT * { skos:broader/skos:related* ?t }` – RobMor Feb 16 '16 at 14:57
1

OpenRDF Workbench Version 2.7.14. You could/should ask the Sesame developers, but anyways, if you're not the admin of this triple store, there is nothing you could do so far. In that case you would have to load the data – if available – into your own triple store. – UninformedUser Feb 16 '16 at 18:15
@JoshuaTaylor Admin confirms that supports 1.1. The query you proposed arises the error, as mentioned before, only if in the second operand of the third expression `?o (:|!:)* :uri8` you insert the negation. Either using star or not. If executed as: `?o (:)* :uri8` returns too many results – RobMor Feb 17 '16 at 08:45
@RobMor ?o (:)* :uri8 probably shouldn't return any results except for ?o = :uri8 since it's unlikely that you're using : as a property in your data. But either way, it still sounds like a endpoint bug (since I showed a working query) or maybe the data doesn't meet the prerequisites (i.e., a unique path from uri1 to uri8). – Joshua Taylor Feb 17 '16 at 12:02
@JoshuaTaylor Yes the fact is that there could be more paths connecting URIs. When using wildcards, as you suggested, the output is too verbose – RobMor Feb 18 '16 at 07:26
@RobMor Without seeing some of your actual data, I don't know if there's much more we can do. I don't know what "too verbose" means in this context; either the results in the query are correct or not. For the data you showed in your question, this solution works. If you want to filter out some results from your actual data, you'll need to show us more realistic data, and the extra results that you get. – Joshua Taylor Feb 18 '16 at 12:23

SPARQL which is the path connecting two objects?

1 Answers1

Linked