複数の親木(または有向グラフ)の実装のSQL Server 2005
-
21-08-2019 - |
質問
私は、SQL Server 2005の上に多親がツリー(または有向グラフ)を実装する必要があります。 私はいくつかの記事を読んだが、それらのほとんどは、次のようなユニークなルートでシングル親木を使用します。
-My PC
-Drive C
-Documents and Settings
-Program Files
-Adobe
-Microsoft
-Folder X
-Drive D
-Folder Y
-Folder Z
この1で、すべてがルート要素(私のPC)に由来します。
私の場合、子供は以下のように、1人の以上の親を持つことができます:
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
期待される結果のSETます:
Id NextId
-------------------- --------------------
G B
A B
B C
B X
C E
C D
D F
E F
関係G-> Bは、それが(私は最初からルートオブジェクトを知らないので、また、私のために動作しません)、開始オブジェクトを要求するので、不足しているとスタートとして使用していることに注意してください点は、G-> Bの関係は無視されます。
それはひとり親木に明らかである開始オブジェクト、(常にルートオブジェクトとなります)を要求しますので、だから、このコードは、私の場合には動作しません。 (例では、GおよびAがルートが親(祖先)を持っていないオブジェクトである「ルート」オブジェクト、あるように)しかし、多親木で、あなたは以上1「ルート」オブジェクトを持つことができます。
だから私は一種のstuckedここにいるよ...私は開始オブジェクトを求めると、再帰的にツリー全体を横断しないようにクエリを変更する必要があります。 それが実装(同上、NEXTID)で可能かどうかはわからない...私は(<参照発生率行列、隣接行列または任意のいくつかの種類を使用してグラフのようにそれを格納する必要があるかもしれのhref = "のhttp:/ /willets.org/sqlgraphs.html」REL = "nofollowをnoreferrer"> http://willets.org/sqlgraphs.html に)。
すべてのヘルプ?あなたは人をどう思いますか?
)=お時間をありがとうございました乾杯!
ソース: 3 の
解決
まあ、私は最終的に以下の解決策を考え出しました。 それは私がマルチルートの木ともサイクリング有向グラフをサポートすることが分かっ方法です。
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私のためであります おかげ
他のヒント
は、まずルートオブジェクト(葉)に関する情報を含めるようにしてデータを更新する必要があります。あなたは、次のインサートを追加する必要があります:
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回を横断しているためです。
このは(DISTINCT
に注意)これにSELECT文を変更することにより、固定することができます:
SELECT DISTINCT o.*
FROM Objects o
、これはどうなります!
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