title: Tree Structure and Recursion
body: <p>Using a PostgreSQL 8.4.14 database, I have a table representing a tree structure like the following example:</p>
  
  <pre class="lang-sql prettyprint-override"><code>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);
  </code></pre>
  
  <pre class="lang-none prettyprint-override"><code> id |    name      | parent_id 
  ----+--------------+-----------
    1 | parent       |          
    2 | child        |         1
    3 | grandchild A |         2
    4 | grandchild B |         2
  </code></pre>
  
  <p>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.</p>
  
  <pre class="lang-sql prettyprint-override"><code>CREATE TABLE acl (
      unit_id bigint NOT NULL PRIMARY KEY,
      FOREIGN KEY (unit_id) REFERENCES unit (id)
  );
  INSERT INTO acl VALUES (1), (4);
  </code></pre>
  
  <pre class="lang-none prettyprint-override"><code> unit_id 
  ---------
         1
         4
  </code></pre>
  
  <p>I'm using a view to determine if a unit is inheriting it's ACL from an ancestor:</p>
  
  <pre class="lang-sql prettyprint-override"><code>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;
  </code></pre>
  
  <pre class="lang-none prettyprint-override"><code> unit_id | inheriting 
  ---------+------------
         1 | f
         2 | t
         3 | t
         4 | f
  </code></pre>
  
  <p><strong>My question is:</strong> how can I get the nearest unit which is <em>NOT</em> inheriting the ACL from an ancestor? My expected result should look similar to the following table/view:</p>
  
  <pre><code> unit_id | acl 
  ---------+------------
         1 | 1
         2 | 1
         3 | 1
         4 | 4
  </code></pre>