Problem solve Get help with specific problems with your technologies, process and projects.

# 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).

## SearchDataManagement

• ### Oracle brings GoldenGate data integration service to cloud

Oracle is making its GoldenGate real time data technology available on its second-generation Oracle Cloud Infrastructure platform...

• ### Era Software raises \$15.25M for enterprise data management

The startup that began as the EraDB time series database is advancing its efforts with new funding and a cloud service for its ...

• ### Dgraph GraphQL database users detail graph use cases

Graph DB vendor Dgraph Labs is expanding its AWS cloud footprint with new regions and adding change data capture capabilities in ...

• ### TigerGraph unveils support for GCP, adds new connectors

Graph database vendor TigerGraph unveiled support for Google Cloud and new connectors to Snowflake and Tableau on April 21 during...

• ### Startup Veezoo emerges from stealth with NLQ-based platform

Aiming to be 'Siri for enterprises,' an analytics startup emerged from stealth with a platform that enables users to interact ...

• ### 15 data science tools to consider using in 2021

Numerous tools are available for data science applications. Read about 15, including their features, capabilities and uses, to ...

## SearchSAP

• ### S/4HANA Cloud SaaS ERP: Buying team overview

SAP's multi-tenant SaaS ERP, S/4HANA Cloud, is a viable choice for companies that need ease in their infrastructure management. ...

• ### SAP forms financial services partnership with Dediq

SAP and financial industry investment firm Dediq are forming a new business unit to develop applications that help banks and ...

• ### Unpatched applications threaten SAP security

Cyberattacks are a significant threat to unpatched, unprotected SAP applications, according to a new threat intelligence report ...

## SearchSQLServer

• ### SQL Server database design best practices and tips for DBAs

Good database design is a must to meet processing needs in SQL Server systems. In a webinar, consultant Koen Verbeeck offered ...

• ### SQL Server in Azure database choices and what they offer users

SQL Server databases can be moved to the Azure cloud in several different ways. Here's what you'll get from each of the options ...

• ### Using a LEFT OUTER JOIN vs. RIGHT OUTER JOIN in SQL

In this book excerpt, you'll learn LEFT OUTER JOIN vs. RIGHT OUTER JOIN techniques and find various examples for creating SQL ...

## TheServerSide.com

• ### Incorporate diversity and inclusion in technology design

DEI in technology is about more than creating a diverse workplace. We talked to a few DEI professionals about how teams build ...

• ### Microsoft previews OpenJDK distro to the delight of devs

In a move meant to attract more Java developers to its Azure cloud and further support the Java community, Microsoft launched a ...

• ### Supreme Court ruling on Java APIs eases developer worries

Now that the Supreme Court has ruled for Google over Oracle in their high-stakes copyright battle over Java APIs, developers can ...

## SearchDataCenter

• ### Nvidia SDK simulates quantum computing circuits on GPU systems

Nvidia edged its way into the quantum computing market with an SDK that simulates quantum circuits by adding horsepower to ...

• ### Programmable processor technology for next-gen data centers

The right processing technology can benefit your data center. Learn about advancements in CPU technologies, recent vendor ...

• ### Data processing units accelerate infrastructure performance

DPUs often run on networking packets to move information in the data center, instead of supporting processing workflows. Get an ...

## SearchContentManagement

• ### Hyland gets digital asset management tech with Nuxeo buy

By acquiring a smaller competitor's digital asset management platform, Hyland looks to build on its 2020 purchase of Alfresco, ...

• ### OpenText releases Cloud Editions content services updates

OpenText CE 21.2 includes federated document compliance that extends to Microsoft Office 365, along with a revamped content ...

As the pandemic disrupts paper workflows, Adobe courts small business users with simple webforms, digital signatures and payments...

## SearchHRSoftware

• ### Shift to HR shared services could save Connecticut millions

By consolidating 17 separate HR operations into one shared service, Connecticut expects to save significantly on costs, most of ...

• ### 10 steps to support your HCM system post go-live

To ensure a new system's success, HR leaders need to develop a plan for how they will support their new HCM system post go-live. ...

• ### Face mask detection a newcomer to employee surveillance

Face mask detection has emerged as another form of employee surveillance technology, and its adoption may be helped indirectly by...

Close