Simon: I actually reviewed that article (and quite a few others) in detail before I decided on how I wanted implement everything. The only three cases I wanted to use the adjacency list model was for one level traversals where I'll already have IDs to make it blazing fast to be handled by a single query: Parent - SELECT (...) FROM nodes WHERE id = <curNode.mptt_parent> LIMIT 1; Siblings - SELECT (...) FROM nodes WHERE mptt_parent = <curNode.mptt_parent> AND id != <curNode.id>; Children - SELECT (...) FROM nodes WHERE mptt_parent = <curNode.id>;
I can't imagine that the speed of the suggested queries (with self- joining and nesting), even optimized, would even come close to the speed of the queries I'm proposing. Note that my original goal was two-fold (speed and simplicity) but as an added bonus it provides a myriad of other benefits. I feel that the results would be more robust in terms of protection against corruption as opposed to less so (the most dangerous operation, move_node, involves only a single row change in the adjacency model). It makes it easy for the code to be maintained by others because with one glance they can see exactly what is occurring. It makes it easy to ensure that different database platforms with slightly different takes on ANSI don't need different queries (I admit, I don't know if that would be a problem, but I could see it being one--we are using PDO to enable multiple DB backends). Yes, there is a SQL-based MPTT approach to those three queries but I find that it fails to provide any of the benefits that the adjacency model does in these three scenarios (speed, simplicity, maintainability, robustness, portability). In summary, I see a hybrid approach as the optimal solution as it gives us the benefits of each whenever the output scenario makes better use of that approach. Nathan On Oct 16, 8:28 am, drzax <[EMAIL PROTECTED]> wrote: > 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 > fromhttp://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 > fromhttp://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 -~----------~----~----~----~------~----~------~--~---
