Take the 2-minute tour ×
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. It's 100% free, no registration required.

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.

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
add comment

1 Answer 1

up vote 3 down vote accepted

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

Your Answer

 
discard

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.