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

# Comparing trees in the nested sets model

## Some SQL code to compare nodes and structures of trees in the Nested Sets model for hierarchies.

Code updated on July 31, 2002.

Here is some SQL code to compare nodes and structures of trees in the Nested Sets model for hierarchies. Rudy Limeback replied to a question about comparing rows in different tables on 21 September 2001. The requester was asking it in regards to my nested sets model of trees, so I would like to reply.

There are really several kinds of equality comparisons when you are dealing with a hierarchy:

1. Same nodes in both tables
2. Same structure in both tables
3. Same nodes and structure in both tables -- they are identical

Let me once more invoke my semi-quasi-famous organization chart in the nested sets model. If you do not understand the nested sets model, then read the earlier articles here and here:

``` 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) );
```

Insert sample data:

``` 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)
```

Case one: Same nodes

Let's create a second table with the same nodes, but with a different structure:

``` CREATE TABLE Personnel_2
(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) );
```

Insert sample data:

``` Personnel_2
emp         lft  rgt
======================
'Albert'      1   12
'Bert'        2    3
'Chuck'       4    5
'Donna'       6    7
'Eddie'       8    9
'Fred'       10   11

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

Rudy gave a few different ways of matching nodes between Personnel and Personnel_2. Here is one way that is a little different:

```SELECT 'They have the same nodes'
FROM Personnel_2 AS P0
FULL OUTER JOIN
Personnel_3 AS P1
ON P0.emp = P1.emp
HAVING (SELECT COUNT(*) FROM Personnel_2)
= (SELECT COUNT(*) FROM Personnel_3)
AND (SELECT COUNT(*) FROM Personnel_2)
= COUNT(*)
AND (SELECT COUNT(*) FROM Personnel_3)
= COUNT(*);
```

In fairness, a FULL OUTER JOIN is hard to find in many SQL products, even today. The idea is that anyone without a match in the other table will get generated NULLs and become a row by himself for the count.

Case two: Same structure

I will not bother with an ASCII drawing, but let's present a table with sample data that has different people inside the same structure.

``` Personnel_3
emp         lft  rgt
======================
'Amber'      1   12
'Bobby'      2    3
'Charles'    4   11
'Donald'     5    6
'Edward'     7    8
'Frank'      9   10
```

If these things are really separate trees, then life is easy. You do the same join as before but with the (lft,rgt) pairs:

``` SELECT DISTINCT 'They have the same structure'
FROM Personnel AS P0
WHERE COUNT(P0.emp)
= (SELECT COUNT(*)
FROM Personnel AS P0
FULL OUTER JOIN
Personnel_3 AS P1
ON P0.lft = P1.lft
AND P0.rgt = P1.rgt);
```

Case three: Same nodes and same structure

``` SELECT DISTINCT 'They are identical'
FROM Personnel AS P0
WHERE COUNT(P0.emp)
= (SELECT COUNT(*)
FROM Personnel AS P0
FULL OUTER JOIN
Personnel_2 AS P1
ON P0.lft = P1.lft
AND P0.rgt = P1.rgt
AND P0.emp = P1.emp);
```

But more often than not, you will be comparing subtrees within the same tree. This is best handled by putting the two sub-trees into a canonical form. First you need the root node (i.e the emp in this sample data) and then you can re-number the (lft, rgt) pairs with a derived table of this form:

``` (SELECT emp,
lft - (SELECT MIN(lft FROM Personnel),
rgt - (SELECT MIN(lft FROM Personnel)
FROM Personnel AS P0
WHERE P0.lft
BETWEEN (SELECT lft
FROM Personnel
WHERE emp = :emp_root_subtree_2)
AND (SELECT rgt
FROM Personnel
WHERE emp = :emp_root_subtree_2))
AS CP0 (emp, lft, rgt)
```

The derived table with have its (lft,rgt) pairs start at zero instead of one. That is actually an advantage when you insert a canonical tree structure into an existing table, but that is another article.

If you would like to see this all in one monster query:

``` SELECT CASE COUNT(P.emp)
WHEN (SELECT COUNT(*)
FROM Personnel AS P0
FULL OUTER JOIN
Personnel_3 AS P1
ON P0.lft = P1.lft
AND P0.rgt = P1.rgt
AND P0.emp = P1.emp)
THEN 'The trees are identical'
WHEN (SELECT COUNT(*)
FROM Personnel AS P0
FULL OUTER JOIN
Personnel_2 AS P1
ON P0.emp = P1.emp)
THEN 'The trees have the same nodes'
WHEN (SELECT COUNT(*)
FROM Personnel AS P0
FULL OUTER JOIN
Personnel_2 AS P1
ON P0.lft = P1.lft
AND P0.rgt = P1.rgt)
THEN 'The trees have the same structure'
ELSE 'The trees have different node sets and structure'
FROM Personnel AS P;
```

This depends on the CASE expression operating from left to right and returning the first TRUE clause it finds. Since there will a lot of indexes on the tree tables, joins and aggregate functions should be relatively fast to perform. For an exercise, try writing the same structure queries with the adjacency list model.

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

This was last published in March 2002

#### Start the conversation

Send me notifications when other members comment.

## SearchDataManagement

• ### Chief data officer role: Searching for consensus

The chief data officer role is about many things -- regulations, innovation, AI and more. Consultant Randy Bean discussed the ...

• ### How graph data modeling can help evaluate database tools

Mapping data to a graph model can be challenging -- but it can also help an organization create prototypes to evaluate graph ...

• ### eHarmony hooks up with Redis NoSQL database for hot storage

The Redis key-value store finds use in a system to match would-be romantic partners on dating site eHarmony, which employs a ...

• ### Heat map view sets table for food warehouse optimization

Inspired by the vivid views of stadium heat maps, a Midwest food distributor worked with Information Builders to gain a better ...

• ### Streamlining predictive analytics in retail marketing

Online flash-sale retailer Zulily uses BigQuery and Tableau to help power its predictive analytics, which, in turn, boosts its ...

• ### Airbnb, Univision highlight best practices in BI

At the Real Business Intelligence conference, Airbnb and Univision execs presented some of the BI strategies their organizations ...

## SearchSAP

• ### On-premises, hosted most popular S/4HANA deployment options

The pure cloud -- SaaS -- version of SAP's newest ERP, S/4HANA Cloud, lacks some of the same features of the on-premises version....

• ### S/4HANA public cloud version can get lost in cloud confusion

The 'true' public cloud is the streamlined SaaS version of on-premises S/4. But private cloud options are often conflated with ...

• ### SAP S/4HANA migration: What you need to know

There's a lot to consider when contemplating a move to SAP S/4HANA, and this essential guide provides a starting point, including...

## SearchSQLServer

• ### Six sample databases for SQL Server and how to find them

SQL Server sample databases are useful for test and dev, but they can be difficult to parse. Use this SQL database sample ...

• ### A quick tutorial on SQL Server maintenance plans

SQL Server maintenance plans get a bad rap, but for DBAs who need a simple way to maintain databases, Microsoft's built-in tools ...

• ### Proposed Microsoft-GitHub buy confirms open source role in cloud

The looming Microsoft-GitHub pairing confirms the company's rebirth as an open source friend. Data tools on the Azure cloud are ...

## TheServerSide.com

• ### Attain Jenkins Git integration with a GitHub pull request

This Jenkins Git integration tutorial demonstrates how to create a freestyle build job that performs a Jenkins GitHub pull ...

• ### Financial firms, vendors push self-service software delivery

Self-service DevOps automation appeals to enterprises that must push out new code as they adapt to changing requirements.

• ### IT projects and software teams need to include Agile people

Not every idea deserves equal weight in a software development project, but Agile people know that garnering input from a wide ...

## SearchDataCenter

• ### Rackspace colocation program hosts users' legacy servers

Rackspace now has a managed colocation program that it hopes to upsell its customers with additional services, once their servers...

Broadcom has acquired CA Technologies in a move some believe is largely financially motivated, while others see an opportunity ...

• ### Ten Linux process management commands that simplify admin workflows

If you work in Linux, chances are you have to do some process management. Here are some commands to simplify that workflow.

## SearchContentManagement

• ### Augmented reality devices speed van repairs at Volkswagen U.K.

Augmented reality headsets for garage mechanics speed collaboration between repair shops and experts in the home office to solve ...

• ### Endpoint security tool fueled OpenText's Guidance Software acquisition

Endpoint security was the primary draw for OpenText's Guidance Software acquisition. But plans to improve e-discovery and data ...

• ### Digital transformation benefits follow a not-so-fast track

Choosing among the many digital transformation strategies in the content management sphere is not easy but can pay off when ...

## SearchHRSoftware

• ### Automated recruiting solves Groupon's sourcing talent woes

Building a talent pool through effective sourcing is a major effort by Groupon. It is using a recruiting automation tool to find ...

• ### New HR tools for hourly workers, employee retention announced

This week's news roundup includes an HR tool designed just for hourly workers, a new offering from Limeade to help with talent ...

• ### Eight human capital management functions every HR department needs

Employee self-service and wellness portals are no longer enough. Now, you need a multipronged strategy that tackles the most ...

Close