# How to select nodes where all children is satisfied?

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.

-
Select nodes with all immediate children turned on or all children recursively? – Erwin Brandstetter May 28 '13 at 10:28
Ahh... yes thats a detail which is missing - thanks! – Chau May 28 '13 at 10:30
Including or excluding nodes without children? – Erwin Brandstetter May 28 '13 at 10:33

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
)
``````
-
My example is simplified and I need the structure for other reasons. – Chau May 28 '13 at 10:25