nested-interval Hierarchical Data Management in Relational Databases using Nested Interval Node Key Encoding

  1. Requirements
  2. Usage

Nested Intervals provide a means of managing hierarchical data in a relational database by keying nodes in the tree using rational numbers.

The Nested Interval Behavior is an implementation of the encoding scheme presented in "Using Rational Numbers to Key Nested Sets"; Dan Hazel 19 June 2008. (http://arxiv.org/PS_cache/arxiv/pdf/0806/0806.3115v1.pdf)

The key of a node is calculated from the key of the parent node in such a way that places every descendant of a node before the next sibling of the node.

A key feature of the encoding is a significantly reduced requirement for re-indexing of nodes; addition or deletion of a last child node requires no re-indexing, and deletion of any other node only requires re-indexing of sibling sub-trees.

Nested Interval encoding also provides inherent support for multiple trees.

Requirements

Built and tested with Yii 1.1.8; should work with Yii 1.1.x

Usage

Attach the behavior to a model in the normal way. Your DB table will need four integer columns to support the behavior - the names default to "nv", "dv", "snv", and "sdv", but can be configured.

There are many methods to add data (these are used in place of CActiveRecord::save()), named scopes and getters to access data, methods to get information about a node, move nodes within the hierarchy, and delete nodes.

A few examples; please see the documentation for details of the API; you can also take a look at the Unit Tests (in the download) for examples.

$node->children()->findAll(); // return all the children of $node
$node->firstChild()->find(); // return the first child of $node

These could also be written as:

$node->children; // return all the children of $node
$node->firstChild; // return the first child of $node

Add a new node (there are many methods that allow the node to be added exactly where needed)

$node = new MyModel();
// set attributes here
$node->appendTo($target); // append $node to (add as last child of) $target

Find out some information about a node (there are many methods that give information about nodes)

$node->isChildOf($target); // find out if one node is the child of another

Move a node (there are many methods to move a node to exactly the right place)

$node->moveAfter($target); // move $node (and its descendants) to be the next sibling of $target
13 0
18 followers
697 downloads
Yii Version: 1.1
License: BSD-2-Clause
Category: Database
Developed by: Yeti
Created on: Dec 3, 2011
Last updated: 6 years ago

Downloads

show all

Related Extensions