Adjacency List Model with two tables

Question

So I think my issue boils down to two questions:

1. How do I build a traversable tree structure in PHP when the tree is stored in MySQL (between two tables) using the Adjacency List Model approach while keeping performance in mind?

2. What's a maintainable approach to displaying the tree in the needed formats without duplicating traversal code and littering the logic with if/else and switch statements?

Below are more details:

I'm using the Zend Framework.

I'm working with a questionnaire. It's stored in a MySQL database between two separate tables: questions and question_groups. Each table extends the appropriate Zend_Db_Table_* classes. The hierarchy is represented using the Adjacency List Model approach.

I realize the problems I'm running into are likely due to the fact that I'm stuffing a tree structure into an RDBMS so I'm open to alternatives. However, I'm also storing questionnaire respondents and their responses so alternative approaches would need to support that.

The questionnaire needs to be displayed in various HTML formats:

1. As a form for entering responses (using Zend_Form)
2. As an ordered list (nested) with questions (and some groups) as links to view responses by question or by group.
3. As an ordered list (nested) with responses appended to each question.

Questions are leaf nodes and question_groups can contain other question_groups and/or questions. Combined, there are a little over 100 rows to process and display.

Currently, I have a view helper that does all the processing using recursion to retrieve a question_group's children (a query which performs a UNION between the two tables: QuestionGroup::getChildren($id)). Plus when displaying questionnaire with the question response an additional two queries are needed to retrieve the respondent and their response to each question.

While the page load time isn't very long this approach feels wrong. Recursion plus multiple database queries for almost every node does not make me feel very warm and fuzzy inside.

I've tried recursion-less and recursive methods on the full tree array returned from the UNION to build a hierarchical array to traverse and display. However, that seems to break down since there are duplicated node ids due to the fact that groups and questions are stored in separate tables. Maybe I'm missing something there...

Currently, the logic to display the tree in the formats listed above is quite a mess. I'd prefer not to duplicate the traversal logic all over the place. However, conditionals all over the place don't produce the most easily maintainable code either. I've read up on Visitors, Decorators and some of the PHP SPL iterators but I'm still feeling unclear as to how that would all work together with the classes that are extending Zend_Db_Table, Zend_Db_Table_Rowset and Zend_Db_Table_Row. Especially since I haven't solved the previous problem of building the hierarchy from the database. It would be nice to add new display formats (or modify existing ones) somewhat easily.

Answer 1

• The Adjacency List traditionally gives you a parent_id column in each row that links a row to its immediate parent. The parent_id is NULL if the row is the root of a tree. But this leads you to run many SQL queries, which is expensive.

• Add another column root_id so each row knows what tree it belongs to. That way you can fetch all nodes of a given tree with a single SQL query. Add a method to your Table class to fetch a Rowset by the tree's root id.

  class QuestionGroups extends Zend_Db_Table_Abstract
  {
      protected $_rowClass = 'QuestionGroup';
      protected $_rowsetClass = 'QuestionGroupSet';
      protected function fetchTreeByRootId($root_id)
      {
           $rowset = $this->fetchAll($this
              ->select()
              ->where('root_id = ?', $root_id)
              ->order('id');
          );
          $rowset->initTree();
          return $rowset;
      }
  }
  

• Write a custom class extending Zend_Db_Table_Row and write functions to retrieve the given row's parent and also a Rowset of its children. The Row class should contain protected data objects to reference the parent and the array of children. A Row object can also have a getLevel() function and a getAncestorsRowset() function for breadcrumbs.

  class QuestionGroup extends Zend_Db_Table_Row_Abstract
  {
      protected $_children = array();
      protected $_parent   = null;
      protected $_level    = null;
      public function setParent(Zend_Db_Table_Row_Abstract $parent)
      {
          $this->_parent = $parent;
      }
      public function getParent()
      {
          return $this->_parent;
      }
      public function addChild(Zend_Db_Table_Row_Abstract $child)
      {
          $this->_children[] = $child;
      }
      public function getChildren()
      {
          return $this->_children;
      }
      public function getLevel() {}
      public function getAncestors() {}
  }
  

• Write a custom class extending Zend_Db_Table_Rowset that has a function to iterate over the rows in the rowset, setting parent and children references so that you can subsequently traverse them as a tree. Also the Rowset should have a getRootRow() function.

  class QuestionGroupSet extends Zend_Db_Table_Rowset_Abstract
  {
      protected $_root = null;
      protected function getRootRow()
      {
          return $this->_root;
      }
      public function initTree()
      {
          $rows = array();
          $children = array();
          foreach ($this as $row) {
            $rows[$row->id] = $row;
            if ($row->parent_id) {
              $row->setParent($rows[$row->parent_id]);
              $rows[$row->parent_id]->addChild($row);
            } else {
              $this->_root = $row;
            }
          }
      }
  }
  

Now you can call getRootRow() on a rowset, and it returns the root node. Once you have the root node, you can call getChildren() and loop over them. Then you can call getChildren() also on any of these intermediate children, and recursively output a tree in any format you want.