MySQL – Select Top-Most Folder in a Hierarchy by Criteria

hierarchyMySQL

I'm using MySQL (5.7.20) to store a folder hierarchy. Each folder is stored together with all direct and indirect parents including the distance. As an example, the following folders

A
+- B
   + C
   + D

would be stored like this:

parent | child | dist
-------+-------+-----
A      | A     | 0
A      | B     | 1
A      | C     | 2
A      | D     | 2
B      | B     | 0
B      | C     | 1
B      | D     | 1
C      | C     | 0
D      | D     | 0

Additionally, there is another table that links a folder to one or many users, like this:

child | user
------+-----
A     | U1
B     | U1
C     | U2
D     | U2

What I'm now trying to achieve is to query this hierarchy by user in a way that only the highest matches in the hierarchy are returned.

So as in the example above, if I query for folders of user U1, I only want A as a result, because the second match B is a child of A. On the other hand, if I query for folders of user U2, the result should be C, D as both folders are on the same hierarchy level.

The closest query I could imagine was SELECT child, dist AS d FROM folders JOIN users ON folders.child = users.child GROUP BY folders.parent HAVING d = min(d); but unfortunately it is not giving the right results, as for example a query for user U1 would still give folders A,B as a result.

Does anyone have an idea how this could be done?

Best Answer

I think you want this. All the results from users table except those that have a parent in users:

SELECT u.user, u.child
FROM users AS u 
WHERE NOT EXISTS
      ( SELECT 1 
        FROM users AS u2
             JOIN folder AS f 
             ON f.parent = u2.child
        WHERE f.child = u.child
          AND f.dist > 0         -- this could be: AND f.parent <> f.child
          AND u2.user = u.user
      ) ;

Compromise Solution...

You will still need a Stored Procedure, but not using recursion. Using a simple loop, you can construct a self-join query and executed it dynamically. Given the depth of the tree you are looking for, here is such a Stored Procedure:

DELIMITER $$

DROP PROCEDURE IF EXISTS `dianuj`.`GetTopParentGivenDepth` $$
CREATE PROCEDURE `dianuj`.`GetTopParentGivenDepth` (GivenDepth INT)
BEGIN

    DECLARE x1,x2 INT;

    SET x = 0;
    SET y = 1;
    SET @SQ = 'SELECT DISTINCT A0.id FROM prarent A0';
    WHILE y < GivenDepth DO
        SET @SQ = CONCAT(@SQ,' INNER JOIN prarent A',y,' ON A',x,'.id = A',y,'.parent_id');
        SET x = y;
        SET y = x + 1;
    END WHILE;
    SET @SQ = CONCAT(@SQ,' WHERE A0.parent_id = 0');
    SELECT @SQ;
    PREPARE stmt FROM @SQ;
    EXECUTE stmt;
    DEALLOCATE PREPARE stmt;

END $$

DELIMITER ;

After loading your data into MySQL on my desktop, I ran the Stored Procedure with...

Depth 1

mysql> call GetTopParentGivenDepth(1);
+--------------------------------------------------------------+
| @SQLSTMT                                                     |
+--------------------------------------------------------------+
| SELECT DISTINCT A0.id FROM prarent A0 WHERE A0.parent_id = 0 |
+--------------------------------------------------------------+
1 row in set (0.00 sec)

+----+
| id |
+----+
|  1 |
|  2 |
|  3 |
+----+
3 rows in set (0.00 sec)

Query OK, 0 rows affected (0.00 sec)

mysql>

Depth 2

mysql> call GetTopParentGivenDepth(2);
+------------------------------------------------------------------------------------------------------------+
| @SQLSTMT                                                                                                   |
+------------------------------------------------------------------------------------------------------------+
| SELECT DISTINCT A0.id FROM prarent A0 INNER JOIN prarent A1 ON A0.id = A1.parent_id WHERE A0.parent_id = 0 |
+------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)

+----+
| id |
+----+
|  3 |
|  2 |
+----+
2 rows in set (0.01 sec)

Query OK, 0 rows affected (0.01 sec)

mysql>

Depth 3 .. 6

mysql> call GetTopParentGivenDepth(3);
+----------------------------------------------------------------------------------------------------------------------------------------------------------+
| @SQLSTMT                                                                                                                                                 |
+----------------------------------------------------------------------------------------------------------------------------------------------------------+
| SELECT DISTINCT A0.id FROM prarent A0 INNER JOIN prarent A1 ON A0.id = A1.parent_id INNER JOIN prarent A2 ON A1.id = A2.parent_id WHERE A0.parent_id = 0 |
+----------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)

+----+
| id |
+----+
|  3 |
+----+
1 row in set (0.00 sec)

Query OK, 0 rows affected (0.00 sec)

mysql> call GetTopParentGivenDepth(4);
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| @SQLSTMT                                                                                                                                                                                               |
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| SELECT DISTINCT A0.id FROM prarent A0 INNER JOIN prarent A1 ON A0.id = A1.parent_id INNER JOIN prarent A2 ON A1.id = A2.parent_id INNER JOIN prarent A3 ON A2.id = A3.parent_id WHERE A0.parent_id = 0 |
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)

+----+
| id |
+----+
|  3 |
+----+
1 row in set (0.00 sec)

Query OK, 0 rows affected (0.00 sec)

mysql> call GetTopParentGivenDepth(5);
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| @SQLSTMT                                                                                                                                                                                                                                             |
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| SELECT DISTINCT A0.id FROM prarent A0 INNER JOIN prarent A1 ON A0.id = A1.parent_id INNER JOIN prarent A2 ON A1.id = A2.parent_id INNER JOIN prarent A3 ON A2.id = A3.parent_id INNER JOIN prarent A4 ON A3.id = A4.parent_id WHERE A0.parent_id = 0 |
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.01 sec)

+----+
| id |
+----+
|  3 |
+----+
1 row in set (0.01 sec)

Query OK, 0 rows affected (0.01 sec)

mysql> call GetTopParentGivenDepth(6);
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| @SQLSTMT                                                                                                                                                                                                                                                                                           |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| SELECT DISTINCT A0.id FROM prarent A0 INNER JOIN prarent A1 ON A0.id = A1.parent_id INNER JOIN prarent A2 ON A1.id = A2.parent_id INNER JOIN prarent A3 ON A2.id = A3.parent_id INNER JOIN prarent A4 ON A3.id = A4.parent_id INNER JOIN prarent A5 ON A4.id = A5.parent_id WHERE A0.parent_id = 0 |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)

Empty set (0.00 sec)

Query OK, 0 rows affected (0.01 sec)

mysql>

Notice that Depth 6 has no return value. To find the maximum depth, you would have to iterate on it until no rows comes back.

CAVEAT

The worst case scenario would be to use the number of rows in the table as the depth. Such a tree would be nothing more than a degenerate linked list.
I cannot give you any guarantees on query performance, such on SQL construction and subsequent execution. Any kind of recursion would be the sole responsibility of the Query Parser.

Give it a Try !!!

Mysql – Which files in the “MySQL-5.0.27-win32” folder do i need to backup

You are using a very old, end-of-life, and unsupported version of MySQL.

There is not exactly a correct answer to your question, because it is impossible in many cases to safely back up or clone a MySQL server that is still running.

The only absolutely safe way to copy data using this method is by stopping the mysqld process, gracefully, and copying all of the files, for all of the databases.

If you are using MyISAM, which, again, you almost certainly should not, it is possible to copy a single database by copying all of the files in that database's named directory, but the tables have to be locked and flushed, or the backup will either not contain the most recent changes, or will be corrupt.

If you are using InnoDB, it is almost impossible to copy only one database from one server by copying files, unless you use the "transportable tablespaces" feature introduced in MySQL 5.6.

The correct answer to the question is "don't do it this way."

The correct solution is to use mysqldump to make the backup, which does not copy files at all. Instead, it creates a file containing the SQL statements necessary to recreate your tables and reinsert the data that was in those tables when the backup was made.

The output of mysqldump is also human-readable, so you can actually examine what's in the backup.

http://dev.mysql.com/doc/refman/5.0/en/mysqldump.html