3

My production data looks similar to adjacency list model explained here...

http://mysql.stu.edu.tw/tech-resources/articles/hierarchical-data.html

My questions is how do I know how deep the nesting is? In this case it is 4 from last leaf "Flash" to first node "Electronics". Is there a query that will return this max depth number?

shantanuo
  • 31,689
  • 78
  • 245
  • 403
  • I thinking adding a depth column will simplify your query. It will also perform better. See solution below. – dan b Jul 09 '15 at 10:51
  • Have you been able to consider adding a depth column? – dan b Jul 10 '15 at 14:39
  • http://stackoverflow.com/questions/10999888/mysql-adjacency-list-model-get-depth check this – rajatsaurastri Jul 13 '15 at 05:07
  • If you want a pure SQL query to return the "max depth number... for an unbounded depth, the answer is no, there is no SQL query that will get you that. For checking a bounded (finite) depth (up to some specified limit), yes, there is a query. See my answer for that. To get an unbounded depth, you'll need something other than just plain SQL, such as a MySQL stored program (procedure). – spencer7593 Jul 13 '15 at 22:27

4 Answers4

6

MYSQL do not has CTE neither recursion features. You can solve it with a 'classical loop':

DELIMITER $$
DROP FUNCTION IF EXISTS figure_up_depth $$

--encapsulated as a function:
CREATE FUNCTION figure_up_depth(idToSearch INT) RETURNS INT BEGIN

 --var to count steps from node to root:
 DECLARE depth INT;
 SET depth = 1;

 --while we are not on root node:
 WHILE ( idToSearch  is not  null) DO

   SET idToSearch = ( select parent
     from category
     where category_id = idToSearch
                  );

   SET depth = depth + 1;

 END WHILE;

 RETURN depth;

END;
$$
DELIMITER ;

Checking:

mysql> select figure_up_depth(7);
+--------------------+
| figure_up_depth(7) |
+--------------------+
|                  4 |
+--------------------+
1 row in set (0.00 sec)

EDITED 8 Jul 2015

I realize that OP ask for max depth, not for a node depth. A easy as:

mysql> select max( figure_up_depth(category_id) ) as max_depth
       from category;

If performance matters the right solution is:

  1. Put all categories.parent in a temporary table table1.
  2. Join table1 with categories using categories.id = table1.id, put result joined field categories.parent on temporary table table2.
  3. Drop table1 and rename table2 as table1.
  4. Go step 2 if table1 has rows.

Number of loops iteration will be tree depth:

DELIMITER $$
DROP PROCEDURE IF EXISTS letsgo;
CREATE PROCEDURE letsgo() BEGIN
 DECLARE R int;
 DECLARE D int;
 SET D=0;
 DROP TEMPORARY TABLE IF EXISTS children;
 CREATE TEMPORARY TABLE children AS (SELECT category_id as id 
                                       FROM category 
                                      WHERE parent is NULL );
 DROP TEMPORARY TABLE IF EXISTS children_prev;
 CREATE TEMPORARY TABLE children_prev AS (SELECT * FROM children );
 SET R = ( SELECT count(*) FROM children ); 
 WHILE ( R > 0 ) DO
   DROP TEMPORARY TABLE IF EXISTS children_aux;
   CREATE TEMPORARY TABLE children_aux AS (
     SELECT category_id as id 
       FROM category R  
       INNER JOIN  children_prev C on C.id = R.parent
   );
   SET R = ( SELECT count(*) FROM children_aux );  
   INSERT INTO children 
      SELECT * FROM children_aux;
   TRUNCATE TABLE children_prev;
   INSERT INTO children_prev
      SELECT * FROM children_aux;   
   SET D=D+1;
 END WHILE;
 SELECT D;
END;
$$
DELIMITER ;

Testing:

mysql> call letsgo();
+------+
| D    |
+------+
|    4 |
+------+
1 row in set (0.14 sec)

Notice: sorry about dirty solution, this is mysql: no CTE, no recursion, no selects on function recursion, not DO-While, ...

dani herrera
  • 48,760
  • 8
  • 117
  • 177
2

For a solution that works for a finite "maximum" depth, you can use a query like this:

  SELECT CASE 
         WHEN MAX(l8.category_id IS NOT NULL) THEN 8
         WHEN MAX(l7.category_id IS NOT NULL) THEN 7
         WHEN MAX(l6.category_id IS NOT NULL) THEN 6
         WHEN MAX(l5.category_id IS NOT NULL) THEN 5
         WHEN MAX(l4.category_id IS NOT NULL) THEN 4
         WHEN MAX(l3.category_id IS NOT NULL) THEN 3
         WHEN MAX(l2.category_id IS NOT NULL) THEN 2
         WHEN MAX(l1.category_id IS NOT NULL) THEN 1
         ELSE 0
         END AS max_depth
    FROM category l1
    LEFT JOIN category l2 ON l2.parent = l1.category_id
    LEFT JOIN category l3 ON l3.parent = l2.category_id
    LEFT JOIN category l4 ON l4.parent = l3.category_id
    LEFT JOIN category l5 ON l5.parent = l4.category_id
    LEFT JOIN category l6 ON l6.parent = l5.category_id
    LEFT JOIN category l7 ON l7.parent = l6.category_id
    LEFT JOIN category l8 ON l8.parent = l7.category_id
   WHERE l1.parent IS NULL

In this case, if the "tree" is more than eight levels deep, the query will return 8, the maximum depth it checks for.

This could be extended, but this approach requires some finite maximum. (MySQL has a limit on the number of table references in a query).

The "root" node of the tree will have a NULL value for parent. So, that's the node at level 1. (There could be multiple rows with a NULL value, multiple roots. (I' choosing to identify a one level tree with a max depth of 1, and choosing to return 0 if there are no "root" node(s).

The expression ln.category_id IS NOT NULL will return a 1 if it's true, and 0 if it's false. If there's any row where it's a non-null value, we know the tree is at least that many levels deep.

The CASE expression is basically checking: is the tree at least 8 levels deep? If yes, we're done. If not, is the tree at least 7 levels deep? If not, is it at least 6 levels deep? etc.

If you remove that CASE wrapper expression, and the MAX aggregates, what you get back is each node in the tree, and it's path back to the root node. You might want to order those from top down... level 1, level 2, level 3, etc.

For checking the maximum depth of the tree, we want to check from the bottom up.

To check for some unbounded depth, you'd need recursion, and MySQL doesn't support anything like that in the context of a SQL statement. You'd be into the realm of a MySQL stored program (procedure or function) to get a recursive solution.

(Other databases give us a convenient CONNECT BY syntax. But alas, MySQL doesn't.)

spencer7593
  • 106,611
  • 15
  • 112
  • 140
1

Well this is the nice long way about it :)

begin transaction

CREATE TABLE #category(
category_id INT PRIMARY KEY,
name VARCHAR(20) NOT NULL,
parent INT DEFAULT NULL);

INSERT INTO #category
VALUES(1,'ELECTRONICS',NULL),(2,'TELEVISIONS',1),(3,'TUBE',2),
(4,'LCD',2),(5,'PLASMA',2),(6,'PORTABLE ELECTRONICS',1),
(7,'MP3 PLAYERS',6),(8,'FLASH',7),
(9,'CD PLAYERS',6),(10,'2 WAY RADIOS',6);

DECLARE @SQL NVARCHAR(MAX)
DECLARE @SQLF NVARCHAR(MAX)
DECLARE @SQLFINAL NVARCHAR(MAX)
DECLARE @CT as VARCHAR(10)
DECLARE @CTP as VARCHAR(10)
DECLARE @SQLFINALP as NVARCHAR(MAX)

SET @CT = 1
SET @CTP = 1
SET @SQL = 'Select t1.name ''lev1'' '
SET @SQLF = 'FROM #category t1 '
SET @SQLFINAL = @SQL + CHAR(13) + @SQLF +  'where t1.name = electronics and t1.name is not null'

While @@ROWCOUNT > 0 
    Begin
    SET @SQLFINALP = @SQL + CHAR(13) + @SQLF + 'WHERE t1.name =''electronics'''
    SET @CTP = @CT
    Set @CT = @CT + 1
    SET @SQL = @SQL +' , t' +@CT+'.name ''lev' + @CT + ''''
    SET @SQLF = @SQLF + ' left join #category t' + @CT + ' on t' + @CTP + '.category_id = t' + @CT + '.parent '
    SET @SQLFINAL = @SQL + 'into #temp' + CHAR(13) + @SQLF +  'where t' + @Ct + '.name is not null and t1.name = ''electronics'''
    exec SP_EXECUTESQL @SQLFINAL
    end
print @@ROWCOUNT
Select @CTP

print @SQLFINALp
exec SP_EXECUTESQL @SQLFINALp

rollback
Holmes IV
  • 1,673
  • 2
  • 23
  • 47
1

You may want to consider adding a depth column. When you insert a node in the hierarchy the depth is 0 if it has no parent, otherwise add 1 to the depth of the parent. Then you can just select it directly. This approach will be very efficient and works for any depth

dan b
  • 1,172
  • 8
  • 20