# Converting an adjacency list model to a nested set model

## Another way of representing trees in SQL is to show them as nested sets. Here's how.

As you will recall from my previous article, the usual example of a tree structure in SQL books is called an adjacency...

list model and it looks like this:

``` CREATE TABLE Personnel (emp CHAR(10) NOT NULL PRIMARY KEY, boss CHAR(10) DEFAULT NULL REFERENCES Personnel(emp)); Personnel emp boss =================== 'Albert' 'NULL' 'Bert' 'Albert' 'Chuck' 'Albert' 'Donna' 'Chuck' 'Eddie' 'Chuck' 'Fred' 'Chuck'
```

Another way of representing trees is to show them as nested sets. Since SQL is a set oriented language, this is a better model than the usual adjacency list approach you see in most text books. Let us define a simple Personnel table like this, ignoring the left (lft) and right (rgt) columns for now. This problem is always given with a column for the employee and one for his boss in the textbooks. This table without the lft and rgt columns is called the adjacency list model, after the graph theory technique of the same name; the pairs of nodes are adjacent to each other.

``` CREATE TABLE Personnel (emp CHAR(10) NOT NULL PRIMARY KEY, lft INTEGER NOT NULL UNIQUE CHECK (lft > 0), rgt INTEGER NOT NULL UNIQUE CHECK (rgt > 1), CONSTRAINT order_okay CHECK (lft < rgt) ); Personnel emp lft rgt ====================== 'Albert' 1 12 'Bert' 2 3 'Chuck' 4 11 'Donna' 5 6 'Eddie' 7 8 'Fred' 9 10
```

The organizational chart would look like this as a directed graph:

``` Albert (1,12) / \ / \ Bert (2,3) Chuck (4,11) / | \ / | \ / | \ / | \ Donna (5,6) Eddie 7,8) Fred (9,10)
```

To show a tree as nested sets, replace the nodes with ovals, then nest subordinate ovals inside each other. The root will be the largest oval and will contain every other node. The leaf nodes will be the innermost ovals with nothing else inside them and the nesting will show the hierarchical relationship. The rgt and lft columns (I cannot use the reserved words LEFT and RIGHT in SQL) are what shows the nesting.

To convert the graph into a nested sets model think of a little worm crawling along the tree. The worm starts at the top, the root, makes a complete trip around the tree. When he comes to a node, he puts a number in the cell on the side that he is visiting and increments his counter. Each node will get two numbers, one of the right side and one for the left. Computer Science majors will recognize this as a modified preorder tree traversal algorithm.

The code for implementing this in T-SQL is a straight forward stack implementation. First, let's load up some data into a tree table and then create a stack table. I will explain how the stack works in a minute.

``` -- Tree holds the adjacency model CREATE TABLE Tree (emp CHAR(10) NOT NULL, boss CHAR(10)); -- insert the sample data for testing INSERT INTO Tree VALUES ('Albert', NULL); INSERT INTO Tree VALUES ('Bert', 'Albert'); INSERT INTO Tree VALUES ('Chuck', 'Albert'); INSERT INTO Tree VALUES ('Donna', 'Chuck'); INSERT INTO Tree VALUES ('Eddie', 'Chuck'); INSERT INTO Tree VALUES ('Fred', 'Chuck'); -- Stack starts empty, will holds the nested set model CREATE TABLE Stack (stack_top INTEGER NOT NULL, emp CHAR(10) NOT NULL, lft INTEGER, rgt INTEGER);
```

Each row of the stack holds the nested set (lft, rgt) pair, the node value (emp) and an integer that represents the current top of the stack as an integer. When the stack_top is positive, something has been pushed onto the stack. When the stack_top is negative, it has been popped off the stack.

The algorithm is pretty straight forward, though there are some tricks about representing a stack in T-SQL. Here is what we know:

1. We will do (2 * (SELECT COUNT(*) FROM Tree)) operation to build the (lft, rgt) pairs for each node. We need a general counter for this.
2. When a node is pushed on the stack, we give it a lft number and increment the counter.
3. When a node is popped from the stack, we give it a rgt number and increment the counter.
4. We start at the root. Each nodes goes on and off the stack once and only once.
5. We look at the top of the stack and push the youngest subordinate of that node onto the stack
6. When the node on the top of stack is a leaf node or a node without "un-popped" subordinates back in the tree, pop it off the stack.

Here is the code in T-SQL:

``` DROP TABLE Stack; CREATE TABLE Stack (stack_top INTEGER NOT NULL, child VARCHAR(10) NOT NULL, lft INTEGER NOT NULL, rgt INTEGER); -- you can create optional indexes on stack_top and child columns BEGIN DECLARE @lft_rgt INTEGER, @stack_pointer INTEGER, @max_lft_rgt INTEGER; SET @max_lft_rgt = 2 * (SELECT COUNT(*) FROM Tree); INSERT INTO Stack SELECT 1, child, 1, @max_lft_rgt FROM Tree WHERE parent IS NULL; SET @lft_rgt = 2; SET @Stack_pointer = 1; DELETE FROM Tree WHERE parent IS NULL; -- The Stack is now loaded and ready to use WHILE (@lft_rgt < @max_lft_rgt) BEGIN IF EXISTS (SELECT * FROM Stack AS S1, Tree AS T1 WHERE S1.child = T1.parent AND S1.stack_top = @stack_pointer) BEGIN -- push when stack_top has subordinates and set lft value INSERT INTO Stack SELECT (@stack_pointer + 1), MIN(T1.child), @lft_rgt, NULL FROM Stack AS S1, Tree AS T1 WHERE S1.child = T1.parent AND S1.stack_top = @stack_pointer; -- remove this row from Tree DELETE FROM Tree WHERE child = (SELECT child FROM Stack WHERE stack_top = @stack_pointer + 1); SET @stack_pointer = @stack_pointer + 1; END -- push ELSE BEGIN -- pop the Stack and set rgt value UPDATE Stack SET rgt = @lft_rgt, stack_top = -stack_top WHERE stack_top = @stack_pointer SET @stack_pointer = @stack_pointer - 1; END; -- pop SET @lft_rgt = @lft_rgt + 1; END; -- if END; -- while SELECT * FROM Stack ORDER BY lft; Stack stack_top emp lft rgt ----------------------------- -1 Albert 1 12 -2 Bert 2 3 -2 Chuck 4 11 -3 Donna 5 6 -3 Eddie 7 8 -3 Fred 9 10
```

Note that the leftover stack_top numbers are the negatives of the depth of their node in the original tree. Also, notice that the original tree is being destroyed in this procedure; you might want to save and use a copy in a temporary table instead.

Joe Celko is author of SQL for Smarties: Advanced SQL Programming (Morgan-Kaufmann, 1999).

This was last published in February 2002

## Content

Find more PRO+ content and other member only offers, here.

#### Start the conversation

Send me notifications when other members comment.

## SearchDataManagement

• ### Cross-platform integration, data preparation process grows in cloud

While cloud computing may be convenient and more cost-effective for users, it can also lead to new challenges and requirements in...

• ### Graph data model cements tight relationships between data elements

Graph databases can help define and discover relationships between entities -- and offer increased flexibility and better ...

• ### Microsoft SQL Server 2016 relational DBMS overview

Microsoft SQL Server 2016 for Windows comes in four editions, with updates that include a new stretch database feature, Polybase,...

• ### Difficulties in hiring data scientists can waylay analytics efforts

Advanced analytics software provides a lot of functionality, but finding skilled data scientists who can use the available tools ...

• ### Creative projects leave people guessing about future impact of AI

A push is underway to write creative AI algorithms that can engage in music, film and design projects. So far, they have ...

## SearchSAP

• ### Hillarys Blinds speeds SAP S/4HANA upgrade with Panaya tool

Hillarys Blinds, a veteran of several SAP ECC upgrades, completed a move to SAP S/4HANA in just six months using the Panaya ...

• ### Charlotte Hornets build data warehouse with SAP HANA-based Phizzle

The Charlotte Hornets implemented Phizzle FanTracker, an SAP HANA-based platform, to consolidate fan records from many data ...

• ### Does SAP ONE Support Launchpad make SAP support any easier to use?

The new Fiori user experience makes it easier to access applications and support services, but product-specific support still ...

## SearchSQLServer

• ### SQL Server on Linux signals Microsoft's changing development landscape

Expert Joey D'Antoni explains what SQL Server on Linux and the addition of Enterprise Edition features to Standard Edition say ...

• ### How to get the most out of virtual SQL Server with Microsoft Hyper-V

SQL Server is a CPU-intensive technology, which can make it tricky to run in a virtualized environment. Keep your SQL Server ...

• ### Microsoft previews SQL Server on Linux, opens features across editions

Microsoft looks to broaden the horizons of SQL Server, as it moves some Enterprise features to Standard Edition and issues the ...

## TheServerSide

• ### Docker instances become the new norm and adoption goes mainstream

Many organizations use Docker instances for many reasons, although security, data storage and monolithic fears remain barriers to...

• ### How to turn your DevOps failures into ALM successes

Doing the right thing doesn't always mean you're doing things right. But don't fret, because short-term DevOps failures can mean ...

• ### From chatbots to IBM's Watson: How software deals with conversational language

The next big thing in software development is conquering the conversational language development hurdle. Here's how the big ...

## SearchDataCenter

• ### Build a data center shutdown procedure to prepare for the worst

A data center shutdown checklist helps IT teams focus on backup, testing and system verification before pulling the plug and ...

• ### Telcos purge colocation data centers, open door to neutral connections

Enterprise customers in Verizon and CenturyLink's colocation data centers should expect better cloud and network connection ...

• ### IT slowly embraces composable infrastructure

If there will be a way to make an enterprise data center as efficient and optimized as cloud computing, composable infrastructure...

## SearchContentManagement

• ### Microsoft brings its flavor of AI with Microsoft Cognitive Services

Microsoft Cognitive Services has a new array of APIs to make it easier to scan text, video and audio data and to bring ...

• ### Users prefer Office 365 suite collaboration features over SharePoint

Users don't want to jump through hoops, and they want applications to work on mobile devices. Those needs may kill traditional ...

• ### What new SharePoint features to expect in the next 12 months

Now that Microsoft is developing its SharePoint features, there are new feature rollouts all the time. Here's a rundown of the ...

## SearchFinancialApplications

• ### Foot Locker seeks a good fit with Infor pre-employment assessment tool

Foot Locker is among a growing number of companies using cloud-based pre-hire assessment to screen job applicants for character ...

• ### Project planning for a new corporate performance management system

A corporate performance management system touches most aspects of any business. You need a carefully thought-out plan to ensure a...

• ### No one-size-fits-all strategy for cloud ERP software migration

Experts say a cloud ERP transition plan will vary according to a variety of factors, from company size to an organization's ...

Close