Database management system, method and program for supporting the mutation of a composite object without read/write and write/write conflicts
First Claim
1. A method for mutating, in response to a query language statement, a composite object in a database, the method comprising:
- creating a copy of the composite object before the composite object is to be mutated; and
using the copy by a mutator function in the query language statement.
1 Assignment
0 Petitions
Accused Products
Abstract
The system, method, and program of this invention avoids potential write/write conflicts and read/write conflicts when a subcomponent of a composite object (e.g., an ADT) is mutated. The embodiments of this invention define a copy semantic for the mutation function. In one embodiment, a copy function is inserted prior to any mutation function. In a another embodiment, a global compile-time analysis is performed to determine if a write/write or read/write conflict exists; and to eliminate redundant copy constructors if a conflict does exist. In a preferred embodiment, only a local analysis is performed during the parsing phase, thereby avoiding a global compile-time analysis. A mutation safe flag is associated with each parse tree node. A read target leaf parse tree node is set to false while non-leaf parse tree nodes (functions) derive their value from an incoming node, except that constructors and copy constructor functions are always true. Whether or not a copy is made of the composite object (i.e., whether or not a copy constructor is inserted) prior to a mutation is determined according to the setting of the mutation safe flags and according to the following. If a mutation safe flag for a mutation function is false, a copy constructor is inserted for the mutated composite object and the mutation safe flag is set to true. In addition, for update and trigger statements, the mutation safe flag for a mutated target is defaulted to true. Furthermore, related update entries are grouped together and a copy is generated for the common target. The generated copy is used as the common target for all of the mutations caused by the update entries grouped together in order to accumulate all of the desired mutations in a same copy of the composite object.
-
Citations
31 Claims
-
1. A method for mutating, in response to a query language statement, a composite object in a database, the method comprising:
-
creating a copy of the composite object before the composite object is to be mutated; and using the copy by a mutator function in the query language statement. - View Dependent Claims (2, 3, 5)
-
-
4. A method for mutating, in response to a query language statement, a composite object in a database managed by a database management system, the method comprising:
-
inserting a copy constructor in a parsed representation of the query language statement to create a copy of the composite object when the composite object is being mutated; using the copy by a mutator function in the query language statement; and using an original of the composite object for other functions in the query language statement.
-
-
6. A method of mutating, in response to a query language statement, a composite object in a database managed by a database management system, the method comprising:
-
performing a compile time analysis to determine if a write/write or read/write conflict exists; and inserting a minimum number of copy constructors, if the conflict exists, in order to avoid the conflict. - View Dependent Claims (7)
-
-
8. A method of mutating, in response to a query language statement, a composite object in a database managed by a database management system, the method comprising:
-
performing a compile time analysis for determining if an observer function is present; and inserting a copy constructor for an innermost mutation if the observer function is present.
-
-
9. A method of mutating, in response to a query language statement, a composite object in a database managed by a database management system, the method comprising:
-
setting a mutation safe status for each parse tree node of the query language statement according to the following; a) for each leaf node corresponding to a composite object, setting the mutation safe status to indicate that the node is not safe; b) for each non-leaf node, deriving the mutation safe status from an incoming node and from the function itself; and inserting a copy constructor for a mutated composite object, if the mutation safe status is not safe, and setting the mutation safe status to true for a mutator node of the mutated composite object.
-
-
10. A method of processing a SET statement, the method comprising:
-
grouping together update entries based upon a same target being updated; generating, by a compiler, a copy of a composite object which is the same target being updated; and using the generated copy as a common target for mutations caused by the update entries of a same group. - View Dependent Claims (11, 12, 13)
-
-
14. A method for processing a SET statement, the method comprising:
-
generating, by a query compiler, a copy (a mutation target) of a common composite object being updated in the statement; transforming an update entry of the form
space="preserve" listing-type="equation">C..f.sub.1. . . f.sub.n =expressioninto a mutation function call
space="preserve" listing-type="equation">f.sub.n (f.sub.n-1 ( . . . (f.sub.1 (C)) . . . ), expression)where C is the mutation target generated by the compiler; and merging all of the mutation function calls for all related update entries together into a nested sequence function invocation, wherein a first argument of the function is returned as a result and a second argument of the function obtains an effect caused by a mutation, to create an accumulated effect for the mutations in the copy of the common composite object.
-
-
15. A method for processing a SET statement, the method comprising:
-
generating, by a query compiler, a copy (a mutation target) of a common composite object being updated in the statement; grouping together update entries in a sequence of nested function invocations, a function invocation for each attribute being updated, wherein a first argument of the function is returned as a result and a second argument of the function obtains an effect caused by a mutation; and setting an indicator associated with a parse tree node of the mutation target to indicate that mutation is safe thereby avoiding a copy function being inserted and creating an accumulated effect for the mutations in the copy of the common composite object.
-
-
16. A system for handling a mutation of a composite object in a database, the system comprising:
-
means for generating a copy of the composite object before the composite object is to be mutated; and means for using the copy by a mutator function in a query language statement. - View Dependent Claims (17, 18)
-
-
19. A system for handling a mutation of a composite object in a database managed by a database management system, the system comprising:
-
means for inserting a copy constructor in a parsed representation of a query language statement to create a copy of the composite object when the composite object is being mutated; means for using the copy by a mutator function in the query language statement; and means for using an original of the composite object for other functions, if any, in the query language statement.
-
-
20. A system for handling a mutation of a composite object in a database managed by a database management system, the system comprising:
-
a query compiler having means for performing a compile-time analysis to determine if a write/write or read/write conflict exists; and means for inserting a minimum number of copy constructors, if the conflict exists, in order to avoid the conflict. - View Dependent Claims (21)
-
-
22. A system for handling a mutation of a composite object in a database managed by a database management system, the system comprising:
-
a query parser having means for setting a mutation safe status for each parse tree node of the query language statement according to the following; a) for each leaf node corresponding to a composite object, setting the mutation safe status to indicate that the node is not safe; b) for each non-leaf node, deriving the mutation safe status from an incoming node and from the function itself; and means for inserting a copy constructor for a mutated composite object, if the mutation safe status is not safe, and means for resetting the mutation safe status to true for a mutator node of the mutated composite object.
-
-
23. A database management system having means for processing a SET statement, the system comprising:
-
means for grouping together update entries based upon a same target being updated; a compiler for generating a copy of a composite object which is the same target being updated; and means for using the generated copy as a common target for mutations caused by the update entries of a same group; and means for setting a mutation safe indicator associated with the common target to true to avoid a copy function being inserted for subsequent mutations. - View Dependent Claims (24)
-
-
25. A program, having computer readable program code means on a computer usable medium, having means for handling a mutation of a composite object in a database, the program comprising:
-
means for causing a generation of a separate copy of each composite object before each time each composite object is to be mutated; and means for causing a use of the separate copy by a mutator function in a query language statement.
-
-
26. A program, having computer readable program code means on a computer usable medium, having means for handling a mutation of a composite object in a database, the program comprising:
-
means for causing an insertion of a copy constructor in a parsed representation of a query language statement to create a copy of the composite object when the composite object is being mutated; means for causing a use of the copy by a mutator function in the query language statement; and means for causing a use of an original of the composite object for other functions in the query language statement.
-
-
27. A program, having computer readable program code means on a computer usable medium, having means for handling a mutation of a composite object in a database, the program comprising:
-
means for carrying out a compile time analysis to determine if a write/write or read/write conflict exists; and means for causing an insertion of a minimum number of copy constructors, if the conflict exists, in order to avoid the conflict.
-
-
28. A program, having computer readable program code means on a computer usable medium, having means for handling a mutation of a composite object in a database, the program comprising:
-
means for causing a generation of a copy of the composite object before the composite object is to be mutated; means for causing a setting of a mutation safe status, during parsing, for each parse tree node of a query language statement wherein a determination as to where to insert the generated copy in a parsing of the query language statement is determined according to the mutation safe status; and means for causing a use of the copy by a mutator function in the query language statement.
-
-
29. A program, having computer readable program code means on a computer usable medium, having means for handling a mutation of a composite object in a database, the program comprising:
-
means for causing a setting of a mutation safe status for each parse tree node of a query language statement according to the following; a) for each leaf node corresponding to a composite object, setting the mutation safe status to indicate that the node is not safe; b) for each non-leaf node, deriving the mutation safe status from an incoming node except that constructors and copy constructors are always safe; and means for causing an insertion of a copy constructor for a mutated composite object, if the mutation safe status is not safe, and causing a setting of the mutation safe status to true for a mutator node of the mutated composite object.
-
-
30. A program, having computer readable program code means on a computer usable medium, having means for processing a SET statement, the program comprising:
-
means for causing a generation of a copy (a mutation target) of a common composite object being updated in the statement; means for transforming an update entry of the form
space="preserve" listing-type="equation">C..f.sub.1. . . f.sub.n =expressioninto a mutation function call
space="preserve" listing-type="equation">f.sub.n (f.sub.n-1 ( . . . (f.sub.1 (C)) . . . ), expression)where C is the mutation target generated by the compiler; and means for merging all of the mutation function calls for all related update entries together into a nested sequence function invocation, wherein a first argument of the function is returned as a result and a second argument of the function obtains an effect caused by a mutation, to create an accumulated effect for the mutations in the copy of the common composite object.
-
-
31. A program, having computer readable program code means on a computer usable medium, having means for processing a SET statement, the program comprising:
-
means for causing a generation of a copy (a mutation target) of a common composite object being updated in the statement; means for causing a grouping together of update entries in a sequence of nested function invocations, a function invocation for each attribute being updated, wherein a first argument of the function is returned as a result and a second argument of the function obtains an effect caused by a mutation; and means for causing a setting of an indicator associated with a parse tree node of the mutation target to indicate that mutation is safe thereby avoiding a copy function being inserted and creating an accumulated effect for the mutations in the copy of the common composite object.
-
Specification