@toddbarry

Можно ли использовать двойной SELECT в RECURSIVE CTE?

Здравствуйте. Я столкнулся с проблемой реализации запроса к базе данных. Проблема заключается в реализации двойного SELECT в рекурсивных запросах. Подробнее - ниже.

У меня есть две таблицы, которые описывают ориентированный граф (отношение many-to-many), в котором узлы расположены на определенных позициях на сетке. grid_x, grid_y - координаты узла на сетке.
Table nodes
id
grid_x
grid_y

Table edges
id
source
target


Пусть представление информации в базе выглядит следующим образом:
2019-09-05-6-51-13.png

В табличном виде это представляется следующим образом:
5d729e862183e898109848.png5d729e8f3a2df092188069.png

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

WITH RECURSIVE
cte(id, grid_x, grid_y) AS (
    SELECT id, grid_x, grid_y
    FROM nodes WHERE id = 0
    UNION ALL
    SELECT current.id, current.grid_x, current.grid_y
        FROM nodes AS current, cte AS prev
    WHERE current.grid_x = prev.grid_x + 1
        AND current.grid_y = prev.grid_y
    )
    SELECT * FROM cte;


легко видеть что этот запрос вернет узлы 0 и 13: участок anchor выделит узел с id = 0, в рекурсивной части на первой итерации выделится узел, находящийся в непосредственной близости от узла 0 - то есть узел с id = 13. На 2й итерации в непосредственной близости правее узла 13 не окажется никаких узлов и поиск завершится.

Все работает хорошо, но мне необходимо выделять на каждой итерации помимо узлов, находящихся правее в непосредственной близости, так же дочерние узлы по отношению к выделенным на предыдущей итерации. Что я имею ввиду?

Например для приведенного выше предсатвления данных - anchor участок запроса должен выделить узел с id = 0. На первой итерации рекурсивного цикла должны выделиться узлы 13 (поскольку он находится в непосредственной близости правее узла 0), а так же 5 и 1 - поскольку они являются дочерними по отношению к узлу 0. На второй итерации должен выделиться узел 2, поскольку он находится в непосредственной близости правее узла 1 (узел 1 находится правее узла 5, однако он (узел 1) уже был выделен ранее), а так же узлы 12, 6, 7 - поскольку они являются дочерними по отношению к узлам 5 и 1, выделенными на предыдущей итерации и узел 3, поскольку он является дочерним по отношению к узлу 13, выделенному на предыдущей итерации. На третьей итерации среди новых узлов, не выделенных ранее должны быть узлы 8 и 9 поскольку они являются дочерними по отношению к узлам 2 и 3, выделенными ранее. Наконец на 4 итерации будет выделен узел 10, который находится в непосредственной близости от узла 9. На 5 итерации поиск должен прекратиться, поскольку нет новых узлов, являющихся дочерними к предыдущим или находящихся в непосредственной близости правее предыдущих.

Я попытался реализовать такой запрос следующим образом
WITH RECURSIVE
    cte(id, grid_x, grid_y) AS (
        SELECT id, grid_x, grid_y
        FROM nodes WHERE id = 0
    UNION ALL
        SELECT * FROM (
        SELECT current.id, current.grid_x, current.grid_y
        FROM nodes AS current, cte AS prev
        WHERE current.grid_x = prev.grid_x + 1
            AND current.grid_y = prev.grid_y
        UNION
        SELECT c.id, c.grid_x, c.grid_y
        FROM nodes AS c, cte AS p, edges AS e
        WHERE p.id = e.source AND c.id = e.target
            AND here should be checking on existing node at cte
        )
    )
    SELECT * FROM cte;


Однако получил ошибку:
recursive reference to query "cte" must not appear within a subquery


А попытка добиться результата при помощи запроса вида

WITH RECURSIVE
    cte(id, grid_x, grid_y) AS (
        SELECT id, grid_x, grid_y
        FROM nodes WHERE id = 0
    UNION ALL
    SELECT current.id, current.grid_x, current.grid_y
        FROM nodes AS current, edges AS e, cte AS prev
    WHERE (current.grid_x = prev.grid_x + 1
        AND current.grid_y = prev.grid_y)
        OR (prev.id = e.source AND e.target = current.id)
    )
    SELECT * FROM cte;


возвращает всего один узел 0.

Пожалуйста, помогите справитсья с данной задачей.
  • Вопрос задан
  • 154 просмотра
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы