Как сделать выборку всех категорий нижнего уровня в дереве категорий?

Question

[Егор Михеев]

Здравствуйте есть БД. psioner.com/myadmin usr: test pass: test, (выйдет ошибка после обращения, замените https:// на http:// прямо в строке с сохранением полного пути)
Забуксовал на тестовом вопросе:
3. На выборку всех категорий нижнего уровня ( т.е. не имеющих детей)

Сделал следующий запрос: SELECT DISTINCT * FROM `category` WHERE 1 GROUP BY `parent_category_id` Вывело список полей:
17-3
11-2
9-5
5-1
13-3
Но этого недостаточно,нужен запрос, который бы исключал еще и значения 1 столбца, встречающиеся во 2 (В данном случае это минус: 5-1 и 13-3, так как у них есть потомки.)
Прошу помощи!

Answer 1

[Rsa97]

В JOIN'ах вся сила!

SELECT `cat`.`id`, `cat`.`name`
    FROM `category` AS `cat`
    LEFT JOIN (
        SELECT DISTINCT `parent_category_id` AS `parent`
            FROM `category`
    ) AS `sub` ON `cat`.`id` = `sub`.`parent`
    WHERE `sub`.`parent` IS NULL

Но вообще, с деревом удобнее работать через Nested Set

Comments

[Егор Михеев]

Спасибо я читал про них, тогда вобще проще использовать специально заточенные под это БД https://en.wikipedia.org/wiki/Graph_database, просто суть задачи на готовой таблице. Спасибо попробую Вашу подсказку.

[Егор Михеев]

Ну это не полный ответ, тут выводит практически все категории и с потомками.

[Rsa97]

егор михеев: Вот ваша таблица в виде дерева:

1 - Авто
    5 - Раздел 1.1
        9 - Раздел 1.1.1
        10 - Раздел 1.1.2
    6 - Раздел 1.2
    7 - Раздел 1.3
    8 - Раздел 1.4
2 - Авто
    11 - Раздел 2.1
    12 - Раздел 2.2
3 - Раздел 3
    13 - Раздел 3.1
        17 - Раздел 3.1.1
        18- Раздел 3.1.2
    14 - Раздел 3.2
    15 - Раздел 3.3
    16 - Раздел 3.4
4 - Раздел 4

Потомки есть только у разделов 1, 2, 3, 5, 13
Вот результат моего запроса:

| 4  | Раздел 4
| 6  | Раздел 1.2
| 7  | Раздел 1.3
| 8  | Раздел 1.4
| 9  | Раздел 1.1.1
| 10 | Раздел 1.1.2
| 11 | Раздел 2.1
| 12 | Раздел 2.2
| 14 | Раздел 3.2
| 15 | Раздел 3.3
| 16 | Раздел 3.4
| 17 | Раздел 3.1.1
| 18 | Раздел 3.1.

Ни один раздел, имеющий потомков в выборку не попал.

[Егор Михеев]

А блин а может и Вы правы? Я немного по другому себе это представлял.

[Егор Михеев]

Хорошо, а можно. на БИС механику запроса описать, а то действительно сложновато с join как то.

[Rsa97]

егор михеев: Для нормальной работы с уровнями надо добавлять ещё одно поле - level, иначе придётся писать встроенную функцию, рассчитывающую уровень для каждой строки.

[Егор Михеев]

Т.е в контексте данной таблицы, то что я думал реализовать невозможно?

[Rsa97]

егор михеев: А ничего сложного в JOIN`ах нет, это просто функции из теории множеств. В данном случае берётся множество строк из таблицы `category` и множество уникальных (DISTINCT) `parent_category_id` из неё же. Затем для каждой строки первого множества (LEFT) справа добавляются (JOIN) по очереди все строки, соответствующие условию объединения (ON). Поскольку в правом множестве значения из условия уникальные, то каждой левой строке будет дописана одна правая ,если строка является родителем и её `id` есть среди `parent_category_id`, или ничего (NULL), если такого `id` там нет.
Остаётся во WHERE выбрать строки, имеющие NULL в нужном поле.

Первое множество (cat):

+----+--------------------+--------------+
| id | parent_category_id |     name     |
+----+--------------------+--------------+
|  1 |                  0 | Авто         |
|  2 |                  0 | Авто         |
|  3 |                  0 | Раздел 3     |
|  4 |                  0 | Раздел 4     |
|  5 |                  1 | Раздел 1.1   |
|  6 |                  1 | Раздел 1.2   |
|  7 |                  1 | Раздел 1.3   |
|  8 |                  1 | Раздел 1.4   |
|  9 |                  5 | Раздел 1.1.1 |
| 10 |                  5 | Раздел 1.1.2 |
| 11 |                  2 | Раздел 2.1   |
| 12 |                  2 | Раздел 2.2   |
| 13 |                  3 | Раздел 3.1   |
| 14 |                  3 | Раздел 3.2   |
| 15 |                  3 | Раздел 3.3   |
| 16 |                  3 | Раздел 3.4   |
| 17 |                 13 | Раздел 3.1.1 |
| 18 |                 13 | Раздел 3.1.2 |
+----+--------------------+--------------+

Второе множество (sub):
+--------+
| parent |
+--------+
| 0 |
| 1 |
| 2 |
| 3 |
| 5 |
| 13 |
+--------+

Результат объединения LEFT JOIN по условию в ON:

+--------+------------------------+--------------+------------+
| cat.id | cat.parent_category_id |   cat.name   | sub.parent |
+--------+------------------------+--------------+------------+
|      1 |                      0 | Авто         |          1 |
|      2 |                      0 | Авто         |          2 |
|      3 |                      0 | Раздел 3     |          3 |
|      4 |                      0 | Раздел 4     |       NULL |
|      5 |                      1 | Раздел 1.1   |          5 |
|      6 |                      1 | Раздел 1.2   |       NULL |
|      7 |                      1 | Раздел 1.3   |       NULL |
|      8 |                      1 | Раздел 1.4   |       NULL |
|      9 |                      5 | Раздел 1.1.1 |       NULL |
|     10 |                      5 | Раздел 1.1.2 |       NULL |
|     11 |                      2 | Раздел 2.1   |       NULL |
|     12 |                      2 | Раздел 2.2   |       NULL |
|     13 |                      3 | Раздел 3.1   |         13 |
|     14 |                      3 | Раздел 3.2   |       NULL |
|     15 |                      3 | Раздел 3.3   |       NULL |
|     16 |                      3 | Раздел 3.4   |       NULL |
|     17 |                     13 | Раздел 3.1.1 |       NULL |
|     18 |                     13 | Раздел 3.1.2 |       NULL |
+--------+------------------------+--------------+------------+

[Rsa97]

егор михеев: С уровнями - возможно, но надо писать встроенную процедуру, считающую уровень для строки (то есть проходящую от сроки до корня), затем делать выборку всех строк с уровнями, затем по этой таблице выбирать максимальный уровень и все строки с таким уровнем. Сделать можно, но работать будет крайне медленно.

[Rsa97]

егор михеев: Да, это если заранее неизвестен максимальный уровень. Если он известен и фиксирован (скажем, всегда третий), то можно написать несколькими JOIN'ами получение конкретного уровня.

[Rsa97]

SELECT * 
     FROM `category` AS `lvl1`
     LEFT JOIN `category` AS `lvl2` ON `lvl2`.`parent_category_id` = `lvl1`.`id`
     LEFT JOIN `category` AS `lvl3` ON `lvl3`.`parent_category_id` = `lvl2`.`id`
     WHERE `lvl1`.`parent_category_id` = 0
     ORDER BY `lvl1`.`name`, `lvl2`.`name`, `lvl3`.`name`

[Егор Михеев]

Спасибо огромное, очень доходчиво объяснили!

[Егор Михеев]

Вобщем LEFT JOIN это объединение двух множеств.

[Rsa97]

егор михеев: Объединение множеств - это JOIN в целом. Если не накладывать условие в ON, то все варианты работают одинаково, к каждому элементу левого множества добавляется элемент правого множества:
{1, 2} JOIN {1, 3} => {1|1, 1|3, 2|1, 2|3}
Если добавляется условие, то в результат попадают только комбинации, соответствующие условию (JOIN, CROSS JOIN и INNER JOIN - синтаксически эквивалентны):
{1, 2} INNER JOIN {1, 3} ON left = right => {1|1}
Если надо, чтобы элемент левого множества включался в результат даже если для него нет подходящего элемента в правом множестве, используется LEFT JOIN:
{1, 2} LEFT JOIN {1, 3} ON left = right => {1|1, 2|NULL}
Аналогично RIGHT JOIN в любом случае включает все элементы из правого множества:
{1, 2} RIGHT JOIN {1, 3} ON left = right => {1|1, NULL|3}
В SQL есть ещё не поддерживаемый в MySQL OUTER JOIN, в нём элементы обоих множеств включаются в любом случае:
{1, 2} OUTER JOIN {1, 3} ON left = right => {1|1, 2|NULL, NULL|3}