Get all descendants from 3 hierarchical tables

Question

I have the following tables within a database:

+-------------+   +-------------+-------------+   +---------------------------+
|  project1   |   |          project2         +   |         project3          |
+-------------+   +-------------+-------------+   +---------------------------+
| project1_id |   | project2_id | project1_id |   | project3_id | project2_id |
+-------------+   +-------------+-------------+   +---------------------------+
|    hnc1     |   |    hnc4     |     hnc1    |   |     hnc7    |    hnc4     |
|    hnc2     |   |    hnc5     |     hnc1    |   |     hnc8    |    hnc4     |
|    hnc3     |   |    hnc6     |     hnc3    |   |     hnc9    |    hnc6     |
+-------------+   +-------------+-------------+   +---------------------------+

I need to retrieve all descendants of a given ID from all three tables - including the ID itself if it is found in any table.

For example, if I query using the ID 'hnc4' it should get:

+-------------+
| descendants |
+-------------+
|    hnc7     |
|    hnc8     |
|    hnc4     |
+-------------+

If I query using the ID 'hnc1':

+-------------+
| descendants |
+-------------+
|    hnc4     |
|    hnc5     |
|    hnc7     |
|    hnc8     |
|    hnc1     |
+-------------+

The query must work even if the ID is only in the last table project3.

I was searching and found that a recursive CTE could be useful but I don't know how to make it with 3 tables involved.

Any guidance on how to get with the right results?

Answer 1

Identifiers cannot be parameterized, so I can't think of a way to traverse multiple tables with an rCTE.

Assuming UNIQUE or PRIMARY KEY constraints on each table, so we don't have to worry about duplicates.

I wrapped the query in a SQL function to simplify passing the ID:

CREATE OR REPLACE FUNCTION f_all_descendants_of(_id text)
  RETURNS TABLE (descendants text) AS
$func$
   WITH p2 AS (
      SELECT project2_id
      FROM   project2
      WHERE  project1_id = $1
         OR  project2_id = $1
      )

   SELECT project3_id AS descendants
   FROM   project3
   WHERE  project2_id IN (TABLE p2)
      OR  project3_id = $1

   UNION ALL TABLE p2

   UNION ALL
   SELECT project1_id
   FROM   project1
   WHERE  project1_id = $1;
$func$  LANGUAGE sql;

The SELECT on project2 goes into CTE p2, so we can reuse the result for the SELECT on project3. The same is not needed for project1 and project3.

Call:

SELECT * FROM f_all_descendants_of('hnc4');

Produces your desired result exactly.

SQL Fiddle.

If the tables are big, be sure to have the right indexes. Related:

• Is a composite index also good for queries on the first field?

Answer 2

Schema Upgrade

You don't need three tables to have a single-inheritance. You can do that with a single table. This is not just faster and cleaner, and better at maintaining integrity but it allows more than three levels of depth (n-level)

CREATE TABLE foo (
  id         int  PRIMARY KEY,
  id_parent  int  REFERENCES foo,
  CHECK (id>id_parent)
);

INSERT INTO foo (id, id_parent)
VALUES
  (1,null),  -- null = no parent, ancestors
  (2,null),  -- all of these are separate trees.
  (3,null),
  ( 4, 1 ),
  ( 5, 1 ),
  ( 6, 3 ),
  ( 7, 4 ),
  ( 8, 4 ),
  ( 9, 6 );

Now we can query it,

WITH RECURSIVE t(id, id_parent, level, path) AS (
  SELECT id, id_parent, 0, ARRAY[id]
  FROM foo
  WHERE id_parent IS NULL
  UNION ALL
    SELECT foo.id, foo.id_parent, level+1, path + foo.id
    FROM t
    JOIN foo ON (foo.id_parent = t.id)
)
SELECT *
FROM t;

 id | id_parent | level |  path   
----+-----------+-------+---------
  1 |           |     0 | {1}
  2 |           |     0 | {2}
  3 |           |     0 | {3}
  4 |         1 |     1 | {1,4}
  5 |         1 |     1 | {1,5}
  6 |         3 |     1 | {3,6}
  7 |         4 |     2 | {1,4,7}
  8 |         4 |     2 | {1,4,8}
  9 |         6 |     2 | {3,6,9}
(9 rows)

This pattern is called a "single-table hierarchy", or a self-referencing table.

Backwards Compatable

In fact if you want to get back to the silly three table design..

Create a view that does that last query,

CREATE VIEW foo_level1 AS
WITH RECURSIVE t(id, id_parent, level, path) AS (
  SELECT id, id_parent, 0, ARRAY[id]
  FROM foo
  WHERE id_parent IS NULL
  UNION ALL
    SELECT foo.id, foo.id_parent, level+1, path + foo.id
    FROM t
    JOIN foo ON (foo.id_parent = t.id)
)
SELECT *
FROM t WHERE level = 0;

Just keep following that..

CREATE VIEW foo_level2 AS [...] WHERE level = 1;
CREATE VIEW foo_level3 AS [...] WHERE level = 2;

Your queries

To get all the ancestors of hcn4 or 4 in my table, change the terminal point and build it in the opposite direction.

WITH RECURSIVE t(id, id_parent, level, path) AS (
  SELECT id, id_parent, 0, ARRAY[id]
  FROM foo
  WHERE id = 4
  UNION ALL
    SELECT foo.id, foo.id_parent, level+1, path + foo.id
    FROM t
    JOIN foo ON (t.id = foo.id_parent)
)
 AS
  SELECT * FROM t;

Want hcn1 just need to switch it to WHERE id = 1;

WITH RECURSIVE t(id, id_parent, level, path) AS (
  SELECT id, id_parent, 0, ARRAY[id]
  FROM foo
  WHERE id = 1
  UNION ALL
    SELECT foo.id, foo.id_parent, level+1, path + foo.id
    FROM t
    JOIN foo ON (t.id = foo.id_parent)
)
SELECT *
FROM t;

 id | id_parent | level |  path   
----+-----------+-------+---------
  1 |           |     0 | {1}
  4 |         1 |     1 | {1,4}
  5 |         1 |     1 | {1,5}
  7 |         4 |     2 | {1,4,7}
  8 |         4 |     2 | {1,4,8}
(5 rows)

The equivolent, f_all_descendants_of(int) becomes,

CREATE FUNCTION f_all_descendants_of(_id int)
RETURNS TABLE (id int, id_parent int, level int, path int[]) AS $$
  WITH RECURSIVE t(id, id_parent, level, path) AS (
    SELECT id, id_parent, 0, ARRAY[id]
    FROM foo
    WHERE id = _id
    UNION ALL
      SELECT foo.id, foo.id_parent, level+1, path + foo.id
      FROM t
      JOIN foo ON (t.id = foo.id_parent)
  )
  SELECT * FROM t;
$$ LANGUAGE sql
IMMUTABLE;