Overview
MojoMojo is web content authoring sofware. With MojoMojo (MM) it is easy to create a hierarchy of pages because it stores page content in an acyclic directed graph1. However, the structure has not been fully exploited yet. This articles paves the way to bearing more fruit from MojoMojo’s database design. Specifically it serves as a design document for moving and deleting pages using MM.
Moving Branches of a Tree
How does one take advantage of the tree structure when moving pages (nodes) around. For example, suppose we have page that we want to move. Further, suppose that the page in question has sub-pages which we’d like to bring along on the move. How can we do that within MojoMojo while leveraging its tree structure2. Given that the pages are nodes in a tree and they are stored in a relational database with left and right enumerators, one can use the luxury of cheap SQL3 to gather up the pages for the move.
Gathering the Parts
MojoMojo stores information about its pages in a relational database (PostgreSQL, SQLite, or MySQL). In particular we are interested in the page table and the following fields:
- lft
- The left number assigned to the node. This number comes from counting depth and left first through the nodes of a tree. One starts at and returns to the single origin (top node). This means every node is passed twice. On the first pass (downward movement), one assign the left number, and on the second pass (upward movement) one assigns the right number. This sequence of node numbers makes it trivial to find the descendants of a node because they will have left (and right) numbers that fall between the left and right numbers of the node in question.
- rgt
- The right number assigned to the node
- depth
- This number indicates how many nodes a given node is removed from the origin. For example, a child of the origin is removed by 1.
Child Pages
Given the node numbering structure defined above one can easily query for the children of a page node. For example, to get the children of a page with id 113 do:
SELECT p1.*
FROM page AS p1, page AS p2
WHERE p1.lft BETWEEN p2.lft AND p2.rgt
AND p2.id = 113
Un altre metode:
SELECT p2.*
FROM page AS p1, page AS p2
WHERE p2.lft BETWEEN p1.lft AND p1.rgt
AND p1.id = 113;
Getting the Depth of the Node to Move
The depth of a node is even easier to come by:
SELECT page.depth FROM page WHERE page.id=113
Nodes Between Two Nodes
Given two nodes m and n where lft number of n > lft number of m.
SELECT p3.* FROM page AS p1, page AS p2, page AS p3 WHERE p3.lft > p1.rgt AND p3.rgt < p2.lft AND p1.id=113 AND p2.id=238;
Nodes Outside Two Node (Inclusive)
SELECT p3.* FROM page AS p1, page AS p2, page AS p3 WHERE ( p3.lft < p1.rgt OR p3.rgt > p2.lft) AND (p1.id=113 AND p2.id=238);
Observations about Relocating a Node and its Descendants
In order to make a design for relocating nodes, it’s helpful to make some observations:
- A node can either be moved to a higher or lower (left) number.
- A node can be moved to depth 1 (directly under the origin) or any other depth.
- The numbers of a node and its descendants form a consecutive sequence of natural numbers.
- We’ll use the terminology node family to indicate the move node and all its descendants.
Definitions
In order to make the move, we will need to update the database fields defined above. In order to do so we will need to do some arithmetic based on some left and right node numbers. To facilitate this process, we make the following definitions:
- move_node_left_number
- The left number of the node to move.
- sequence_size
- The difference in the right and left numbers of the move node.
- target_parent_node_left_number
- The left number of the parent node under which we want to move the node (and it’s children). This refers to the original left number of the parent number before we re-sequence the tree nodes.
- target_parent_node_new_left_number
- The left number of the parent node where we want to move the node (and it’s children). This refers to the left number of the parent node after we re-sequence it.
- move_node_new_left_number
- The left number of the move node where after we move (and re-sequence) it.
old bullets:
* The branch to move will hang off a terminal node.
* record node to move left and right numbers in array - @move_node = (left_number, right_number)
* record target parent node number -@target_parent_node = (left_number, right_number)
* calculate number of childen of move node
* calculate size of move sequence5- $number_of_children_to_move = 2*$number_of_nodes_to_move
Updating Left and Right Numbers
Given a node to move and the parent node to place it under, one can make the move by recomputing the left and right node numbers. Here’s the nitty gritty:
Non-Players
For some of the nodes in the tree, no updates have to be performed on their left and right numbers:
- nodes with a left number less than the move node keep the same left, right numbers (static).
- nodes with a left number greater than the target parent node left number are static.
SELECT page.id FROM page
WHERE page.lft < 41
In Between Players
The nodes in between the move and parent node will have their left and right numbers shifted down by twice the number of nodes being moved (move node and its childrens4)
UPDATE TABLE page SET page.lft = ( SELECT 2*( 1 + COUNT(p2.id) ) FROM page AS p1, page AS p2 WHERE p2.lft BETWEEN p1.lft AND p1.rgt AND p1.id = 113 ) WHERE
Target Parent
The target parent node has its left number change, but not the right.
The left number reduces by the sequence_size5.
- target_parent_node_left
- The left number of the parent node under which we want to move the node (and it’s children). This refers to the original left number of the parent number before we re-sequence the tree nodes.
- target_parent_node_new_left
- The left number of the parent node where we want to move the node (and it’s children). This refers to the left number of the parent node after we re-sequence it.
Move Node Family
Right Move - Move to Higher Node Number
The left numbers of the move nodes need to start at a higher number and still remain in sequence. The new amount is 1 greater than what the parent node left number just changed to (target_parent_old_left - size_of_sequence). Thus the difference between the new and old move_node left number is (target_old_left - size_of_sequence) + 1 - move_old_left. This difference can be added to the move node numbers to get their new node numbers.
In summary, the move node family numbers will be incremented by:
target_parent_node_left_number + 1 - move_node_left_number
Appendix
Ancestor Pages
To get the ancestors for page with id 113:
SELECT p2.*
FROM page AS p1, page AS p2
WHERE p1.lft BETWEEN p2.lft AND p2.rgt
AND p1.id = 113
Footnotes
1 Acyclic directed graphs are commonly referred to as trees.
2 MojoMojo tracks the left and right numbers of a tree node in the table page in the fields lft and rgt.
3 The term “nested sets” seems to be popularized by Joe Celko.
4 In this context ‘childrens’ means not just first generation children, but all generations. This is just a synonym for descendants.
5 Note that a node and its children always for a sequence of numbers. The amount of numbers in the sequence is twice the number of nodes involved.
Showing changes from previous revision. Removed | Added
