SHORTEST_PATH (Transact-SQL)

项目
06/29/2023

适用于：SQL Server 2019 (15.x) 及更高版本Azure SQL数据库 Azure SQL 托管实例

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

最短路径

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_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. 查找两个人之间的最短路径

在以下示例中，我们找到了 Jacob 和 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. 在图中查找从给定节点到所有其他节点的最短路径。

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

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. 计算在图中从一个人到另一个人所遍历的跃点/级别数。

以下示例查找 Jacob 和 Alice 之间的最短路径，并打印从 Jacob 到 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 个跃点的人

以下示例在图中查找 Jacob 与所有与他相距一到三个跃点的人之间的最短路径。

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. 查找离给定人员只有两个跃点的人

以下示例在图中查找 Jacob 和离他只有两个跃点的人之间的最短路径。

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 个跃点的图中查找 Jacob 与他联系的所有人员之间的最短路径。该查询还根据用户对给定餐厅的喜好来筛选已连接的人员。在下面的示例中，返回 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'