T
T
toddbarry2019-09-06 20:56:08
PostgreSQL
toddbarry, 2019-09-06 20:56:08

Is it possible to use a double SELECT in a RECURSIVE CTE?

Hello. I ran into a problem with implementing a database query. The problem lies in the implementation of the double SELECT in recursive queries. More details below.
I have two tables that describe a directed graph (many-to-many relationship) in which the nodes are located at certain positions on the grid. grid_x, grid_y - node coordinates on the grid.

Table nodes
id
grid_x
grid_y

Table edges
id
source
target

Let the representation of information in the database look like this:
2019-09-05-6-51-13.png
In tabular form, it is represented as follows:
5d729e862183e898109848.png5d729e8f3a2df092188069.png
I can write a database query that recursively returns all nodes that are in the immediate vicinity to the right of a given node.
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;

it is easy to see that this query will return nodes 0 and 13: the anchor section will select the node with id = 0; there will be no nodes to the right of node 13 and the search will end.
Everything works well, but I need to select at each iteration, in addition to the nodes located to the right in close proximity, also the child nodes in relation to those selected in the previous iteration. What I mean?
For example, for the above data representation - anchor, the query section should select the node with id = 0. At the first iteration of the recursive loop, nodes 13 should be selected (since it is located in the immediate vicinity to the right of node 0), as well as 5 and 1 - since they are children in relation to node 0. At the second iteration, node 2 should be selected, since it is located in the immediate vicinity to the right of node 1 (node ​​1 is to the right of node 5, but it (node ​​1) has already been selected earlier), as well as nodes 12, 6 , 7 because they are children of nodes 5 and 1 allocated in the previous iteration and node 3 because it is a child of node 13 allocated in the previous iteration. At the third iteration, among the new nodes, nodes 8 and 9 that were not previously allocated should be, since they are children of nodes 2 and 3 that were previously allocated. Finally, at iteration 4, node 10 will be selected, which is in close proximity to node 9. At iteration 5, the search should stop, since there are no new nodes that are children of the previous ones or are in close proximity to the right of the previous ones.
I tried to implement such query like this
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;

However got an error:
recursive reference to query "cte" must not appear within a subquery

And an attempt to achieve a result using a query like
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;

returns only one node 0.
Please help us with this task.

Answer the question

In order to leave comments, you need to log in

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question