Nested data in a database table

Question

I have a table which contains records which are related in the following way:

parent, child, grandchild.

I would like to be able to run queries to do the following:

1. retrieve all records that are descended from a particular record
2. retrieve all records that are direct children of a particular record (i.e. only direct children)
3. retrieve all records that are grandchildren of a particular record (i.e. only grand children)
4. retrieve the grandparent of a record
5. retrieve the parent of a record
6. retrieve all records (and their children and grand children)

I want this query return the data in a sorted way, so I can create a structured document (e.g. XML from the query result). By "sorted", I mean that the result set is "GROUPED" by parent THEN child, THEN grandchild

I have designed a simple table like this (PSEUDO CODE):

CREATE TABLE family_tree {id integer
                    , parent_id integer
                    , child_id integer
                    , fname varchar(16)
                    , lname varchar(32) };

I have a number of questions:

1. (Bearing in mind the queries I want to run [(1)-(6) above]) is this is the best (i.e. most efficient table structure I can use?. If no, what is ?

2. Can anyone help me on writing ANSI SQL statements to perform queries (1)-(6) above?

Answer 1

Check the sitepoint tutorial on this.

• The recursive method of storing data (id, parent_id) allows you to retrieve direct descendants of particular node.
• The preordered tree traversal method allows you to retrieve whole branch of particular node.

So having id,parent_id,left,right columns is your best bet. That tutorial holds whole code, but SQL queries should be clear enough.

You should be able to derive all queries from those provided in tutorial.

Answer 2

I see you have already accepted Eimantas' answer, saying that

"So having id,parent_id,left,right columns is your best bet."

I want to explicitly point out the following quote from the cited link (italics mine) :

"Adding a Node

How do we add a node to the tree? There are two approaches: you can keep the parent column in your table *and just rerun the rebuild_tree() function* -- a simple but not that elegant function; or you can update the left and right values of all nodes at the right side of the new node."