Cartesius - a method of storing and retrieving tree structures in relational databases or SQL trees without worms and cockroaches

It is better not to think about finding any truth at all than to do it without any method. (Rene Descartes)

A database developer often has to deal with tree structures. Everything in this world is part of one or many hierarchies, and therefore the ability to effectively store and manage this kind of data is a very important task.

There are many methods from the most primitive to very complex and perhaps too complex. We will not describe them in this article. If you wish, you can find many excellent review articles on the Internet “Google forever”.
')
We present to the developers the Cartesius method which is based on the representation of the hierarchical structure on the coordinate plane where each node has its coordinate in the form of two parameters ord and dep.

So let's get started. Take for example the following hierarchy of wines.

• Wines
  
  • White wines
    
    • French white wines
      
      • Chardonnay
      • Colombard
      • Folle blanche
      • Ugni blanc
      • Muscadelle
      • Sauvignon
    • Italian white wines
      
      • Castelli Romani Bianco
      • Tusculum bianco
  • Red wines
    
    • French red wines
      
      • Cabernet
        
        • Franc
        • Sauvignon
      • Carmenere
      • Beaujolais nouveau
    • Italian red wines
      
      • Bardolino
      • Syrah cabernet
      • Castelli Romani Rosso

Place the entire hierarchy on the coordinate plane and get the coordinates of each node in the hierarchy.



The Y axis, which goes from top to bottom, will be called ord (from the word order - order), and the X axis will be called dep (from the word depth - depth).

Now each node has its own coordinates. For example, Bardolino (ord 20, dep 3), Chardonnay (ord 3, dep 3), Sauvignon (ord 16, dep 4), etc.

Create a SQL table and enter this data into it. (in this article, all examples are developed under MySQL).

CREATE TABLE IF NOT EXISTS `tree` ( `id` int(11) NOT NULL auto_increment, `name` varchar(255) collate utf8_bin NOT NULL, `ord` int(11) unsigned NOT NULL, `dep` int(11) NOT NULL, PRIMARY KEY (`id`) ) ENGINE=MyISAM DEFAULT CHARSET=utf8 COLLATE=utf8_bin; INSERT INTO `tree` (`id`, `name`, `ord`, `dep`) VALUES (1, '', 0, 0), (2, '  ', 1, 1), (3, '  ', 2, 2), (4, 'Chardonnay', 3, 3), (5, 'Colombard', 4, 3), (6, 'Folle blanche', 5, 3), (7, 'Ugni blanc', 6, 3), (8, 'Muscadelle', 7, 3), (9, 'Chenin', 8, 3), (10, '  ', 9, 2), (11, 'Castelli Romani Bianco', 10, 3), (12, 'Tusculum Bianco', 11, 3), (13, '  ', 12, 1), (14, '  ', 13, 2), (15, 'Cabernet', 14, 3), (16, 'Franc', 15, 4), (17, 'Sauvignon', 16, 4), (18, 'Carmenere', 17, 3), (19, 'Beaujolais nouveau', 18, 3), (20, '  ', 19, 2), (21, 'Bardolino', 20, 3), (22, 'Syrah Cabernet', 21, 3), (23, 'Castelli Romani Rosso', 22, 3); 

So, we have two parameters, ord and dep, as well as the name and id of each node.

Add another node called artesius_plug with a maximum ord value of 23 in this case and a dep value of 0. This node will always have a maximum ord. Why we did it you will be a little later.

 INSERT INTO tree (`id`, `name`, `ord`, `dep`) VALUES ('24', ' artesius_plug', '23', '0'); 

We define the most common tasks that developers encounter.

• Print all tree
• Print the node and all its descendants
• Output node and descendants of the first level
• Print the node and all its ancestors
• Add a node
• Delete node

Print all tree

Since the node artesius_plug has only a technical purpose, it does not need us to output the entire tree, so the query will look like this.

 SELECT name, ord, dep FROM tree WHERE ord < (SELECT MAX(ord) FROM tree) ORDER by ord 

Note that in our example, the Root root node (ord 0, dep 0) is only one, but there can be as many of them as you like.


From this data, create XML or JSON. If someone has an interest, we can give an example of constructing json-a from this data in Perl, in one cycle .

Print the node and all its descendants

Suppose we need to derive the node “Red wines” (ord 12, dep 1) and all its descendants. Therefore, we need to derive nodes for which ord> = 12 and which is less than ord-and break points.

What is a break point? The break point is a node that has the following requirements:

1. ord must be greater than the ord node of the descendants of which you want to output
2. dep must be less than or equal to the dep-node of whose descendants you want to output
3. It must have a minimum ord of the set of nodes that meet the previous two conditions.

For example, for the node “French white wines” the point of the gap will be the node “Italian white wines”, its ord is greater than the ord node of the node “French white wines”, dep is equal to dep-y “French white wines” and, finally, has the minimum ord from the set of nodes that follow the node “French white wines”, that is, the first node that follows the descendants of the node “French white wines”.



So, the node “Red varieties of wines” has id = 13. The SQL query will look like this:

 SELECT name, ord, dep FROM tree WHERE ord>=(SELECT ord FROM tree WHERE id=13) AND ord<(SELECT MIN(ord) FROM tree WHERE ord>(SELECT ord FROM tree WHERE id=13) AND dep<=(SELECT dep FROM tree WHERE id=13)) ORDER BY ord 

In the above query

 SELECT MIN(ord) FROM tree WHERE ord>(SELECT ord FROM tree WHERE id=13) AND dep<=(SELECT dep FROM tree WHERE id=13) 

gives us ord break points, which in this case is artesius_plug which has ord 23.


It's time to explain the purpose of the artesius_plug node. Note that at the node “Red wines varieties” descendants reach the end of the hierarchy. Accordingly, we could not find a break point for this node. This is where artesius_plug comes to the rescue, which always has the maximum ord and in this case will be a break point for the “Red wines” node.

If it is necessary to display only descendants, without a parent node, it is enough to take nodes whose ord-s are larger, but not equal to the ord-Red node of the wines.

 SELECT name, ord, dep FROM tree WHERE ord>(SELECT ord FROM tree WHERE id=13) AND ord<(SELECT MIN(ord) FROM tree WHERE ord>(SELECT ord FROM tree WHERE id=13) AND dep<=(SELECT dep FROM tree WHERE id=13)) ORDER BY ord 

Output node and descendants of the first level

To output a node and descendants only of the first level, it suffices to add to the previous query the condition limiting the depth:

 dep >= (SELECT dep FROM tree WHERE id=13) dep <= (SELECT dep+1 FROM tree where id=13) 

The SQL query will look like this:

 SELECT id, name, ord, dep FROM tree WHERE ord >= ( SELECT ord FROM tree WHERE id=13 ) AND ord < ( SELECT MIN( ord ) FROM tree WHERE ord > ( SELECT ord FROM tree WHERE id=13 ) AND dep <= ( SELECT dep FROM tree WHERE id=13 ) ) AND dep >= (SELECT dep FROM tree WHERE id=13) AND dep <= (SELECT dep+1 FROM tree where id=13) ORDER BY ord 

Print the node and all its ancestors

To solve this problem, just look at the coordinate plane. The ancestors of the node “French red wines” are the tops of the yellow columns. Thus, nodes whose ord are smaller than the ord “french red wines” node and which have the maximum ord are grouped by dep, and finally, the dep must be less than or equal to the dep — at the french red wines node.

The SQL query will look like this:

 SELECT (SELECT name FROM tree WHERE ord=MAX(a.ord)) AS name FROM tree a WHERE a.ord<=(SELECT ord FROM tree WHERE id=14) AND dep <= (SELECT dep FROM tree WHERE id = 14) GROUP BY a.dep ORDER BY a.ord 

Result:

• Wines
• Red wines
• French red wines

Add a node

To add a new node, follow these steps.

A. If it is added after any node, for example after the “Tusculum Bianco” node

1. Define break point for “Tusculum Bianco”
2. Add to ord that are greater than or equal to the ord break point one
3. Insert a new node with ord th equal to the ord break point and dep th equal to the dep point of the “Tusculum Bianco”

B. If added as a descendant for example to the “Tusculum Bianco” node

• We add to ord-s, which are larger than the ord-s of the “Tusculum Bianco” node
• Insert the new node with the ord-th equal to the ord-at the node “Tusculum Bianco” + 1 and dep-th equal to the dep-at the node “Tusculum Bianco” +1

This is best done with a procedure. Below is the universal procedure code.

 CREATE DEFINER=`root`@`localhost` PROCEDURE `sp_add`( IN relativ_menu int, IN direct tinyint, IN name_menu varchar(255) charset utf8 ) BEGIN DECLARE relativ_menu_ord INT; DECLARE relativ_menu_dep INT; IF (direct=0) THEN SELECT ord, dep INTO relativ_menu_ord, relativ_menu_dep FROM tree WHERE id = relativ_menu; UPDATE tree SET ord=ord+1 WHERE ord>=relativ_menu_ord; INSERT INTO tree (name, ord, dep) VALUES (name_menu, relativ_menu_ord, relativ_menu_dep); ELSEIF (direct=1) THEN SELECT MIN(ord) INTO relativ_menu_ord FROM tree WHERE ord>(SELECT ord FROM tree WHERE id =relativ_menu) AND dep<=(SELECT dep FROM tree WHERE id =relativ_menu); SELECT dep INTO relativ_menu_dep FROM tree WHERE id =relativ_menu; UPDATE tree SET ord=ord+1 WHERE ord>=relativ_menu_ord; INSERT INTO tree (name, ord, dep) VALUES (name_menu, relativ_menu_ord, relativ_menu_dep); ELSEIF (direct=2) THEN SELECT ord, dep INTO relativ_menu_ord, relativ_menu_dep FROM tree WHERE id =relativ_menu; UPDATE tree SET ord=ord+1 WHERE ord>relativ_menu_ord; INSERT INTO tree (name, ord, dep) VALUES (name_menu, relativ_menu_ord+1, relativ_menu_dep+1); END IF; END$$ 

where direct = 0 add to selected node, direct = 1 add after selected node, direct = 2 add child to selected node

 CALL sp_add (12, 0, 'node_name') 

Delete node

To delete a node, follow these steps:

A. If a single node is deleted, for example “Cabernet”:

1. Determine break point for “Cabernet”
2. We subtract from ord-s that are larger than the ord "Cabernet" unit
3. We subtract a unit from the dep-s at nodes whose ord-s are greater than the “Cabernet” ord and less than the ord-point break point
4. Remove the node

B. If a node and all its descendants are deleted, for example “Cabernet”:

1. Determine break point for “Cabernet”
2. Determine the number of nodes to be deleted the node itself, plus all its descendants.
3. Remove nodes whose ord are greater than or equal to the ord of the node being deleted and less than the ord of the break point
4. We subtract from ord-s that are greater than or equal to ord-the break point the number of nodes to be removed which was determined in paragraph 2

This is best done with a procedure. Below is the universal procedure code.

 CREATE DEFINER=`root`@`localhost` PROCEDURE `sp_del`(IN id_menu int, IN direct tinyint) BEGIN DECLARE min_ord INT; DECLARE max_ord INT; DECLARE count_id INT; DECLARE menu_ord INT; DECLARE menu_dep INT; DECLARE id_node_pr INT; SELECT ord, dep INTO menu_ord, menu_dep FROM tree WHERE id = id_menu; SELECT MIN(ord) INTO max_ord FROM tree WHERE ord> menu_ord AND dep<= menu_dep; IF (direct=0) THEN UPDATE tree SET dep=dep-1 WHERE ord > menu_ord AND ord < max_ord; UPDATE tree SET ord=ord-1 WHERE ord > menu_ord; DELETE FROM tree WHERE id=id_menu; ELSEIF (direct=1) THEN SELECT COUNT(id) INTO count_id FROM tree WHERE ord >= menu_ord AND ord < max_ord; DELETE FROM tree WHERE ord >= menu_ord AND ord < max_ord; UPDATE tree SET ord=ord-count_id WHERE ord >= max_ord; END IF; END$$ 

where direct = 0 deletes one node, direct = 1 deletes a node and all its descendants

 CALL sp_del(15,0) CALL sp_del(15,1)