Database Parent-Child Relationships
2006-05-20
Two approaches for implementing database record parent-child relationships. The second method is something I came up with that makes selecting nested records a snap.
1. Parent ID Specifier
This is the standard, straight-forward, most popular method. A database record has both id and parentId fields. If the parentID is 0, then the record is a top-level parent. Otherwise, the record is a child of the record with the id specified by the parentId field.
Pro
Inserting new records is easy. Merely specify a parentId if the new record is a child.
Con
Need to recursively perform queries to fetch nested/child records.
2. Tier Field
This is something I came up with around 2002/2003, though I'm sure I'm not the first to think of it. Each database record contains a "tier" field, which is a string of digits.
The first record is at the top level with a tier of "0100". A child of "0100" would be "0101". A sibling of our first record would be "0200". Another sibling would be "0300" and a child of this sibling would be "0301". Another child of "0300" would be "0302". Got it?
The above examples use two digits for each tier level. Thus, there could be 99 top-level records, each having up to 99 children. Of course, you could implement base 16 and bump this up to 255 while still using two characters per tier level. Also, my examples use fixed-length zero-padded (on the right) tier specifiers that allow for only two levels. It may be more practical to allow the length to vary which would make zero padding the right side irrelevant. In that case the number of levels would only be limited by the type of database column you choose.
A friend of mine implemented a clever method for selecting all parents of a particular record purely in SQL, but it only works if tiers are not padded on the right by zeroes. It took me a while to understand what's going on. If you're interested, drop me a note and I'll explain, or I'll have him do it.
select b.* from categories a left join categories b on length(b.tier) <= length(a.tier) and b.tier = left(a.tier,length(b.tier)) where a.id = $categoryId order by b.tier
Pro
Easier DB queries to fetch nested records. Merely sort by the tier field. The records will be returned in the following order:
01
0101
010101
02
03
0301
When selecting children of a particular record use "tier like '0102%' and tier != '0102'" or similar. This would select all siblings of the "0102" record, excluding the record itself.
Con
Insertion logic is somewhat complex, depending on which numbering scheme you use: base 10, base 16, etc.
Possibly a limited number of nesting levels, dependent upon which field type is used for the tier field and if tiers are fixed-length and right padded with zeroes. Number of nesting levels might need to be decided at DB creation time.
