Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase

Adjacency list / linked list / hierarchical data SELECT Expand / Collapse
Author
Message
Posted Monday, January 7, 2013 11:58 AM


SSC Veteran

SSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC Veteran

Group: General Forum Members
Last Login: Wednesday, November 26, 2014 7:58 AM
Points: 211, Visits: 559
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
Posted Monday, January 7, 2013 12:07 PM


SSCommitted

SSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommitted

Group: General Forum Members
Last Login: Today @ 3:42 AM
Points: 1,943, Visits: 20,180
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
Post #1403802
Posted Monday, January 7, 2013 12:20 PM


SSC Veteran

SSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC Veteran

Group: General Forum Members
Last Login: Wednesday, November 26, 2014 7:58 AM
Points: 211, Visits: 559
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
Posted Monday, January 7, 2013 12:35 PM


SSChampion

SSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampion

Group: General Forum Members
Last Login: Thursday, December 18, 2014 9:58 AM
Points: 13,872, Visits: 9,600
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
Posted Tuesday, January 8, 2013 8:50 AM


SSC Veteran

SSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC Veteran

Group: General Forum Members
Last Login: Wednesday, November 26, 2014 7:58 AM
Points: 211, Visits: 559
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 »

Add to briefcase

Permissions Expand / Collapse