2

複数の親を持つツリー (またはダイグラフ) を SQL Server 2005 に実装する必要があります。いくつかの記事を読みましたが、それらのほとんどは、次のような一意のルートを持つ単一の親ツリーを使用しています。

-My PC
   -Drive C
      -Documents and Settings
      -Program Files
         -Adobe
         -Microsoft
      -Folder X
   -Drive D
      -Folder Y
      -Folder Z

この例では、すべてがルート要素 (My PC) から派生しています。

私の場合、子は次のように複数の親を持つことができます。

G  A
 \ /
  B
 / \ 
X   C
  /  \
  D   E
  \ /
   F

だから私は次のコードを持っています：

create table #ObjectRelations
(
    Id varchar(20),
    NextId varchar(20)
)

insert into #ObjectRelations values ('G', 'B')
insert into #ObjectRelations values ('A', 'B') 
insert into #ObjectRelations values ('B', 'C')
insert into #ObjectRelations values ('B', 'X')
insert into #ObjectRelations values ('C', 'E') 
insert into #ObjectRelations values ('C', 'D') 
insert into #ObjectRelations values ('E', 'F') 
insert into #ObjectRelations values ('D', 'F') 

declare @id varchar(20)
set @id = 'A';

WITH Objects (Id, NextId) AS
( -- This is the 'Anchor' or starting point of the recursive query
  SELECT rel.Id,
         rel.NextId
    FROM #ObjectRelations rel
   WHERE rel.Id = @id
   UNION ALL -- This is the recursive portion of the query
  SELECT rel.Id,
         rel.NextId
    FROM #ObjectRelations rel
   INNER JOIN Objects -- Note the reference to CTE table name (Recursive Join)
      ON rel.Id = Objects.NextId
)
SELECT  o.*
FROM    Objects o

drop table #ObjectRelations

次のSETを返します。

Id                   NextId
-------------------- --------------------
A                    B
B                    C
B                    X
C                    E
C                    D
D                    F
E                    F

期待される結果セット:

Id                   NextId
-------------------- --------------------
G                    B
A                    B
B                    C
B                    X
C                    E
C                    D
D                    F
E                    F

関係 G->B が欠落していることに注意してください。これは、開始オブジェクトを要求し (最初からルート オブジェクトがわからないため、これも機能しません)、開始点として A を使用すると無視されるためです。 G→Bの関係。

したがって、このコードは私の場合は機能しません。これは、SINGLE-parent ツリーで明らかな開始オブジェクトを要求するためです (常にルート オブジェクトになります)。しかし、複数の親を持つツリーでは、複数の「ルート」オブジェクトを持つことができます (例のように、G と A は「ルート」オブジェクトであり、ルートは親 (先祖) を持たないオブジェクトです)。

だから私はここで立ち往生しています...開始オブジェクトを要求せず、ツリー全体を再帰的にトラバースするようにクエリを変更する必要があります。(Id, NextId) 実装でそれが可能かどうかはわかりません...何らかの種類のインシデントマトリックス、隣接マトリックスなどを使用してグラフのように保存する必要があるかもしれません ( http://willets.org/を参照) sqlgraphs.html )。

何か助けはありますか？皆さんどう思いますか？お時間をいただきありがとうございました=）

乾杯！

ソース: ソース 1 ソース 2 ソース 3

4

3 に答える 3

2

さて、私は最終的に次の解決策を思いつきました。これは、マルチルート ツリーと循環有向グラフをサポートするために私が見つけた方法です。

create table #ObjectRelations
(
    Id varchar(20),
    NextId varchar(20)
)

/* Cycle */
/*
insert into #ObjectRelations values ('A', 'B')
insert into #ObjectRelations values ('B', 'C') 
insert into #ObjectRelations values ('C', 'A')
*/

/* Multi root */

insert into #ObjectRelations values ('G', 'B')
insert into #ObjectRelations values ('A', 'B') 
insert into #ObjectRelations values ('B', 'C')
insert into #ObjectRelations values ('B', 'X')
insert into #ObjectRelations values ('C', 'E') 
insert into #ObjectRelations values ('C', 'D') 
insert into #ObjectRelations values ('E', 'F') 
insert into #ObjectRelations values ('D', 'F') 


declare @startIds table
(
    Id varchar(20) primary key
)

;WITH 
    Ids (Id) AS
    (
        SELECT  Id
        FROM    #ObjectRelations
    ),
    NextIds (Id) AS
    (
        SELECT  NextId
        FROM    #ObjectRelations
    )
INSERT INTO @startIds
/* This select will not return anything since there are not objects without predecessor, because it's a cyclic of course */
SELECT DISTINCT
    Ids.Id
FROM
    Ids
LEFT JOIN
    NextIds on Ids.Id = NextIds.Id
WHERE
    NextIds.Id IS NULL
UNION
/* So let's just pick anyone. (the way I will be getting the starting object for a cyclic doesn't matter for the regarding problem)*/
SELECT TOP 1 Id FROM Ids

;WITH Objects (Id, NextId, [Level], Way) AS
( -- This is the 'Anchor' or starting point of the recursive query
  SELECT rel.Id,
         rel.NextId,
         1,
         CAST(rel.Id as VARCHAR(MAX))
    FROM #ObjectRelations rel
   WHERE rel.Id IN (SELECT Id FROM @startIds)

   UNION ALL -- This is the recursive portion of the query

  SELECT rel.Id,
         rel.NextId,
         [Level] + 1,
         RecObjects.Way + ', ' + rel.Id
    FROM #ObjectRelations rel
   INNER JOIN Objects RecObjects -- Note the reference to CTE table name (Recursive Join)
      ON rel.Id = RecObjects.NextId
   WHERE RecObjects.Way NOT LIKE '%' + rel.Id + '%'

)
SELECT  DISTINCT 
        Id,
        NextId,
        [Level]
FROM    Objects
ORDER BY [Level]

drop table #ObjectRelations

誰かのために役立つかもしれません。それは私のためです = P ありがとう

于 2009-06-03T20:10:52.317 に答える
1

すべてのルート オブジェクトを開始オブジェクトとして使用する場合は、最初にデータを更新して、ルート オブジェクト (およびリーフ) に関する情報を含める必要があります。次の挿入を追加する必要があります。

insert into #ObjectRelations values (NULL, 'G')
insert into #ObjectRelations values (NULL, 'A')
insert into #ObjectRelations values ('X', NULL)
insert into #ObjectRelations values ('F', NULL)

もちろん、Idとして出現しないを持つレコードをルート ノードとして選択するような方法でアンカー クエリを作成することもできますが、そのNextId方が簡単です。

次に、アンカー クエリを次のように変更します。

SELECT rel.Id,
       rel.NextId
FROM #ObjectRelations rel
WHERE rel.Id IS NULL

このクエリを実行すると、多くの重複が発生し、多くのアークが複数回発生することがわかります。これは、アンカー クエリの結果が 2 つになり、ツリーが 2 回トラバースされるためです。

これは、select ステートメントを次のように変更することで修正できます ( に注意してくださいDISTINCT)。

SELECT DISTINCT o.*
FROM   Objects o
于 2009-05-13T06:30:10.727 に答える
0

Ronald が提案する挿入を行いたくない場合は、これで十分です。

WITH CTE_MultiParent  (ID, ParentID) 
AS 
(
    SELECT ID, ParentID FROM #ObjectRelations
    WHERE ID NOT IN 
    (
        SELECT DISTINCT ParentID FROM #ObjectRelations
    )
    UNION ALL
    SELECT ObjR.ID, ObjR.ParentID FROM #ObjectRelations ObjR INNER JOIN CTE_MultiParent
    ON CTE_MultiParent.ParentID = ObjR.Id
)

SELECT DISTINCT * FROM CTE_MultiParent
于 2012-04-05T12:54:07.333 に答える