13

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.

Improve this question

2 Answers 2

Reset to default
8

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
Improve this answer
3
  • 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
    Commented Jan 4, 2011 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
    Commented Jan 4, 2011 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 ♦
    Commented Jan 5, 2011 at 5:28
6

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.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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