Copy-on-write versioning of documents

• US 20080104141A1
• Filed: 10/30/2006
• Published: 05/01/2008
• Est. Priority Date: 10/30/2006
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: McMahon, Douglas James
• Granted Patent: US 7,627,615 B2
• Time in Patent Office: Days
• US Class Current: 707/203
• CPC Class Codes: G06F 40/197 Version control for software G06F8/71

Abstract

Approach for versioning of documents is described. A version accumulator structure stores one or more version values indicating different versions of a data object. The data object is decomposable into a plurality of nodes. One or more copies of each node of the plurality of nodes are stored, where the one or more copies are associated with non-overlapping version ranges. A first request to perform a change to the data object is received. The first request specifies an effective version value for the change, which involves a particular node. The change is performed based on the effective version value and without making a deep copy of the data object. A second request to retrieve a certain version of the data object is received. The certain version is retrieved based on the version ranges associated with the one or more copies of each node of the plurality of nodes.

Claims

1. A method for versioning of data objects comprising performing a machine-executed operation involving instructions, wherein the machine-executed operation is at least one of:

A) sending the instructions over transmission media;

B) receiving the instructions over transmission media;

C) storing the instructions onto a machine-readable storage medium; and

D) executing the instructions;

wherein the instructions, when executed by one or more processors, cause;

storing one or more version values in a version accumulator structure, wherein each of the one or more version values indicates a different version of a data object;

wherein the data object includes, and is decomposable into, a plurality of nodes;

storing one or more copies of each node of the plurality of nodes, wherein each copy of the one or more copies is associated with a version range which does not overlap with any other version range that is associated with any other copy of the one or more copies;

receiving a first request to perform a change to the data object, wherein the change involves a particular node of the plurality of nodes, and wherein the first request specifies an effective version value for the change;

performing the change based on the effective version value, wherein performing the change does not include making a complete copy of the data object that reflects the change;

receiving a second request to retrieve a certain version of the data object; and

retrieving the certain version of the data object based on version ranges associated with the one or more copies of each node of the plurality of nodes.

2. The method of claim 1, wherein the version range associated with any of the one or more copies of any node of the plurality of nodes includes a minimum version value and a maximum version value.

3. The method of claim 2, wherein version values included in the version range are drawn from a domain of values that comprises any one of:

datetime values;

real number values; and

an ordered set of values.

4. The method of claim 1, wherein the plurality of nodes included in the data object are organized in a hierarchical tree.

5. The method of claim 1, wherein the plurality of nodes included in the data object are not organized in any particular logical representation.

6. The method of claim 1, wherein the one or more copies of each node of the plurality of nodes included in the data object are stored in one or more relational tables of one or more relational databases.

7. The method of claim 1, wherein:

the version range associated with any of the one or more copies of any node of the plurality of nodes includes a minimum version value and a maximum version value;

the one or more copies of each node of the plurality of nodes are stored in one or more storage structures; and

the instructions further comprise instructions which, when executed by the one or more processors, cause creating and maintaining at least one index over the one or more storage structures, wherein the at least one index is based on at least one of minimum version values and maximum version values associated with copies of the plurality of nodes.

8. The method of claim 1, wherein the version accumulator structure is stored within a particular node of the plurality of nodes included in the data object.

9. The method of claim 1, wherein the second request includes a certain version value that indicates the certain version specified in the second request, wherein the certain version value that does not match any version value stored in the version accumulator structure.

10. The method of claim 1, wherein:

the effective version value specified in the first request indicates a non-current version of the data object; and

the instructions that cause performing the change to the data object further comprise instructions which, when executed by the one or more processors, cause performing the change relative to a non-current copy of the particular node of the plurality of nodes.

11. The method of claim 1, wherein the instructions that cause performing the change to the data object further comprise instructions which, when executed by the one or more processors, cause any one of:

adding the particular node as a new node to the plurality of nodes included in the data object;

removing the particular node from the plurality of nodes included in the data object;

modifying the particular node of the plurality of nodes included in the data object;

moving the particular node of the plurality of nodes to a different location in the data object.

12. The method of claim 1, wherein the instructions that cause performing the change to the data object further comprise instructions which, when executed by the one or more processors, cause adding the particular node to the plurality of nodes included in the data object, wherein adding the particular node to the plurality of nodes comprises:

determining a terminal version value from the version accumulator structure, wherein the terminal version value is the smallest version value indicated in the version accumulator structure which is greater than the effective version value;

storing a copy of the particular node, wherein the copy of the particular node is associated with a particular version range, wherein the minimum version value included in the particular version range is set to the effective version value, and wherein the maximum version value included the particular version range is set to the terminal version value; and

if the effective version value is not already stored in the version accumulator structure, then storing the effective version value in the version accumulator structure.

13. The method of claim 1, wherein the instructions that cause performing the change to the data object further comprise instructions which, when executed by the one or more processors, cause removing the particular node from the plurality of nodes included in the data object, wherein removing the particular node from the plurality of nodes comprises:

determining a terminal version value from the version accumulator structure, wherein the terminal version value is the smallest version value indicated in the version accumulator structure which is greater than the effective version value;

determining a particular copy of the one or more copies of the particular node, wherein the particular copy is associated with a particular version range, wherein the effective version value is grater than or equal to the minimum version value included in the particular version range, and wherein the effective version value is less than the maximum version value included in the particular version range;

if the minimum version value is equal to the effective version value and the maximum version value is greater than the terminal version value, then setting the minimum version value to the terminal version value in the particular version range associated with the particular copy;

if the maximum version value is greater than the terminal version value, then storing the particular copy as a new copy of the particular node, wherein the new copy is associated with a new version range, wherein the new minimum version value included in the new version range is set to the terminal version value, and wherein the new maximum version value included the new version range is set to the maximum version value;

if the minimum version value is less than the effective version value, then setting the maximum version value to the effective version value in the particular version range associated with the particular copy;

if the minimum version value is equal to the effective version value and the maximum version value is equal to the terminal version value, then deleting the particular copy of the one or more copies of the particular node; and

if the effective version value is not already stored in the version accumulator structure, then storing the effective version value in the version accumulator structure.

14. The method of claim 13, wherein:

the plurality of nodes included in the data object are organized in a hierarchical tree;

the particular node is a parent node of one or more descendant nodes in the hierarchical tree; and

the instructions that cause removing the particular node further comprise instructions which, when executed by the one or more processors, cause;

recursively traversing the one or more descendant nodes; and

removing any copies of the one or more descendant nodes which are associated with version ranges that match the particular version range associated with the particular copy.

15. The method of claim 1, wherein the instructions that cause performing the change to the data object further comprise instructions which, when executed by the one or more processors, cause modifying the particular node of the plurality of nodes included in the data object, wherein modifying the particular node of the plurality of nodes comprises:

determining a terminal version value from the version accumulator structure, wherein the terminal version value is the smallest version value indicated in the version accumulator structure which is greater than the effective version value;

determining a particular copy of the one or more copies of the particular node, wherein the particular copy is associated with a particular version range, wherein the effective version value is grater than or equal to the minimum version value included in the particular version range, and wherein the effective version value is less than the maximum version value included in the particular version range;

if the minimum version value is equal to the effective version value and the maximum version value is equal to the terminal version value, then updating the particular copy of the particular node to include the requested change;

if the maximum version value is greater than the terminal version value, then storing a new copy of the particular node that includes the requested change, wherein the new copy is associated with a new version range, wherein the new minimum version value included in the new version range is set to the terminal version value, and wherein the new maximum version value included the new version range is set to the maximum version value;

if the minimum version value is less than the effective version value, then;

storing the particular copy as a new copy of the particular node, wherein the new copy is associated with a new version range, wherein the new minimum version value included in the new version range is set to the minimum version value, and wherein the new maximum version value included the new version range is set to the effective version value;

updating the particular copy with the requested change; and

setting the minimum version value included in the particular version range to the effective version value and setting the maximum version value included in the particular version range to the terminal version value; and

if the effective version value is not already stored in the version accumulator structure, then storing the effective version value in the version accumulator structure.

16. The method of claim 1, wherein:

the plurality of nodes included in the data object are organized in a hierarchical tree, wherein each child node in the hierarchical tree stores a pointer to a parent node; and

the instructions that cause performing the change to the data object further comprise instructions which, when executed by the one or more processors, cause moving the particular node of the plurality of nodes under a different parent node in the hierarchical tree.

17. The method of claim 1, wherein:

the plurality of nodes included in the data object are organized in a hierarchical tree, wherein each parent node in the hierarchical tree stores a list of pointers to one or more child nodes; and

the instructions that cause performing the change to the data object further comprise instructions which, when executed by the one or more processors, cause moving the particular node of the plurality of nodes under a different parent node in the hierarchical tree, wherein moving the particular node comprises modifying the different parent node.

18. The method of claim 1, wherein:

the second request includes a certain version value that indicates the certain version of the data object; and

the instructions that cause retrieving the certain version of the data object further comprise instructions which, when executed by the one or more processors, cause traversing each node of the plurality of nodes, wherein traversing said each node comprises;

determining a particular copy of the one or more copies of said each node, wherein the particular copy is associated with a particular version range, wherein the certain version value is grater than or equal to the minimum version value included in the particular version range, and wherein the certain version value is less than the maximum version value included in the particular version range; and

retrieving the particular copy of said each node.

19. The method of claim 18, wherein:

the plurality of nodes included in the data object are organized in a hierarchical tree; and

the instructions that cause traversing each node of the plurality of nodes further comprise instructions which, when executed by the one or more processors, cause traversing the hierarchical tree by descending downward from a parent node of the hierarchical tree to any child nodes thereof.

20. The method of claim 18, wherein:

the plurality of nodes included in the data object are organized in a hierarchical tree; and

the instructions that cause traversing each node of the plurality of nodes further comprise instructions which, when executed by the one or more processors, cause traversing the hierarchical tree by ascending upward from a child node of the hierarchical tree to any parent nodes thereof.

21. The method of claim 1, wherein:

the plurality of nodes included in the data object are organized in a hierarchical tree;

the certain version specified in the second request is a flattened version of the data object; and

the instructions that cause retrieving the certain version of the data object further comprise instructions which, when executed by the one or more processors, cause traversing each node of the plurality of nodes, wherein traversing said each node comprises;

recursively traversing each child node of said each node;

for said each child node, determining a particular copy of the one or more copies of said each child node, wherein the particular copy is associated with a particular version range that overlaps a certain version range associated with a certain copy of said each node;

determining a new version range for the particular copy of said each child node based on the particular version range and the certain version range;

retrieving the particular copy of said each child node; and

returning an output in response to the second request, wherein in the output the particular copy is associated with the new version range instead of the particular version range.

22. The method of claim 1, wherein:

the plurality of nodes included in the data object are organized in a hierarchical tree;

the certain version specified in the second request is a flattened version of the data object; and

the instructions that cause retrieving the certain version of the data object further comprise instructions which, when executed by the one or more processors, cause traversing each node of the plurality of nodes, wherein traversing said each node comprises;

for each ancestor node of said each node in the hierarchical tree, determining a particular copy of the one or more copies of said each ancestor node, wherein the particular copy is associated with a particular version range that overlaps a certain version range associated with a certain copy of said each node;

determining a new version range for the particular copy of said each ancestor node based on the particular version range and the certain version range;

retrieving the particular copy of said each ancestor node; and

returning an output in response to the second request, wherein in the output the particular copy is associated with the new version range instead of the particular version range.