SHORTEST_PATH (Transact-sql) SHORTEST_PATH (Transact-SQL)

适用于:Applies to:是SQL Server 2017 (14.x)SQL Server 2017 (14.x)yesSQL Server 2017 (14.x)SQL Server 2017 (14.x)及更高版本 是Azure SQL 数据库Azure SQL DatabaseYesAzure SQL 数据库Azure SQL Database是Azure SQL 托管实例Azure SQL Managed InstanceYesAzure SQL 托管实例Azure SQL Managed Instance适用于:Applies to: 是SQL Server 2017 (14.x)SQL Server 2017 (14.x)yesSQL Server 2017 (14.x)SQL Server 2017 (14.x) and later 是Azure SQL 数据库Azure SQL DatabaseYesAzure SQL 数据库Azure SQL Database 是Azure SQL 托管实例Azure SQL Managed InstanceYesAzure SQL 托管实例Azure SQL Managed Instance

指定关系图的搜索条件,该搜索条件是以递归方式或重复方式搜索的。Specifies a search condition for a graph, which is searched recursively or repetitively. 可以在 SELECT 语句中与 graph 节点和边缘表匹配中使用 SHORTEST_PATH。SHORTEST_PATH can be used inside MATCH with graph node and edge tables, in the SELECT statement.

主题链接图标 Transact-SQL 语法约定Topic link icon Transact-SQL Syntax Conventions

最短路径Shortest Path

SHORTEST_PATH 函数允许你查找:The SHORTEST_PATH function lets you find:

  • 两个给定节点/实体之间的最短路径A shortest path between two given nodes/entities
  • ) (单个源最短路径。Single source shortest path(s).
  • 从多个源节点到多个目标节点的最短路径。Shortest path from multiple source nodes to multiple target nodes.

它采用任意长度的模式作为输入,并返回两个节点之间存在的最短路径。It takes an arbitrary length pattern as input and returns a shortest path that exists between two nodes. 此函数只能在 MATCH 内使用。This function can only be used inside MATCH. 函数在任意两个给定节点之间仅返回一个最短路径。The function returns only one shortest path between any two given nodes. 如果存在两个或两个以上的源节点和目标节点对之间的两个或两个以上的最短路径 () ,则该函数只返回遍历期间首先找到的一个路径。If there exists, two or more shortest paths of the same length between any pair of source and destination node(s), the function returns only one path that was found first during traversal. 请注意,只能在 SHORTEST_PATH 函数内指定任意长度的模式。Note that, an arbitrary length pattern can only be specified inside a SHORTEST_PATH function.

有关语法,请参阅 SQL Graph) (匹配 Refer to the MATCH (SQL Graph) for syntax.

对于路径FOR PATH

对于,路径必须与 FROM 子句中的任何节点或边界表名称一起使用,这将参与任意长度的模式。FOR PATH must be used with any node or edge table name in the FROM clause, which will participate in an arbitrary length pattern. 对于 "路径",指示引擎节点或边缘表将返回一个已排序的集合,该集合表示沿遍历的路径找到的节点或边缘的列表。FOR PATH tells the engine that the node or edge table will return an ordered collection representing the list of nodes or edges found along the path traversed. 不能直接在 SELECT 子句中投影这些表中的属性。The attributes from these tables cannot be projected directly in the SELECT clause. 若要投影这些表中的属性,必须使用图形路径聚合函数。To project attributes from these tables, graph path aggregate functions must be used.

任意长度模式Arbitrary Length Pattern

此模式包括节点和边缘,必须反复遍历这些节点和边缘,直到达到所需的节点或达到模式中指定的最大迭代数。This pattern includes the nodes and edges that must be traversed repeatedly until the desired node is reached or until the maximum number of iterations as specified in the pattern is met. 每次执行查询时,执行此模式的结果将是从开始节点到结束节点的路径遍历的节点和边缘的有序集合。Each time the query is executed, the result of executing this pattern will be an ordered collection of the nodes and edges traversed along the path from the start node to the end node. 这是正则表达式样式语法模式,支持以下两种模式限定符:This is a regular expression style syntax pattern and the following two pattern quantifiers are supported:

  • "+":重复模式1次或多次。‘+’: Repeat the pattern 1 or more times. 找到最短路径后立即终止。Terminate as soon as a shortest path is found.
  • {1,n} :重复模式 1到“n”次。{1,n}: Repeat the pattern 1 to ‘n’ times. 找到最短的时立即终止。Terminate as soon as a shortest is found.

LAST_NODELAST_NODE

LAST_NODE () 函数允许链接两个任意长度的遍历模式。LAST_NODE() function allows chaining of two arbitrary length traversal patterns. 它可用于以下情况:It can be used in scenarios where:

  • 一个查询中使用了多个最短路径模式,一个模式从上一模式的最后一个节点开始。More than one shortest path patterns are used in a query and one pattern begins at the LAST node of the previous pattern.
  • 两个最短路径模式合并到同一个 LAST_NODE () 。Two shortest path patterns merge at the same LAST_NODE().

图形路径顺序Graph Path Order

Graph 路径顺序指的是输出路径中数据的顺序。Graph path order refers to the order of data in the output path. 输出路径顺序始终从模式的非递归部分开始,后面是在递归部分中显示的节点/边缘。The output path order always starts at the non-recursive part of the pattern followed by the nodes/edges that appear in the recursive part. 在查询优化/执行期间遍历关系图的顺序与输出中打印的顺序无关。The order in which the graph is traversed during query optimization/execution has nothing to do with the order printed in the output. 同样,递归模式中箭头的方向也不会影响关系图路径顺序。Similarly, the direction of arrow in the recursive pattern also does not affect the graph path order.

Graph 路径聚合函数Graph Path Aggregate Functions

由于任意长度模式中涉及的节点和边缘返回 (的节点 () s 的集合,) 在该路径) 遍历的 (,因此用户无法使用常规 attributename 语法直接投影属性。Since the nodes and edges involved in arbitrary length pattern return a collection (of node(s) and edge(s) traversed in that path), users cannot project the attributes directly using the conventional tablename.attributename syntax. 对于需要从中间节点或边缘表投影属性值的查询,在遍历的路径中,使用以下图形路径聚合函数: STRING_AGG、LAST_VALUE、SUM、AVG、MIN、MAX 和 COUNT。For queries where it is required to project attribute values from the intermediate node or edge tables, in the path traversed, use following graph path aggregate functions: STRING_AGG, LAST_VALUE, SUM, AVG, MIN, MAX and COUNT. 在 SELECT 子句中使用这些聚合函数的常规语法为:The general syntax to use these aggregate functions in the SELECT clause is:

<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_AGGSTRING_AGG

STRING_AGG 函数采用表达式和分隔符作为输入并返回一个字符串。The STRING_AGG function takes an expression and separator as input and returns a string. 用户可以在 SELECT 子句中使用此函数来投影所遍历路径中的中间节点或边缘中的属性。Users can use this function in the SELECT clause to project attributes from the intermediate nodes or edges in the path traversed.

LAST_VALUELAST_VALUE

若要从遍历的路径的最后一个节点投影属性,可以使用 LAST_VALUE 聚合函数。To project attributes from the last node of path traversed, LAST_VALUE aggregate function can be used. 将边缘表别名作为此函数的输入提供是错误的,只能使用节点表名称或别名。It is an error to provide edge table alias as an input to this function, only node table names or aliases can be used.

最后一个节点:最后一个节点引用在遍历的路径中最后显示的节点,而不考虑匹配谓词中的箭头方向。Last Node: The last node refers to the node which appears last in the path traversed, irrespective of the direction of arrow in the MATCH predicate. 例如:MATCH(SHORTEST_PATH(n(-(e)->p)+) )For example: MATCH(SHORTEST_PATH(n(-(e)->p)+) ). 此处,路径中的最后一个节点将是最后访问的 P 节点。Here the last node in the path will be the last visited P node.

相反,最后一个节点是此模式的输出关系图路径中的最后一个第 n 个节点: MATCH(SHORTEST_PATH((n<-(e)-)+p))Whereas, last node is the last Nth node in the output graph path for this pattern: MATCH(SHORTEST_PATH((n<-(e)-)+p))

SUMSUM

此函数返回在遍历路径中显示的已提供节点/边缘属性值或表达式的总和。This function returns the sum of provided node/edge attribute values or expression that appeared in the traversed path.

COUNTCOUNT

此函数返回路径中所需节点/边缘属性的非 null 值的数量。This function returns the number of non-null values of the desired node/edge attribute in the path. COUNT 函数支持 * 带有节点或边界表别名的 "" 运算符。The COUNT function supports the '*' operator with a node or edge table alias. 如果没有节点或边缘表别名,则的使用 * 不明确,将导致错误。Without the node or edge table alias, the usage of * is ambiguous and will result in an error.

{  COUNT( <expression> | <node_or_edge_alias>.* )  <order_clause>  }

AVGAVG

返回在所遍历的路径中出现的所提供的节点/边缘属性值或表达式的平均值。Returns the average of provided node/edge attribute values or expression that appeared in the traversed path.

MINMIN

返回所提供的节点/边缘属性值或所遍历路径中出现的表达式的最小值。Returns the minimum value from the provided node/edge attribute values or expression that appeared in the traversed path.

MAXMAX

返回所提供的节点/边缘属性值或所遍历路径中出现的表达式的最大值。Returns the maximum value from the provided node/edge attribute values or expression that appeared in the traversed path.

备注Remarks

shortest_path 函数只能在 MATCH 内使用。shortest_path function can only be used inside MATCH.
仅 shortest_path 支持 LAST_NODE。LAST_NODE is only supported inside shortest_path.
如果查找加权最短路径,则不支持所有路径或所有最短路径。Finding weighted shortest path, all paths or all shortest paths is not supported.
在某些情况下,可能会为具有更多跃点数的查询生成错误的计划,从而提高查询执行时间。In some cases, bad plans may be generated for queries with higher number of hops, which results in higher query execution times. 使用哈希联接提示可能会有所帮助。Using a hash join hint may help.

示例Examples

对于此处所示的示例查询,我们将使用在SQL Graph中创建的节点和边缘表示例For the example queries shown here, we are going ot use the node and edge tables created in SQL Graph sample

A.A. 查找两名人员之间的最短路径Find shortest path between 2 people

在下面的示例中,我们找到 Jacob 与 Alice 之间的最短路径。In the following example, we find shortest path between Jacob and Alice. 我们需要从 graph 示例脚本创建的人员节点和 FriendOf 边缘。We will need the Person node and FriendOf edge created from graph sample script.

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.B. 查找关系图中从给定节点到所有其他节点的最短路径。Find shortest path from a given node to all other nodes in the graph.

下面的示例查找 Jacob 连接到的关系图中的所有人员,以及从 Jacob 开始到所有这些人员的最短路径。The following example finds all the people that Jacob is connected to in the graph and the shortest path starting from Jacob to all those people.

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.C. 计算在图形中遍历以从一个人到另一个人的跃点/级别数。Count the number of hops/levels traversed to go from one person to another in the graph.

下面的示例查找 Jacob 与 Alice 之间的最短路径,并打印从 Jacob 到 Alice 需要的跃点数。The following example finds the shortest path between Jacob and Alice and prints the number of hops it takes to go from Jacob to 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.D. 查找离开给定人员的人员1-3 跃点Find people 1-3 hops away from a given person

下面的示例查找 Jacob 与他连接到的关系图1-3 跃点的所有用户之间的最短路径。The following example finds the shortest path between Jacob and all the people that he is connected to in the graph 1-3 hops away from him.

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.E. 查找来自给定人员的完全2个跃点Find people exactly 2 hops away from a given person

下面的示例查找 Jacob 与图形中正好有2个跃点的用户之间的最短路径。The following example finds the shortest path between Jacob and people who are exactly 2 hops away from him in the graph.

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

另请参阅See Also

匹配 (SQL Graph) MATCH (SQL Graph)
CREATE TABLE (SQL Graph) CREATE TABLE (SQL Graph)
INSERT(SQL 图形)]INSERT (SQL Graph)]
使用 SQL Server 2017 进行图形处理Graph processing with SQL Server 2017