Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

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.

share|improve this question
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
up vote 3 down vote accepted

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

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

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

FROM   a
JOIN   b ON a.node_id =
LEFT   JOIN a ca ON ca.child_node_id = a.node_id
LEFT   JOIN b cb ON = ca.node_id AND cb.state = FALSE
WHERE  b.state = FALSE

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:

FROM   a
JOIN   b ON a.node_id =
   SELECT 1 
   FROM   a ca
   JOIN   b cb ON = ca.node_id
   WHERE  ca.child_node_id = a.node_id
   AND    cb.state = FALSE
share|improve this answer
My example is simplified and I need the structure for other reasons. – Chau May 28 '13 at 10:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.