While I can see that the Adjacency List Model and the MPTT Model aren't totally mutually exclusive, it does seem to be defeating the purpose of MPTT to be adding what is the essence of Adjacency List to the mix. As well as that, I believe you're over stating the problems with you Scenario 1. There are a few ways to get the siblings of a node back without also returning the entire sub trees below them.
The most immediate solution, taken straight from http://dev.mysql.com/tech-resources/articles/hierarchical-data.html, is to do a first query to find the parent and then run a second to get it's immediate subordinates: SELECT node.name, (COUNT(parent.name) - (sub_tree.depth + 1)) AS depth FROM nested_category AS node, nested_category AS parent, nested_category AS sub_parent, ( SELECT node.name, (COUNT(parent.name) - 1) AS depth FROM nested_category AS node, nested_category AS parent WHERE node.lft BETWEEN parent.lft AND parent.rgt AND node.name = 'PORTABLE ELECTRONICS' GROUP BY node.name ORDER BY node.lft )AS sub_tree WHERE node.lft BETWEEN parent.lft AND parent.rgt AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt AND sub_parent.name = sub_tree.name GROUP BY node.name HAVING depth = 1 ORDER BY node.lft; Of course you could easily turn this into a single query by adding a second sub query: SELECT node.name, (COUNT(parent.name) - (sub_tree.depth + 1)) AS depth FROM nested_category AS node, nested_category AS parent, nested_category AS sub_parent, ( SELECT node.name, (COUNT(parent.name) - 1) AS depth FROM nested_category AS node, nested_category AS parent WHERE node.lft BETWEEN parent.lft AND parent.rgt AND node.name = ( SELECT parent.name FROM nested_category AS node, nested_category AS parent WHERE node.lft BETWEEN parent.lft AND parent.rgt AND node.name = "WHATEVER" AND parent.name <> "WHATEVER" ORDER BY parent.lft DESC LIMIT 1 ) GROUP BY node.name ORDER BY node.lft )AS sub_tree WHERE node.lft BETWEEN parent.lft AND parent.rgt AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt AND sub_parent.name = sub_tree.name GROUP BY node.name HAVING depth = 1 ORDER BY node.lft; This has been a really quick example taking (really sub-optimal) SQL from http://dev.mysql.com/tech-resources/articles/hierarchical-data.html. I'm sure this could be optimised very well. I applaud your efforts to get the ball rolling with Taxonomy, and the basic outline of your class looks good, but I couldn't support the addition of a mptt_parent field to the schema. We chose MPTT over Adjacency List for a reason. Cheers, Simon On Oct 16, 2:36 am, Nathan Hammond <[EMAIL PROTECTED]> wrote: > Owen, > I'll make sure it matches the coding conventions by the time I submit > it for consideration for Habari, no worries. However, I did get a good > start on it using my standard conventions so I'll do that once I've > got it working. Besides, I want this as a standalone class as much for > me as I want it in Habari. *grin* > > The reason I'm including mptt_parent is because of situations where > scalability might be a concern. My concern isn't with getting the > results from the database, I feel that operation will be fast in any > scenario. The problem I see is handling it once it gets back to PHP > which is why I *much* prefer the second scenario: > > Scenario 1 > There is a tree of 500 items that is 10 levels deep. If I wanted to > get all of the siblings of something on the second level I would first > get the parent node (1 query, resultset contains the path to root from > target node) and then get all of the descendants of that node (1 > query, in this scenario resultset contains 499 records--all but the > root node). The keep-it-simple approach to handling tree rebuilding > would require iterating over every single one of those records. With > some fiddling you could come up with a way to skip most of the > processing, but that extra code sounds to me like more places for > errors to be introduced into the codebase. > > Scenario 2 > Using mptt_parent I grab all rows that have a matching mptt_parent > value. One query, and results already returned in a SQL-specified > order across the tree with no additional post-processing. > > As to situations where mptt_parent could fall out of sync, I find that > less likely to occur than mptt_left and mptt_right falling out of > sync. The only time after insertion where mptt_parent would be > modified would be in the function MPTT::move_node(). Considering how > dangerous that function would be to *any* action performed on the MPTT > table, the affected rows should be read and write locked anyway and > the entire process handled in a transaction. However, since updating > mptt_parent only affects a single row it will not create any race > conditions in and of itself and even creates a safe read method > (recursive) to build the tree in the event that move_node() is > running. > > In summary, I find mptt_parent to be the least probable point of > failure (one-row change on move_node) and possibly a life-saver in the > event that the mptt_left and mptt_right *do* get screwed up--it would > allow us to rebuild the tree recursively and then reassign mptt_left > and mptt_right. > > Anything I'm missing? Or does that sound reasonable? > > On Oct 15, 7:35 pm, Owen Winkler <[EMAIL PROTECTED]> wrote: > > > Nathan Hammond wrote: > > > Well, I'm over a week late, but I'm claiming my first piece of the > > > taxonomy segment if nobody tells me not to. First on my list is to > > > provide is an MPTT class with a series of methods that allow for > > > simple hierarchical storing of data in a database. The functionality > > > is easily split into four categories along the lines of CRUD: > > > Sounds good, although note that coding convention in Habari is not > > javaStyleFunctionNames() but uses_underscores_in_lowercase(). > > > > I will be making one schema change to make things as fast as possible: > > > the addition of mptt_parent into the "terms" table. I don't see this > > > as a problem since this table is presently unused. That will allow for > > > single-query sibling selection without parsing the descendants out of > > > the selection. > > > Isn't it possible to glean parent data from an MPTT structure without > > adding this field? I realize that the query result would be faster but: > > > 1) Even a complex query result would be cached so that it's only slow > > after inserts. > > > 2) Introducing additional data that overlaps with the MPTT structure > > could result in contention points. That is, if somehow a node says it's > > parent id is X and the MPTT structure clearly disagrees with that, what > > happens? It seems like it would be more difficult/effort to keep these > > in sync than just using the MPTT fields. > > > 3) Adding schema is not something to take lightly, even if it's > > currently unused. > > > I'm interested in the philosophy here, not trying to dissuade you from > > your efforts. > > > > After this class is complete in a standalone form I'll figure out how > > > to reconcile it with Habari--I'm currently unfamiliar with how all the > > > underlying sections work and where all changes will need to appear. > > > The one place to consider specifically is that the tag system will need > > to move to be implemented in these underlying data structures, but still > > be accessible via the existing classes; facade classes. > > > Owen --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/habari-dev -~----------~----~----~----~------~----~------~--~---
