Versioned relational database system with an optimistic constraint model
View Patent ↗Techniques for doing optimistic constraint checking in a versioned relational database system. The techniques find a subset of the versions of a table that contain all of the rows that need be checked for violation of a constraint when a given version is modified. When the versions of a table are organized into a directed acyclic graph (DAG), the subset for a given version is the ancestry of the given version, that is, the given version plus the ancestors of the given version in the DAG. Within the ancestry, the set of rows that must be checked is termed the version view. A row that belongs to the set has a primary key that is the latest version of the primary key in the given version's ancestry. The technique may be used for constraints including the referential integrity constraint and the unique key constraint. The metadata used to compute the version view is disclosed, as well as the manner in which the constraint checking techniques interact with the workspaces that provide access to the versions. The workspaces may be organized as a DAG. The manner in which the workspaces are organized determines how changes are propagated in the versioned relational database and thus the versions whose ancestry has to be checked for constraint violations.
1. A versioned relational database system comprising:
a set of versions of a table in a relational database system; and
metadata that is automatically created and maintained by the relational database system, the metadata permitting determination of a proper subset of the versions, the subset including those versions in the set in which a constraint violation may occur as a result of an operation on the table that affects a given version, the versioned relational database system employing the metadata in the course of performing the operation to locate rows in the versions of the subset for which the operation may result in a violation of a constraint.
2. The versioned relational database system set forth in claim 1 wherein:
the metadata includes metadata from which a directed acyclic graph of the versions may be determined; and
the versions in the subset for the given version include the versions in an ancestry of the given version that includes the given version and the given version's ancestors in the branches of the directed acyclic graph to which the given version belongs.
3. The versioned relational database set forth in claim 2 wherein:
the metadata includes a view which includes the ancestry of the given version.
4. The versioned relational database system set forth in claim 2 wherein:
the located rows are the rows in the given version's ancestry that have the most recent versions of their primary keys.
5. The versioned relational database system set forth in claim 4 wherein:
the metadata includes a view which computes the latest versions of the primary keys in the table.
6. The versioned relational database system set forth in claim 1 wherein:
the constraint is a referential integrity constraint.
7. The versioned relational database system set forth in claim 1 wherein:
the constraint is a unique key constraint.
8. The versioned relational database system set forth in claim 1 wherein:
the operation affects the given version by modifying a row thereof.
9. The versioned relational database system set forth in claim 1 wherein:
the operation affects the given version by modifying a set of constraints associated with the table.
10. The versioned relational database system set forth in claim 1 wherein:
there is a plurality of the given versions affected by the operation; and
the subset includes for each of the given versions in the plurality thereof those versions in the set in which a constraint violation may occur in consequence of the operation's effect on the given version.
11. Data storage apparatus that may be accessed by a computer system, the data storage apparatus being characterized in that:
the data storage apparatus stores program code which, when executed in the computer system, implements a versioned relational database system comprising a set of versions of a table in a relational database system; and
metadata that is automatically created and maintained by the relational database system, the metadata permitting determination of a proper subset of the versions, the subset including those versions in the set in which a constraint violation may occur as a result of an operation on the table that affects a given version, the computer system employing the metadata in the course of performing the operation to locate rows in the versions of the subset for which the operation may result in a violation of a constraint.
12. A versioned relational database system comprising:
a set of versions of a table in a relational database system;
a set of workspaces, a workspace giving access to a version; and
metadata that is automatically created and maintained by the relational database system, the metadata permitting determination of a proper subset of the versions, the subset including those versions in the set in which a constraint violation may occur as a result of an operation that affects a version that is accessible from a given workspace,
the versioned relational database system employing the metadata in the course of performing the operation to locate rows in versions of the subset for which the operation may result in a violation of a constraint.
13. The versioned relational database system set forth in claim 12 wherein:
the metadata includes metadata from which a directed acyclic graph of the versions may be determined; and
the versions in the subset for the given version include the versions in an ancestry of the given version that includes the given version and the given version's ancestors in the branches of the directed acyclic graph to which the given version belongs.
14. The versioned relational database system set forth in claim 13 wherein:
the metadata includes a view which includes all of the ancestry of the given version.
15. The versioned relational database system set forth in claim 13 wherein:
the located rows are the rows in the given version's ancestry that have the most recent versions of their primary keys.
16. The versioned relational database system set forth in claim 15 wherein:
the metadata includes a view which computes the latest versions of the primary keys in the table.
17. The versioned relational database system set forth in claim 12 wherein:
the operation is a change propagation operation in which a change in a version in a first one of the workspaces is propagated to a version in a second one of the workspaces.
18. The versioned relational database system set forth in claim 17 wherein:
the metadata includes metadata from which a directed acyclic graph of the workspaces may be determined; and
the change propagation operation propagates changes in a version in a given workspace up or down a branch in the directed acyclic graph to which the given workspace belongs.
19. The versioned relational database system set forth in claim 18 wherein:
the change propagation operation propagates changes in a version in the given workspace to a version in an ancestor of the given workspace in the directed acyclic graph.
20. The versioned relational database system set forth in claim 18 wherein:
the change propagation operation propagates changes in a version in an ancestor of the given workspace in the directed acyclic graph to a version in the given workspace.
21. The versioned relational database set forth in claim 18 wherein:
the directed acyclic graph is a hierarchy.
22. The versioned relational database system set forth in claim 12 wherein:
the operation affects the version in the given workspace by modifying a set of constraints associated with the table.
23. The versioned relational database set forth in claim 18 wherein:
a workspace that has multiple parents in the directed acyclic graph is the leaf node of a multi-parent graph of workspaces wherein the workspace that is the common ancestor of the multiple parent workspaces is the root node and the multiple parent workspaces and the workspaces in the directed acyclic graph between the multiple parent workspaces and the root node are intermediate nodes;
the metadata includes metadata from which a multiparent graph for a given multiparent workspace may be determined; and
the change propagation operations include a refresh operation that propagates changes from a version in a root node in the multiparent graph to versions in the non-root nodes.
24. The versioned relational database set forth in claim 18 wherein:
a workspace that has multiple parents is the leaf node of a multi-parent graph of workspaces wherein the workspace that is the common ancestor of the multiple parent workspaces is the root node and the multiple parent workspaces and the workspaces in the directed acyclic graph between the multiple parent workspaces and the root node are intermediate nodes;
the metadata includes metadata from which a multiparent graph for a given multiparent workspace may be determined; and
the change propagation operations include a merge operation that propagates changes from versions in non-root nodes in the multiparent graph to a version in the root node.
25. Data storage apparatus that may be accessed by a computer system, the data storage apparatus being characterized in that:
the data storage apparatus stores program code which, when executed in the computer system, implements a versioned relational database system comprising
a set of versions of a table in a relational database system;
a set of workspaces, a workspace giving access to a version;
metadata that is automatically created and maintained by the relational database system, the metadata permitting determination of a proper subset of the versions, the subset including those versions in the set in which a constraint violation may occur as a result of an operation that affects a version that is accessible from a given workspace,
the computer system employing the metadata in the course of performing the operation to locate rows in versions of the subset for which the operation may result in a violation of a constraint.
26. A method of enforcing a constraint in a set of versions in a versioned relational database system,
the method comprising the steps performed in the database system of:
automatically creating and maintaining metadata in the relational database system from which a proper subset of the set may be determined, the subset including the versions in which a constraint violation may occur as a result of an operation that is performed on a given version; and
when performing an operation on the given version that may result in a violation of a constraint, employing the metadata to determine for the versions of the subset whether the operation will result in a violation of a constraint.
27. The method set forth in claim 26 wherein the metadata further includes metadata from which a directed acyclic graph of the versions may be determined and the method further comprises the steps of:
determining at least one version that is affected by an operation that may result in a constraint violation; and
for each version that is so affected,
using the metadata to determine an ancestry of the affected version that includes the affected version and the affected version's ancestors in the directed acyclic graph; and
locating any rows in versions in the ancestry for which the operation will result in a constraint violation.
28. The method set forth in claim 27 wherein:
the step of maintaining the metadata includes maintaining a view which includes all of the versions in the ancestry of the given version; and
the view is used in the step of using the metadata.
29. The method set forth in claim 27 wherein the step of locating any rows includes the step of:
determining whether a row has a primary key that is the latest version of the primary key in the affected version's ancestry.
30. The method set forth in claim 29 wherein:
the step of maintaining the metadata includes maintaining a view which computes the latest versions of the primary keys in the table; and
the view is used in the step of using the metadata.
31. The method set forth in claim 27 wherein:
the directed acyclic graph is a hierarchy.
32. The method set forth in claim 26 wherein:
the constraint is a unique key constraint.
33. The method set forth in claim 26 wherein:
the constraint is a referential integrity constraint.
34. The method set forth in claim 26 wherein:
the operation modifies a set of constraints associated with the table; and
every version of the table is affected by the operation.
35. Data storage apparatus that may be accessed by a computer system, the data storage apparatus being characterized in that:
the data storage apparatus stores program code which, when executed in the computer system, performs a method of enforcing a constraint in a set of versions in a versioned relational database system comprising the steps of:
automatically creating and maintaining metadata in the relational database system from which a proper subset of the set may be determined, the subset including the versions in which a constraint violation may occur as a result of an operation that is performed on a given version; and
when performing an operation on the given version that may result in a violation of a constraint, employing the metadata to determine for the versions of the subset whether the operation will result in a violation of a constraint.
36. A method of enforcing a constraint in a set of versions in a versioned relational database system that further includes a set of workspaces, a workspace giving access to a version, and
the method comprising the steps performed in the relational database system of:
automatically defining and maintaining metadata in the relational database system from which a proper subset of the versions may be determined, the subset including those versions in the set in which a constraint violation may occur as a result of an operation that affects a version that is accessible from a given workspace; and
employing the metadata in the course of performing the operation to locate rows in versions of the subset for which the operation may result in violation of a constraint.
37. The method set forth in claim 36 wherein:
the step of maintaining the metadata includes maintaining metadata from which a directed acyclic graph of the versions may be determined; and
in the step of employing the metadata, the versions in the subset for the affected version include the versions in an ancestry of the affected version, the ancestry including the affected version and the affected version's ancestors in the directed acyclic graph.
38. The method set forth in claim 37 wherein:
the step of maintaining the metadata includes maintaining metadata from which a directed acyclic graph of the workspaces may be determined; and
the operation is a change propagation operation in which a change in a version in a first one of the workspaces is propagated up or down the workspace directed acyclic graph to an affected version in a second one of the workspaces.
39. The method set forth in claim 38 wherein:
the operation is a refresh operation wherein a change is propagated from a first version in an ancestor workspace for a given workspace in the directed acyclic graph to a second version in the given workspace; and
the second version is the affected version.
40. The method set forth in claim 38 wherein:
the operation is a merge operation wherein a change is propagated from a first version in a given workspace to a second version in an ancestor workspace for the given workspace in the directed acyclic graph; and
the second version is the affected version.
41. The method set forth in claim 38 wherein:
the workspace directed acyclic graph is a hierarchy.
42. The method set forth in claim 38 wherein:
a workspace that has multiple parents is the leaf node of a multi-parent graph of workspaces wherein the workspace that is the common ancestor of the multiple parent workspaces is the root node and the multiple parent workspaces and the workspaces in the directed acyclic graph between the multiple parent workspaces and the root node are intermediate nodes;
the step of maintaining the metadata includes maintaining metadata from which a multi-parent graph for a given multi-parent workspace may be determined; and
the change propagation operations include a refresh operation that propagates changes from a version in a root node in the multiparent graph to affected versions in the intermediate nodes and in the leaf node.
43. The method set forth in claim 38 wherein:
a workspace that has multiple parents is the leaf node of a multi-parent graph of workspaces wherein the workspace that is the common ancestor of the multiple parent workspaces is the root node and the multiple parent workspaces and the workspaces in the directed acyclic graph between the multiple parent workspaces and the root node are intermediate nodes;
the step of maintaining the metadata includes maintaining metadata from which a multi-parent graph for a given multi-parent workspace may be determined; and
the change propagation operations include a merge operation that propagates changes from a version in a leaf node in the multiparent graph to a version in the root node.
44. Data storage apparatus that may be accessed by a computer system,
the data storage apparatus being characterized in that:
the data storage apparatus stores program code which, when executed in the computer system, performs a method of enforcing a constraint in a set of versions in a versioned relational database system that further includes a set of workspaces, a workspace giving access to a version, and
the method comprises the steps performed in the relational database system of:
automatically creating and maintaining metadata in the relational database system from which a proper subset of the versions may be determined, the subset including those versions in the set in which a constraint violation may occur as a result of an operation that affects a version that is accessible from a given workspace; and
employing the metadata in the course of performing the operation to locate rows in versions of the subset for which the operation may result in violation of a constraint.