Optimization of a hierarchical query

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

SQL Server 2008 Forums

Transact-SQL (2008)

Optimization of a hierarchical query

Author

Topic

jb23
Starting Member

5 Posts

Posted - 2011-09-15 : 05:32:24

Hello

I need a query to join the data of 5 tables A,B,C,D,E:


CREATE TABLE A(
	[ID] [int] NOT NULL PRIMARY KEY
);

CREATE TABLE B(
	[ID] [int] NOT NULL PRIMARY KEY,
	A_id [int] REFERENCES A(ID)
);

CREATE TABLE C(
	[ID] [int] NOT NULL PRIMARY KEY,
	A_id [int] REFERENCES A(ID),
	B_id [int] REFERENCES B(ID)
); 

CREATE TABLE D(
	[ID] [int] NOT NULL PRIMARY KEY,
	A_id [int] REFERENCES A(ID),
	B_id [int] REFERENCES B(ID),
	C_id [int] REFERENCES C(ID)
);

CREATE TABLE E(
	[ID] [int] NOT NULL PRIMARY KEY,
	A_id [int] REFERENCES A(ID),
	B_id [int] REFERENCES B(ID),
	C_id [int] REFERENCES C(ID),
	D_id [int] REFERENCES D(ID),
);

Every table should reference only one or no other table.
Sample data:


INSERT INTO A 
VALUES (1),(2),(3),(4),(5);

INSERT INTO B
VALUES 
(1,NULL),
(2,1),
(3,2),
(4,5),
(5,4);

INSERT INTO C
VALUES 
(1,NULL,1),
(2,3,NULL),
(3,NULL,NULL),
(4,NULL,5),
(5,NULL,3);

INSERT INTO D
VALUES 
(1,NULL,4,NULL),
(2,5,NULL,NULL),
(3,NULL,NULL,1),
(4,NULL,NULL,3),
(5,NULL,1,NULL);

INSERT INTO E
VALUES 
(1,2,NULL,NULL,NULL),
(2,NULL,NULL,NULL,1),
(3,NULL,NULL,NULL,1),
(4,NULL,NULL,NULL,NULL),
(5,NULL,3,NULL,NULL),
(6,4,NULL,NULL,NULL),
(7,NULL,NULL,2,NULL),
(8,NULL,NULL,4,NULL),
(9,NULL,NULL,NULL,2),
(10,NULL,NULL,NULL,4);

The Result of the query should be a mix of all of them.
For example:

A Row in E referenced a row in C and that row referenced a row in B and that row in B referenced a row in A.

I need these informations(referencings) in one row.

So I started to make a query, but I think it is to complicated.
Is there another easier query?

Here my query:


;with cte(A_ID, B_ID, C_ID, D_ID, E_ID) as (

select A_ID, B_ID, C_ID, D_ID, E.ID from E
union all
select A_ID, B_ID, C_ID, D.ID, NULL from D
union all
select A_ID, B_ID, C.ID, NULL, NULL from C
union all
select A_ID, B.ID, NULL, NULL, NULL from B
union all
select A.ID, NULL, NULL, NULL, NULL from A

union all

select ISNULL(D.A_ID, cte.A_ID) , ISNULL(D.B_ID, cte.B_ID) , ISNULL(D.C_ID, cte.C_ID) , D.ID , cte.E_ID
from D
join cte on cte.D_ID = D.ID and cte.A_ID is null and cte.B_ID is null and cte.C_ID is null and 
(D.A_ID is not null OR D.B_ID is not null OR D.C_ID IS NOT NULL)

union all

select ISNULL(C.A_ID, cte.A_ID) , ISNULL(C.B_ID, cte.B_ID) , C.ID , cte.D_ID , cte.E_ID
from C
join cte on cte.C_ID = C.ID and cte.A_ID is null and cte.B_ID is null and 
(C.A_ID is not null OR C.B_ID is not null)

union all

select ISNULL(B.A_ID, cte.A_ID) , B.ID , cte.C_ID , cte.D_ID , cte.E_ID
from B
join cte on cte.B_ID = B.ID and cte.A_ID is null and 
(B.A_ID is not null)

)

select MAX(A_ID) A, MAX(B_ID) B, MAX(C_ID) C, MAX(D_ID) D, MAX(E_ID) E
from cte
where E_ID is not null
group by e_ID

Do anyone know a better solution?

visakh16
Very Important crosS Applying yaK Herder

52326 Posts

Posted - 2011-09-15 : 05:57:22

no idea what you're trying to do here
probably you can explain in words what you're trrying to do and give your expected output for the data above

------------------------------------------------------------------------------------------------------
SQL Server MVP
http://visakhm.blogspot.com/

jb23
Starting Member

5 Posts

Posted - 2011-09-15 : 06:40:53

Thank you for your reply.

Sorry. You're right. But it's not so easy to explain.

The problem is that a hierarchy should be mapped in a way that I can easily change references of a set of rows in E.
So I try to explain with an analogy.

E = appels.
D = trees
C = gardens
B = villages
A = state

If I only know a apple is from a special garden then E has the reference to C.
The garden maybe only know the state. So he has the reference to A.

Sometimes someone know the village of the garden, so he add the reference of B and remove the reference to A.
B (village) has the reference to A (state). So there is the hierarchy.

It must be sure that a garden can't reference a apple. So I don't want a big table with self-references and a type number.

I need a query where I can get all references of E. So I can find out the state of an apple without query all the other tables.

The result of the example of the first post is this:


A       B       C       D       E
----------------------------------
2	NULL	NULL	NULL	1
5	4	NULL	1	2
5	4	NULL	1	3
NULL	NULL	NULL	NULL	4
2	3	NULL	NULL	5
4	NULL	NULL	NULL	6
3	NULL	2	NULL	7
4	5	4	NULL	8
5	NULL	NULL	2	9
NULL	NULL	3	4	10

Thanks a lot for any other suggestions.

Ifor
Aged Yak Warrior

700 Posts

Posted - 2011-09-15 : 10:53:08

With your table structure what is wrong with outer joins?


WITH Link1
AS
(
	SELECT COALESCE(E.A_id, D.A_id) AS A
		,COALESCE(E.B_id, D.B_id) AS B
		,COALESCE(E.C_id, D.C_id) AS C
		,E.D_id AS D
		,E.ID AS E
	FROM E
		LEFT JOIN D
			ON E.D_id = D.ID
)
,Link2
AS
(
	SELECT COALESCE(L.A, C.A_id) AS A
		,COALESCE(L.B, C.B_id) AS B
		,L.C
		,L.D
		,L.E
	FROM Link1 L
		LEFT JOIN C
			ON L.C = C.ID
)
SELECT COALESCE(L.A, B.A_id) AS A
	,L.B
	,L.C
	,L.D
	,L.E
FROM Link2 L
	LEFT JOIN B
		ON L.B = B.ID

quote:

So I don't want a big table with self-references and a type number.

You may want to look at this in order to enforce your constraints better and avoid NULLs.
With this structure you would need to PIVOT to get your results.

Ifor
Aged Yak Warrior

700 Posts

Posted - 2011-09-15 : 13:03:03

Something like the following might be worth playing with:


CREATE TABLE HMaster
(
	HLevel tinyint NOT NULL
		CONSTRAINT CK_HMasterHLevel CHECK(HLevel IN (10, 20, 30, 40, 50))
	,HID int NOT NULL
	,CONSTRAINT PK_HMaster PRIMARY KEY(HLevel, HID)	
);

CREATE TABLE States
(
	HLevel tinyint NOT NULL
		CONSTRAINT CK_HMasterHLevel CHECK(HLevel = 10)
	,HID int NOT NULL
	-- other state columns
	,CONSTRAINT PK_States PRIMARY KEY(HLevel, HID)
	,CONSTRAINT UN_States UNIQUE(HID)
	,CONSTRAINT FK_States2HMaster FOREIGN KEY(HLevel, HID) REFERENCES HMaster(HLevel, HID)
);

-- The same with Villages, Gardens, Trees and Apples

CREATE TABLE HRefs
(
	-- 10 = State, 20 = Village, 30 = Garden, 40 = Tree, 50 = Apple
	HLevel tinyint NOT NULL
		CONSTRAINT CK_A2SRsHLevel CHECK(HLevel IN (20, 30, 40, 50))
	,HID int NOT NULL
	,RefHLevel tinyint NOT NULL
		CONSTRAINT CK_A2SRsRefHLevel CHECK(RefHLevel IN (10, 20, 30, 40))
	,RefHID int NOT NULL
	,CONSTRAINT PK_Apple2StateRefs PRIMARY KEY(HLevel, HID)
	,CONSTRAINT CK_A2SRsRefLevels CHECK(RefHLevel < HLevel)
	,CONSTRAINT FK_HRefs2HMaster1 FOREIGN KEY(HLevel, HID) REFERENCES HMaster(HLevel, HID)
	,CONSTRAINT FK_HRefs2HMaster2 FOREIGN KEY(RefHLevel, RefHID) REFERENCES HMaster(HLevel, HID)
)

INSERT INTO HMaster
VALUES
	(10,1),(10,2),(10,3),(10,4),(10,5)
	,(20,1),(20,2),(20,3),(20,4),(20,5)
	,(30,1),(30,2),(30,3),(30,4),(30,5)
	,(40,1),(40,2),(40,3),(40,4),(40,5)
	,(50,1),(50,2),(50,3),(50,4),(50,5),(50,6),(50,7),(50,8),(50,9),(50,10)

INSERT INTO HRefs
VALUES
	(20,2,10,1)
	,(20,3,10,2)
	,(20,4,10,5)
	,(20,5,10,4)
	,(30,1,20,1)
	,(30,2,10,3)
	,(30,4,20,5)
	,(30,5,20,3)
	,(40,1,20,4)
	,(40,2,10,5)
	,(40,3,30,1)
	,(40,4,30,3)
	,(40,5,20,1)
	,(50,1,10,2)
	,(50,2,40,1)
	,(50,3,40,1)
	,(50,5,20,3)
	,(50,6,10,4)
	,(50,7,30,2)
	,(50,8,30,4)
	,(50,9,40,2)
	,(50,10,40,4);


WITH E
AS
(
	SELECT [10] AS A, [20] AS B, [30] AS C, [40] AS [D], E
	FROM
	(
		SELECT HID AS E
			,RefHID, RefHLevel
		FROM HRefs
		WHERE HLevel = 50
	) S
	PIVOT
	(
		MAX(RefHID)
		FOR RefHLevel IN ([10], [20], [30], [40])
	) P
)
,Link1
AS
(
	SELECT
		CASE COALESCE(R.RefHLevel, 0) WHEN 10 THEN R.RefHID ELSE E.A END AS A
		,CASE COALESCE(R.RefHLevel, 0) WHEN 20 THEN R.RefHID ELSE E.B END AS B
		,CASE COALESCE(R.RefHLevel, 0) WHEN 30 THEN R.RefHID ELSE E.C END AS C
		,E.D
		,E.E
	FROM E
		LEFT JOIN HRefs R
			ON E.D = R.HID
				AND R.HLevel = 40
)
,Link2
AS
(
	SELECT
		CASE COALESCE(R.RefHLevel, 0) WHEN 10 THEN R.RefHID ELSE E.A END AS A
		,CASE COALESCE(R.RefHLevel, 0) WHEN 20 THEN R.RefHID ELSE E.B END AS B
		,E.C
		,E.D
		,E.E
	FROM Link1 E
		LEFT JOIN HRefs R
			ON E.C = R.HID
				AND R.HLevel = 30
)
SELECT
	CASE COALESCE(R.RefHLevel, 0) WHEN 10 THEN R.RefHID ELSE E.A END AS A
	,E.B
	,E.C
	,E.D
	,M.HID AS E
FROM HMaster M
	LEFT JOIN Link2 E
		ON M.HID = E.E
	LEFT JOIN HRefs R
		ON E.B = R.HID
			AND R.HLevel = 20
WHERE M.HLevel = 50

jb23
Starting Member

5 Posts

Posted - 2011-09-16 : 03:36:32

Wow. Thank you for the nice PIVOT example.
At first glance, it looks redundant. But I need time to think about it.

Your outer join query looks very nice. Fewer conditions than in my version. It should be faster.
It looks so simple. Many thanks!

Ifor
Aged Yak Warrior

700 Posts

Posted - 2011-09-16 : 05:50:48

I would look at the pivot option.

Once I posted yesterday I realised that the pivot option could be reduced by using recursion but real work intervened.

Here is the ammended query:


WITH AppleRefs
AS
(
	SELECT HLevel, HID, RefHLevel, RefHID
	FROM HRefs
	WHERE HLevel = 50

	UNION ALL
	
	SELECT A.HLevel, A.HID, R.RefHLevel, R.RefHID
	FROM AppleRefs A
		JOIN HRefs R
			ON A.RefHLevel = R.HLevel
				AND A.RefHID = R.HID
)
,ApplePivot
AS
(
	SELECT [10] AS A, [20] AS B, [30] AS C, [40] AS [D], E
	FROM
	(
		SELECT HID AS E
			,RefHID, RefHLevel
		FROM AppleRefs
	) S
	PIVOT
	(
		MAX(RefHID)
		FOR RefHLevel IN ([10], [20], [30], [40])
	) P
)
SELECT
	P.A, P.B, P.C, P.D, M.HID AS E
FROM HMaster M
	LEFT JOIN ApplePivot P
		ON M.HID = P.E
WHERE M.HLevel = 50

jb23
Starting Member

5 Posts

Posted - 2011-09-18 : 11:27:43

Do you think that the pivot version is faster or where is the advantage?

In the table HRefs there you can assign states under gardens, but the gardens should be assigned to states. That should not be possible to make such a mistake.

Ifor
Aged Yak Warrior

700 Posts

Posted - 2011-09-26 : 06:08:55

quote:
Originally posted by jb23

In the table HRefs there you can assign states under gardens, but the gardens should be assigned to states. That should not be possible to make such a mistake.

If you check the DDL you will see there is a constraint to stop this:


	,CONSTRAINT CK_A2SRsRefLevels CHECK(RefHLevel < HLevel)

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources