Tree Structure and Recursion

Question

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 varchar(64) NOT NULL,
    parent_id bigint,
    FOREIGN KEY (parent_id) REFERENCES unit (id)
);
INSERT INTO unit VALUES (1, 'parent', NULL), (2, 'child', 1)
                      , (3, 'grandchild A', 2), (4, 'grandchild B', 2);

 id |    name      | parent_id 
----+--------------+-----------
  1 | parent       |          
  2 | child        |         1
  3 | grandchild A |         2
  4 | grandchild B |         2

I want to create an Access Control List for those units, where each unit may have it's own ACL, or is inheriting it from the nearest ancestor with an own ACL.

CREATE TABLE acl (
    unit_id bigint NOT NULL PRIMARY KEY,
    FOREIGN KEY (unit_id) REFERENCES unit (id)
);
INSERT INTO acl VALUES (1), (4);

 unit_id 
---------
       1
       4

I'm using a view to determine if a unit is inheriting it's ACL from an ancestor:

CREATE VIEW inheriting_acl AS
    SELECT u.id AS unit_id, COUNT(a.*) = 0 AS inheriting
    FROM unit AS u
    LEFT JOIN acl AS a ON a.unit_id = u.id
    GROUP BY u.id;

 unit_id | inheriting 
---------+------------
       1 | f
       2 | t
       3 | t
       4 | f

My question is: how can I get the nearest unit which is NOT inheriting the ACL from an ancestor? My expected result should look similar to the following table/view:

 unit_id | acl 
---------+------------
       1 | 1
       2 | 1
       3 | 1
       4 | 4

Solution

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 IS NOT NULL
ORDER  BY 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.

Comments

[Erwin Brandstetter]

+1 Very nice question. As always, your version of PostgreSQL should be included.