Storing Hierarchical Data in a Database

README.md

Storing Hierarchical Data in a Database

adjacency_list_model.php

<?php

$link = mysql_connect('localhost', 'root', 'asdf');
mysql_select_db('foods', $link);

function display_children($parent, $level) {
    $result = mysql_query("SELECT title FROM food WHERE parent='{$parent}'");
    while ($row = mysql_fetch_array($result)) {
        echo str_repeat('&nbsp;&nbsp;', $level) . $row['title'] . "<br/>";
        display_children($row['title'], $level + 1);
    }
}

function get_path($node)
{
    $result = mysql_query("SELECT parent FROM food WHERE title = '{$node}'");

    $row = mysql_fetch_array($result);

    $path = array();

    if (!empty($row['parent'])) {
        $path[] = $row['parent'];

        $path = array_merge(get_path($row['parent']), $path);
    }

    return $path;
}


display_children('Food', 0);

var_dump(get_path('Cherry'));

food.sql

-- phpMyAdmin SQL Dump
-- version 4.0.0-dev
-- http://www.phpmyadmin.net
--
-- Host: localhost
-- Generation Time: Aug 13, 2012 at 12:11 AM
-- Server version: 5.5.27-log
-- PHP Version: 5.4.5

SET SQL_MODE = "NO_AUTO_VALUE_ON_ZERO";
SET time_zone = "+00:00";


/*!40101 SET @OLD_CHARACTER_SET_CLIENT=@@CHARACTER_SET_CLIENT */;
/*!40101 SET @OLD_CHARACTER_SET_RESULTS=@@CHARACTER_SET_RESULTS */;
/*!40101 SET @OLD_COLLATION_CONNECTION=@@COLLATION_CONNECTION */;
/*!40101 SET NAMES utf8 */;

--
-- Database: `foods`
--

-- --------------------------------------------------------

--
-- Table structure for table `food`
--

CREATE TABLE IF NOT EXISTS `food` (
  `title` varchar(255) NOT NULL,
  `parent` varchar(255) NOT NULL,
  `lft` int(11) NOT NULL,
  `rgt` int(11) NOT NULL,
  PRIMARY KEY (`title`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

--
-- Dumping data for table `food`
--

INSERT INTO `food` (`title`, `parent`, `lft`, `rgt`) VALUES
('Food', '', 1, 22),
('Fruit', 'Food', 2, 15),
('Green', 'Fruit', 3, 6),
('Pear', 'Green', 4, 5),
('Red', 'Fruit', 7, 10),
('Cherry', 'Red', 8, 9),
('Yellow', 'Fruit', 11, 14),
('Banana', 'Yellow', 12, 13),
('Meat', 'Food', 16, 21),
('Beef', 'Meat', 17, 18),
('Pork', 'Meat', 19, 20);

/*!40101 SET CHARACTER_SET_CLIENT=@OLD_CHARACTER_SET_CLIENT */;
/*!40101 SET CHARACTER_SET_RESULTS=@OLD_CHARACTER_SET_RESULTS */;
/*!40101 SET COLLATION_CONNECTION=@OLD_COLLATION_CONNECTION */;

modified_preorder_tree_traversal_algorithm.php

<?php

$link = mysql_connect('localhost', 'root', 'asdf');
mysql_select_db('foods', $link);

function display_tree($root)
{
    $result = mysql_query("SELECT lft, rgt FROM food WHERE title ='{$root}'");

    $row = mysql_fetch_array($result);

    $right  = [];

    $result = mysql_query(
        "SELECT title, lft, rgt FROM food "
        . "WHERE lft BETWEEN '{$row['lft']}' AND '{$row['rgt']}' ORDER BY lft ASC"
    );

    while ($row = mysql_fetch_array($result)) {
        if (count($right) > 0) {
            while ($right[count($right) - 1] < $row['rgt']) {
                array_pop($right);
            }
        }
        echo str_repeat('&nbsp;&nbsp;', count($right)) . $row['title'] . '<br/>';

        $right[] = $row['rgt'];
    }
}


function rebuild_tree($parent, $left)
{
    $right = $left + 1;

    $result = mysql_query("SELECT title FROM food WHERE parent = '{$parent}'");

    while ($row = mysql_fetch_array($result)) {
        $right = rebuild_tree($row['title'], $right);
    }

    mysql_query("UPDATE food SET lft = '{$left}', rgt = '{$right}' WHERE title = '{$parent}'");

    return $right + 1;
}

rebuild_tree('Food', 1);

function add_node($title, $parent)
{
    $result = mysql_query("SELECT rgt FROM food WHERE title = '{$parent}'");
    $row = mysql_fetch_array($result);
    $right =$row['rgt'];
    mysql_query("UPDATE food set rgt = rgt + 2 WHERE rgt >= '{$right}'");
    mysql_query("UPDATE food set lft = lft + 2 WHERE lft >= '{$right}'");
    $left = $right;
    $right = $left + 1;
    mysql_query(
        "INSERT INTO food "
        ."SET title = '{$title}', lft = '{$left}', rgt = '{$right}', parent = '{$parent}'"
    );
}

function remove_node($title)
{
    $result = mysql_query("SELECT rgt FROM food WHERE title = '{$title}'");
    $row = mysql_fetch_array($result);
    $right = $row['rgt'];
    mysql_query("UPDATE food set rgt = rgt - 2 WHERE rgt > '{$right}'");
    mysql_query("UPDATE food set lft = lft - 2 WHERE lft > '{$right}'");
    mysql_query("DELETE FROM food WHERE title = '{$title}'");
}



$now = time();

add_node('Hongfushi' . $now, 'Yellow');


display_tree('Food');

echo '<hr/>';

remove_node('Hongfushi' . $now, 'Yellow');

display_tree('Food');