Postgresql – How to select nodes where all children is satisfied

postgresqlrelational-theoryselecttree

I have a tree structure of light bulbs. I want to turn on all the light bulbs starting from the leafs of the tree. A light bulb cannot be turned on unless all its immediate children are turned on.

The relation between the nodes in the tree structure is represented by table A:

Table A:

node_id integer
child_node_id integer

Table B represents the nodes in the tree:

Table B:

id integer
state boolean

The state of table B represents the states true = on and false = off.

Question:
I would like to select all the light bulbs which are turned off AND has all immediate children turned on.

This is probably very simple, but I can't seem to get my head around it.

Best Answer

I would first rethink the design. You only need one table:

CREATE TABLE c (
  id integer PRIMARY KEY
 ,parent_id integer REFERENCES c(id)
 ,state boolean
);

With the layout as presented in the question, the query could be:

SELECT DISTINCT a.*
FROM   a
JOIN   b ON a.node_id = b.id
LEFT   JOIN a ca ON ca.child_node_id = a.node_id
LEFT   JOIN b cb ON cb.id = ca.node_id AND cb.state = FALSE
WHERE  b.state = FALSE
AND    cb.id IS NULL

This includes nodes that are turned off and have no children at all.
To exclude nodes without children, replace the first LEFT JOIN with a plain JOIN.

Or, may be faster:

SELECT a.*
FROM   a
JOIN   b ON a.node_id = b.id
WHERE  NOT EXISTS (
   SELECT 1 
   FROM   a ca
   JOIN   b cb ON cb.id = ca.node_id
   WHERE  ca.child_node_id = a.node_id
   AND    cb.state = FALSE
   )
Related Question