Skip to end of metadata
Go to start of metadata

<ac:macro ac:name="unmigrated-inline-wiki-markup"><ac:plain-text-body><![CDATA[

<ac:macro ac:name="unmigrated-inline-wiki-markup"><ac:plain-text-body><![CDATA[

Zend Framework: Zend_Db_Table_Mptt Component Proposal

Proposed Component Name Zend_Db_Table_Mptt
Developer Notes
Proposers Nick Pack, Hector Virgen
Zend Liaison TBD
Revision 1.3 - 20 August 2009: Refactored Skeleton, Extra UC's. (wiki revision: 19)

Table of Contents

1. Overview

Zend_Db_Table_Mptt is an extension to Zend_Db_Table to implement the Modified Preorder Tree Traversal algorithm

2. References

3. Component Requirements, Constraints, and Acceptance Criteria

  • This component will automatically update the left and right values of each node on update, insert and delete
  • This component will provide a method to retrieve ancestor nodes (e.g. for building breadcrumbs)
  • This component will provide a method to build a tree of all nodes in hierachy
  • This component will provide a method of retrieving child nodes of a parent node
  • This component will provide a method to convert existing data into MPTT

4. Dependencies on Other Framework Components

  • Zend_Db_Table
  • Zend_Db_Table_Exception

5. Theory of Operation

This component will retrieve hierarchical data with the minimum amount of overhead

6. Milestones / Tasks

  • Milestone 1: Complete Skeleton Class/Proposal
  • Milestone 2: Working prototype
  • Milestone 3: Working prototype checked into the incubator
  • Milestone 4: Unit tests exist, work, and are checked into SVN.
  • Milestone 5: Initial documentation exists.

7. Class Index

  • Zend_Db_Table_Mptt
  • Zend_Db_Table_Mptt_Exception

8. Use Cases


9. Class Skeletons




Enter labels to add to this page:
Please wait 
Looking for a label? Just start typing.
  1. Jul 27, 2009

    <p>Very nice work.</p>

  2. Jul 27, 2009

    <p>This is a great component that I can use on every project. </p>

  3. Sep 08, 2009

    <p>Two suggestions:</p>

    <p>Perhaps the possible keys for the $_traversal array should be defined as class constants:<br />
    so you could use:</p>

    <p>protected $_traversal = array( <br />
    self::TRAVERSAL_LEFT => 'lt', <br />
    self::TRAVERSAL_RIGHT => 'rt', <br />
    self::TRAVERSAL_COLUMN => 'row_id', <br />
    self::TRAVERSAL_REF_COLUMN => 'parent_id' <br />

    <p>Also, perhaps there could also be a Zend_Db_Table_Row_Mptt (or would it be Zend_Db_Table_Mptt_Row?) that can define fetchAllDescendents(Zend_Db_Select $select = null) so that you don't have to pass the row into the table object to do so. Same with the delete(), fetchTree(), and fetchAllAncestors() methods.</p>

    1. Sep 09, 2009

      <p>Thanks for the suggestions Konr, I will add the constants to the skeleton when I next make a revision.</p>

      <p> I'll look into the Zend_Db_Table_Row_Mptt idea, could you expand a little on the purpose of that?<br class="atl-forced-newline" /></p>

      <p>Thanks Again.<br class="atl-forced-newline" /></p>

      <p>Nick </p>

  4. Sep 21, 2009

    <ac:macro ac:name="code"><ac:plain-text-body><![CDATA[
    class Zend_Db_Table_Mptt_Row extends Zend_Db_Table_Row_Abstract

    • Fetches all descendents of a given node
    • @param Zend_Db_Select $select - optional custom select object
    • @return Zend_Db_Table_Rowset|null
      public function fetchAllDescendents (Zend_Db_Select $select = null)
      Unknown macro: { return $this->getTable()->fetchAllDescendents($this, $select); }


    • Fetches all descendents of a given node and returns them as a tree
    • @param Zend_Db_Select $select - optional select object
    • @return Zend_Db_Table_Rowset|null
      public function fetchTree (Zend_Db_Select $select = null)
      Unknown macro: { return $this->getTable()->fetchTree($this, $select); }


    • Fetches all ancestors of a given node
    • @param Zend_Db_Select $select - optional custom select object
    • @return Zend_Db_Table_Rowset|null
      public function fetchAllAncestors (Zend_Db_Select $select = null)
      Unknown macro: { return $this->getTable()->fetchAllAncestors($this, $select); }


    • Moves a node to another node when parent changes
      protected function _update()
      if ($this->_cleanData['id_parent'] != $this->id_parent) {

    $nodeSize = ($this->_cleanData['rt'] - $this->_cleanData['lt']) + 1;

    if ($this->id_parent)

    Unknown macro: { // node has been assigned to new parent $parentRow = $this->getTable()->fetchRow('id = ' . $this->id_parent); $maxRt = $parentRow->rt; }


    Unknown macro: { // node has had parent removed add to end of root node $maxRt = (double) $this->getTable()->fetchRow($this->getTable()->select(array('theMax' => "MAX(`rt`)")))->theMax + 1; }

    // lock tables
    $connection = $this->getTable()>getDefaultAdapter()>getConnection();
    $connection->exec("LOCK TABLE `".$this->getTable()->info('name')."` WRITE;");

    //temporary remove moving node and children
    $data = array(
    'lt' => new Zend_Db_Expr('0-`lt`'),
    'rt' => new Zend_Db_Expr('0-`rt`')
    $where = '`lt` >= "' . $this->_cleanData['lt'] . '" AND `rt` <= "'. $this->_cleanData['rt'] . '"';

    //step 2: decrease left and/or right position values of currently 'lower' items (and parents)
    $data = array(
    'lt' => new Zend_Db_Expr('`lt` - ' . $nodeSize)
    $where = '`lt` > ' . $this->_cleanData['rt'];

    $data = array(
    'rt' => new Zend_Db_Expr('`rt` - ' . $nodeSize)
    $where = '`rt` > ' . $this->_cleanData['rt'];

    //step 3: increase left and/or right position values of future 'lower' items (and parents)
    $data = array(
    'lt' => new Zend_Db_Expr('`lt` + ' . $nodeSize)
    $limit = ($maxRt > $this->_cleanData['rt']) ? $maxRt - $nodeSize : $maxRt ;
    $where = '`lt` >= ' . $limit;

    $data = array(
    'rt' => new Zend_Db_Expr('`rt` + ' . $nodeSize)
    $limit = ($maxRt > $this->_cleanData['rt']) ? $maxRt - $nodeSize : $maxRt;
    $where = '`rt` >= ' . $limit;
    $this->getTable()->update($data, $where);

    //step 4: move node (and it's subnodes)
    $limit1 = ($maxRt > $this->_cleanData['rt']) ? $maxRt - $this->_cleanData['rt'] 1 : $maxRt - $this>_cleanData['rt'] -1 + $nodeSize;
    $limit2 = ($maxRt > $this->_cleanData['rt']) ? $maxRt - $this->_cleanData['rt'] 1 : $maxRt - $this>_cleanData['rt'] -1 + $nodeSize;
    $data = array(
    'lt' => new Zend_Db_Expr('0-(`lt`)+' . $limit1),
    'rt' => new Zend_Db_Expr('0-(`rt`)+' . $limit2),
    $where = '`lt` <= "' . (0-$this->_cleanData['lt']) . '" and `rt` >= "'.(0-$this->_cleanData['rt'] . '"');

    // unlock tables
    $connection->exec("UNLOCK TABLES;");


    <p>I also have delete() proxy in row class to table method.</p>

    <p>I prefer NestedSet over MPTT.  </p>

  5. Nov 03, 2009

    <p>Is there anything that we (the community) can do to help push this proposal along? </p>

    1. Nov 04, 2009

      <p>My work commitments are presently taking up most of my time, I am keen to finalise the class skeleton and get this proposal submitted for peer review but I dont have much free time at the moment to do the actual development, hence it hasnt yet been submitted for review.</p>

      <p> I am trying desperately to find some time to do some work on this, but at present I can't tell you when that will be.</p>

  6. Jan 14, 2010

    <p>I have some free time to help get this going again. Some of the things I want to look at are:</p>

    <p><strong>Row deletion</strong><br />
    When a leaf is deleted, it's simple to adjust the left/right values so there are no gaps, but when a branch is deleted there must be some mechanism in place to handle the hole. In a previous e-mail conversation with Nick and others, it was suggested to mimic foreign key constraints, so we would have options like:<br />
    – Cascade: Deletes all child nodes when a parent node is deleted.<br />
    – Restrict: Enforces that no child nodes must exist before deleting the node.<br />
    – Reassign/Reattach: Deletes the node and reassigns all children to the original node's parent.<br />
    – Set null: Sets all children's parents to the null, effectively moving them to the root of the tree.<br />
    Each table instance could define its own delete rule, so that table A could use the "cascade" option while table B uses the "restrict" option.</p>

    <p><strong>Auto-rebuild MPTT Data</strong><br />
    Set an auto-rebuild option that randomly rebuilds the MPTT data after X number of instantiations. This may be useful for projects where another file is also updating this table but does not provide MPTT data (for example, batch imports).</p>

    <p>@michael, I like your implementation of the MPTT Row object. This would be a great addition to the proposal.</p>

    <p>Overall my only concern with this project is the SQL itself – is it valid SQL across all major DBs? I know this works in MySQL but we would need to test others and, if necessary, move the SQL to another class.</p>

    <p>Any thoughts on moving the SQL to the Zend_Db_Adapter_* classes? That would allow each DB to provide their own MPTT implementation.</p>

  7. Jan 15, 2010

    <p>I have made a few modifications to the underlying implementation of the class.</p>

    <li>Traversal information / verification is now lazy loaded. This means the traversal columns won't be verified until a traversal-specific method (like fetchAllDescendents()) is called.</li>

    <li>All exceptions thrown are now of type Zend_Db_Table_Mptt_Exception.</li>

    <li>Removed the pre*() / post*() hooks. These are not required for MPTT implementation.</li>

    <li>Created constants for the keys of the $this-><em>traversal array. All class constants are prefixed with MPTT</em> (not sure if this is necessary).</li>

  8. Mar 28, 2010

    <p>Hi, how does it look, any updates? It would be very nice if this component is implemented soon.</p>

  9. Feb 05, 2011

    <p>Archiving this proposal, feel free to recover it when you want to work on it again. For more details see <a href="">this email</a>.</p>