Adjacency list / linked list / hierarchical data SELECT

SQLServerCentral is supported by Red Gate Software Ltd.

Popular Topics

Home

Members

Calendar

Who's On

Home » SQL Server 2008 » SQL Server 2008 - General » Adjacency list / linked list / hierarchical...

Adjacency list / linked list / hierarchical data SELECT

Rate Topic

Display Mode

Topic Options

Author

Message

sqlgreg

Posted Monday, January 07, 2013 11:58 AM

SSC Veteran

Group: General Forum Members
Last Login: Friday, May 31, 2013 8:27 AM
Points: 211, Visits: 552

I'm working on a SELECT statement to get all employees that are under the CEO Al Knowing. Ultimately these tables won't be super large (millions of rows), but performance is pretty important.

What I have currently requires that I run a recursive function for EVERY row in Employee_Hierarchy, and that doesn't seem like a good idea! There must be a better way, given the table structure.

My code is as follows:

USE [Sandbox]
GO

SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
SET ANSI_PADDING ON
GO
CREATE TABLE [dbo].[Employee](
	[employee_id] [int] NOT NULL,
	[employee_first_name] [nvarchar](50) NOT NULL,
	[employee_last_name] [nvarchar](50) NOT NULL,
	[employee_title] [varchar](50) NULL,
 CONSTRAINT [PK_Employee] PRIMARY KEY CLUSTERED 
(
	[employee_id] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]
GO
SET ANSI_PADDING OFF
GO
INSERT [dbo].[Employee] ([employee_id], [employee_first_name], [employee_last_name], [employee_title]) VALUES (1, N'Al', N'Knowing', N'CEO')
INSERT [dbo].[Employee] ([employee_id], [employee_first_name], [employee_last_name], [employee_title]) VALUES (2, N'Thomas', N'Funk', N'VP')
INSERT [dbo].[Employee] ([employee_id], [employee_first_name], [employee_last_name], [employee_title]) VALUES (3, N'Trillian', N'Folklore', N'Senior Fancypants')
INSERT [dbo].[Employee] ([employee_id], [employee_first_name], [employee_last_name], [employee_title]) VALUES (4, N'Godwin', N'Nuggit', N'Head of Maintenance')
INSERT [dbo].[Employee] ([employee_id], [employee_first_name], [employee_last_name], [employee_title]) VALUES (5, N'John', N'Crispy', N'Janitorial Associate')
INSERT [dbo].[Employee] ([employee_id], [employee_first_name], [employee_last_name], [employee_title]) VALUES (6, N'Magenta', N'Black', N'Graphic Artist')
INSERT [dbo].[Employee] ([employee_id], [employee_first_name], [employee_last_name], [employee_title]) VALUES (7, N'Lenny ', N'Listless', N'Head of Marketing')
INSERT [dbo].[Employee] ([employee_id], [employee_first_name], [employee_last_name], [employee_title]) VALUES (8, N'Elizabeth', N'Quintessential', N'Business Analyst')
INSERT [dbo].[Employee] ([employee_id], [employee_first_name], [employee_last_name], [employee_title]) VALUES (9, N'Menachem', N'Li', N'CIO')
INSERT [dbo].[Employee] ([employee_id], [employee_first_name], [employee_last_name], [employee_title]) VALUES (10, N'Lik', N'Chu', N'Director of Development')
INSERT [dbo].[Employee] ([employee_id], [employee_first_name], [employee_last_name], [employee_title]) VALUES (11, N'Philip ', N'Factor', N'DBA')
INSERT [dbo].[Employee] ([employee_id], [employee_first_name], [employee_last_name], [employee_title]) VALUES (12, N'Topanga', N'Daniels', N'CEO')
INSERT [dbo].[Employee] ([employee_id], [employee_first_name], [employee_last_name], [employee_title]) VALUES (13, N'Terry', N'Cherry', N'VP - Operations')
INSERT [dbo].[Employee] ([employee_id], [employee_first_name], [employee_last_name], [employee_title]) VALUES (14, N'Shalom', N'Slalom', N'Activities Director')
INSERT [dbo].[Employee] ([employee_id], [employee_first_name], [employee_last_name], [employee_title]) VALUES (15, N'Anakin', N'Groundflyer', N'Web Dude')
INSERT [dbo].[Employee] ([employee_id], [employee_first_name], [employee_last_name], [employee_title]) VALUES (16, N'Crispin', N'Quent', N'Associate')
INSERT [dbo].[Employee] ([employee_id], [employee_first_name], [employee_last_name], [employee_title]) VALUES (17, N'Gary', N'Weinrib', N'Resident Composer')
INSERT [dbo].[Employee] ([employee_id], [employee_first_name], [employee_last_name], [employee_title]) VALUES (18, N'Joseph', N'Silky', N'Manager')

SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
CREATE TABLE [dbo].[Employee_Hierarchy](
	[boss_id] [int] NOT NULL,
	[employee_id] [int] NOT NULL,
 CONSTRAINT [PK_Employee_Hierarchy] PRIMARY KEY CLUSTERED 
(
	[boss_id] ASC,
	[employee_id] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]
GO
INSERT [dbo].[Employee_Hierarchy] ([boss_id], [employee_id]) VALUES (1, 2)
INSERT [dbo].[Employee_Hierarchy] ([boss_id], [employee_id]) VALUES (1, 9)
INSERT [dbo].[Employee_Hierarchy] ([boss_id], [employee_id]) VALUES (2, 3)
INSERT [dbo].[Employee_Hierarchy] ([boss_id], [employee_id]) VALUES (2, 4)
INSERT [dbo].[Employee_Hierarchy] ([boss_id], [employee_id]) VALUES (2, 7)
INSERT [dbo].[Employee_Hierarchy] ([boss_id], [employee_id]) VALUES (3, 6)
INSERT [dbo].[Employee_Hierarchy] ([boss_id], [employee_id]) VALUES (4, 5)
INSERT [dbo].[Employee_Hierarchy] ([boss_id], [employee_id]) VALUES (9, 10)
INSERT [dbo].[Employee_Hierarchy] ([boss_id], [employee_id]) VALUES (10, 8)
INSERT [dbo].[Employee_Hierarchy] ([boss_id], [employee_id]) VALUES (10, 11)
INSERT [dbo].[Employee_Hierarchy] ([boss_id], [employee_id]) VALUES (12, 13)
INSERT [dbo].[Employee_Hierarchy] ([boss_id], [employee_id]) VALUES (13, 14)
INSERT [dbo].[Employee_Hierarchy] ([boss_id], [employee_id]) VALUES (13, 18)
INSERT [dbo].[Employee_Hierarchy] ([boss_id], [employee_id]) VALUES (14, 17)
INSERT [dbo].[Employee_Hierarchy] ([boss_id], [employee_id]) VALUES (18, 15)
INSERT [dbo].[Employee_Hierarchy] ([boss_id], [employee_id]) VALUES (18, 16)

SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
-- =============================================
-- Author:		sqlgreg
-- Create date: 1/7/2013
-- Description:	
-- select dbo.GetTopDude(10)
-- =============================================
CREATE FUNCTION [dbo].[GetTopDude] 
(
	@Employee_ID int
)
RETURNS int
AS
BEGIN
	DECLARE @CurrentValue int
		, @LastValue int
	
	SELECT @CurrentValue = boss_id
	FROM Employee_Hierarchy
	WHERE employee_id = @Employee_ID
	
	WHILE @CurrentValue is not null BEGIN
		SET @LastValue = @CurrentValue
		SELECT @CurrentValue = dbo.GetTopDude(@CurrentValue)	
	END

	RETURN @LastValue
END
GO

ALTER TABLE [dbo].[Employee_Hierarchy]  WITH CHECK ADD  CONSTRAINT [FK_Employee_Hierarchy_Employee] FOREIGN KEY([employee_id])
REFERENCES [dbo].[Employee] ([employee_id])
GO
ALTER TABLE [dbo].[Employee_Hierarchy] CHECK CONSTRAINT [FK_Employee_Hierarchy_Employee]
GO

ALTER TABLE [dbo].[Employee_Hierarchy]  WITH CHECK ADD  CONSTRAINT [FK_Employee_Hierarchy_Employee2] FOREIGN KEY([boss_id])
REFERENCES [dbo].[Employee] ([employee_id])
GO
ALTER TABLE [dbo].[Employee_Hierarchy] CHECK CONSTRAINT [FK_Employee_Hierarchy_Employee2]
GO

.. and some uses of the function here:

SELECT boss_id
	, employee_id
	, dbo.GetTopDude(employee_id) as top_dude_id
FROM Employee_Hierarchy

SELECT B.employee_first_name + ' ' + B.employee_last_name + ', ' + B.employee_title as boss
	, E.employee_first_name + ' ' + E.employee_last_name + ', ' + E.employee_title as employee		
	, TD.employee_first_name + ' ' + TD.employee_last_name + ', ' + TD.employee_title as top_dude
FROM Employee_Hierarchy H
INNER JOIN Employee E
ON H.employee_id = E.employee_id
INNER JOIN Employee B
ON H.employee_id = B.employee_id
INNER JOIN Employee TD
ON dbo.GetTopDude(H.employee_id) = TD.employee_id

Post #1403795

J Livingston SQL

Posted Monday, January 07, 2013 12:07 PM

UDP Broadcaster

Group: General Forum Members
Last Login: Today @ 5:45 AM
Points: 1,472, Visits: 14,595

further reading here may give you some ideas

http://www.sqlservercentral.com/articles/Hierarchy/94040/

http://www.sqlservercentral.com/articles/T-SQL/94570/

__________________________________________________________________
you can lead a user to data....but you cannot make them think !
__________________________________________________________________

Post #1403802

sqlgreg

Posted Monday, January 07, 2013 12:20 PM

SSC Veteran

Group: General Forum Members
Last Login: Friday, May 31, 2013 8:27 AM
Points: 211, Visits: 552

Thanks for the links. Jeff knows what he's talkin' 'bout! If I get some time this afternoon (or later), I will dig further into these.

Post #1403807

GSquared

Posted Monday, January 07, 2013 12:35 PM

SSCoach

Group: General Forum Members
Last Login: 2 days ago @ 1:45 PM
Points: 15,442, Visits: 9,572

There's a lot of data out there about how to build and maintain hierarchies in SQL Server.

First question is, are you using SQL 2008, as per the forum you posted in, or a prior version of SQL Server?

Connected to that, if you are using SQL 2008, is your hierarchy likely to go more than 400 levels deep? (This is rare, but does occur in multi-level-marketing.)

If the answers are "yes" on SQL 2008 and "no" on 400+ levels deep, then seriously consider switching to the HierarchyID datatype instead of using an adjacency list.

If the first answer is "no" or the second is "yes", consider adding a "Nested Sets Hierarchy" to the data. You'll still want to keep your adjacency list, for ease-of-updates, but you'll want to add in nested sets. Bing/Google/whatever "nested sets hierarchies" and you'll find a ton of data on the subject.

Jeff's articles, that J Livingston SQL posted links to, are good, but they assume you already know your way around hierarchies, particularly adjacency hierarchies. What they really have is a clever way to convert adjacency to nested sets quickly. (One of my hierarchies articles actually has a faster method of doing the same thing. Links to that in the discussion on Jeff's articles.)

If you are stuck with adjacency, look up "SQL Server recursive CTE" on your favorite search engine. The MSDN articles on it tell you how to query an adjacency list without having to build a recursive UDF.

- Gus "GSquared", RSVP, OODA, MAP, NMVP, FAQ, SAT, SQL, DNA, RNA, UOI, IOU, AM, PM, AD, BC, BCE, USA, UN, CF, ROFL, LOL, ETC
Property of The Thread

"Nobody knows the age of the human race, but everyone agrees it's old enough to know better." - Anon

Post #1403817

sqlgreg

Posted Tuesday, January 08, 2013 8:50 AM

SSC Veteran

Group: General Forum Members
Last Login: Friday, May 31, 2013 8:27 AM
Points: 211, Visits: 552

Yup, the recursive CTE gave me what was needed. I needed to be able to get one particular Top Dude's descendents (employees), and this worked ok:

USE Sandbox;
GO

-- 1 and 12 are the top dudes, and we want to be able to get each's tree separately
DECLARE @TopDude BIGINT;
SET @TopDude = 12;	

WITH DirectReports (boss_id, employee_id, [level])
AS
(
	-- Anchor member definition
    SELECT e.boss_id, e.employee_id, 
        0 AS [level]
    FROM dbo.Employee_Hierarchy AS e
    --WHERE boss_id IS NULL
    WHERE boss_id = 0
    and employee_id = @TopDude
    UNION ALL
	-- Recursive member definition
    SELECT e.boss_id, e.employee_id,
        [level] + 1
    FROM dbo.Employee_Hierarchy AS e
    INNER JOIN DirectReports AS d
        ON e.boss_id = d.employee_id
)
-- Statement that executes the CTE
SELECT R.boss_id
	, B.employee_first_name + ' ' + B.employee_last_name + ', ' + B.employee_title as boss
	, R.employee_id
	, E.employee_first_name + ' ' + E.employee_last_name + ', ' + E.employee_title as employee 
	, [level]
FROM DirectReports R
INNER JOIN dbo.Employee E
ON R.employee_id = E.employee_id
LEFT JOIN Employee B
ON R.boss_id = B.employee_id

and here's the DDL for Employee_Hierarchy:

USE [Sandbox]
GO

SET ANSI_NULLS ON
GO

SET QUOTED_IDENTIFIER ON
GO

CREATE TABLE [dbo].[Employee_Hierarchy](
	[employee_hierarchy_id] [int] IDENTITY(1,1) NOT NULL,
	[employee_id] [int] NOT NULL,
	[boss_id] [int] NULL,
 CONSTRAINT [PK_Employee_Hierarchy] PRIMARY KEY NONCLUSTERED 
(
	[employee_hierarchy_id] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]

GO

ALTER TABLE [dbo].[Employee_Hierarchy]  WITH CHECK ADD  CONSTRAINT [FK_Employee_Hierarchy_Employee] FOREIGN KEY([boss_id])
REFERENCES [dbo].[Employee] ([employee_id])
GO

ALTER TABLE [dbo].[Employee_Hierarchy] CHECK CONSTRAINT [FK_Employee_Hierarchy_Employee]
GO

ALTER TABLE [dbo].[Employee_Hierarchy]  WITH CHECK ADD  CONSTRAINT [FK_Employee_Hierarchy_Employee_Hierarchy] FOREIGN KEY([employee_hierarchy_id])
REFERENCES [dbo].[Employee_Hierarchy] ([employee_hierarchy_id])
GO

ALTER TABLE [dbo].[Employee_Hierarchy] CHECK CONSTRAINT [FK_Employee_Hierarchy_Employee_Hierarchy]
GO

ALTER TABLE [dbo].[Employee_Hierarchy]  WITH CHECK ADD  CONSTRAINT [FK_Employee_Hierarchy_Employee2] FOREIGN KEY([employee_id])
REFERENCES [dbo].[Employee] ([employee_id])
GO

ALTER TABLE [dbo].[Employee_Hierarchy] CHECK CONSTRAINT [FK_Employee_Hierarchy_Employee2]
GO

CREATE UNIQUE CLUSTERED INDEX [UIX_Employee_Hierarchy] ON [dbo].[Employee_Hierarchy] 
(
	[employee_id] ASC,
	[boss_id] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
GO

Post #1404294

« Prev Topic | Next Topic »

Permissions