Marking Tree Rows as "First" / "Last"

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)

Marking Tree Rows as "First" / "Last"

Author

Topic

Kristen
Test

22859 Posts

Posted - 2010-06-03 : 10:46:11

I need to update a table to indicate which rows are the First / Last branch at that level.

Setting the First seems to be easy - if previous row is at a lower level then the current row is the first.

I'm struggling with Last, particularly when I get to the bottom of the tree and there are no further child branches to reference

In the table, below, there are two data sets - and a DELETE statement which will leave one, or other, for testing.

I've put First / Last on the data to show what it should be, and there are IsFirst / IsLast columns to be set

This will be called frequently, so needs to be as efficient as possible. Its doing my head in trying to work out how to do it!


-- http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=145286

SET NOCOUNT ON

DECLARE	@tblTree TABLE
(
	[Scenario]	int NOT NULL,
	[Sequence]	int NOT NULL,
	[Level]		int NOT NULL,
	[Value]		varchar(10) NOT NULL,

	[First]		varchar(10) NULL,
	[Last]		varchar(10) NULL,

	[IsFirst]	int NULL,
	[IsLast]	int NULL,

	PRIMARY KEY
	(
		[Scenario],
		[Sequence]
	)
)

INSERT INTO @tblTree
(
	[Scenario],
	[Sequence],
	[Level],
	[Value],
	[First],
	[Last]
)
SELECT *
FROM
(
SELECT	[Scenario] = 1, [Sequence] = 1, [Level] = 1, [Value] = '1.1', [First] = 'First', [Last] = '' UNION ALL
SELECT	1, 2, 2, '2.1', 'First', '' UNION ALL
SELECT	1, 3, 3, '3.1', 'First', '' UNION ALL
SELECT	1, 4, 3, '3.2', '', '' UNION ALL
SELECT	1, 5, 4, '4.1', 'First', '' UNION ALL
SELECT	1, 6, 4, '4.2', '', 'Last' UNION ALL
SELECT	1, 7, 3, '3.3', '', 'Last' UNION ALL
SELECT	1, 8, 4, '4.4', 'First', 'Last' UNION ALL
SELECT	1, 9, 2, '2.2', '', '' UNION ALL
SELECT	1, 10, 2, '2.3' , '', 'Last' UNION ALL
SELECT	1, 11, 1, '1.2' , '', 'Last' UNION ALL
--
SELECT	2, 1, 1, '1.1', 'First', '' UNION ALL
SELECT	2, 2, 2, '2.1', 'First', '' UNION ALL
SELECT	2, 3, 3, '3.1', 'First', '' UNION ALL
SELECT	2, 4, 3, '3.2', '', '' UNION ALL
SELECT	2, 5, 4, '4.1', 'First', '' UNION ALL
SELECT	2, 6, 4, '4.2', '', 'Last' UNION ALL
SELECT	2, 7, 3, '3.3', '', 'Last' UNION ALL
SELECT	2, 8, 4, '4.4', 'First', 'Last' UNION ALL
SELECT	2, 9, 2, '2.2', '', '' UNION ALL
SELECT	2, 10, 2, '2.3' , '', 'Last' UNION ALL
SELECT	2, 11, 3, '3.3' , 'First', 'Last' UNION ALL
SELECT	2, 12, 4, '4.5' , 'First', 'Last' UNION ALL
SELECT	2, 13, 5, '5.1' , 'First', 'Last' UNION ALL
SELECT	2, 14, 1, '1.2' , '', 'Last'
) AS T
ORDER BY [Sequence]

DELETE	D
FROM	@tblTree AS D
WHERE	[Scenario] <> 1	-- Set to Scenario you want to test

-- This seems to work for "first"
UPDATE	T
SET	[IsFirst] = 1
FROM	@tblTree AS T
	LEFT OUTER JOIN @tblTree AS T_Prev
		ON T_Prev.[Sequence] = T.[Sequence] - 1
WHERE	   T_Prev.[Sequence] IS NULL	-- First row
	OR T_Prev.[Level] < T.[Level]

SELECT
	[IsFirst],
	[IsLast],
	[First],
	[Last],
	[Level],
	REPLICATE('..', [Level]-1) + [Value]
FROM	@tblTree
ORDER BY [Sequence]

SET NOCOUNT OFF

Kristen
Test

22859 Posts

Posted - 2010-06-03 : 11:04:21

I wonder if this is good enough?


UPDATE	T
SET	[IsLast] = 1
FROM	@tblTree AS T
	LEFT OUTER JOIN @tblTree AS T_Next
		ON T_Next.[Sequence] = T.[Sequence] + 1
WHERE	   T_Next.[Sequence] IS NULL	-- Last row
	OR T_Next.[Level] < T.[Level]
	OR NOT EXISTS
	(
		SELECT	*
		FROM	@tblTree AS T1
		WHERE	    T1.[Sequence] > T.[Sequence]	-- Following items
			AND T1.[Level] = T.[Level]		-- Same level
	)

lazerath
Constraint Violating Yak Guru

343 Posts

Posted - 2010-06-03 : 20:08:16

I'm a sucker for hierarchies, and I haven't seen this approach before, so I pretty much had to find an elegant, over thought approach. :-)


-----------------------------------------------------
-- Your initialization code
-----------------------------------------------------
SET NOCOUNT ON

DECLARE	@tblTree TABLE
(
	[Scenario]	int NOT NULL,
	[Sequence]	int NOT NULL,
	[Level]		int NOT NULL,
	[Value]		varchar(10) NOT NULL,

	[First]		varchar(10) NULL,
	[Last]		varchar(10) NULL,

	[IsFirst]	int NULL,
	[IsLast]	int NULL
	PRIMARY KEY
	(
		[Scenario],
		[Sequence]
	)
)

INSERT INTO @tblTree
(
	[Scenario],
	[Sequence],
	[Level],
	[Value],
	[First],
	[Last]
)
SELECT *
FROM
(
SELECT	[Scenario] = 1, [Sequence] = 1, [Level] = 1, [Value] = '1.1', [First] = 'First', [Last] = '' UNION ALL
SELECT	1, 2, 2, '2.1', 'First', '' UNION ALL
SELECT	1, 3, 3, '3.1', 'First', '' UNION ALL
SELECT	1, 4, 3, '3.2', '', '' UNION ALL
SELECT	1, 5, 4, '4.1', 'First', '' UNION ALL
SELECT	1, 6, 4, '4.2', '', 'Last' UNION ALL
SELECT	1, 7, 3, '3.3', '', 'Last' UNION ALL
SELECT	1, 8, 4, '4.4', 'First', 'Last' UNION ALL
SELECT	1, 9, 2, '2.2', '', '' UNION ALL
SELECT	1, 10, 2, '2.3' , '', 'Last' UNION ALL
SELECT	1, 11, 1, '1.2' , '', 'Last' UNION ALL
--
SELECT	2, 1, 1, '1.1', 'First', '' UNION ALL
SELECT	2, 2, 2, '2.1', 'First', '' UNION ALL
SELECT	2, 3, 3, '3.1', 'First', '' UNION ALL
SELECT	2, 4, 3, '3.2', '', '' UNION ALL
SELECT	2, 5, 4, '4.1', 'First', '' UNION ALL
SELECT	2, 6, 4, '4.2', '', 'Last' UNION ALL
SELECT	2, 7, 3, '3.3', '', 'Last' UNION ALL
SELECT	2, 8, 4, '4.4', 'First', 'Last' UNION ALL
SELECT	2, 9, 2, '2.2', '', '' UNION ALL
SELECT	2, 10, 2, '2.3' , '', 'Last' UNION ALL
SELECT	2, 11, 3, '3.3' , 'First', 'Last' UNION ALL
SELECT	2, 12, 4, '4.5' , 'First', 'Last' UNION ALL
SELECT	2, 13, 5, '5.1' , 'First', 'Last' UNION ALL
SELECT	2, 14, 1, '1.2' , '', 'Last'
) AS T
ORDER BY Scenario,[Sequence];

-----------------------------------------------------
-- Hierarchy Code
-----------------------------------------------------
WITH			cte1
AS
(
SELECT 			ROW_NUMBER() OVER(ORDER BY t1.Scenario, t1.Sequence) AS RowPK,
				t1.Scenario,
				t1.Sequence,
				t1.Level,
				MIN(t2.Sequence) AS NextSequence,
				t1.Value,
				t1.First,
				t1.Last,
				t1.IsFirst,
				t1.IsLast
FROM			@tblTree
AS				t1
LEFT JOIN		@tblTree
AS				t2
ON				t1.Scenario
=				t2.Scenario
AND				t1.Sequence
<				t2.Sequence
AND				t1.Level
>=				t2.Level
GROUP BY		t1.Scenario,
				t1.Sequence,
				t1.Level,
				t1.Value,
				t1.First,
				t1.Last,
				t1.IsFirst,
				t1.IsLast
)
,				cteTraverse
AS
(
SELECT 			t1.RowPK,
				t1.Scenario,
				t1.Sequence,
				t1.Level,
				t1.NextSequence,
				t1.Value,
				CONVERT(BIGINT,NULL) AS ParentPK,
				t1.First,
				t1.Last
FROM			cte1
AS				t1
WHERE			t1.Level
=				1
UNION ALL
SELECT			t1.RowPK,
				t1.Scenario,
				t1.Sequence,
				t1.Level,
				t1.NextSequence,
				t1.Value,
				t2.RowPK AS ParentPK,
				t1.First,
				t1.Last
FROM			cte1
AS				t1
JOIN			cteTraverse
AS				t2
ON				t1.Scenario
=				t2.Scenario
AND				t1.Sequence
>				t2.Sequence
AND				t1.Sequence
<				COALESCE(t2.NextSequence,t1.Sequence+1)
AND				t1.Level
=				t2.Level+1

)
,				cteTest
AS
(
SELECT			*,
				CASE ROW_NUMBER() OVER(PARTITION BY t1.Scenario, t1.ParentPK ORDER BY t1.Sequence ASC ) WHEN 1 THEN 1 END AS isFirst,
				CASE ROW_NUMBER() OVER(PARTITION BY t1.Scenario, t1.ParentPK ORDER BY t1.Sequence DESC) WHEN 1 THEN 1 END AS isLast
FROM			cteTraverse
AS				t1
)
SELECT			*
FROM			cteTest
AS				t
/*
WHERE NOT		(
				t.First
=				CASE t.isFirst WHEN 1 THEN 'First' ELSE '' END
AND				t.Last
=				CASE t.isLast WHEN 1 THEN 'Last' ELSE '' END
				)
--*/
ORDER BY		t.Scenario,
				t.Sequence;


SET NOCOUNT OFF

You don't need cteTest, just the part of it that does isFirst and isLast. With cteTest, you can just uncomment the where clause at the end to see that it works.

I haven't performance tested your code, but I'd hazard a guess that this would outperform what you have on large datasets (with proper indexes). I could be wrong, so if you test it let me know.

Kristen
Test

22859 Posts

Posted - 2010-06-04 : 02:22:01

"I pretty much had to find an elegant, over thought approach"

Hehehe ... thanks Lazerath, I'm out of the office for a couple of days but will try it next week.

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources