Tree Structure And Recursion

Using a PostgreSQL 8.4.14 database, I have a table representing a tree structure like the following example: CREATE TABLE unit ( id bigint NOT NULL PRIMARY KEY, name varcha

Solution 1:

A query with a recursive CTE could do the job. Requires PostgreSQL 8.4 or later:

WITH RECURSIVE next_in_line AS (
    SELECT u.id AS unit_id, u.parent_id, a.unit_id AS acl
    FROM   unit u
    LEFT   JOIN acl a ON a.unit_id = u.id

    UNION  ALL
    SELECT n.unit_id, u.parent_id, a.unit_id
    FROM   next_in_line n
    JOIN   unit u ON u.id = n.parent_id AND n.acl IS NULL
    LEFT   JOIN acl a ON a.unit_id = u.id
    )
SELECT unit_id, acl
FROM   next_in_line
WHERE  acl ISNOT NULL
ORDERBY unit_id

The break condition in the second leg of the UNION is n.acl IS NULL. With that, the query stops traversing the the tree as soon as an acl is found. In the final SELECT we only return the rows where an acl was found. Voilá.

As an aside: It is an anti-pattern to use the generic, non-descriptive id as column name. Sadly, some ORMs do that by default. Call it unit_id and you don't have to use aliases in queries all the time.