get parents and children of tree folder structure in my sql < 8 and no CTEs

Question

I have a folder table that joins to itself on an id, parent_id relationship:

CREATE TABLE folders (
  id int(10) unsigned NOT NULL AUTO_INCREMENT,
  title nvarchar(255) NOT NULL,
  parent_id int(10) unsigned DEFAULT NULL,
  PRIMARY KEY (id)
);

INSERT INTO folders(id, title, parent_id) VALUES(1, 'root', null);
INSERT INTO folders(id, title, parent_id) values(2, 'one', 1);
INSERT INTO folders(id, title, parent_id) values(3, 'target', 2);
INSERT INTO folders(id, title, parent_id) values(4, 'child one', 3);
INSERT INTO folders(id, title, parent_id) values(5, 'child two', 3);
INSERT INTO folders(id, title, parent_id) values(6, 'root 2', null);
INSERT INTO folders(id, title, parent_id) values(7, 'other child one', 6);
INSERT INTO folders(id, title, parent_id) values(8, 'other child two', 6);

I want a query that returns all the parents of that record, right back to the route and any children.

So if I ask for folder with id=3, I get records: 1, 2, 3, 4, 5. I am stuck how to get the parents.

The version of MYSQL is 5.7 and there are no immediate plans to upgrade so sadly CTEs are not an option.

I have created this sql fiddle

Answer 1

In your table design, ID and PARENT_ID corresponds to the "Adjacency List Model" for storing a tree.

There is another design, called the "Nested Set Model", which makes it easier to perform the operations you want here.

See this excellent article from Mike Hillyer describing both: managing-hierarchical-data-in-mysql

In summary:

The tree is stored in a table like:

CREATE TABLE nested_category (
        category_id INT AUTO_INCREMENT PRIMARY KEY,
        name VARCHAR(20) NOT NULL,
        lft INT NOT NULL,
        rgt INT NOT NULL
);

Finding the path from the root to a given node (here, 'FLASH'):

SELECT parent.name
FROM nested_category AS node,
        nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
        AND node.name = 'FLASH'
ORDER BY parent.lft;

Finding all children of a given node (here 'PORTABLE ELECTRONICS'):

SELECT node.name, (COUNT(parent.name) - (sub_tree.depth + 1)) AS depth
FROM nested_category AS node,
        nested_category AS parent,
        nested_category AS sub_parent,
        (
                SELECT node.name, (COUNT(parent.name) - 1) AS depth
                FROM nested_category AS node,
                        nested_category AS parent
                WHERE node.lft BETWEEN parent.lft AND parent.rgt
                        AND node.name = 'PORTABLE ELECTRONICS'
                GROUP BY node.name
                ORDER BY node.lft
        )AS sub_tree
WHERE node.lft BETWEEN parent.lft AND parent.rgt
        AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt
        AND sub_parent.name = sub_tree.name
GROUP BY node.name
HAVING depth <= 1
ORDER BY node.lft;

After renaming to your folders table

• TABLE nested_category -> TABLE folders
• Column category_id -> Column id
• Column name -> Column title

The solution is:

CREATE TABLE folders (
        id INT AUTO_INCREMENT PRIMARY KEY,
        title VARCHAR(20) NOT NULL,
        lft INT NOT NULL,
        rgt INT NOT NULL
);

INSERT INTO folders(id, title, lft, rgt) values(1, 'root', 1, 10);
INSERT INTO folders(id, title, lft, rgt) values(2, 'one', 2, 9);
INSERT INTO folders(id, title, lft, rgt) values(3, 'target', 3, 8);
INSERT INTO folders(id, title, lft, rgt) values(4, 'child one', 4, 5);
INSERT INTO folders(id, title, lft, rgt) values(5, 'child two', 6, 7);
INSERT INTO folders(id, title, lft, rgt) values(6, 'root 2', 11, 16);
INSERT INTO folders(id, title, lft, rgt) values(7, 'other child one', 12, 13);
INSERT INTO folders(id, title, lft, rgt) values(8, 'other child two', 14, 15);

Path to the target:

SELECT parent.title
FROM folders AS node,
        folders AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
        AND node.title = 'target'
ORDER BY parent.lft;

Target children:

SELECT node.title, (COUNT(parent.title) - (sub_tree.depth + 1)) AS depth
    FROM folders AS node,
            folders AS parent,
            folders AS sub_parent,
            (
              SELECT node.title, (COUNT(parent.title) - 1) AS depth
                    FROM folders AS node,
                            folders AS parent
                    WHERE node.lft BETWEEN parent.lft AND parent.rgt
                            AND node.title = 'target'
                    GROUP BY node.title
                    ORDER BY node.lft
            )AS sub_tree
    WHERE node.lft BETWEEN parent.lft AND parent.rgt
            AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt
            AND sub_parent.title = sub_tree.title
    GROUP BY node.title
    HAVING depth <= 1
    ORDER BY node.lft;

See sqlfiddle

To get all the data in a single query, a union should do.

Answer 2

In MySQL 8.0, you can make use of the Recursive Common Table Expressions to adress this use case.

The following query gives you the parents of a given record (including the record itself):

with recursive parent_cte (id, title, parent_id) as (
  select id, title, parent_id
  from folders
  where id = 3
  union all
  select  f.id, f.title, f.parent_id
  from folders f
  inner join parent_cte pc on f.id = pc.parent_id
)
select * from parent_cte;

| id  | title  | parent_id |
| --- | ------ | --------- |
| 3   | target | 2         |
| 2   | one    | 1         |
| 1   | root   |           |

And here is a slightly different query, that returns the children tree of a given record:

with recursive children_cte (id, title, parent_id) as (
  select id, title, parent_id
  from folders
  where parent_id = 3
  union all
  select  f.id, f.title, f.parent_id
  from folders f
  inner join children_cte cc on f.parent_id = cc.id
)
select * from children_cte;

| id  | title     | parent_id |
| --- | --------- | --------- |
| 4   | child one | 3         |
| 5   | child two | 3         |

Both queriers can be combined as follows:

with recursive parent_cte (id, title, parent_id) as (
  select id, title, parent_id
  from folders
  where id = 3
  union all
  select  f.id, f.title, f.parent_id
  from folders f
  inner join parent_cte pc on f.id = pc.parent_id
),
children_cte (id, title, parent_id) as (
  select id, title, parent_id
  from folders
  where parent_id = 3
  union all
  select  f.id, f.title, f.parent_id
  from folders f
  inner join children_cte cc on f.parent_id = cc.id
)
select * from parent_cte
union all select * from children_cte;

| id  | title     | parent_id |
| --- | --------- | --------- |
| 3   | target    | 2         |
| 2   | one       | 1         |
| 1   | root      |           |
| 4   | child one | 3         |
| 5   | child two | 3         |

Demo on DB Fiddle