Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Составление SQL-запросов > Помогите написать хитровыдуманный запрос

Автор: polin11 22.11.2018, 02:36

СУБД postgresql.
Помогите написать хитровыдуманный
запрос, есть иерархическая таблица - боги Древней Греции.
У каждой записи, есть поле parent_id - идентификатор родителя записи, level - уровень записи.
Уровень 1. Корень - Хаос (дети: Зевс, Посейдон)
Уровень 2. Зевс (дети: Афина, Гермес)
           Посейдон(дети: Тритон)
Уровень 3. Афина (дети: Эрхитоний)
           Гермес (дети: нет)
           Тритон (дети: нет)
Уровень 4. Эрхитоний (дети: нет)

Код


CREATE TABLE gods(id integer PRIMARY KEY, name text,  parent_id integer, level integer);
INSERT INTO Gods VALUES(1,'Хаос', NULL, 1);
INSERT INTO Gods VALUES(2,'Зевс', 1, 2);
INSERT INTO Gods VALUES(3,'Посейдон', 1, 2);
INSERT INTO Gods VALUES(4,'Афина', 2, 3);
INSERT INTO Gods VALUES(6,'Гермес', 2, 3);
INSERT INTO Gods VALUES(7,'Тритон',3,3);
INSERT INTO Gods VALUES(8,'Эрхитоний',4,4);

Как итог имеем n-арное дерево, нужно написать хитровыдуманный запрос,
который сделает прямой обход этого дерева.
В итоге нужно получить список
1) Хаос
2) Зевс
3) Афина
4) Эрхитоний
5)Гермес
6) Посейдон
7) Тритон

Автор: ksnk 22.11.2018, 11:44

polin11, А цель хитровыдуманности какая ? Для обучения и спорта, или потом с этим надо будет жить ? Если жить - то можно трансформировать табличку в nested-sets (добавить в нее пару полей) и получать поддерево любой веточки одним простым запросом.
Если хочется спорта и постгресса, то вот поправленный запрос с предыдущего ответа
https://www.db-fiddle.com/f/6iRkVhCfa3Z6wuw6dMETC5/0

P.S. smile

Куда-то пропал предыдущий ответ, но мы его помним ...

Автор: Akina 22.11.2018, 12:27

Цитата(polin11 @ 22.11.2018, 03:36

)

нужно написать хитровыдуманный запрос,
который сделает прямой обход этого дерева.

Обход дерева в глубину - это итерационная задача, а не реляционная. Решать её нужно на стороне клиента.
Можно, конечно, делать это и на стороне сервера в формате хранимой процедуры - но неразумно. Только если в реальной задаче соотношение размера записи таблицы к размеру записи выходного набора достаточно велико (хотя бы 2).
А поле level в данной задаче вообще нафиг не нужно.

Автор: Snowy 22.11.2018, 12:39

Код

CREATE TABLE gods(id integer PRIMARY KEY, name text,  parent_id integer REFERENCES gods ON DELETE CASCADE, level integer);

INSERT INTO Gods (id, name, parent_id, level)
VALUES (1,'Хаос', NULL, 1), (2,'Зевс', 1, 2), (3,'Посейдон', 1, 2), (4,'Афина', 2, 3), (6,'Гермес', 2, 3), (7,'Тритон',3,3), (8,'Эрхитоний',4,4);

WITH RECURSIVE r AS (
  SELECT g.id, array[id] as path
  FROM gods g WHERE g.parent_id IS NULL
  UNION ALL
  SELECT g.id, path || g.id
  FROM r, gods g
  WHERE g.parent_id=r.id
) SELECT g.*, r.path FROM gods g, r WHERE g.id=r.id ORDER BY r.path;

Автор: Akina 22.11.2018, 12:47

Snowy, нормализуйте g.id ведущими нулями - иначе при сортировке чисел как строк всё поплывёт... или добавьте разделитель.

Автор: Snowy 22.11.2018, 12:51

Цитата(Akina @ 22.11.2018, 13:27

)

А поле level в данной задаче вообще нафиг не нужно.

Угу. оно элементарно высчитывается, как cardinality(r.path)

Цитата(Akina @ 22.11.2018, 13:47

)

Snowy, нормализуйте g.id ведущими нулями - иначе при сортировке чисел как строк всё поплывёт...

Это не строка, а массив integer[]