Nested Directory Structure in SQL

directories-my.sql

-- Create our directories table.
CREATE TABLE `directories` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) DEFAULT NULL,
  `lft` int(11) NOT NULL,
  `rgt` int(11) NOT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `directory_lft` (`lft`),
  UNIQUE KEY `directory_rgt` (`rgt`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

-- A procedure for creating space in the directory tree.
CREATE PROCEDURE allocate_directory_space (IN position int(11), IN size int(11))
MODIFIES SQL DATA
BEGIN
  DECLARE EXIT HANDLER FOR SQLEXCEPTION, SQLWARNING ROLLBACK;
  START TRANSACTION;
  UPDATE `directories` SET `lft` = `lft` + size WHERE `lft` >= position ORDER BY `lft` DESC;
  UPDATE `directories` SET `rgt` = `rgt` + size WHERE `rgt` >= position ORDER BY `rgt` DESC;
  COMMIT;
END;

-- A procedure for removing space in the directory tree.
CREATE PROCEDURE deallocate_directory_space (IN position int(11), IN size int(11))
MODIFIES SQL DATA
BEGIN
  DECLARE EXIT HANDLER FOR SQLEXCEPTION, SQLWARNING ROLLBACK;
  START TRANSACTION;
  UPDATE `directories` SET `lft` = `lft` - size WHERE `lft` > position ORDER BY `lft` ASC;
  UPDATE `directories` SET `rgt` = `rgt` - size WHERE `rgt` > position ORDER BY `rgt` ASC;
  COMMIT;
END;

-- A procedure for moving trees into or next to other trees.
CREATE PROCEDURE move_directory_tree (
  IN subject int(11),
  IN mode enum('left','right','into'),
  IN target int(11)
)
MODIFIES SQL DATA
BEGIN
  DECLARE old_lft int(11);
  DECLARE old_rgt int(11);
  DECLARE new_lft int(11);
  DECLARE EXIT HANDLER FOR SQLEXCEPTION, SQLWARNING BEGIN
    ROLLBACK;
    SELECT 0 AS `ok`, old_lft AS `lft`, old_rgt AS `rgt`;
  END;

  START TRANSACTION;

  -- Query for the old left and right values.
  SELECT `lft`, `rgt` INTO old_lft, old_rgt FROM `directories` WHERE `id` = subject;

  -- Check if the move is valid.
  IF target IN (SELECT `id` FROM `directories` WHERE `lft` >= old_lft AND `rgt` <= old_rgt) THEN
    ROLLBACK;
    SELECT 0 AS `ok`, old_lft AS `lft`, old_rgt AS `rgt`;
  ELSE
    -- Remove the directory we're moving by flipping it into negative space.
    UPDATE `directories` SET `lft` = (0 - `lft`), `rgt` = (0 - `rgt`)
    WHERE `lft` >= old_lft AND `rgt` <= old_rgt;

    -- Remove the space we've created.
    CALL deallocate_directory_space (old_lft, (old_rgt - old_lft) + 1);

    -- Determine target position.
    SELECT CASE mode
    WHEN 'left' THEN `lft`
    WHEN 'right' THEN `rgt` + 1
    WHEN 'into' THEN `rgt`
    END INTO new_lft FROM `directories` WHERE `id` = target;

    -- Allocate space at target position.
    CALL allocate_directory_space (new_lft, (old_rgt - old_lft) + 1);

    -- Move the subject and all of its children into the allocated space.
    UPDATE `directories`
    SET `lft` = (0 - `lft` + (new_lft - old_lft)), `rgt` = (0 - `rgt` + (new_lft - old_lft))
    WHERE `lft` < 0;

    COMMIT;
    SELECT 1 AS `ok`, new_lft AS `lft`, new_lft + (old_rgt - old_lft) AS `rgt`;
  END IF;
END;

-- A procedure for creating a new directory with a parent.
CREATE PROCEDURE create_directory (IN new_name varchar(255), IN parent int(11))
MODIFIES SQL DATA
BEGIN
  DECLARE position int(11);
  DECLARE EXIT HANDLER FOR SQLEXCEPTION, SQLWARNING ROLLBACK;
  START TRANSACTION;
  SELECT `rgt` INTO position FROM `directories` WHERE `id` = parent;
  CALL allocate_directory_space (position, 2);
  INSERT INTO `directories` (`name`, `lft`, `rgt`) VALUES (new_name, position, position + 1);
  COMMIT;
  SELECT LAST_INSERT_ID() AS `id`;
END;

-- A procedure for creating a new directory without parents.
CREATE PROCEDURE create_directory_tree (IN new_name varchar(255))
MODIFIES SQL DATA
BEGIN
  INSERT INTO `directories` (`name`, `lft`, `rgt`)
  SELECT new_name, IFNULL(MAX(`rgt`) + 1, 1), IFNULL(MAX(`rgt`) + 2, 2)
  FROM `directories`;

  SELECT LAST_INSERT_ID() AS `id`;
END;

-- A procedure for removing a directory and its descendants.
CREATE PROCEDURE delete_directory_tree (IN subject int(11))
MODIFIES SQL DATA
BEGIN
  DECLARE old_lft int(11);
  DECLARE old_rgt int(11);
  DECLARE EXIT HANDLER FOR SQLEXCEPTION, SQLWARNING ROLLBACK;
  START TRANSACTION;
  SELECT `lft`, `rgt` INTO old_lft, old_rgt FROM `directories` WHERE `id` = subject;
  DELETE FROM `directories` WHERE `lft` >= old_lft AND `rgt` <= old_rgt;
  CALL deallocate_directory_space (old_lft, (old_rgt - old_lft) + 1);
  COMMIT;
END;

directories-postgre.sql

-- Create our tags table.
CREATE TABLE tags (
  id SERIAL NOT NULL,
  name character varying(255) NOT NULL,
  lft integer NOT NULL,
  rgt integer NOT NULL,
  PRIMARY KEY (id),
  UNIQUE (lft) DEFERRABLE INITIALLY IMMEDIATE,
  UNIQUE (rgt) DEFERRABLE INITIALLY IMMEDIATE
);

-- A function for creating space in the tag tree.
CREATE FUNCTION allocate_tag_space(pos integer, size integer) RETURNS void AS $$
  BEGIN
  SET CONSTRAINTS ALL DEFERRED;
  UPDATE tags SET lft = lft + size WHERE lft >= pos;
  UPDATE tags SET rgt = rgt + size WHERE rgt >= pos;
  END;
$$ LANGUAGE PLPGSQL;

-- A function for removing space in the tag tree.
CREATE FUNCTION deallocate_tag_space(pos integer, size integer) RETURNS void AS $$
  BEGIN
  SET CONSTRAINTS ALL DEFERRED;
  UPDATE tags SET lft = lft - size WHERE lft > pos;
  UPDATE tags SET rgt = rgt - size WHERE rgt > pos;
  END;
$$ LANGUAGE PLPGSQL;

-- A function for moving trees into or next to other trees.
CREATE TYPE move_tag_tree_mode AS ENUM ('left', 'right', 'into');
CREATE FUNCTION move_tag_tree(
  subject tags.id%TYPE,
  mode move_tag_tree_mode,
  target tags.id%TYPE
) RETURNS void AS $$

  DECLARE
    old_lft tags.lft%TYPE;
    old_rgt tags.rgt%TYPE;
    new_lft tags.lft%TYPE;
  BEGIN

  -- Query for the old left and right values.
  SELECT lft, rgt INTO old_lft, old_rgt FROM tags WHERE id = subject;

  -- Check if the move is valid.
  IF target IN (SELECT id FROM tags WHERE lft >= old_lft AND rgt <= old_rgt) THEN
    RAISE EXCEPTION 'Attempt to move tree into itself';
  END IF;

  -- Remove the tag we're moving by flipping it into negative space.
  UPDATE tags SET lft = (0 - lft), rgt = (0 - rgt)
  WHERE lft >= old_lft AND rgt <= old_rgt;

  -- Remove the space we've created.
  PERFORM deallocate_tag_space (old_lft, (old_rgt - old_lft) + 1);

  -- Determine target pos.
  SELECT CASE mode
  WHEN 'left' THEN lft
  WHEN 'right' THEN rgt + 1
  WHEN 'into' THEN rgt
  END INTO new_lft FROM tags WHERE id = target;

  -- Allocate space at target pos.
  PERFORM allocate_tag_space (new_lft, (old_rgt - old_lft) + 1);

  -- Move the subject and all of its children into the allocated space.
  UPDATE tags
  SET lft = (0 - lft + (new_lft - old_lft)), rgt = (0 - rgt + (new_lft - old_lft))
  WHERE lft < 0;

  END;
$$ LANGUAGE PLPGSQL;

-- A function for creating a new tag with a parent.
CREATE FUNCTION create_tag(new_name tags.name%TYPE, parent tags.id%TYPE) RETURNS tags.id%TYPE AS $$
  DECLARE pos integer; last_insert_id tags.id%TYPE; BEGIN
  SELECT rgt INTO pos FROM tags WHERE id = parent;
  IF pos IS NULL THEN RAISE EXCEPTION 'Parent not found'; END IF;
  PERFORM allocate_tag_space (pos, 2);
  INSERT INTO tags (name, lft, rgt) VALUES (new_name, pos, pos + 1)
  RETURNING id INTO last_insert_id;
  RETURN last_insert_id;
  END;
$$ LANGUAGE PLPGSQL;

-- A function for creating a new tag without parents.
CREATE FUNCTION create_tag_tree(new_name tags.name%TYPE) RETURNS tags.id%TYPE AS $$
  DECLARE last_insert_id tags.id%TYPE; BEGIN
  INSERT INTO tags (name, lft, rgt)
  SELECT new_name, COALESCE(MAX(rgt) + 1, 1), COALESCE(MAX(rgt) + 2, 2)
  FROM tags RETURNING id INTO last_insert_id;
  RETURN last_insert_id;
  END;
$$ LANGUAGE PLPGSQL;

-- A function for removing a tag and its descendants.
CREATE FUNCTION delete_tag_tree(subject tags.id%TYPE) RETURNS void AS $$
  DECLARE old_lft tags.lft%TYPE; old_rgt tags.rgt%TYPE; BEGIN
  SELECT lft, rgt INTO old_lft, old_rgt FROM tags WHERE id = subject;
  DELETE FROM tags WHERE lft >= old_lft AND rgt <= old_rgt;
  PERFORM deallocate_tag_space (old_lft, (old_rgt - old_lft) + 1);
  END;
$$ LANGUAGE PLPGSQL;

unflatten.js

// MySQLDir :: { id :: Number, name :: String, lft :: Number, rgt :: Number }
// Directory :: { id :: Number, name :: String, children :: Array Directory }
// unflatten :: Array MySQLDir -> Array Directory
const unflatten = directories => {
  if (directories.length === 0) { return []; }
  const head = directories[0];
  const children = directories.filter(dir => dir.lft > head.lft && dir.rgt < head.rgt);
  const remainder = directories.filter(dir => dir.lft > head.rgt);
  return [{id: head.id, name: head.name, children: unflatten(children)}]
  .concat(unflatten(remainder));
};