Skip to end of metadata
Go to start of metadata

Zend Framework: Zend_Db_NestedSet Component Proposal

Proposed Component Name Zend_Db_NestedSet
Developer Notes http://framework.zend.com/wiki/display/ZFDEV/Zend_Db_NestedSet
Proposers Graham Anderson
Zend Liaison TBD
Revision 1.0 - 16 January 2010: Initial Draft. (wiki revision: 5)

Table of Contents

1. Overview

Zend_Db_NestedSet is an implementation of the modified pre-order traversal pattern for storing
hierarchical data structures in a relational database. This data storage pattern allows for fast
retrieval of tree-like structures that are used in common web page elements.

2. References

3. Component Requirements, Constraints, and Acceptance Criteria

  • This component will support single tree or multi tree database tables.
  • This component will allow data queried from the database table to be rebuilt into a tree-like structure suitable for use with Zend_Navigation
  • This component will allow data to be presented either as a multi-dimensional associate array or as a recursive iterator object.
  • This component will allow tree nodes or branches to be moved or deleted within the database
  • This component will provide functionality to retrieve a whole tree or a branch(sub tree).
  • This component will provide functionality to get the path, depth, siblings or immediate descendants of a specific tree node.
  • This component will not provide retrieval or modification of data using materialised path or adjency list techniques
  • This component will provide common interfaces that other hierarchical retrieval techniques might use.

4. Dependencies on Other Framework Components

  • Zend_Db_Table

5. Theory of Operation

The component provides for fast and efficient retrieval of hierarchical data using a minimum amount of database queries.

6. Milestones / Tasks

  • Milestone 1: [DONE] Initial class skeletons & proposal
  • Milestone 2: [DONE] Working prototype gitHub repo
  • Milestone 3: Working prototype checked into the incubator supporting use cases #3 and #4.
  • Milestone 4: Unit tests exist, work, and are checked into SVN.
  • Milestone 5: Initial documentation exists.

7. Class Index

  • Zend_Db_TreeInterface (interface)
  • Zend_Db_TreeNodeinterface (interface)
  • Zend_Db_TreeBranchInterface (interface)
  • Zend_Db_NestedSet
  • Zend_Db_NestedSet_Node
  • Zend_Db_NestedSet_Branch
  • Zend_Db_NestedSet_Exception

8. Use Cases

UC-01
Get the full tree
UC-02
Get the full tree as a multidimensional associative array
UC-03
Get the full tree as a recursive iterator
UC-04
Get a branch starting at a specific node
UC-05
Move a single node or a branch

9. Class Skeletons

Zend_Db_TreeInterface
Zend_Db_TreeBranchInterface
Zend_Db_TreeNodeInterface
Zend_Db_NestedSet
Zend_Db_NestedSet_Branch
Zend_Db_NestedSet_Node

Labels:
None
Enter labels to add to this page:
Please wait 
Looking for a label? Just start typing.

3 Comments

comments.show.hide

  1. Jan 18, 2010

    Hector Virgen

    Hi Graham, it looks like we're working on similar proposals. I'm working with Nick Pack to add MPTT support to Zend_Db_Table. Maybe we can collaborate on this. Take a look at our proposal here:

    http://framework.zend.com/wiki/pages/viewpage.action?pageId=15565007

  2. Jan 23, 2010

    Alexander Steshenko

    Hello.

    Does it allow to store tree and the data in different tables? If no - it's not worth using. But the code has impressed me, I believe it may be improved in some ways (I haven't really examine yet, just some pieces, so sorry if I'm wrong somewhere).

    I've been preparing similar proposal but got stuck with the implementation and the architecture (generally because of the lack of time not because of problems that can't be solved or smth like that) it's been paused now, but I can try to help you with some uncertainties you have. If you have some of course and you are interested at all - tell me if you are not.

    I have some suggestions by now:

    1) You can check out my old code http://code.google.com/p/zfru-proposal-zend-db-tree/source/browse/ which was initial prepared for the proposal (it is only for nestedsed as yours). It's working live in some projects, you might find something useful there.

    2) DB queries should be separated in another file (probably). Yes, Zend_Db gives some universality already and you can probably switch the database easy, but it's not completly universal. Besides, it's quite logical to keep all the 'algorithm' stuff in one place and all the db related stuff in another. Check the link I gave above. You may not agree here, ignore it if so...

    3) I suggest to extend it to the Zend_Db_Tree proposal with adapter based supporting of different kinds of algorithms (Nested Sets, adjacency lists, materialized paths). We should also support using them on their own.
    Here is my class index:

    Zend_Db_Tree

    Zend_Db_Tree_NodeAbstract
    Zend_Db_Tree_NodeInterface

    Zend_Db_Tree_Adapter_AdapterInterface
    Zend_Db_Tree_Adapter_AdapterAbstract

    Zend_Db_Tree_Adapter_Exception

    Zend_Db_Tree_Adapter_DbAdapterAbstract
    Zend_Db_Tree_Adapter_DbAdapterInterface

    Zend_Db_Tree_Adapter_Nestedset
    Zend_Db_Tree_Adapter_Nestedset_Node
    Zend_Db_Tree_Adapter_Nestedset_DbAdapter_Pdo_Abstract
    Zend_Db_Tree_Adapter_Nestedset_DbAdapter_Pdo_Mysql
    ...
    Zend_Db_Tree_Adapter_Materializedpath
    Zend_Db_Tree_Adapter_Materializedpath_Node
    ...
    Zend_Db_Tree_Adapter_Adjacencylist
    Zend_Db_Tree_Adapter_Adjacencylist_Node
    ...

    not sure it's going to be useful, but just in case.

  3. Apr 16, 2010

    Graham Anderson

    Thanks for your comments but I will not be pursuing this proposal for inclusion to Zend Framework. Feel free to use/abuse anything posted on this page but the code in the github repo will be soon moving to a BSD incompatible License.