通过

SHORTEST_PATH （Transact-SQL）

  • 项目

适用于： sql Server 2019 （15.x） 及更高版本Azure SQL 数据库 Azure SQL 托管实例 Microsoft Fabric 中的 SQL 数据库

指定以递归或重复方式搜索的图形的搜索条件。 SHORTEST_PATH可以在 SELECT 语句中将 MATCH 与图形节点和边缘表配合使用。

Transact-SQL 语法约定

最短路径

SHORTEST_PATH函数使你可以找到：

  • 两个给定节点/实体之间的最短路径
  • 单个源最短路径。。
  • 从多个源节点到多个目标节点的最短路径。

它采用任意长度模式作为输入，并返回两个节点之间存在的最短路径。 此函数只能在 MATCH 内使用。 该函数仅返回任意两个给定节点之间的最短路径。 如果存在，则任何源节点和目标节点对之间长度相同的两个或多个最短路径，则函数仅返回遍历期间第一个找到的路径。 只能在SHORTEST_PATH函数内指定任意长度模式。

有关完整语法，请参阅 MATCH （SQL Graph）。

FOR PATH

FOR PATH 必须与 FROM 子句中的任何节点或边缘表名称一起使用，该子句参与任意长度模式。 FOR PATH 告知引擎节点或边缘表返回一个有序集合，该集合表示沿遍历路径的节点或边缘列表。 这些表中的属性不能直接投影到 SELECT 子句中。 若要从这些表投影属性，必须使用图形路径聚合函数。

任意长度模式

此模式包括必须重复遍历的节点和边缘，直到以下任一操作：

  • 达到所需的节点。
  • 满足模式中指定的最大迭代次数。

支持以下两种模式限定符：

  • “+”：重复模式 1 次或多次。 找到最短路径后立即终止。
  • {1,n}：重复模式 1到 n 次。 找到最短时间后立即终止。

LAST_NODE

LAST_NODE（） 函数允许链接两个任意长度遍历模式。 可在以下情况下使用：

  • 查询中使用了多个最短的路径模式，一个模式从上一模式的 LAST 节点开始。
  • 两种最短的路径模式在同一LAST_NODE（）合并。

图形路径顺序

图形路径顺序是指输出路径中的数据顺序。 输出路径顺序始终从模式的非递归部分开始，后跟递归部分中显示的节点/边缘。 在查询优化/执行期间遍历图形的顺序与输出中打印的顺序无关。 同样，递归模式中的箭头方向也不会影响图形路径顺序。

图形路径聚合函数

由于任意长度模式涉及的节点和边缘返回在该路径中遍历的集合（节点和边缘），因此用户无法使用传统的 tablename.attributename 语法直接投影属性。 对于需要从中间节点或边缘表投影属性值的查询，在遍历的路径中，使用以下图形路径聚合函数：STRING_AGG、LAST_VALUE、SUM、AVG、MIN、MAX 和 COUNT。 在 SELECT 子句中使用这些聚合函数的一般语法是：

<GRAPH_PATH_AGGREGATE_FUNCTION>(<expression> , <separator>)  <order_clause>

    <order_clause> ::=
        { WITHIN GROUP (GRAPH PATH) }

    <GRAPH_PATH_AGGREGATE_FUNCTION> ::=
          STRING_AGG
        | LAST_VALUE
        | SUM
        | COUNT
        | AVG
         | MIN
        | MAX

STRING_AGG

STRING_AGG函数采用表达式和分隔符作为输入并返回字符串。 用户可以在 SELECT 子句中使用此函数来投影路径中中间节点或边缘的属性。

LAST_VALUE

若要从遍历路径的最后一个节点投影属性，可以使用LAST_VALUE聚合函数。 提供边缘表别名作为此函数的输入是错误的，只能使用节点表名或别名。

最后一个节点：最后一个节点是指在遍历路径中最后显示的节点，而不考虑 MATCH 谓词中的箭头方向。 例如：MATCH(SHORTEST_PATH(n(-(e)->p)+) )。 路径中的最后一个节点是上次访问的 P 节点。

在模式中 MATCH(SHORTEST_PATH((n<-(e)-)+p)) ，最后一个节点是访问的最后一个 N 节点。

SUM

此函数返回在遍历路径中显示的提供的节点/边缘属性值或表达式的总和。

COUNT

此函数返回路径中指定节点/边缘属性的非 null 值数。 COUNT 函数不支持 * 运算符 - 尝试在 * 语法错误中使用结果。

{  COUNT( <expression> )  <order_clause>  }

AVG

返回在遍历路径中显示的提供的节点/边缘属性值或表达式的平均值。

MIN

从提供的节点/边缘属性值或表达式中返回在遍历路径中显示的最小值。

MAX

从提供的节点/边缘属性值或表达式中返回在遍历路径中显示的最大值。

注解

  • SHORTEST_PATH函数只能在 MATCH 内使用。
  • LAST_NODE函数仅在SHORTEST_PATH内受支持。
  • SHORTEST_PATH函数返回 节点之间的任意 最短路径。 它当前不支持返回 节点之间的所有最短路径 ;也不支持返回 节点之间的所有路径 。
  • SHORTEST_PATH实现找到一条不加权的最短路径。
  • 在某些情况下，可能会为具有较高跃点数的查询生成错误的计划，从而导致查询执行时间较高。 评估查询提示（如 OPTION（HASH JOIN）和/或 OPTION（MAXDOP 1）是否有帮助。

示例

对于此处显示的示例查询，我们使用在 SQL Graph 示例中创建的节点表和边缘表

A. 查找两个人之间的最短路径

在以下示例中，我们发现雅各布和 Alice 之间的最短路径。 我们需要Person从 SQL Graph 示例创建的节点和friendOf边缘。

SELECT PersonName, Friends
FROM (
    SELECT
        Person1.name AS PersonName,
        STRING_AGG(Person2.name, '->') WITHIN GROUP (GRAPH PATH) AS Friends,
        LAST_VALUE(Person2.name) WITHIN GROUP (GRAPH PATH) AS LastNode
    FROM
        Person AS Person1,
        friendOf FOR PATH AS fo,
        Person FOR PATH  AS Person2
    WHERE MATCH(SHORTEST_PATH(Person1(-(fo)->Person2)+))
    AND Person1.name = 'Jacob'
) AS Q
WHERE Q.LastNode = 'Alice'

B. 查找从给定节点到图中所有其他节点的最短路径。

以下示例查找雅各布在图中连接到的所有人员，以及从雅各布到所有这些人的最短路径。

SELECT
    Person1.name AS PersonName,
    STRING_AGG(Person2.name, '->') WITHIN GROUP (GRAPH PATH) AS Friends
FROM
    Person AS Person1,
    friendOf FOR PATH AS fo,
    Person FOR PATH  AS Person2
WHERE MATCH(SHORTEST_PATH(Person1(-(fo)->Person2)+))
AND Person1.name = 'Jacob'

°C 计算从图中的一个人到另一个人遍历的跃点/级别数。

以下示例查找雅各布和 Alice 之间的最短路径，并打印从雅各布到 Alice 所花费的跃点数。

 SELECT PersonName, Friends, levels
FROM (
    SELECT
        Person1.name AS PersonName,
        STRING_AGG(Person2.name, '->') WITHIN GROUP (GRAPH PATH) AS Friends,
        LAST_VALUE(Person2.name) WITHIN GROUP (GRAPH PATH) AS LastNode,
        COUNT(Person2.name) WITHIN GROUP (GRAPH PATH) AS levels
    FROM
        Person AS Person1,
        friendOf FOR PATH AS fo,
        Person FOR PATH  AS Person2
    WHERE MATCH(SHORTEST_PATH(Person1(-(fo)->Person2)+))
    AND Person1.name = 'Jacob'
) AS Q
WHERE Q.LastNode = 'Alice'

D. 从给定的人中查找 1-3 跃点

下面的示例找到雅各布和雅各布与图中与他相连接的最短路径，即一到三个跃点。

SELECT
    Person1.name AS PersonName,
    STRING_AGG(Person2.name, '->') WITHIN GROUP (GRAPH PATH) AS Friends
FROM
    Person AS Person1,
    friendOf FOR PATH AS fo,
    Person FOR PATH  AS Person2
WHERE MATCH(SHORTEST_PATH(Person1(-(fo)->Person2){1,3}))
AND Person1.name = 'Jacob'

E. 找到离给定人只有两个跃点的人

以下示例在图中找到雅各布和离他两个跃点的人之间的最短路径。

SELECT PersonName, Friends
FROM (
    SELECT
        Person1.name AS PersonName,
        STRING_AGG(Person2.name, '->') WITHIN GROUP (GRAPH PATH) AS Friends,
        COUNT(Person2.name) WITHIN GROUP (GRAPH PATH) AS levels
    FROM
        Person AS Person1,
        friendOf FOR PATH AS fo,
        Person FOR PATH  AS Person2
    WHERE MATCH(SHORTEST_PATH(Person1(-(fo)->Person2){1,3}))
    AND Person1.name = 'Jacob'
) Q
WHERE Q.levels = 2

F. 找到 1-3 跃点远离给定的人， 谁也喜欢特定的餐厅

以下示例找到雅各布和他与图 1-3 跃点相联系的所有人之间的最短路径。 该查询还通过喜欢给定餐厅来筛选连接人员。 在下面的示例中，返回 LAST_NODE(Person2) 每个最短路径的最终节点。 然后，从LAST_NODE中获取的“最后一个”Person节点可以“链接”，以便进一步遍历找到他们喜欢的餐馆。

SELECT
    Person1.name AS PersonName,
    STRING_AGG(Person2.name, '->') WITHIN GROUP (GRAPH PATH) AS Friends,
    Restaurant.name
FROM
    Person AS Person1,
    friendOf FOR PATH AS fo,
    Person FOR PATH  AS Person2,
    likes,
    Restaurant
WHERE MATCH(SHORTEST_PATH(Person1(-(fo)->Person2){1,3}) AND LAST_NODE(Person2)-(likes)->Restaurant )
AND Person1.name = 'Jacob'
AND Restaurant.name = 'Ginger and Spice'

G. 查找从给定节点到图中所有其他节点的最短路径，不包括“循环”

以下示例查找 Alice 在关系图中连接到的所有人员，以及从 Alice 到所有这些人的最短路径。 该示例显式检查路径的起始节点和结束节点是否相同。

SELECT PersonName, Friends
FROM (
    SELECT
        Person1.name AS PersonName,
        STRING_AGG(Person2.name, '->') WITHIN GROUP (GRAPH PATH) AS Friends,
        LAST_VALUE(Person2.name) WITHIN GROUP (GRAPH PATH) AS LastNode
    FROM
        Person AS Person1,
        friendOf FOR PATH AS fo,
        Person FOR PATH  AS Person2
    WHERE MATCH(SHORTEST_PATH(Person1(-(fo)->Person2)+))
    AND Person1.name = 'Alice'
) AS Q
WHERE Q.LastNode != 'Alice'

后续步骤