6

各行がグラフネットワークのエッジを表すSQLサーバーテーブルがあります。FromNodeIDとToNodeIDはノードテーブルへの外部キーであり、スキーマは次のようになります。

CREATE TABLE #Edges (
  EdgeID int identity (1,1),
  FromNodeID int,
  ToNodeID int
  );

INSERT INTO #Edges (FromNodeID, ToNodeID) VALUES
  (1,2),
  (1,3),
  (1,4),
  (2,3),
  (3,5),
  (4,5),
  (5,6);

さて、各エッジが方向付けられている（つまり、一方向）と考えると、どのノードからでも直接アクセスできるすべてのノードを簡単に見つけることができます。FromNodeID列にインデックスを追加してから、次のようなクエリを実行します。

SELECT ToNodeID FROM #Edges WHERE FromNodeID = 3

結果：5

しかし、各エッジを単方向として扱いたい場合、テーブル/クエリを構造化するための最良の方法は何でしょうか。つまり、ノード3から始めて、結果を取得したいと思います。

結果：1、2、5

私が考えることができる最も簡単な方法は、ToNodeID列にインデックスを追加してから、次のようなクエリを実行することです。

SELECT ToNodeID FROM #Edges WHERE FromNodeID = 3 
UNION SELECT FromNodeID FROM #Edges WHERE ToNodeID = 3;

しかし、これには明らかに2つのクエリの結果セットを組み合わせることが含まれ、あまり効率的ではないようです。これを1つのクエリで記述するためのより良い方法はありますか？（反転したエッジをテーブルに再度挿入したくないことに注意してください。実行時にエッジを有向または無向として扱うことができる必要があります）。

アドバイスありがとうございます！

4

3 に答える 3

4

しかし、これには明らかに 2 つのクエリからの結果セットを結合することが含まれており、あまり効率的ではないようです。これを 1 つのクエリで記述するより良い方法はありますか?

これで十分効率的です。

あなたはこれを行うことができます：

SELECT  CASE 3 WHEN FromNodeId THEN ToNodeId ELSE FromNodeId END
FROM    Edges
WHERE   3 IN (FromNodeId, ToNodeId)

しかし、これは本質的に同じです (UNIONこれらのインデックスはボンネットの下にあります)。

テストするスクリプトは次のとおりです。

CREATE TABLE #Edges
        (
        EdgeID INT IDENTITY (1,1) PRIMARY KEY,
        FromNodeID int NOT NULL,
        ToNodeID int NOT NULL
        )
CREATE INDEX ix_edges_from ON #Edges (FromNodeID, ToNodeId)
CREATE INDEX ix_edges_to ON #Edges (ToNodeID, FromNodeId)
;
WITH    q (rn) AS
        (
        SELECT  1
        UNION ALL
        SELECT  rn + 1
        FROM    q
        WHERE   rn < 1000
        )
INSERT
INTO    #Edges (FromNodeId, ToNodeId)
SELECT  q1.rn, q2.rn
FROM    q q1
CROSS JOIN
        q q2
WHERE   (q1.rn + q2.rn) % 37 = 0
OPTION (MAXRECURSION 0)

の場合UNION:

SELECT  ToNodeId
FROM    #Edges
WHERE   FromNodeId = 3
UNION
SELECT  FromNodeId
FROM    #Edges
WHERE   ToNodeId = 3


  |--Stream Aggregate(GROUP BY:([Union1006]))
       |--Merge Join(Concatenation)
            |--Index Seek(OBJECT:([tempdb].[dbo].[#Edges]), SEEK:([tempdb].[dbo].[#Edges].[FromNodeID]=(3)) ORDERED FORWARD)
            |--Index Seek(OBJECT:([tempdb].[dbo].[#Edges]), SEEK:([tempdb].[dbo].[#Edges].[ToNodeID]=(3)) ORDERED FORWARD)

の場合IN:

  |--Compute Scalar(DEFINE:([Expr1003]=CASE WHEN (3)=[tempdb].[dbo].[#Edges].[FromNodeID] THEN [tempdb].[dbo].[#Edges].[ToNodeID] ELSE [tempdb].[dbo].[#Edges].[FromNodeID] END))
       |--Sort(DISTINCT ORDER BY:([tempdb].[dbo].[#Edges].[EdgeID] ASC))
            |--Concatenation
                 |--Index Seek(OBJECT:([tempdb].[dbo].[#Edges]), SEEK:([tempdb].[dbo].[#Edges].[FromNodeID]=(3)) ORDERED FORWARD)
                 |--Index Seek(OBJECT:([tempdb].[dbo].[#Edges]), SEEK:([tempdb].[dbo].[#Edges].[ToNodeID]=(3)) ORDERED FORWARD)

ご覧のとおり、プランは基本的に同じです。どちらも対応するインデックスから値を取得し、結果を連結します。

結果を連結するために を使用し、マージ結合からレコードが自然に順序付けられて出力されるため、クエリUNIONは実際にはもう少し効率的です。したがって、はソートする必要がありません。Merge JoinStream Aggregate

于 2011-01-26T21:08:35.867 に答える
1

グラフを SQL Server から直接処理する必要がありますか? パフォーマンスが本当に気になる場合は、グラフの表現と処理専用のデータ構造の 1 つを使用する必要があります。私がグラフを使って行った作業のほとんど (そして私はたくさんの作業を行ってきました) は、汎用データベース バックエンドを使用してグラフを参照した場合、実行不可能だったでしょう。

私が使用した最も効果的な表現の 1 つは、私が持っているコンパイラの本の付録に記載されています。

于 2011-01-26T21:18:40.493 に答える
0

私が考えることができる 3 つのオプションがあります: テーブルでのみ、クエリでのみ、またはビューを作成します。テーブルに対して、対称クロージャーを強制するトリガーを作成します(たとえば、(a,b) を挿入するときは (b,a) も挿入します。(a,b) を (c,d) に更新するときは、古い対称性を維持する ( b,a) ペア、次に (d,c)) を挿入します。一部の RDBMS (SQL Server かどうかはわかりません) では、トリガーが起動されたテーブルへの挿入/更新が許可されていないため、これは機能しない可能性があることに注意してください。

クエリでは、

SELECT CASE FromNodeID WHEN 3 THEN ToNodeId ELSE FromNodeId END
  FROM #Edges 
    WHERE FromNodeID=3 OR ToNodeID=3

ビューについては、元のテーブルの対称クロージャーであるビューを作成します。まだUNIONを使用する必要があると思いますが、クエリの作成を簡素化できます。

CREATE VIEW undirected_edges (FirstEdgeID,SecondEdgeId)
  AS (SELECT FromNodeID, ToNodeID FROM #Edges)
  UNION DISTINCT
    (SELECT ToNodeID, FromNodeID FROM #Edges)
于 2011-01-26T21:11:04.880 に答える