0

I am new in Sparql. I have a car ontology in OWL format. I am trying to write a query that takes names of two nodes from me and shows all the existing paths between them. For example in the following picture: example of my ontology's graph, if the input nodes are G and E, the path between them can be G c b e, G c a d b e, G c a thing b e, G h I e

I have used apache Jena to connect to my ontology from Eclipse. Now I need to write the query mentioned above. Is there any example that can help me to write the query?

Hoda
  • 1
  • 6
  • 1
    Has been asked here before, please use the search function first. – UninformedUser Jun 22 '16 at 14:17
  • "Is there any example that can help me to write the query?" Please note that "Questions asking us to recommend or find a book, tool, software library, tutorial or other off-site resource are off-topic for Stack Overflow as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it." Showing an attempt and asking how to fix it would be more productive. – Joshua Taylor Jun 22 '16 at 16:04
  • That said, as @AKSW mentioned, there are other questions with code that may help. I think you might find http://stackoverflow.com/q/30916040/, http://stackoverflow.com/q/19587520/, http://stackoverflow.com/q/18024413/, and http://stackoverflow.com/q/28900290/ helpful, among others. While you're looking at those, be sure to have a look at the questions listed in the "Linked" section on the right; there may be more helpful questions and answers listed there, too. – Joshua Taylor Jun 22 '16 at 16:07
  • Dear Joshoua Taylor, my reason to repeat this question is that non of the other similar questions's solution dont worked for me and in some of them people mentioned that Sparql queries are not able to answer this question. – Hoda Jun 23 '16 at 09:28
  • Then what is the solution? Is any other type of query that can answer my question? or is any implemented Jena source code to answer my question? – Hoda Jun 23 '16 at 09:29
  • @Hoda if those don't work, we really need to see some data that we can work with, as well as what you tried, or else we can't really help you – Joshua Taylor Jun 23 '16 at 12:06
  • Should the path G c f k i E be included too? – Joshua Taylor Jun 23 '16 at 12:21
  • yes this path is include as well (I forgot to add it) – Hoda Jun 23 '16 at 13:23
  • by data you mean a XML file of my ontology? – Hoda Jun 23 '16 at 13:25
  • or you need a OWL file? – Hoda Jun 23 '16 at 13:57

2 Answers2

0

This not a use case where SPARQL shines. Although SPARQL uses graphs as a metaphor, it is not really ideal for implementing classical graph algorithms.

In some cases, it may be easiest to implement things using multiple, iterative queries. In other cases, it may be easier to use SPARQL to construct a subgraph containing the relevant individuals and property assertions, then uses that as input to one of the usual algorithms.

Note that the problem of finding all paths between two nodes is NP-hard , so reducing the number of nodes that need to be considered is a good thing. You may want to instead look for the top k shortest paths - the results of the ESWC 2016 challenge on this topic are now available ; unfortunately the papers aren't currently self-archived or open access.

Depending on the implementation of the triple store, and the structure of the graph, it may be feasible to find all the triples involved in some path between a and b by looking for every c such that a owl:topObjectProperty+ ?c and ?c owl:topObjectProperty+ b. It is also possible that this kind of query may cause the server to melt, or your DBA to tie you to a chair and do evil things with UPS parts.

Some systems provide extensions that make implementing such algorithms easier- for example AllegroGraph has non-standard support for first class paths.

Community
  • 1
  • 1
Simon Spero
  • 86
  • 3
0

I think the best way to do that is to implement an algorithm for it! I don't think this task could be completed using SPARQL or some querying method. I have implemented the following algorithm in Java and Jena to find all the directed paths connecting a set of nodes in an OWL ontology. You can use your two required nodes as your input.

Given a graph G= (V, E) that is:

  1. directed,
  2. acyclic,
  3. non-weighted,
  4. may have more than one edge between two vertices (thus, source and destination are not enough to determine an edge).

And given a set of vertices, let's call them vSet; that contains a vertex vRoot; we need to find ALL paths pSet between vSet elements respecting the following:

  1. any vertex that appears as a source for some path in pSet must be reachable from vRoot.
  2. any path in pSet must has its source and destination from vSet, and must not contain any other vertex of vSet.

The following algorithm is similar to BFS, that starts from vRoot (according to 1 above), grow each of the current paths with one edge per an iteration until it reaches another vertex v1 of vSet; then store this reaching path and start growing new set of paths starting from v1.

Here is the pseudo code:

output = ∅;
maxLengthPaths = ∅;
1. add all edges that vRoot is there source to maxLengthPaths
2. while size(maxlengthpaths) != ∅ do
  (a) paths := ∅;
  (b) extendedPaths := ∅;
  (c) foreach path p in maxLengthPaths do
    i. if (destination of p in vSet)
      1. add p to output 
      2. for each edge e that destination of p is its source
        A. add e to extendedPaths
    ii. else
      1. add p to paths
    iii. for path p1 in paths 
      1. for each edge that destination of p1  is its source
        A. extend p1 by a edge and add it to extendedPaths
  (d) maxLengthPaths = extendedPaths
Median Hilal
  • 1,483
  • 9
  • 17