选择依赖树上的连接顶点并按深度排序 (SPARQL)

Question

我正在为 RDF 使用 SPARQL，但在想出一个查询时遇到了问题，该查询将允许我 select 树上的一组顶点，并将所有连接（直接和传递）的顶点连接到那些 selected 被 returned，并且按照它们在依赖树上存在的深度顺序（最深的顶点在前）。

这是我正在处理的图（树）的可视化表示，其中包含 RDF 类型的节点 :dependency。在这棵树中，依赖项具有到它们所需的每个依赖项的传出边，这在图中使用 :requires 边表示。

这是创建此图表的数据：

INSERT DATA {
   :A             rdf:type   :dependency .
   :B             rdf:type   :dependency .
   :C             rdf:type   :dependency .
   :D             rdf:type   :dependency .
   :E             rdf:type   :dependency .
   :F             rdf:type   :dependency .
   :G             rdf:type   :dependency .
   :H             rdf:type   :dependency .
   :I             rdf:type   :dependency .
   :J             rdf:type   :dependency .
   :K             rdf:type   :dependency .

   :A             :requires  :B .
   :A             :requires  :C .
   :A             :requires  :I .
   :B             :requires  :J .
   :B             :requires  :E .
   :C             :requires  :D .
   :E             :requires  :F .
   :E             :requires  :G .
   :D             :requires  :G . 
   :H             :requires  :I .     
   :H             :requires  :K .
}

我想形成一个查询，允许我 select 一组依赖项，并且 return 该 selection 的所有依赖项按顺序排列，其中最低的:required 依赖项首先 returned，这样如果“依赖项 X”: 需要“依赖项 Y”，则依赖项 X 必须在结果中在依赖项 Y 之后设置。

本质上想问图：

"给我这组顶点需要的所有顶点，并按顺序return它们使得最低级别的依赖在结果集上优先

例如，在上图中指定这个select离子的情况下：[B, H]

一个有效的结果集应该是： [G, F, E, J, B, I, K, H]

（因为G和F是B的最低依赖，其次是E，J等等……）

以下结果集也将被视为有效： [J, F, G, E, B, I, K, H]

因为 J 是在 F、G 和 H 之前还是之后 return 并不重要，因为它不依赖于在它们上面（重要的是它在 B 之前 returned，因为 B 需要所有这些）

到目前为止，我已尝试对 selection [B, H] 进行此查询，它能够 return B 和 H 的所有必需依赖项]，但它们并未 return 按照最低依赖优先级的顺序排列。

SELECT ?requires {
    ?dependency a :dependency .
    FILTER (?dependency IN (:B, :H))
    ?dependency :requires+ ?requires .
}

其中 return 结果集的顺序不正确： [E, F, G, J, I, K]

任何人都知道我如何构建一个本质上对顶点执行深度优先搜索排序的查询？

Answer 1

感谢@UninformedUser 分享的this answer，我可以获得与我正在寻找的内容足够接近的结果集。基本上我们可以使用属性路径来确定所有 :requires 位于一组指定顶点下方的边，同时保留一个计数器，该计数器将 return 每个边的深度：

如果我们想确定这个选择的顺序 [B, H]，那么我们可以使用这个查询，它是上面答案中查询的一个稍微修改的版本，允许选择开头顶点而不是从顶部选择所有路径：

select ?begin ?midI ?midJ (count(?counter) as ?position) ?end where {
  ?begin a :dependency .
  FILTER (?begin IN (:B, :H))
  ?begin :requires* ?counter .
  ?counter :requires* ?midI .

  ?midI :requires ?midJ .

  ?midJ :requires* ?end .
  FILTER NOT EXISTS { ?end :requires [] }
}
group by ?begin ?end ?midI ?midJ 
order by DESC(?position) ?begin ?end

这 return 是以下结果集：

----------------------------------------
| begin | midI | midJ | position | end |
========================================
| :B    | :E   | :F   | 2        | :F  |
| :B    | :E   | :G   | 2        | :G  |
| :B    | :B   | :E   | 1        | :F  |
| :B    | :B   | :E   | 1        | :G  |
| :B    | :B   | :J   | 1        | :J  |
| :H    | :H   | :I   | 1        | :I  |
| :H    | :H   | :K   | 1        | :K  |
----------------------------------------

这足以让我在客户端使用代码执行剩余的排序，其中对于 begin 列中的每个唯一值，收集 midJ 的所有值（开始从上到下），直到所有相同 begin 值的行都用完，然后最后将值包含在 begin 列中。对上述结果集执行此操作时，我们得到了有效答案： [F, G, E, B, J, I, K, H]

选择依赖树上的连接顶点并按深度排序 (SPARQL)

Selecting connected vertices on a dependency tree and ordering them by depth (SPARQL)

sparql

rdf

amazon-neptune