You will extend the example of using stored functions and procedures to access and modify a rooted, labeled tree. I have provided a CREATE TABLE statement for the tree, example stored functions for finding the depth of a node and for testing whether one node is an ancestor of another, and example stored procedures for adding a leaf, changing a node's parent, and deleting a node. I have also provided sample data taken from Gustavus's administrative hierarchy and some sample queries and procedure calls using these functions and procedures, as well as those you will write.
Each of the example functions I provided climbs up the tree however far proves necessary, something that is not possible with an ordinary SQL query. The same will be true for the function you write. Each of the example procedures I provided modifies the table in a controlled manner, ensuring that it continues to represent a rooted tree: exactly one node is parentless and the parent relationship is acyclic. Your programming will also retain this property.
I plan to assign partners to work together on this project.
You should define a stored function named lowest_common_ancestor. It should take two integer input parameters that must be the identifiers of two nodes in the tree. It should return an integer that is also the identifier of a node, namely the lowest common ancestor of the two that were given.
Recall from the example function for testing ancestry that each node is considered to be an ancestor of itself. As such, the lowest common ancestor of two nodes will be the same as one of those two nodes if it is an ancestor of the other. As a particular case of this, if the two input parameters are identical, so that the request is for the lowest common ancestor of a node and itself, then that node will be returned as the result.
Here is pseudo-code for a reasonable algorithm for finding the lowest common ancestor of node1 and node2:
Let depth1 be the depth of node1 and depth2 be the depth of node2.
While depth1 is greater than depth2, change the node1 variable to refer to the current node1's parent and reduce depth1 correspondingly.
While depth2 is greater than depth1, change the node2 variable to refer to the current node2's parent and reduce depth2 correspondingly.
While node1 and node2 are not the same, change each of these variables to refer to its parent.
Return the value of either node1 or node2. (They are equal.)
Notice that at most one of the first two loop bodies will be executed. The first one handles the case that node1 starts out deeper than node2 and moves up through node1's ancestors until one is reached that is of the same depth as node2. Likewise, the second loop handles the case that node2 starts out deeper than node1. If the two nodes were already of the same depth, neither of these loop bodies executes at all. In any case, by the time the third loop is reached, the two nodes are of equal depth. Perhaps they are even the same node, but they might also be siblings or cousins. The third loop moves each of them up the tree just far enough to reach a common ancestor; at worst, this will be the root of the tree.
The stored procedure I provided for changing a node's parent has the limitation that the new parent must not be NULL. That is, the node's new position in the tree must not be at the root. Your goal is to remove that limitation.
Because the tree must have only one root, if a node is moved to newly become the root, the previous root should be moved down in the tree. Specifically, the previous root should become a child of the new root. You are to modify the change_parent procedure to behave in this way.
You should email me the code of your stored function and your modified version of the stored procedure.