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've got a MySQL table with columns id and parent, wherein each row has another row as a parent, except for some special root rows with parent=0. There are no cycles or broken relations.

In order to cache which root row each row is associated with, I decided to add an ancestor column. My current plan is to build the tree in some other programming language, find all ancestors recursively and then update the table.

However, I'm convinced that there's a clever way to do this in SQL, requiring not more queries than the depth of the three. Could someone help me design this?

There are ~1000 rows and the depth is ~5, so performance is not really an issue.

share|improve this question
5  
Your tag says sql-server, your text says MySQL. Which one is it? –  Remus Rusanu Mar 16 '12 at 16:38
    
@Remus: Sorry, I wrote "sql" and it seems to have been auto-completed. I'm on MySQL. –  Tim Mar 17 '12 at 8:01
add comment

1 Answer 1

up vote 1 down vote accepted

@Tim you have come to the right place.

It just so happens that I answered a question like this ( Find highest level of a hierarchical field: with vs without CTEs ) back in Oct 24, 2011.

I wrote Stored Procedures that traverse a table with id and parent fields. I also included sample data.

However, you may not have to resort to the Stored Procedures.

Here is what I mean: Let's start with the sample data

USE junk 
DROP TABLE IF EXISTS pctable; 
CREATE TABLE pctable 
( 
    id INT NOT NULL AUTO_INCREMENT, 
    parent_id INT, 
    PRIMARY KEY (id) 
) ENGINE=MyISAM; 
INSERT INTO pctable (parent_id) VALUES (0); 
INSERT INTO pctable (parent_id) SELECT parent_id+1 FROM pctable; 
INSERT INTO pctable (parent_id) SELECT parent_id+2 FROM pctable; 
INSERT INTO pctable (parent_id) SELECT parent_id+3 FROM pctable; 
INSERT INTO pctable (parent_id) SELECT parent_id+4 FROM pctable; 
INSERT INTO pctable (parent_id) SELECT parent_id+5 FROM pctable; 
SELECT * FROM pctable; 

To reach any grandparent, you could just perform a JOIN of the pctable against itself:

SELECT P.id,GP.parent_id FROM pctable P
INNER JOIN pctable GP ON P.parent_id = GP.id;

To reach any great-grandparent, you could just perform a JOIN of the pctable against itself twice:

SELECT P.id,GGP.parent_id FROM pctable P
INNER JOIN pctable GP ON P.parent_id = GP.id;
INNER JOIN pctable GGP ON GP.parent_id = GGP.id;

Since your depth is no more than three, doing these JOINs should be quite enough.

share|improve this answer
    
Thank you, a neat and simple solution! I kept thinking I'd have to solve the general case, but that'd be completely unnecessary. –  Tim Mar 17 '12 at 8:02
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.