tag:blogger.com,1999:blog-15319370.post112501520528295259..comments2024-03-05T11:16:00.846+01:00Comments on Roland Bouman's blog: Yet another way to model hierarchiesrpboumanhttp://www.blogger.com/profile/13365137747952711328noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-15319370.post-67284830713481874492008-09-15T12:48:00.000+02:002008-09-15T12:48:00.000+02:00Hi, Roland.I've been reading about methods to repr...Hi, Roland.<BR/>I've been reading about methods to represent hierarchies in SQL and suddenly I came up with an idea.<BR/>My idea is a hybrid between "Adjacency list" and "Relative path" methods. To represent the tree I use 2 tables - first table (let`s call it ENTITY) contains column PARENT_ID and as many other columns as you wish. PARENT_ID is a foreign key into ENTITY itself (this is a classic adjacency list model, or also called "parent-child" relationship - I prefer that name).<BR/>The second table (let`s call it HELPER) contains 3 columns: CHILD_ID, ANCESTOR_ID, DISTANCE<BR/>CHILD_ID is a foreign key into ENTITY; ANCESTOR_ID is also a foreign key into ENTITY, such that CHILD_ID is DISTANCE levels underneath the ANCESTOR_ID; DISTANCE can be between 1 and the number of levels in tree. CHILD_ID and ANCESTOR_ID form a unique key inside table HELPER.<BR/>I have no source code for tree manipulation yet (I'm writing this post right now as I though of the idea) but it will be ready in a few days.<BR/>I'm willing to hear from you about my idea, to further continue conversation and study it. I will be very happy if this becomes usefull for other people.<BR/>My email is:<BR/>ivo underscore gelov at gmx dot net,<BR/>or my ICQ is 72406680<BR/><BR/>Best wishes,<BR/>IVO GELOVAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-15319370.post-1152685825212751442006-07-12T08:30:00.000+02:002006-07-12T08:30:00.000+02:00Hi Jayman,Ok, now I get it...nested interval is a ...Hi Jayman,<BR/><BR/>Ok, now I get it...nested interval is a distinct model, and it is dicussed in the links you provided, right? Thanks for that, I will go and get educated on that.<BR/><BR/>Listen, I'd like to blog up my code and the idea's behind the nested set/adjacency list, but I'm really swamped. However if you need a solution right now, I am more than willing to let you have it. Just send me an mail. Youll find the address with my blogger profile data.<BR/><BR/>thanks for posting comments and the nested interval links,<BR/><BR/>Rolandrpboumanhttps://www.blogger.com/profile/13365137747952711328noreply@blogger.comtag:blogger.com,1999:blog-15319370.post-1152656763570933902006-07-12T00:26:00.000+02:002006-07-12T00:26:00.000+02:00Hi Jayman,thanks for posting.First of all, let me ...Hi Jayman,<BR/><BR/>thanks for posting.<BR/><BR/>First of all, let me stress that the 'ordered level' technique is, like the nested set model, based on a depth-first traversal of the tree. <BR/><BR/>Second, the scope column in the example is actually something that has nothing to do with this particular model. Think of it: you can always add an extra column to any table to compartimentalize the data inside it. <BR/><BR/>I do not really agree with:<BR/><BR/>"..like most other techniques (except maybe nested interval)..to insert a new node in the middle of a given tree...many nodes in the tree may have to be recomputed, correct?"<BR/><BR/>(I'm assuming you mean "nested set" instead of "nested interval")<BR/><BR/>There are basically three (or four) ways to store trees in a database:<BR/><BR/>1) adjacency list <BR/>2a) 'ordered level'<BR/>2b) nested set <BR/>3) 'materialized path'<BR/><BR/>I've arranged this list according to the amount of overhaul (in descending order) involved when restructuring the tree. <BR/><BR/>I think I can make a good case to prove that the less effort is involved to change the structure of the tree, the more effort it is to query the tree.<BR/><BR/>At least it holds for this list, and the reason for that must be sought in the amount of redundancy contained within the model. Now don't start thinking about redundancy the way one normally does concerning data modelling issues. I mean redundancy as a informal term here. <BR/><BR/>Look, the adjacency list is the least redundant in the sense that no more than the bare minimum of information that is needed to relate one particular node to another node is used. Each node "knows" only something about it's parent node - all other information must be derived from this data. A parent node has no way of knowing what it's children are - it must do a query first.<BR/><BR/>For this reason, the adjaceny list is very good in restructuring the tree. Giving a particular node another parent node instantaneously relocates the descandant nodes because each individual node contains no information whatsoever concerning the lineage (that is, the rest of the structure), but for the single pointer to the parent.<BR/><BR/>For the 'ordered level' model, the nodes are chained together by position, that is, the depth first order. Each node "knows" about the previous and next node directly via that position. This means that at the very least, restructuring of the tree implies updating the chain downstream of the insert or delete.<BR/><BR/>The nested set is similar: each node know about both the ancestors as well as the dscendants.<BR/><BR/>In the materialized path model, each node know everything about all other nodes ancestors. Censequently, this is the easiest to query: to get to all the descendants, simply look for all the nodes that share the same prefix, and all ancestors are implied.<BR/><BR/>In the mean time, I actully worked out the hybrid solution. My comment about how difficult it would be to implement turn out to be bogus. <BR/><BR/>I did not think of it then, but the solution is indeed to have two separate tables. <BR/>I'm now using a 'public' table - people can insert,update and delete against it. This table needs to have triggers for all these actions. The triggers manipulate a second 'private' table and that stores the nested set representation. So, there's a one to one relationship between records in the adjacency list and nested set models.<BR/><BR/>In MySQL, it is maybe not impossible to maintain it in one table. However, I can live with two tables. As it turns out, it is actually convenient as I dont want people to be able to update the nested set model directly anyway. Having a separate table makes it easy to handle privileges.<BR/>Also, queries become easier to read because usually, the query you're writing almost never serves a hybrid purpose. <BR/><BR/>I found the hybrid solution to be very useful, and I can recommed it to anyone. I would probably use it in other database too, regardless of what cool construct they might have to handle hierarchies.<BR/><BR/>hope this helps,<BR/><BR/>Rolandrpboumanhttps://www.blogger.com/profile/13365137747952711328noreply@blogger.com