How to do a recursive join ?
-
Please can someone help me on how to do a recursive join on the following tables:
Module
smallint PKey [primary key]
varchar MName
-- This table will include alot more columns relative to properties in the module.
Reference
smallint FKey [foreign key] references Table1.Pkey
varchar RName
-- No more properties required in this table
Sorry about my pseudo DDL here but not worked out how to export all this
info to paste in here from MS SQL Management Studio Express. ?
Into table Module I add the following data:
1,FileA
2,FileB
3,FileC
And into table Reference I add:
1,FileB
1,FileD
2,FileC
2,FileE
So this is a represention of some file dependencies I have; e.g
FileA
uses FileB; uses FileD
FileB
uses FileC; uses FileE
FileC
What i want is all the transitive dependencies of a given module.
So if i submit FileA, I would get the following list
FileA, FileB
FileA, FileD
FileA, FileC
FileA, FileE
As FileA uses FileB and FileB uses FileC & FileE these are indirectly dependencies of FileA. If you are reading this far im sure you get the picture
Basically will join Reference.RName == Module.MName and repeat.
So my problem is putting together a CTE that will work with this recursive structure. Im having a problem conceptualising how to put it together.
Would be a walk in the park with a procedural language.
With NestedDepends( nm1, nm2 ) as
(
select Module.MName, Reference.RName from Module join Reference on Module.PKey = Reference.FKey
where Module.MName = 'A'
union all
select Module.MName, Reference.RName from Module join Reference on Module.PKey = Reference.FKey
inner join NestedDepends on Reference.RName = nm1
)
select * from NestedDepends
OPTION(MAXRECURSION 0);
But the recursion does not seem to be happening im getting the following rows only
FileA, FileB
FileA, FileD
Can anyone put me right?
Id be enternally grateful.
Thanks.
-
Your basic problem is that you need to carry the current parent value through the recursion.
Also, you would probably find it easier if the Reference table was structured better by containing ChildIDs and NOT child values.
Something like this should work with your original Reference table:
-- *** Test Data ***
DECLARE @Module TABLE
(
ModuleID smallint NOT NULL PRIMARY KEY
,MName varchar(20) NOT NULL
)
INSERT INTO @Module
SELECT 1, 'FileA' UNION ALL
SELECT 2, 'FileB' UNION ALL
SELECT 3, 'FileC' UNION ALL
SELECT 4, 'FileD' UNION ALL
SELECT 5, 'FileE'
DECLARE @Reference TABLE
(
ModuleID smallint NOT NULL
,RName varchar(20) NOT NULL
)
INSERT INTO @Reference
SELECT 1, 'FileB' UNION ALL
SELECT 1, 'FileD' UNION ALL
SELECT 2, 'FileC' UNION ALL
SELECT 2, 'FileE'
-- *** End Test Data ***
;WITH ChildModules (ModuleID, ChildID, RootID, LevelNo)
AS
(
SELECT R1.ModuleID, M1.ModuleID, R1.ModuleID, 0 AS LevelNo
FROM @Reference R1
JOIN @Module M1
ON R1.RName = M1.MName
WHERE EXISTS (
SELECT *
FROM @Module M1
WHERE R1.ModuleID = M1.ModuleID
AND M1.MName = 'FileA'
)
UNION ALL
SELECT C2.ChildID, M2.ModuleID, C2.RootID, C2.LevelNo + 1
FROM ChildModules C2
JOIN @Reference R2
ON C2.ChildID = R2.ModuleID
JOIN @Module M2
ON R2.RName = M2.MName
)
SELECT MP.MName AS RootParentName
,MC.MName AS ChildName
,C.LevelNo AS RecursionLevel
FROM ChildModules C
JOIN @Module MP
ON C.RootID = MP.ModuleID
JOIN @Module MC
ON C.ChildID = MC.ModuleID
Something like this should work with a modified reference table:
-- ** Test Data ***
DECLARE @Module TABLE
(
ModuleID smallint NOT NULL PRIMARY KEY
,MName varchar(20) NOT NULL
)
INSERT INTO @Module
SELECT 1, 'FileA' UNION ALL
SELECT 2, 'FileB' UNION ALL
SELECT 3, 'FileC' UNION ALL
SELECT 4, 'FileD' UNION ALL
SELECT 5, 'FileE'
DECLARE @Reference TABLE
(
ModuleID smallint NOT NULL
,ChildID smallint NOT NULL
)
INSERT INTO @Reference
SELECT 1, 2 UNION ALL
SELECT 1, 4 UNION ALL
SELECT 2, 3 UNION ALL
SELECT 2, 5
-- *** End Test Data ***
;WITH ChildModules (ModuleID, ChildID, RootID, LevelNo)
AS
(
SELECT R1.ModuleID, R1.ChildID, R1.ModuleID, 0 AS LevelNo
FROM @Reference R1
WHERE EXISTS (
SELECT *
FROM @Module M1
WHERE R1.ModuleID = M1.ModuleID
AND M1.MName = 'FileA'
)
UNION ALL
SELECT C2.ChildID, R2.ChildID, C2.RootID, C2.LevelNo + 1
FROM ChildModules C2
JOIN @Reference R2
ON C2.ChildID = R2.ModuleID
)
SELECT MP.MName AS RootParentName
,MC.MName AS ChildName
,C.LevelNo AS RecursionLevel
FROM ChildModules C
JOIN @Module MP
ON C.RootID = MP.ModuleID
JOIN @Module MC
ON C.ChildID = MC.ModuleID
-
Worked first time Ken, I was able to paste directly into SQL Server Manager Studio express.
Thanks for your effort.
I need to spend some time understanding it now.
----
When i run it with the real data it obviously contains some loops, as it runs infinitely.
I can exit by using the level number.
Is there a neat way to catch those that loop?
eg giving me a recordset like
A,A
Given i added C,A to the reference table.
Thanks again.
-
You may need to make sure that parentID <> ChildID in the reference table.
If you have loops in the data I would suggest you get rid of them using iteration.
Viewing 4 posts - 1 through 4 (of 4 total)
You must be logged in to reply to this topic. Login to reply