SHORTEST_PATH(Transact-SQL)

아티클
08/21/2023

적용 대상: SQL Server 2019(15.x) 이상 Azure SQL Database Azure SQL Managed Instance

그래프에 대한 검색 조건을 지정합니다. 이 조건은 재귀적으로 또는 반복적으로 검색됩니다. SHORTEST_PATH SELECT 문에서 그래프 노드 및 에지 테이블이 있는 MATCH 내에서 사용할 수 있습니다.

최단 경로

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

이 함수는 트래버스된 경로에 나타난 제공된 노드/에지 특성 값 또는 식의 합계를 반환합니다.

개수

이 함수는 경로에 지정된 노드/에지 특성의 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 사이의 가장 짧은 경로를 찾습니다. SQL Graph 샘플에서 만든 노드와 friendOf 에지가 필요합니다Person.

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. 그래프에서 한 사람에서 다른 사용자로 이동하도록 트래버스된 홉/수준 수를 계산합니다.

다음 예제에서는 야곱과 앨리스 사이의 가장 짧은 경로를 찾아 야곱에서 앨리스로 이동하는 데 걸리는 홉 수를 출력합니다.

 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 홉 떨어진 사람 찾기

다음 예제에서는 야곱과 야곱이 그래프에서 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) 에서는 각 가장 짧은 경로에 대한 최종 노드를 반환합니다. 그런 다음, "마지막" Person 노드를 LAST_NODE "연결"하여 추가 순회를 통해 좋아하는 레스토랑을 찾을 수 있습니다.

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'