in reply to storing tree-like structures in tables
Good comments above. I agree that your data model is the common approach. I disagree that serializing a nested hash is a good general solution. Here are my personal experiences with a very large database holding file-system-like and user-group data.
Some databases (Oracle, others?) directly support tree structures. Oracle uses a "connect by" clause, so you can query an entire tree with one query:
I don't know if MySQL supports this -- but you might consider requesting/contributing it because it is a very useful feature.SELECT * FROM item CONNECT BY parent = PRIOR id START WITH id = 0
I frequently use additional columns to identify sub-trees. Think of a military or government organization with a deep hierarchy. Certain levels are explicit and others are ad hoc. You can model the entire structure with the "parent node" pointers. Then annotate this with "branch", "division", "company", etc. pointers. Every row in your table will have a column for each of those pointers.
Those explicit level pointers can be stored in another table. Then you can have one table for any number of explicit levels -- each row has "level name", "member row id". This is useful for handling webs (graphs instead of trees) of relationships. It can also be used to modify an existing database if you need to solve a tree expansion performance problem, but don't want to touch the core data model.
For speed, I sometimes cache a flattened version of a tree. This is especially useful for user group membership tests when the groups can be nested. When a person logs on, I do an expensive tree expansion of the group table (filtered for that person) and insert the results into a temporary session table. The session table can now be used to join against other tables for security checks.
|
---|