Hierarchies - Topological Ordering - Table Setup Script

The enumeration method consists of a depth first left-to-right traversal of the hierarchy, assigning the left number when first visiting a node when last visiting it after all descendent nodes have been enumerated. To achieve this, imagine a thread created starting from the left of the top node, progressing through the left side of the first descendent, wrapping around the first leaf through its right side, up the right of the parent and so on...

Now imagine this thread streatched out. Each node appears twice. Once attached on the left, and once on the right. The objective is to order the nodes of the hierarchy in exactly the order visited by the thread, then enumerate the list, and pivot the left and right numbers against each node.

Try each of the scripts below in sequence. Each one progressively builds on the previous one. By looking at the results step by step it is easier to understand how the method works.

lr1.sql402 bytes
lr2.sql584 bytes
lr3.sql671 bytes
lr4.sql886 bytes
VDM Access: