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

#### Start the conversation

Send me notifications when other members comment.

## SearchDataManagement

• ### Hitachi Vantara acquires data catalog vendor Waterline Data

With the acquisition of Waterline Data, Hitachi Vantara is bringing new data catalog capabilities that will expand the Lumada ...

• ### New Confluent Platform release boosts event streaming quality

Based on the open-source Kafka event streaming platform, the Confluent Platform 5.4 update adds new capabilities to help meet ...

• ### Where InfluxDB time series database is going

Users need more than SQL for querying databases, according to Paul Dix, co-founder and CTO of InfluxData. That's why the vendor ...

• ### ThoughtSpot IPO could be coming after vendor adds first CFO

Hiring of a CFO for the first time signals that ThoughtSpot may be positioning itself for an IPO and comes six months after what ...

• ### 5 ways enterprises adapt to the data scientist shortage

Where are all the data scientists? Coping with the data scientist shortage is a struggle for many enterprises. Here are five ways...

• ### Storytelling using data makes information easy to digest

In a Q&A, Nate Nichols and Anna Schena Walsh of AI-based analytics vendor Narrative Science talk about how data storytelling can ...

## SearchSAP

• ### SAP S/4HANA migration: Critical advice for moving off ECC

With the end of SAP ECC support looming in 2025, organizations must make some tough decisions. Here's a look at your choices.

• ### New SAP leadership faces big challenges in 2020

Industry analysts discuss SAP's biggest issues in 2020, including how the two new CEOs will guide the company deeper into the ...

• ### SAP Data Hub opens predictive possibilities at Paul Hartmann

When medical supply firm Paul Hartmann AG tested a supply chain analysis system built on SAP Data Hub, it found that it could ...

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

• ### Don't ever put a non-Java LTS release into production

Development teams should avoid non-long-term support releases at all costs. Pay attention to the Java release cycle to make sure ...

• ### Public API strategy considerations for enterprise adoption

As organizations look for more cost-effective ways to manage data, an evolving landscape with APIs has made the technology more ...

• ### Ideas on how to hold a successful code hackathon

Want to host a hackathon? Here are some ideas on what a company can do to host an event that solves problems and reenergizes the ...

## SearchDataCenter

• ### Top data center skills admins can use in 2020

The 2019 tech job sector saw consistent growth and job availability. In 2020, admins should develop expertise on cloud ...

• ### Organizations try to predict the effect of 5G infrastructure

With more 5G and IoT devices emerging, admins must prepare their data centers to support low-latency apps and edge computing with...

• ### Top infrastructure and operations technology myths of 2019

Admins are consistently evaluating technology to improve I&O efficiency. Cost, integration and business goals are key components ...

## SearchContentManagement

• ### 4 popular content collaboration platforms to consider

Companies need to be organized if they want to be efficient. Content collaboration platforms are useful, but first, ensure that ...

• ### AI can enhance content security with a bit of planning

Microsoft and Box both use AI technologies to keep content secure in the cloud. But before using such tools, businesses first ...

• ### Ex-SAP exec steers Episerver CMS toward digital experience market

Alex Atzberger discusses leaving the helm of SAP's CX platform to become Episerver CEO. Now, Episerver looks to reinvent itself ...

## SearchHRSoftware

• ### Critical tips for managing contingent workers

Contingent workers save companies both time and money, so it's important to manage them in a win-win way. Here is what HR teams ...

• ### Impact of AI on jobs goes on the presidential campaign trail

The impact of AI on jobs is a major issue for employers, who are struggling with how to address it. Robots, automation and AI ...

• ### Why mobile recruiting is the future

Recruiters can use text recruiting to connect with great candidates. Here's a look at how mobile recruiting works, why it's ...

Close