T-SQL Challenge - Identifying Related Tables

The challenge at hand involves writing a recursive query that returns all tables related through foreign keys to a table whose name is given as input, directly or indirectly. For sample data use the following code:

USE testfk;

 

CREATE TABLE dbo.D(d INT PRIMARY KEY);

CREATE TABLE dbo.E(e INT PRIMARY KEY, d INT REFERENCES dbo.D);

CREATE TABLE dbo.A(a INT PRIMARY KEY, e INT REFERENCES dbo.E, aa INT REFERENCES dbo.A);

CREATE TABLE dbo.C(c INT PRIMARY KEY);

CREATE TABLE dbo.B(b INT PRIMARY KEY, c INT REFERENCES dbo.C);

CREATE TABLE dbo.AB(a INT REFERENCES dbo.A, b INT REFERENCES dbo.B, PRIMARY KEY(a, b));

 

CREATE TABLE dbo.G(g INT PRIMARY KEY);

CREATE TABLE dbo.F(f INT PRIMARY KEY, g INT REFERENCES dbo.G);

 

Here’s a graphical depiction of the relationships between the tables:

 


Given a table name as input, e.g.,

 

DECLARE @table AS NVARCHAR(261) = N'dbo.E';

 

Your challenge is to write a recursive query returning all related tables. You’re supposed to return the names of tables related to the input one directly or indirectly, including tables related through a connection table. So, for example, for the given input table name E, your code should return the following output:

obj_schema_name  obj_name

---------------- ---------

dbo              E

dbo              D

dbo              A

dbo              AB

dbo              B

dbo              C

 

Coming up with a solution that works is not that hard, for example using loops, like so:

DECLARE @T AS TABLE ( id INT NOT NULL PRIMARY KEY );

 

INSERT INTO @T(id)

 

  SELECT referenced_object_id AS id

  FROM sys.foreign_keys

  WHERE parent_object_id = OBJECT_ID(@table)

 

  UNION

 

  SELECT parent_object_id

  FROM sys.foreign_keys

  WHERE referenced_object_id = OBJECT_ID(@table);

 

WHILE @@ROWCOUNT > 0

 

  INSERT INTO @T(id)

 

    SELECT referenced_object_id AS id

    FROM sys.foreign_keys AS FK

      JOIN @T

        ON FK.parent_object_id = [@T].id

 

    UNION

 

    SELECT parent_object_id

    FROM sys.foreign_keys AS FK

      JOIN @T

        ON FK.referenced_object_id = [@T].id

   

    EXCEPT

   

    SELECT id FROM @T;

 

SELECT OBJECT_SCHEMA_NAME(id) AS obj_schema_name, OBJECT_NAME(id) AS obj_name

FROM @T;

 

However, coming up with a solution using a recursive query is not that trivial due to all kinds of restrictions that SQL Server imposes on recursive queries. For example, among other restrictions, you’re not allowed to refer to the CTE name more than once from the recursive query. So with this constraint in place—using a recursive query—can you find a solution?

Please post your solutions as comments to this blog entry or if you prefer directly to me.

 

Good luck!

BG

 

Discuss this Blog Entry 5

on May 27, 2010
Email sent!
on May 28, 2010
Itzik, add this table to your set

CREATE TABLE dbo.Y(d INT PRIMARY KEY);

and substitute your @table variable with this

DECLARE @table AS NVARCHAR(261) = N'dbo.Y';

and run your query again.









on May 28, 2010
GeriReshef, substitute your @table variable with this

DECLARE @table AS NVARCHAR(261) = N'dbo.X';

and run your suggestion again.





on May 28, 2010
In coincidence I published this week a post in my blog about The Minimum Spanning Tree Problem (unfortunately in Hebrew: http://gerireshef.wordpress.com/2010/05/25/%D7%A2%D7%A5-%D7%A4%D7%95%D7%A8%D7%A9-%D7%9E%D7%99%D7%A0%D7%99%D7%9E%D7%9C%D7%99/).

Your challenge is a spanning tree problem- begining with dbo.E one should find paths to all the nodes in the connected graph (=tree).

My solution (I tried to send a mail but it has been rejected):
DECLARE @table AS NVARCHAR(261) = N'dbo.E';
With T1 As
(Select Distinct Schema_Name(P.schema_id)+'.'+P.name P,
Schema_Name(R.schema_id)+'.'+R.name R
From sys.foreign_key_columns F
Inner Join sys.objects P
On F.parent_object_id=P.object_id
Inner Join sys.objects R
On F.referenced_object_id=R.object_id),
T2 As
(Select ROW_NUMBER() Over(Order By Case When @table =P Then 1 When @table =R Then 2 Else 3 End,P,R) Mispar,
*
From T1),
T3 As
(Select Mispar,
P,
R,
P PR,
(-1) Idcun,
Cast(','+P+',' As Varchar(Max)) S_in
From T2
Where Mispar=1

Union All
Select Mispar,
P,
R,
Case When Idcun=1 Then R When Idcun=2 Then P Else '' End PR,
Case When Idcun=2 Then 1 Else Idcun End Idcun,
Cast(S_in+Case When Idcun=1 Then R+',' When Idcun=2 Then P+',' Else '' End As Varchar(Max)) S_in
From (Select T2.Mispar,
T2.P,
T2.R,
Case When T3.S_in Like '%,'+T2.P+',%' And T3.S_in Not Like '%,'+T2.R+',%' Then 1
When T3.S_in Not Like '%,'+T2.P+',%' And T3.S_in Like '%,'+T2.R+',%' Then 2
Else 0 End Idcun,
T3.S_in
From T3
Inner Join T2
On T3.Mispar+1=T2.Mispar
Where T3.Idcun<=0) T

Union All
Select Mispar,
P,
R,
Case When Idcun=1 Then R When Idcun=2 Then P Else '' End PR,
Case When Idcun=2 Then 1 Else Idcun End Idcun,
Cast(S_in+Case When Idcun=1 Then R+',' When Idcun=2 Then P+',' Else '' End As Varchar(Max)) S_in
From (Select T2.Mispar,
T2.P,
T2.R,
Case When T3.S_in Like '%,'+T2.P+',%' And T3.S_in Not Like '%,'+T2.R+',%' Then 1
When T3.S_in Not Like '%,'+T2.P+',%' And T3.S_in Like '%,'+T2.R+',%' Then 2
Else 0 End Idcun,
T3.S_in
From T3
Inner Join T2
On T3.Idcun=1
And T2.Mispar=1) T)
Select PR
From T3
Where PR<>'';

Explanation:
1. The "anchor" of he CTE finds the first node in the tree.
2. All links (dependencies) are scanned till the first one which is connected to tree is found, and is added (the first recursion).
3. The links are rescanned fro the bagining (the second recursion).











































































on May 28, 2010
Pesomannen: you're right, and I should have checked the query better..
Now I hope it's correct, but less elegant:
http://img2.timg.co.il/forums/1_141923195.txt

Please or Register to post comments.

What's Puzzled By T-SQL Blog?

T-SQL tips and logical puzzles from Itzik Ben-Gan.

Blog Archive

Sponsored Introduction Continue on to (or wait seconds) ×