使用 SPARQL 查询查找最短路径 [英] Finding shortest path with SPARQL query

问题描述

我正在尝试了解 SPARQL 查询的计算限制，并且我想知道如何编写一个查询来确定两个对象之间是否存在有向路径.

I am trying to understand the computational limitations of the SPARQL query, and I would like know how to write a query that will determine if there is a directed path between two objects.

我知道一种针对特定长度的路径执行此操作的方法:

I know a way to do it for a path of a specific length:

SELECT ?a ?b ?c ?d
WHERE { ?a  <http://graphtheory/hasNeighbor>  ?b . 
        ?b  <http://graphtheory/hasNeighbor>  ?c .
        ?c  <http://graphtheory/hasNeighbor>  ?d .
        FILTER (?a != ?c && ?b != ?d
                && ?a = <http://graphtheory/node/1>
                && ?d = <http://graphtheory/node/2>)
      }
LIMIT 10

有没有办法在单个查询中搜索任意长度的路径?这对 SPARQL 来说是不可能的吗?

Is there a way to search for any length path in a single query? Is this impossible with SPARQL?

推荐答案

AndyS 提供了所有元素来回答这个问题，但有一些拼写错误可能会使它们难以应用.正如他所说:

AndyS gave all the elements to answer this question, but there are some typos that might make it hard to apply them. As he says:

SPARQL 1.1 具有属性路径，其中包含任意数量的 * 运算符.

SPARQL 1.1 has property path which includes the * operator for any number of.

它不会告诉你路径是什么，也不会告诉你最短路径的长度——只告诉你是否有这样的路径.

It does not tell you what the path is nor the length of the shortest path - only whether there is such a path.

这样做的方法(基于 AndyS，但有两个小问题)是:

The way to do this (based on AndyS, but with two little fixes) is:

PREFIX : <http://graphtheory/>
PREFIX node: <http://graphtheory/node/>

ASK { node:1 :hasNeighbor* node:2 }

据我所知，不使用属性路径就无法做到这一点.

As far as I can tell, there is no way to do this without using property paths.

这篇关于使用 SPARQL 查询查找最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！