本文介紹了SQL Server圖形數(shù)據(jù)庫(kù)-使用多種邊類型的最短路徑的處理方法，對(duì)大家解決問(wèn)題具有一定的參考價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)吧！

問(wèn)題描述

我已經(jīng)在SQL Server GraphDB上做了研究，但到目前為止我找到的所有人工示例都只使用了一個(gè)邊表。例如，它總是Person-friend_of->Person。在我的例子中，我已經(jīng)創(chuàng)建了數(shù)據(jù)中心中已部署的軟件組件的圖表，并且有不同的邊/關(guān)系。類似Application-connects_to->SqlDatabase和Server-hosts->Application的內(nèi)容。

我想要編寫(xiě)一個(gè)查詢，該查詢將顯示任意兩個(gè)節(jié)點(diǎn)之間的最短路徑，而不考慮所使用的邊。我想如果我使用Neo4j，我會(huì)把MATCH寫(xiě)成這樣：

Server-*->SqlDatabase請(qǐng)注意星號(hào)。

在SQL Server中有這樣做的慣用方法嗎？

推薦答案

從SQL Server2019開(kāi)始，您可以使用派生表或視圖準(zhǔn)確地實(shí)現(xiàn)這一點(diǎn)。我找不到任何有關(guān)此功能的官方文檔，但我在video about Bill of Materials中找到了一條小注釋。
問(wèn)題是，它目前(SQL Server 2019)有錯(cuò)誤，工作不像預(yù)期的那樣(或者我預(yù)計(jì)它會(huì)工作)。

編輯：他們?cè)谠撘曨l中有一些鏈接，但我們只需關(guān)注此Github example。

編輯2：我發(fā)現(xiàn)了一個(gè)重大錯(cuò)誤，它基本上使異類查詢無(wú)法在實(shí)際使用中使用。

要點(diǎn)是您使用多個(gè)邊(或節(jié)點(diǎn))表的UNION ALL在MATCH運(yùn)算符中充當(dāng)一個(gè)邊(或節(jié)點(diǎn))表。

您應(yīng)該使用查看如果您使用子選擇，您可以做的事情會(huì)受到一些限制(見(jiàn)下文)
您可以使用SUBSELECT，但不能在聚合函數(shù)中使用SUBSELECT的列(這可能是可能的，但不容易使用，而且肯定沒(méi)有文檔記錄)
您可以不使用公用表表達(dá)式

示例

此示例使用異類節(jié)點(diǎn)視圖和異類邊緣視圖。它還描述了兩個(gè)主要錯(cuò)誤(我會(huì)稱之為錯(cuò)誤，但它可能是一個(gè)功能，這是一個(gè)需要M$回答的問(wèn)題)錯(cuò)誤：

如果要查找兩個(gè)異類節(jié)點(diǎn)之間的最短路徑，則它們都必須是異類。如果從特定的節(jié)點(diǎn)開(kāi)始，然后繼續(xù)處理異類節(jié)點(diǎn)，則無(wú)論出于何種原因，算法都將能夠遍歷距離起始節(jié)點(diǎn)只有一條邊的圖形。
如果嘗試對(duì)路徑中的節(jié)點(diǎn)或邊表使用聚合函數(shù)，則它們當(dāng)前僅對(duì)邊表行正確工作；對(duì)節(jié)點(diǎn)行的聚合函數(shù)返回隨機(jī)(？)垃圾。

/** TOC:
* 1. prepare tables
* 2. prepare data
* 3. prepare heterogenous views
* 4. QUERIES
* 4.a. BUG 1
* 4.b. BUG 2
* 4.c. WORKS
**/

BEGIN TRANSACTION
GO

/*******************
| 1. prepare tables |
*******************/
CREATE TABLE graph.SmallCities   (Name nvarchar(1000), Weight INTEGER, SmallCity_ID INTEGER IDENTITY(666,666) PRIMARY KEY) AS NODE;
CREATE TABLE graph.LargeCities   (Name nvarchar(1000), Weight INTEGER, LargeCity_ID INTEGER IDENTITY(666,666) PRIMARY KEY) AS NODE;
CREATE TABLE graph.Villages      (Name nvarchar(1000), Weight INTEGER, Village_ID   INTEGER IDENTITY(666,666) PRIMARY KEY) AS NODE;
CREATE TABLE graph.Hamlets       (Name nvarchar(1000), Weight INTEGER, Hamlet_ID    INTEGER IDENTITY(666,666) PRIMARY KEY) AS NODE;

CREATE TABLE graph.Hikes     (INDEX UQ UNIQUE nonclustered ($from_id, $to_id)) AS EDGE;
CREATE TABLE graph.Footpaths (INDEX UQ UNIQUE nonclustered ($from_id, $to_id)) AS EDGE;
CREATE TABLE graph.Roads     (INDEX UQ UNIQUE nonclustered ($from_id, $to_id)) AS EDGE;
CREATE TABLE graph.Railways  (INDEX UQ UNIQUE nonclustered ($from_id, $to_id)) AS EDGE;

INSERT INTO graph.SmallCities (Name, Weight) VALUES (N'SmallCityOnRoad', 3);
INSERT INTO graph.LargeCities (Name, Weight) VALUES (N'BigCityOnRailway', 5), (N'BiggishCityOnR&R', 4);
INSERT INTO graph.Villages    (Name, Weight) VALUES (N'VillageInMountains', 2);
INSERT INTO graph.Hamlets     (Name, Weight) VALUES (N'HutInThePass', 1);

/*****************
| 2. prepare data |
*****************/
INSERT INTO graph.Railways
  ($from_id, $to_id) 
SELECT
  L1.$node_id, L2.$node_id
FROM
  graph.LargeCities AS L1,
  graph.LargeCities AS L2
WHERE
  L1.Name = N'BigCityOnRailway' 
  AND L2.Name = N'BiggishCityOnR&R';

INSERT INTO graph.Roads
  ($from_id, $to_id) 
SELECT
  L1.$node_id, L2.$node_id
FROM
  graph.LargeCities AS L1,
  graph.SmallCities AS L2
WHERE
  L1.Name = N'BiggishCityOnR&R'
  AND L2.Name = N'SmallCityOnRoad';

INSERT INTO graph.Footpaths
  ($from_id, $to_id) 
SELECT
  L1.$node_id, L2.$node_id
FROM
  graph.SmallCities AS L1,
  graph.Villages AS L2
WHERE
  L1.Name = N'SmallCityOnRoad'
  AND L2.Name = N'VillageInMountains';

INSERT INTO graph.Hikes
  ($from_id, $to_id) 
SELECT
  L1.$node_id, L2.$node_id
FROM
  graph.Villages AS L1,
  graph.Hamlets AS L2
WHERE
  L1.Name = N'VillageInMountains'
  AND L2.Name = N'HutInThePass';

GO

/*******************************
| 3. prepare heterogenous views |
*******************************/
CREATE VIEW graph.AllResidentialAreas AS
  SELECT
    LC.$node_id AS node_id,
    LC.Name,
    LC.Weight,
    LC.LargeCity_ID AS Area_ID,
    'Large city' AS AreaType
  FROM
    graph.LargeCities AS LC
  UNION ALL
  SELECT
    SC.$node_id AS node_id,
    SC.Name,
    SC.Weight,
    SC.SmallCity_ID,
    'Small city' AS AreaType
  FROM
    graph.SmallCities AS SC
  UNION ALL
  SELECT
    V.$node_id AS node_id,
    V.Name,
    V.Weight,
    V.Village_ID,
    'Village' AS AreaType
  FROM
    graph.Villages AS V
  UNION ALL
  SELECT
    H.$node_id AS node_id,
    H.Name,
    H.Weight,
    H.Hamlet_ID,
    'Hamlet' AS AreaType
  FROM
    graph.Hamlets AS H;

GO

CREATE VIEW graph.AllPaths AS
  SELECT
    $edge_id AS edge_id,
    $from_id AS from_id,
    $to_id AS to_id,
    'Railway' AS PathType
  FROM
    graph.RailWays
  UNION ALL
  SELECT
    $edge_id,
    $from_id AS from_id,
    $to_id AS to_id,
    'Road' AS PathType
  FROM
    graph.Roads
  UNION ALL
  SELECT
    $edge_id,
    $from_id AS from_id,
    $to_id AS to_id,
    'Footpath' AS PathType
  FROM
    graph.Footpaths
  UNION ALL
  SELECT
    $edge_id,
    $from_id AS from_id,
    $to_id AS to_id,
    'Hike' AS PathType
  FROM
    graph.Hikes;

GO

/************
| 4. QUERIES |
************/

/*************
| 4.a. BUG 1 - combining views and underlaying tables doesn't work
*/
SELECT
  STRT.Name AS FromArea,
  LAST_VALUE(NOD.Name) within GROUP (graph PATH) AS ToArea,
  STRT.NAME + '->' + STRING_AGG(NOD.Name, '->') WITHIN GROUP (graph PATH) AS Way
FROM
  graph.LargeCities                  AS STRT, -------this is a problem, view vs edge table
  graph.AllPaths            FOR PATH AS PTH,
  graph.AllResidentialAreas FOR PATH AS NOD
WHERE 1=1
  AND MATCH(
    SHORTEST_PATH(
      STRT(-(PTH)->NOD)+
    )
  )
  AND STRT.NAME = 'BigCityOnRailway';

/**OUTPUT:
--The problem is, that the SHORTEST_PATH doesn't "see" more than one step behind the starting underlaying table
FromArea          ToArea            Way
BigCityOnRailway  BiggishCityOnR&R  BigCityOnRailway->BiggishCityOnR&R
BigCityOnRailway  SmallCityOnRoad   BigCityOnRailway->BiggishCityOnR&R->SmallCityOnRoad
*/

/*****************
| 4.b. BUG 2 - using node rows along the SHORTEST_PATH found
*/
SELECT
  STRT.Name AS FromArea,
  LAST_VALUE(NOD.Name) within GROUP (graph PATH) AS ToArea,
  STRING_AGG(PTH.PathType, '->') WITHIN GROUP (graph PATH) AS Path,
  STRT.NAME + '->' + STRING_AGG(NOD.Name, '->') WITHIN GROUP (graph PATH) AS Way, --this has problem
  SUM(NOD.Weight) WITHIN GROUP (graph PATH) AS Weight, --this has similar problem
  COUNT(PTH.PathType) WITHIN GROUP (graph PATH) AS Path_Length
FROM
  graph.AllResidentialAreas          AS STRT,
  graph.AllPaths            FOR PATH AS PTH,
  graph.AllResidentialAreas FOR PATH AS NOD
WHERE 1=1
  AND MATCH(
    SHORTEST_PATH(
      STRT(-(PTH)->NOD)+
    )
  )
  AND STRT.Name = 'BigCityOnRailway'
  AND STRT.AreaType = 'Large city';

/**OUTPUT
--This correctly finds the "transitive closure" (columns FromArea and ToArea)
--This correctly finds the edges that need to be traversed (column Path)
--BUT the nodes along the way are wrong - see the last two rows:
--  first, second and the last nodes are OK,
--  but all the nodes between are just the first node repeated
--  this is also visible in the Weight column, where the correct weights should be (4, 7, 9, 10)
FromArea          ToArea              Path                           Way                                                                                   Weight  Path_Length
BigCityOnRailway  BiggishCityOnR&R    Railway                        BigCityOnRailway->BiggishCityOnR&R                                                    4       1
BigCityOnRailway  SmallCityOnRoad     Railway->Road                  BigCityOnRailway->BiggishCityOnR&R->SmallCityOnRoad                                   7       2
BigCityOnRailway  VillageInMountains  Railway->Road->Footpath        BigCityOnRailway->BiggishCityOnR&R->BigCityOnRailway->VillageInMountains              11      3
BigCityOnRailway  HutInThePass        Railway->Road->Footpath->Hike  BigCityOnRailway->BiggishCityOnR&R->BigCityOnRailway->BigCityOnRailway->HutInThePass  15      4
*/

/***********************************
| 4.c. WORKS, but isn't heterogenous
*/
CREATE TABLE graph.AllAreas (Name nvarchar(1000), Weight INTEGER, Area_ID INTEGER IDENTITY(666,666) PRIMARY KEY, AreaType VARCHAR(1000)) AS NODE;
CREATE TABLE graph.AllWays (PathType VARCHAR(1000), INDEX UQ UNIQUE nonclustered ($from_id, $to_id)) AS EDGE;

INSERT INTO graph.AllAreas
  (Name, Weight, AreaType)
SELECT
  ARA.Name,
  ARA.Weight,
  ARA.AreaType
FROM
  graph.AllResidentialAreas AS ARA WITH(NOLOCK);

INSERT INTO graph.AllWays
  ($from_id, $to_id, PathType)
SELECT
  AA_FROM.$node_id,
  AA_TO.$node_id,
  AP.PathType
FROM
  graph.AllPaths AS AP
  JOIN graph.AllResidentialAreas AS ARA_FROM ON ARA_FROM.node_id = AP.from_id
  JOIN graph.AllResidentialAreas AS ARA_TO   ON ARA_TO.node_id   = AP.to_id
  JOIN graph.AllAreas AS AA_FROM ON AA_FROM.Name = ARA_FROM.Name
  JOIN graph.AllAreas AS AA_TO   ON AA_TO.Name   = ARA_TO.Name;

SELECT
  STRT.Name AS FromArea,
  LAST_VALUE(NOD.Name) within GROUP (graph PATH) AS ToArea,
  STRING_AGG(PTH.PathType, '->') WITHIN GROUP (graph PATH) AS Path,
  STRT.NAME + '->' + STRING_AGG(NOD.Name, '->') WITHIN GROUP (graph PATH) AS Way, --this has problems too, 
  SUM(NOD.Weight) WITHIN GROUP (graph PATH) AS Weight, --this has similar problem
  COUNT(PTH.PathType) WITHIN GROUP (graph PATH) AS Path_Length
FROM
  graph.AllAreas          AS STRT,
  graph.AllWays  FOR PATH AS PTH,
  graph.AllAreas FOR PATH AS NOD
WHERE 1=1
  AND MATCH(
    SHORTEST_PATH(
      STRT(-(PTH)->NOD)+
    )
  )
  AND STRT.Name = 'BigCityOnRailway'
  AND STRT.AreaType = 'Large city';

/**OUTPUT:
FromArea          ToArea              Path                           Way                                                                                    Weight  Path_Length
BigCityOnRailway  BiggishCityOnR&R    Railway                        BigCityOnRailway->BiggishCityOnR&R                                                     4       1
BigCityOnRailway  SmallCityOnRoad     Railway->Road                  BigCityOnRailway->BiggishCityOnR&R->SmallCityOnRoad                                    7       2
BigCityOnRailway  VillageInMountains  Railway->Road->Footpath        BigCityOnRailway->BiggishCityOnR&R->SmallCityOnRoad->VillageInMountains                9       3
BigCityOnRailway  HutInThePass        Railway->Road->Footpath->Hike  BigCityOnRailway->BiggishCityOnR&R->SmallCityOnRoad->VillageInMountains->HutInThePass  10      4
*/

GO
IF @@TRANCOUNT > 0
  ROLLBACK TRANSACTION
GO

這篇關(guān)于SQL Server圖形數(shù)據(jù)庫(kù)-使用多種邊類型的最短路徑的文章就介紹到這了，希望我們推薦的答案對(duì)大家有所幫助，