MySQL Tree ordered by parent and child

Question

I'm trying to display a tree structure in MYSQL with this reference (http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/) and I'm seeing that only works with 1 parent in same table.
If you have another table to join with, nothing go well. Example:

Table Menu:

+----+--------+-------+
| id |  name  | order |
| 1  | Father |   0   |
| 2  | Father |   1   |
| 3  | Son    |   0   |
| 4  | Child  |   1   |
| 5  | Granson|   2   |
+----+--------+-------+

Table Relations

+----+---------+-----------+
| id | menu_id | parent_id |
| 1  |    1    |    NULL   |
| 2  |    2    |    NULL   |
| 3  |    3    |     1     |
| 4  |    4    |     3     |
| 5  |    5    |     4     |
+----+---------+-----------+

Do the SELECT

SELECT child_menu.*, menu.* FROM menu, relations AS child_menu
WHERE menu.id = child_menu.menu_id
GROUP BY menu_id

I Have this:

+----+--------+-------+
| id |  name  | order |
| 1  | Father |   0   |
| 2  | Father |   1   |
| 3  | Son    |   0   |
| 4  | Child  |   1   |
| 5  | Granson|   2   |
+----+--------+-------+

I'm trying to leave their children in order in the same SELECT.
From what I see in the examples, only works if the parent is in the same table.
Can someone help me? thank you

Edited: EXPECTED OUTPUT:

+----+--------+-------+
| id |  name  | order |
| 1  | Father |   0   |
| 3  | Son    |   0   |
| 4  | Child  |   1   |
| 5  | Granson|   2   |
| 2  | Father |   1   |
+----+--------+-------+

I.E. Father
       Son
         Child
            Grandson

Answer 1

If you can create a MySQL User Defined Function, then you can dynamically create your family tree at execution time using something like the following:

DELIMITER //

CREATE FUNCTION fnFamilyTree ( id INT ) RETURNS TEXT
BEGIN
   SET @tree = '';
   SET @qid = id;
   WHILE (@qid > 0) DO
      SELECT IFNULL(r.parent_id,-1),m.ordr INTO @pid,@ordr FROM Relations r JOIN Menu m ON m.id = r.id WHERE r.id = @qid LIMIT 1;
      SET @tree = CONCAT(@ordr,' ',@tree);
      SET @qid = @pid;
   END WHILE;
   RETURN RTRIM(@tree);
END//

DELIMITER ;

Then the following SQL should give you the sequence you are seeking:

SELECT m.id
      ,m.name
      ,r.parent_id
      ,fnFamilyTree( r.id )
  FROM Relations r
  JOIN Menu m
    ON m.id = r.menu_id
 ORDER BY fnFamilyTree( r.id )
;

Try it at http://sqlfiddle.com/#!2/199c25/1. Results are:

ID  NAME            PARENT_ID        FNFAMILYTREE( R.ID )
1   Father          (null)           0
3   Son             1                0 0
4   Child           3                0 0 1
5   Granson         4                0 0 1 2
2   Father          (null)           1

At least, I think this is what you're after.

Update for actual schema

User Defined Function:

DELIMITER //

CREATE FUNCTION fnFamilyTree ( id INT ) RETURNS TEXT
BEGIN
   SET @tree = '';
   SET @qid = id;
   WHILE (@qid > 0) DO
      SELECT IFNULL(r.`menu_master_id`,-1),m.`order` INTO @pid,@order FROM `menu_has_menu_master` r JOIN `menu` m ON m.`id` = r.`menu_id` WHERE r.`menu_id` = @qid LIMIT 1;
      SET @tree = CONCAT(LPAD(@order,5,'0'),' ',@tree);
      SET @qid = @pid;
   END WHILE;
   RETURN RTRIM(@tree);
END
//

DELIMITER ;

Query:

SELECT m.id
      ,m.name
      ,r.menu_master_id
      ,fnFamilyTree( r.menu_id )
  FROM menu_has_menu_master r
  JOIN menu m
    ON m.id = r.menu_id
 ORDER BY fnFamilyTree( r.menu_id )
;

Results at http://sqlfiddle.com/#!2/cb0384

ID      NAME                  MENU_MASTER_ID    FNFAMILYTREE( R.MENU_ID )
8       Dashboard             (null)            00001
6       Seções do Site      (null)            00002
7       Home                  6                 00002 00003
14      Catalogos             6                 00002 00004
15      Marcas                14                00002 00004 00004
16      Categoria 1           14                00002 00004 00006
9       Arquivos              (null)            00007
1       Administração       (null)            00127
3       Usuarios              1                 00127 00001
5       Secões do iPocket    1                 00127 00001
13      Default Setups        1                 00127 00002
4       Logs                  1                 00127 00003

Answer 2

You need somehow a self join to show the relationship. After ...relations As child_menu you need to add left join relations as r2 on r2.parent_id = child_menu.id...

Answer 3

There are other ways to organize hierarchical data besides the methods shown in Mike Hillyer's blog. I like to use a method I call transitive closure table or closure table for short. In this design, you store every path through the hierarchy, as ancestor/descendant pairs.

create table closure (
    ancestor int,
    descendant int,
    length int,
    primary key (ancestor,descendant),
    key (descendant,ancestor)
);
insert into closure values
(1,1,0),
(1,3,1),
(1,4,2),
(1,5,3),
(2,2,0),
(3,3,0),
(3,4,1),
(3,5,2),
(4,4,0),
(4,5,1),
(5,5,0);

Note that this set includes even the "paths" of length zero, i.e. a menu item is an "parent" of itself.

Now you can join each menu item m to every its set of ancestors a, by joining to paths where m is the descandant. From there, join back to the menu item o which is in the set of ancestors, and you can access the order.

Use GROUP_CONCAT() to make a string of "breadcrumbs" from the order of each in the chain of ancestors, and this becomes a string you can sort by to get the menu order you want.

SELECT m.*, GROUP_CONCAT(o.`order` ORDER BY a.length DESC) AS breadcrumbs
FROM menu AS m
INNER JOIN closure AS a ON a.descendant = m.id
INNER JOIN menu AS o ON a.ancestor = o.id
GROUP BY m.id
ORDER BY breadcrumbs;

+----+----------+-------+-------------+
| id | name     | order | breadcrumbs |
+----+----------+-------+-------------+
|  1 | Father1  |     0 | 0           |
|  3 | Son      |     0 | 0,0         |
|  4 | Child    |     1 | 0,0,1       |
|  5 | Grandson |     2 | 0,0,1,2     |
|  2 | Father2  |     1 | 1           |
+----+----------+-------+-------------+

Note that the breadcrumbs sort as a string, so if you have some order numbers with 2 or 3 digits, you will get irregular results. Make sure your order numbers all have the same number of digits.

---

As an alternative, you could simply store the breadcrumbs strings in your original menu table:

ALTER TABLE menu ADD COLUMN breadcrumbs VARCHAR(255);
UPDATE menu SET breadcrumbs = '0,0,1,2' WHERE id = 5;
etc.

Then you can do a simpler query:

SELECT * FROM menu ORDER BY breadcrumbs;

But then it's up to you to manually recalculate all affected breadcrumb strings, if you ever change the order of the menu items.