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.

Based on Traversing tree-like data in a relational database using SQL question, I would like to know how the way regularly used to describe tree-like data on relational databases considering physical implications?

I'm assuming that the RDBMS has not special features to handling that other than regular SQL ANSI or common available features.

In doubt I'm always interested on MySQL and PostgreSQL and eventually SQLite.

share|improve this question

2 Answers 2

up vote 5 down vote accepted

I believe he is going for something like a binary tree. I would just include three keys that are tied to the unique id of the same table, one for the left, one for the right child, and one for the parent.

i.e.- (very much pseudocode)

TABLE tree
int         id                  autoinc
varchar(16) data_you_care_about
int         parent_id
int         left_child_id
int         right_child_id

FOREIGN KEY parent_id = tree.id
FOREIGN KEY left_child_id = tree.id
FOREIGN KEY right_child_id = tree.id
share|improve this answer
    
A consideration for a doubly linked item is that any changes in tree position under this schema would result in no less than 3 updates instead of one. As you state, this is also a big assumption that a forward/reverse binary tree is what was requested. –  REW Jan 4 '11 at 0:10
    
very true, in my experiences I prefer the update-tax of a doubly-linked list to a single-linked list as I often have to traverse up a tree. but in many instances this would not be necessary –  Patrick Jan 4 '11 at 0:43
    
It definitely depends on the underlying model. I think that the answer given by Patrick is sufficient if that's the right model. –  jcolebrand Jan 5 '11 at 5:28

If each node is truly the same data entity, then the paradigm would still signify one table per entity, and a linking column for the tree traversal where each node is only linked once.

For entities that are linked at multiple points in the tree, a separate linking table or a multiple distinct value column would be used.

share|improve this answer

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.