Baumstruktur und Rekursion

Question

eine PostgreSQL-Datenbank 8.4.14 verwenden, habe ich eine Tabelle, die eine Baumstruktur wie im folgenden Beispiel darstellt:

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 

Ich möchte eine Access Control List für diese Einheiten zu schaffen, wobei jede Einheit ihre eigene ACL haben kann oder sie vom nächsten Vorfahren mit einer eigenen ACL erbt.

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 

Ich verwende eine Ansicht, um zu bestimmen, ob ein Gerät erbt es ACL ist von einem Vorfahren:

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 

Meine Frage ist: wie kann ich das bekommen nächste Einheit, die ist NICHT erbt die ACL von einem Vorfahren? Mein erwartetes Ergebnis sollte auf die folgende Tabelle/Ansicht ähnlich aussehen:

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

Answer 1

Eine Abfrage mit einem recursive CTE könnte die Arbeit erledigen. Benötigt PostgreSQL 8.4 oder später:

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 

Die Abbruchbedingung in der zweiten Etappe der UNION ist n.acl IS NULL. Damit hört die Abfrage auf, den Baum zu durchqueren, sobald eine gefunden wird.
Im letzten SELECT geben wir nur die Zeilen zurück, in denen ein gefunden wurde. Voilá.

Als Nebenbemerkung: Es ist ein Anti-Muster, den generischen, nicht beschreibenden id als Spaltenname zu verwenden. Leider tun dies einige ORMs standardmäßig. Nennen Sie es unit_id und Sie müssen die ganze Zeit keine Aliase in Abfragen verwenden.