Mysql – Hierarchical data in MongoDB

hierarchymongodbMySQL

I have a question regarding Hierarchical data.

Our app shows posts, that are structured inside parents. Here's how it goes:

prof->sprof->subject->post

(Each prof can contain multiple sprofs, and each sprof can contain multiple subjects, and each subject contains multiple posts)

Right now, we've set up a temporary MySQL Database that looks like this:

There are 4 tables: profs, sprofs, subjects and posts. Inside the table profs you have a row for each prof – and each prof has it's unique ID.

Inside the table sprofs, each sprof has it's own unique ID, but It also has a field for the ID of its parent. For example, if there's a prof with the ID 1, a sprof might have a parent_id of 1 (to indicate that its prof (its parent) is prof number 1).

And so on – each subject has a field for its sprof's ID, and each post has a field for its subject's ID.

So for example, if we want to get all the posts under the subject number 2, we do:

SELECT * FROM 'posts' WHERE 'subject_id'=2

A friend told me, that MongoDB can have structured data, so for example I could put a "table" of "posts" under a "row" inside the "table" of "subjects".

Is it true? Will it help? Will it be faster than using MySQL?

I'm not familliar with MongoDB at all, but I'd like to learn that anyway.

Best Answer

The question to answer first is, are any of the possible children bounded or unbounded sets of data? The next question is, how are you going to be requesting the data? Another question would be, how often will the data be written?

One of the things you'll learn quickly with MongoDB is the answer to any schema questions is almost always "It depends". It depends on the answers to the questions I asked above and a few more. To get you on your way though, MongoDB has some great documentation on the subject of hierarchies. This gets you part of the way to your solution.

Then you have to understand your data access patterns and when to normalize or denormalize data. Something to help you make that decision can be read in this great blog.

Sorry to leave you with a not so cut and dry answer. Yes, MongoDB can take care of hierarchical data. How should it be done? It depends. Will it be faster than MySQL, it depends. Can it be faster than MySQL? Most definitely.

Scott

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

Animals hierarchy use-case: multiple farms, multiple species

The best approach would be neither of the two options you've proposed. Instead you should create your own proprietary surrogate key using either a monotonically increasing integer or a GUID if that is how you like to do these things. This key column would be NOT NULL on your animal table (obviously).

You need to keep all of the external IDs that are provided to you (internal/national) and use these to establish the mother_id and father_id of each new animal that you add to your database according to the complex rules that you've described.

This approach allows your system to take advantage of declarative referential integrity and ANSI SQL joining while preserving the mixed bag of external IDs that are provided to you for reference/reporting etc.