SQL Clone
SQLServerCentral is supported by Redgate
 
Log in  ::  Register  ::  Not logged in
 
 
 


Adjacency list / linked list / hierarchical data SELECT


Adjacency list / linked list / hierarchical data SELECT

Author
Message
sqltung
sqltung
SSC Eights!
SSC Eights! (892 reputation)SSC Eights! (892 reputation)SSC Eights! (892 reputation)SSC Eights! (892 reputation)SSC Eights! (892 reputation)SSC Eights! (892 reputation)SSC Eights! (892 reputation)SSC Eights! (892 reputation)

Group: General Forum Members
Points: 892 Visits: 585
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


J Livingston SQL
J Livingston SQL
SSChampion
SSChampion (12K reputation)SSChampion (12K reputation)SSChampion (12K reputation)SSChampion (12K reputation)SSChampion (12K reputation)SSChampion (12K reputation)SSChampion (12K reputation)SSChampion (12K reputation)

Group: General Forum Members
Points: 12319 Visits: 37592
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
and remember....every day is a school day

sqltung
sqltung
SSC Eights!
SSC Eights! (892 reputation)SSC Eights! (892 reputation)SSC Eights! (892 reputation)SSC Eights! (892 reputation)SSC Eights! (892 reputation)SSC Eights! (892 reputation)SSC Eights! (892 reputation)SSC Eights! (892 reputation)

Group: General Forum Members
Points: 892 Visits: 585
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.
GSquared
GSquared
SSC Guru
SSC Guru (58K reputation)SSC Guru (58K reputation)SSC Guru (58K reputation)SSC Guru (58K reputation)SSC Guru (58K reputation)SSC Guru (58K reputation)SSC Guru (58K reputation)SSC Guru (58K reputation)

Group: General Forum Members
Points: 58521 Visits: 9730
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
sqltung
sqltung
SSC Eights!
SSC Eights! (892 reputation)SSC Eights! (892 reputation)SSC Eights! (892 reputation)SSC Eights! (892 reputation)SSC Eights! (892 reputation)SSC Eights! (892 reputation)SSC Eights! (892 reputation)SSC Eights! (892 reputation)

Group: General Forum Members
Points: 892 Visits: 585
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



Go


Permissions

You can't post new topics.
You can't post topic replies.
You can't post new polls.
You can't post replies to polls.
You can't edit your own topics.
You can't delete your own topics.
You can't edit other topics.
You can't delete other topics.
You can't edit your own posts.
You can't edit other posts.
You can't delete your own posts.
You can't delete other posts.
You can't post events.
You can't edit your own events.
You can't edit other events.
You can't delete your own events.
You can't delete other events.
You can't send private messages.
You can't send emails.
You can read topics.
You can't vote in polls.
You can't upload attachments.
You can download attachments.
You can't post HTML code.
You can't edit HTML code.
You can't post IFCode.
You can't post JavaScript.
You can post emoticons.
You can't post or upload images.

Select a forum

































































































































































SQLServerCentral


Search