System and method for asynchronous view maintenance

• US 6,546,402 B1
• Filed: 06/05/2000
• Issued: 04/08/2003
• Est. Priority Date: 06/05/2000
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Beyer, Kevin Scott, Lindsay, Bruce Gilbert, Salem, Kenneth Mark, Cochrane, Roberta Jo
• Primary Examiner(s): Mizrahi, Diane D.
• Assistant Examiner(s): MOFIZ, APU M
• Application Number:
  US09/586,809
• Time in Patent Office: 1,037 Days
• Field of Search: 707/1, 707/3, 707/5, 707/8, 707/10, 707/102, 707/203
• US Class Current: 707/625
• CPC Class Codes: G06F 16/2393 Updating materialised views
• CPC Class Codes: G06F 16/24535 of sub-queries or views
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: Y10S 707/954 Relational
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

A method and system for refreshing materialized join views includes asynchronously evaluating changes to the base tables, i.e., evaluating changes for an intended time t_intended at an evaluation time t_eval that is later than the intended time. Changes made to the base table between the intended time t_intended and evaluation time t_eval are recursively compensated for. The results of the evaluating and compensating are then applied to the materialized view to refresh the view.

Claims

1. A computer system, comprising:

at least one general purpose computer executing method acts to refresh a view table, the method acts comprising;

deriving changes to at least one base table accessible to the computer to render at least one delta table, the base table being combinable with other tables to render the view table;

associating at least one record timestamp with at least one record in at least one delta table;

combining at least one delta table with at least one base table to render a combination table;

computing at least one combination timestamp representing the combining act;

using the combination timestamp, computing at least one compensation table; and

combining at least one compensation table with at least one combination table to render a view delta table useful for refreshing the view table.

2. The system of claim 1, wherein the view table is materialized.

3. The system of claim 2, wherein the act of rendering the view delta table accounts for transactions to a time t_target, and the rendering of the view delta table is undertaken at a time t_eval that is later than t_target, such that the view delta table is rendered asynchronously.

4. The system of claim 3, wherein the method acts are repeated by the computer, and wherein the combination timestamp is t_eval and can be dynamically established during each repetition of the method acts, such that changes to the view are propagated using a series of transactions the sizes of which are established by the selection of t_intended for each repetition.

5. The system of claim 4, wherein tuples in the view delta table are timestamped, such that the applying act is undertaken to propagate changes described by view delta table tuples with timestamps up to a time t_highwater with validity.

6. The system of claim 2, wherein the act of deriving changes to at least one base table to render at least one delta table accounts for transactions from a time t_δ

prior to the time t_intended.

7. The system of claim 1, wherein the view table is associated with at least three base tables, and the computer derives changes to the three base tables by accounting for transactions to three respective times t_new¹, t_new², and t_new³, and the times t_new¹, t_new², and t_new³ can be different from each other.

8. The system of claim 1, wherein the act of computing at least one compensation table is undertaken recursively.

9. The system of claim 1, wherein each tuple in a combination table or compensation table is associated with a count, and the count of each tuple is the product of the counts of the tuples from which it was derived.

10. The system of claim 1, wherein each tuple in a combination table or compensation table is associated with a timestamp, and the timestamp of each tuple is the minimum of the timestamps of the tuples from which it was derived.

11. The system of claim 9, wherein the counts of the tuples of a compensation table are conditionally negated before combining the compensation table with the view delta table.

12. The system of claim 1 wherein each combination table and compensation table has a count column and a timestamp column.

13. A computer-implemented method for refreshing a materialized view, comprising the acts of:

evaluating changes for an intended time t_intended to at least one base table associated with the view at an evaluation time t_eval later than the intended time;

recursively compensating for changes made to at least one base table associated with the view between the intended time t_intended and evaluation time t_eval; and

applying the results of the evaluating and compensating acts to the materialized view to refresh the view.

14. The method of claim 13, wherein the view is derived from at least three base tables, and the act of recursively compensating includes compensating a combination table to render a compensation, and then compensating the compensation.

15. The method of claim 14, wherein changes to the three base tables are derived by accounting for transactions to three respective times t_new¹, t_new², and t_new³, and the times t_new¹, t_new², and t_new³ can be different from each other.

16. The method of claim 13, wherein the act of evaluating further comprises:

deriving changes to at least one base table to render at least one delta table, the base table being combinable with other tables to render the view;

associating at least one record timestamp with at least one record in at least one delta table;

combining at least one delta table with at least one base table to render a combination table;

computing at least one combination timestamp representing the combining act;

using the combination timestamp, computing at least one compensation table; and

combining at least one compensation table with the combination table to render a view delta table useful for refreshing the view table.

17. The method of claim 16, wherein the act of rendering the delta table accounts for transactions to a time t_intended, and the rendering of the delta table is undertaken at a time prior to t_eval that is later than t_intended, such that the delta tables are rendered asynchronously.

18. The method of claim 17, wherein t_intended can be dynamically established during each of a number of repetitions of the method acts, such that changes to the view are propagated using a series of transactions the sizes of which are established by the selection of t_intended for each repetition.

19. The method of claim 18, wherein changes to tuples in the view delta table are timestamped, such that the applying act is undertaken to propagate the changes to a time t_highwater with validity.

20. The method of claim 15, wherein the act of deriving changes to at least one base table to render at least one delta table accounts for transactions from a time to prior to the time t_intended.

21. The method of claim 15, wherein each tuple in a combination table or compensation table is associated with a count, and the count of each tuple is the product of the counts of the tuples from which it was derived.

22. The method of claim 21, wherein the counts of the tuples of a compensation table are conditionally negated before combining the compensation table with the view delta table.

23. The method of claim 16, wherein each tuple in a combination table or compensation table is associated with a timestamp, and the timestamp of each tuple is the minimum of the timestamps of the tuples from which it was derived.

24. A computer program device comprising:

a computer program storage device readable by a digital processing apparatus; and

a program on the program storage device and including instructions executable by the digital processing apparatus to incrementally compute changes to a materialized join view which reflect changes to base tables, the program comprising;

computer readable code means for recording updates to a plurality of base tables as they occur;

computer readable code means for, at subsequent times, extracting the updates that occurred to selected base tables over given time intervals;

computer readable code means for combining extracted updates with the base tables in multiple steps to compute changes to the materialized join view;

wherein the means for combining includes;

computer readable code means for evaluating changes for an intended time t_intended to at least one base table associated with the view at an evaluation time t_eval later than the intended time;

computer readable code means for recursively compensating for changes made to the base table between the intended time t_intended and evaluation time t_eval; and

computer readable code means for applying the results of the evaluating and compensating means to the materialized view to refresh the view.

25. The device of claim 24, wherein the view is derived from at least three base tables, and the means for recursively compensating includes means for compensating at least one base table to render a compensation, and then compensating the compensation.

26. The device of claim 25, wherein means for evaluating further comprises:

computer readable code means for deriving changes to at least one base table to render at least one delta table, the base table being combinable with other tables to render the view;

computer readable code means for associating at least one record timestamp with at least one record in at least one delta table;

computer readable code means for combining at least one delta table with at least one base table to render a combination table;

computer readable code means for computing at least one combination timestamp;

computer readable code means for using the combination timestamp to compute at least one compensation table; and

computer readable code means for applying at least one compensation table and at least one combination table to render a view delta table useful for refreshing the view.

27. The device of claim 26, wherein the means for rendering the delta table accounts for transactions to a time t_intended, and the rendering of the delta table is undertaken prior to a time t_eval that is later than t_intended, such that the delta tables are rendered asynchronously.

28. The device of claim 27, wherein t_intended can be dynamically established during each of a number of repetitions, such that changes to the view are propagated using a series of transactions the sizes of which are established by the selection of t_intended for each repetition.

29. The device of claim 26, wherein each tuple in a combination table or compensation table is associated with a count and a timestamp, and the count of each tuple is the product of the counts of the tuples from which it was derived and the timestamp of each tuple is the minimum of the timestamps of the tuples from which it was derived.

30. The device of claim 29, further comprising computer readable code means for selectively negating the counts of the tuples of a compensation table before combining the compensation table with the view delta table.