Database management system, method and program for supporting the mutation of a composite object without read/write and write/write conflicts

• US 5,857,182 A
• Filed: 01/21/1997
• Issued: 01/05/1999
• Est. Priority Date: 01/21/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rielau, Serge Philippe, Tran, Brian Thinh-Vinh, Lindsay, Bruce Gilbert, Fuh, Gene Y. C., DeMichiel, Linda Gail, Jou, Michelle Mei-Chiou, Mattos, Nelson Mendonca
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US08/786,605
• Time in Patent Office: 714 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 707/6, 707/7, 707/8, 345/342, 395/682, 524/376
• US Class Current: 1/1
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

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.

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.

2. The method of claim 1 wherein the copy of the composite object is made for an innermost mutation if a compile time analysis indicates a write/write or read/write conflict.

3. The method of claim 1 further comprising the step of indicating a mutation safe status for each parse tree node of the query language statement wherein the copy created for the composite object is determined according to the mutation safe status.

5. The method of claim 1 wherein a separate copy is created for every occurrence that any composite object is being mutated.

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.

7. The method of claim 6 wherein the step of performing a compile time analysis further comprises:

accumulating information, for each expression of the query language statement, as to a presence of composite objects, what operations are being performed on each composite object and with respect to which attributes, and whether the operations appear in a same or different expression of the query language statement.

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.

11. The method of claim 10 wherein the step for using further comprises setting a mutation safe indicator associated with the common target to true to avoid a copy function being inserted for subsequent mutations.

12. The method of claim 10 wherein the copy is generated according to the following steps:

a) setting a mutation safe indicator for each parse tree node of the SET statement as follows;

i) for each leaf parse tree node;

1) each read target defaulted to false;

2) each mutated target defaulted to false;

ii) for each non-leaf parse tree node;

1) constructors always true;

2) copy constructors always true;

3) observers inherit from the parse tree node of an observed composite object;

b) wherein the generated copy is generated for a mutated composite object if the mutation safe indicator of the mutated composite object indicated not safe; and

c) setting the mutation safe indicator of the mutator node of the generated copy to safe;

thereby accumulating a plurality of mutated attributes in a same copy of a composite object.

13. The method of claim 10 further comprising generating, for the update entries grouped together, 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.

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 =expression

into 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.

17. The system of claim 16 wherein a separate copy is generated for every occurrence that any composite object is being mutated.

18. The system of claim 16 further comprising a mutation safe status indicator for each parse tree node of the query language statement wherein the copy created for the composite object is determined according to the mutation safe status.

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.

21. The system of claim 20 wherein the query compiler further comprises means for accumulating information, for each expression of a query language statement, as to a presence of composite objects, what operations are being performed on each composite object and with respect to which attributes, and whether the operations appear in a same or different expression of the query language statement.

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.

24. The system of claim 23 further comprising means for generating, for the update entries grouped together, 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.

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 =expression

into 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.