MySQL Adjacency List Model For Managing Hierarchical Data

By /
Managing Hierarchical Data Using Adjacency List Mode

In this tutorial, we will learn what is hierarchical data, what is adjacency list mode and how to manage hierarchical data in MySQL using the adjacency list model. So, let’s get started!

Introduction to Adjacency List Model and Hierarchical Data

Hierarchical data means the data is organized in a tree fashion, i.e., in a hierarchical manner. For example, vehicle->car->honda is a hierarchy of data. Hierarchical data is also known as a tree and every individual data is known as a node.

To manage the hierarchical data, there are many ways; however, an adjacency list model is a best and simplest way.

In the adjacency list model, each node is assigned a pointer that points to its parent.

Let’s understand the tree terminologies first before performing operations on hierarchical data/tree data.

Tree Data Terminologies

  • A parent node is a node which derives the new node.
  • A child node is a node which is derived from another node.
  • The top node which doesn’t have any parent is the root node
  • Nodes which don’t have any children are leaf nodes.
  • The path is the way from the given node to the specific node.
  • Ancestors are a set of all parents, grandparents, etc.
  • Descendants are a set of all children, grandchildren etc.

Check the below image to understand the terminologies.

Tree Representation
Tree Representation

Here, Animal is a root node because it doesn’t have any parent node.

A Reptile and mammal are children of the animal whereas the animal is the parent of the reptile and mammal.

The path from animal to salamander is – Animal -> Reptile -> Lizard -> Salamander

Managing Hierarchical Data Examples

To manage the hierarchical data in MySQL, first, we need to create a table and insert the data of the above tree structure.

CREATE TABLE animals(
id INT AUTO_INCREMENT PRIMARY KEY,
animal_name VARCHAR(20) NOT NULL,
parent_id INT,
is_active INT DEFAULT 1,
FOREIGN KEY(parent_id) REFERENCES animals(id)
ON DELETE CASCADE ON UPDATE CASCADE
);Code language: SQL (Structured Query Language) (sql)

Here, we have created an id column to store the id of each node. The second column will consist names of nodes. The third column will consist of the parent_id which is the id of a parent node. The Forth column will consist of either 0 or 1 where 1 means the node is active and 0 means the node is inactive.

We referenced the foreign key to the same table as the same table will contain the child id and parent id. Because, whenever we change the parent_id, changes must be made in its children also.

Let’s insert the data as shown in the image above.

INSERT INTO animals(animal_name,parent_id)VALUES
("animal",NULL),("Reptile",1),("Lizard",2),("Salamander",3),
("Snake",2),("Crocodile",2),("Mammal",1),("Equine",7),
("Horse",8),("Zebra",8),("Bovine",7),("Cow",11),
("Canine",7),("Wolf",13),("Fox",13);Code language: SQL (Structured Query Language) (sql)
SELECT * FROM animals;Code language: SQL (Structured Query Language) (sql)
Animals Table Data
Animals Table Data

Let’s begin to manage the hierarchical data one by one.

Finding The Root Node

SELECT * FROM animals WHERE parent_id IS NULL;Code language: SQL (Structured Query Language) (sql)
Finding Root Node
Finding Root Node

Finding Immediate Children of any node

SELECT * FROM animals WHERE parent_id = 1Code language: SQL (Structured Query Language) (sql)
Finding Immediate Children
Finding Immediate Children

Finding All Leaf Nodes

SELECT a1.* FROM animals a1
LEFT JOIN animals a2
ON a1.id=a2.parent_id
WHERE a2.id IS NULL;Code language: SQL (Structured Query Language) (sql)
Finding Leaf Nodes
Finding Leaf Nodes

Displaying Path to Every Node from Root Node

Here, we will use a recursive CTE to fetch the complete tree structure.

WITH RECURSIVE animal_cat AS
(SELECT id, animal_name,parent_id,
1 AS depth, animal_name AS path FROM animals
WHERE id = 1
UNION ALL
SELECT a.id,a.animal_name,a.parent_id,ac.depth+1,
CONCAT(ac.path,' --> ',a.animal_name) FROM animal_cat AS ac
JOIN animals AS a ON a.parent_id=ac.id
)
SELECT * FROM animal_cat;Code language: SQL (Structured Query Language) (sql)
Display Whole Tree
Display Whole Tree

Display Subtree of Given Node

Here, we will find the subtree of a given node, i.e, all descendants of a given node.

We will find the subtree of a mammal node. The id of a mammal node is 7.

WITH RECURSIVE animal_cat AS
(SELECT id, animal_name,parent_id,
1 AS depth, animal_name AS path FROM animals
WHERE id = 7
UNION ALL
SELECT a.id,a.animal_name,a.parent_id,ac.depth+1,
CONCAT(ac.path,' --> ',a.animal_name) FROM animal_cat AS ac
JOIN animals AS a ON a.parent_id=ac.id
)
SELECT * FROM animal_cat;Code language: SQL (Structured Query Language) (sql)
Retriving Subtree
Retrieving Subtree

Skipping Inactive Nodes and Descendants

Here, we will display only active nodes, i.e., those nodes which have a value of is_active attribute as 1.

By default, we have set each node as active. Let’s make a node having id 2 inactive. The node having id 2 is a reptile.

So, the whole subtree of a node reptile will become inactive.

UPDATE animals SET is_active=0 WHERE id=2;Code language: SQL (Structured Query Language) (sql)
WITH RECURSIVE animal_cat AS
(SELECT id, animal_name,parent_id,
1 AS depth, animal_name AS path FROM animals
WHERE id = 1
UNION ALL
SELECT a.id,a.animal_name,a.parent_id,ac.depth+1,
CONCAT(ac.path,' --> ',a.animal_name) FROM animal_cat AS ac
JOIN animals AS a ON a.parent_id=ac.id
WHERE a.is_active=1
)
SELECT * FROM animal_cat;Code language: SQL (Structured Query Language) (sql)
Retriving Only Active Nodes
Retrieving Only Active Nodes

Calculating the Level of Each Node

You can think of a Level of a node as a floor of a tree but the count starts from the top node and it’s 0 initially.

For example, the level of the ‘animal’ node is 0, ‘mammal’ and ‘reptile’ is 1, and so on.

WITH RECURSIVE animal_cat AS
(SELECT id, animal_name, 0 AS level FROM animals
WHERE id = 1
UNION ALL
SELECT a.id,a.animal_name,ac.level + 1
FROM animal_cat AS ac
JOIN animals AS a ON a.parent_id=ac.id
)
SELECT * FROM animal_cat ORDER BY level;Code language: SQL (Structured Query Language) (sql)
Finding Level Of Each Node
Finding the Level Of Each Node

Moving Subtree to New Parent

You can move a whole subtree to the new destination by updating the parent id of the node.

Here, we will move the subtree of a node ‘Equine’ to the ‘Bovine’. So, we have to change the parent_id of the ‘Equine’ node.

UPDATE animals SET parent_id = 11 WHERE id=8Code language: SQL (Structured Query Language) (sql)

Deleting a Node and Its Descendants

When we delete any node, all descendants will be deleted automatically as we have applied the ‘ON DELETE’ cascade on the foreign key.

Here, we will delete the node Reptile which will delete all its nodes- lizard, snake, crocodile and salamander.

DELETE FROM animals WHERE id=2;Code language: SQL (Structured Query Language) (sql)

The result of updating and deleting nodes is –

WITH RECURSIVE animal_cat AS
(SELECT id, animal_name,parent_id,
1 AS depth, animal_name AS path FROM animals
WHERE id = 1
UNION ALL
SELECT a.id,a.animal_name,a.parent_id,ac.depth+1,
CONCAT(ac.path,' --> ',a.animal_name) FROM animal_cat AS ac
JOIN animals AS a ON a.parent_id=ac.id
)
SELECT * FROM animal_cat;Code language: SQL (Structured Query Language) (sql)
Update And Delete Nodes
Update And Delete Nodes

Summary

In this tutorial, we have learned-

  • What the Hierarchical Data and Adjacency List model is
  • Tree data terminologies
  • How to find a root node
  • How to find children of a node
  • How to find leaf nodes
  • How to display the whole tree
  • Display subtree
  • How to Calculate the level of each node
  • Update and delete nodes