使用SPARQL查询查找最短路径

Question

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

我知道一种特定长度路径的方法：

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中是否不可能？

- Abraham D Flaxman

---

你好！我正在寻找类似的解决方案，以确定两个节点之间的最短路径长度。你能找到任何解决方案吗？甚至可以使用广度优先或深度优先搜索算法吗？ - Niveditha Karmegam

Answer 1

AndyS提供了回答这个问题的所有元素，但是其中有些拼写错误可能会使它们难以应用。正如他所说：

SPARQL 1.1具有属性路径，其中包括*运算符表示任意数量。

它不告诉您路径是什么，也不告诉最短路径的长度 - 只告诉是否存在此类路径。

按照AndyS的方法（但进行了两个小修复），可以这样做：

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

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

据我所知，没有不使用属性路径的方法来实现这一点。

- Abraham D Flaxman

Answer 2

SPARQL 1.1有属性路径，其中包括“任意数量”的*运算符。

它不会告诉您路径是什么，也不会告诉您最短路径的长度 - 只会告诉您是否存在这样的路径。

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

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

你不需要?a=和?d=，你可以将值写入查询中。

为语言添加path数据类型是未来的工作方向——一些实验性系统已经开始研究这个问题。

- AndyS

---

谢谢，这大大简化了我之前的方法。你的解决方案中有一个小问题：PREFIX节点应该是http://graphtheory/node/（我认为）。一旦进行了此更改，您的查询将返回true，如果节点1和2之间存在边，则返回false，但如果存在路径而不是边，则返回false。 - Abraham D Flaxman

为了使查询在存在路径但不存在边缘时返回true，我在:hasNeighbor的末尾添加了运算符，即"ASK { node:1 :hasNeighbor node:2 }"。是否可以在没有属性路径的情况下完成这个操作？ - Abraham D Flaxman