0

Say I have the mdl_course_categories table:

select cat.id, cat.name, cat.parent, cat.depth, cat.path
from mdl_course_categories cat

| id | name | parent | depth | path     |
|----|------|--------|-------|----------|
| 1  | a    | 0      | 1     | /1       |
| 2  | b    | 0      | 1     | /2       |
| 3  | c    | 1      | 2     | /1/3     |
| 4  | d    | 3      | 3     | /1/3/4   |
| 5  | e    | 4      | 4     | /1/3/4/5 |
| 6  | f    | 0      | 1     | /6       |
| 7  | g    | 6      | 2     | /6/7     |
| 8  | h    | 7      | 3     | /6/7/8   |
| 9  | i    | 3      | 3     | /1/3/9   |
| 10 | j    | 7      | 3     | /6/7/10  |

How can I generate the breadcrumbs as per below? I'm a complete rookie to SQL, and have no experience managing hierarchial data. I had a look at this answer, but was unable to translate it to my table and situation. Thanks in advance!

| id | name | parent | depth | path     | breadcrumb    |
|----|------|--------|-------|----------|---------------|
| 1  | a    | 0      | 1     | /1       | a             |
| 2  | b    | 0      | 1     | /2       | b             |
| 3  | c    | 1      | 2     | /1/3     | a - c         |
| 4  | d    | 3      | 3     | /1/3/4   | a - c - d     |
| 5  | e    | 4      | 4     | /1/3/4/5 | a - c - d - e |
| 6  | f    | 0      | 1     | /6       | f             |
| 7  | g    | 6      | 2     | /6/7     | f - g         |
| 8  | h    | 7      | 3     | /6/7/8   | f - g - h     |
| 9  | i    | 3      | 3     | /1/3/9   | a - b - i     |
| 10 | j    | 7      | 3     | /6/7/10  | f - g - j     |
Zectzozda
  • 77
  • 7

1 Answers1

3
WITH RECURSIVE
cte1 AS 
(
SELECT 1 num
UNION ALL
SELECT num + 1
FROM cte1
WHERE num < ( SELECT MAX(LENGTH(path) - LENGTH(REPLACE(path, '/', '')))
              FROM mdl_course_categories )
),
cte2 AS 
(
SELECT cte1.num, 
       cat.*, 
       SUBSTRING_INDEX(SUBSTRING_INDEX(cat.path, '/', cte1.num+1), '/', -1) onechar
FROM cte1, mdl_course_categories cat
WHERE cte1.num <= (LENGTH(path) - LENGTH(REPLACE(cat.path, '/', '')))
),
cte3 AS 
(
SELECT cte2.*, cat.name onecharname
FROM cte2, mdl_course_categories cat
WHERE cte2.onechar = cat.id
)
SELECT id, name, parent, depth, path, GROUP_CONCAT(onecharname ORDER BY num SEPARATOR ' - ') breadcrumb
FROM cte3
GROUP BY id, name, parent, depth, path;

fiddle

Of course it can be compacted, but I think you can do it by yourself.

At the request of @Shadow I also give a simple solution

SELECT t1.id, 
       t1.name, 
       t1.parent, 
       t1.depth, 
       t1.path, 
       GROUP_CONCAT(t2.name ORDER BY LOCATE(CONCAT('/', t2.id, '/'), CONCAT(t1.path, '/')) SEPARATOR ' - ') breadcrumb
FROM mdl_course_categories t1, 
     mdl_course_categories t2
WHERE LOCATE(CONCAT('/', t2.id, '/'), CONCAT(t1.path, '/'))
GROUP BY t1.id, 
         t1.name, 
         t1.parent, 
         t1.depth, 
         t1.path;

PS. Remember, 1st is O(N*AVG(M)) whereas 2nd is O(N*N) - where N is amount of records, and M is tree depth.

Akina
  • 39,301
  • 5
  • 14
  • 25
  • 1) The whole point of materialised path technique is to avoid recursion, so your solution kinda defeats the purpose of the whole technique. 2) A join and group_concat() can do all the above (yeah, the join will require full table scan) – Shadow Feb 17 '20 at 08:02
  • @Shadow *The whole point of materialised path technique is to avoid recursion* The subtask solved by recursion is not relative to the materialised path technique and solves another task. – Akina Feb 17 '20 at 08:24
  • Yes, it is related to the underlying technique used. If you revert to recursion, then an adjancency list would be easier and faster, since you would not have to do expensive string manipulation. – Shadow Feb 17 '20 at 08:36
  • Thank you for the solution, @Akina! The simplified solution is exactly what I'm looking for! – Zectzozda Feb 17 '20 at 23:15
  • Say, if I only had the `name` of the category I wanted to filter on, how could I filter to only display the category `f` and it's sub-categories? i.e. shows `f`, `f - g`, `f - g - h`, and `f - g - j` in my example data. – Zectzozda Feb 17 '20 at 23:27
  • 1
    @Zectzozda `WHERE LOCATE('f', value) = 1` or `WHERE value LIKE 'f%'`. – Akina Feb 18 '20 at 10:49
  • The 2nd version is not n*n problem, you are not creating a cartesian join. The condition in the where clause can be moved into the join condition (mysql optimiser will probably do that anyway). – Shadow Feb 19 '20 at 07:57
  • @Shadow The condition does not allow index usage - so it is cartesian, fullscan will be used for calculate joining expression value for each separate records pair. *The condition in the where clause can be moved into the join condition (mysql optimiser will probably do that anyway).* Read "How MySQL optimizes joins" - everything is strongly backward. – Akina Feb 19 '20 at 08:12
  • Sorry to point out but in this case your solution is also n*n, since the recursive cte cannot use an index either to restrict the values from the underlying table. – Shadow Feb 19 '20 at 08:35
  • @Shadow Recursive `cte1` does not need in a table in its recursion, and its subquery will be executed once (yes, using fullscan), it is O(N) and do not affect on the final complexity. – Akina Feb 19 '20 at 08:42
  • And then matched against without any indexes to the 2nd cte... Sorry man, not buying your argument. – Shadow Feb 19 '20 at 18:45
  • Is there a way to re-write the `from` and `where` clause into a join? I've tried joining on the where clause, but it only shows the category name - no breadcrumb. `from mdl_course_categories t1 join mdl_course_categories t2 on locate(concat('/', t2.id, '/'), concat(t1.path, '/')) = 1` – Zectzozda Feb 21 '20 at 04:17
  • @Zectzozda Why `=1`? Where it is taken from? Simply `FROM mdl_course_categories t1 JOIN mdl_course_categories t2 ON LOCATE(CONCAT('/', t2.id, '/'), CONCAT(t1.path, '/'))` – Akina Feb 21 '20 at 04:46
  • D'Oh! I thought the join had to resolve to an `a = b`, so I used `= 1` to resolve as true. Thanks for fixing my blonde moment :) – Zectzozda Feb 21 '20 at 04:56
  • @Zectzozda ON clause needs a value which may be treated as boolean. LOCATE() returns integer, which may - if NULL or zero, it is treated as FALSE, else it is treated as TRUE. – Akina Feb 21 '20 at 05:04
  • Anyone here so happens to know the SQL Server 2016 version of this? I've been tearing my hair out trying to figure it out! – Zectzozda Apr 13 '20 at 23:42