Incremental maintenance of aggregated and join summary tables

• US 6,983,291 B1
• Filed: 05/16/2000
• Issued: 01/03/2006
• Est. Priority Date: 05/21/1999
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Pirahesh, Mir Hamid, Cochrane, Roberta Jo, Sidle, Richard Sefton
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): DODDS, HAROLD E
• Application Number:
  US09/571,554
• Time in Patent Office: 2,058 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-205, 707/500, 707/509
• US Class Current: 707/625
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination

Abstract

A method, apparatus, and article of manufacture for incrementally maintaining a summary table derived from a plurality of base tables in a database stored on the computer. A plurality of modifications are applied to the base tables, and the applied modifications are then propagated to the summary table. The propagated modifications include an associated tag column containing a tag value, and the tag value indicates per row of the propagated modifications how many rows are to be added to or deleted from the summary table.

Claims

1. A method of incrementally maintaining a summary table derived from a plurality of base tables in a database stored on the computer, the method comprising:

(a) applying a plurality of modifications to the base tables; and

(b) propagating the applied modifications to the summary table, wherein the propagated modifications include an associated tag column containing a tag value, and the tag value indicates how many rows are to be added or deleted from the summary table.

2. The method of claim 1, wherein the modifications comprise deltas.

3. The method of claim 1, wherein the tag value indicates per row of the propagated modifications how many rows are to be added to or deleted from the summary table.

4. The method of claim 3, wherein a tag value equal to −

n indicates that n rows are to be deleted from the summary table, and a tag value equal to +n indicates that n rows are to be inserted into the summary table.

5. The method of claim 4, further comprising initializing the tag column according to one or more of the following rules:

if the modification is an inserted row, creating a propagated row with values from the inserted row and the tag value equal to +1,

if the modification is a deleted row, creating a propagated row with values from the deleted row and the tag value equal to −

1, and

if the modification is an updated row, decomposing the updated row into two propagated rows, wherein a first propagated row contains old values from the updated row and the tag value equal to −

1, and a second propagated row contains new values from the updated row and the tag value equal to +1.

6. The method of claim 5, wherein the base tables are referred to as Ti, the deleted rows are referred to as D(Ti), the inserted rows are referred to as I(Ti), and i=(1, 2, . . . , N).

7. The method of claim 6, wherein each of the base tables may appear multiple times in a set {T1, T2, . . . , TN}.

8. The method of claim 6, wherein a set of all updated rows for a base table Tj is a union of D(Tj) and I(Tj).

9. The method of claim 8, wherein the set results front a plurality of modifications to the base table.

10. The method of claim 9, wherein the set comprises a delta for the base table.

11. The method of claim 10, wherein the propagating step comprises deriving an output delta from an input delta for one or more relational operations used in generating the summary table.

12. The method of claim 11, further comprising propagating the tag values across the relational operation.

13. The method of claim 12, wherein the relational operation comprises a selection operation and the propagating step comprises:

applying zero ox more predicates to one or mote columns of the input delta to select the rows that will appear in the output delta; and

deriving the tag column of the output delta directly from the input delta tag column, wherein the tag values are not affected by the selection operation.

14. The method of claim 12 wherein the relational operation comprises a projection operation and the propagating step comprises:

selecting one or more columns that are required by the projection operation from the input delta to produce the output delta, and

deriving the output delta tag column directly from the input delta tag column without change to the tag values.

15. The method of claim 12, wherein the relational operation comprises a union all operation and the propagating step comprises:

pruning operands with no input delta from the union all operation,

if there is exactly one operand remaining (N=1) after pruning, then converting the union all operation to a selection operation without predicates, applying zero or more predicates to one or more columns of the input delta to select the rows that will appear in the output delta, and deriving the tag column of the output delta directly from the input delta tag column, wherein the tag values are not affected by the selection operation; and

if there is more than one operand remaining (N>

1) after pruning, then deriving the output delta tag column by unioning together the tag columns of the input deltas, wherein the tag values are not changed by the union all operation.

16. The method of claim 15, wherein the pruning step comprises pruning operands that reference to a table function.

17. The method of claim 15, wherein the pruning step comprises pruning operands that reference a base table that has not been updated.

18. The method of claim 12, wherein the relational operation comprises an inner join operation and the propagating step comprises:

generating one or mote join terms for the inner join operation,

adding an output delta tag column to each of the generated join terms, and

injecting a union operation that includes the generated join terms as its operands into the propagating step, and then applying the following steps;

pruning operands with no input delta from the union operation,

if there is exactly one operand remaining (N=1) after pruning, then converting the union operation to a selection operation without predicates, applying zero or more predicates to one or more columns of the input delta to select the rows that will appear in the output delta, and deriving the tag column of the output delta directly from the input delta tag column, wherein the tag values are not affected by the selection operation; and

if there is more than one operand remaining (N>

1) after pruning, then deriving the output delta tag column with the following rule;

for a given join term that contains K<

=M deltas with corresponding input tag columns input-tag₁, input-tag₂, . . . , input-tag_K;

output delta tag=input-tag₁*input-tag₂* . . . *input-tag_K*(−

1)**(K+1).

19. The method of claim 18, further comprising using repeatable read to access base table references in at least one join expression, unless there is an N-to-1 relationship from the join expression to the base table reference.

20. The method of claim 18, further comprising using cursor stability to access base table references in at least one join expression, when there is an N-to-1 relationship from the join expression to the base table reference.

21. The method of claim 1, further comprising computing a result set from at least one of the base tables and materializing the result set in the summary table.

22. The method of claim 21, wherein the result set is an aggregated result set.

23. The method of claim 21, wherein the result set is generated using join operations in the absence or presence of aggregation operations.

24. The method of claim 21, wherein the result set is generated using union all operations with or without join operations in the presence of aggregation operations.

25. The method of claim 1, wherein the summary table is a self-maintainable materialized view and the propagating step further comprises maintaining the summary table in an incremental manner by processing only a set of updated rows without reference to the base tables.

26. The method of claim 1, wherein the summary table satisfies one or more of the following criteria:

(1) the summary table is defined as an aggregate query,

(2) a FROM clause for the aggregate query contains only inner joins,

(3) a FROM clause for the aggregate query contains only a single table reference,

(4) the aggregate query does not contain a HAVING clause,

(5) aggregate functions in a SELECT list of the query are self-maintainable with respect to insertions and deletions, and

(6) a SELECT DISTINCT operation is not allowed.

27. The method of claim 1, wherein the summary table has a single table reference in a FROM clause and thus is self-maintainable.

28. The method of claim 1, wherein the summary table that contains ner joins in a FROM clause and is not self-maintainable.

29. The method of claim 1, wherein the propagated modifications are performed on after images of the modified base tables.

30. A computer-implemented apparatus for incrementally maintaining a summary table derived from a plurality of base tables in a database stored on the computer, comprising:

(a) logic, performed by the computer, for;

(1) applying a plurality of modifications to the base tables; and

(2) propagating the applied modifications to the summary table, wherein the propagated modifications include an associated tag column containing a tag value, and the tag value indicates how many rows are to be added or deleted from the summary table.

31. The apparatus of claim 30, wherein the modifications comprise deltas.

32. The apparatus of claim 30, wherein the tag value indicates per row of the propagated modifications how many rows are to be added to or deleted from the summary table.

33. The apparatus of claim 32, wherein a tag value equal to −

n indicates that n rows are to be deleted from the summary table, and a tag value equal to +n indicates that n rows are to be inserted into the summary table.

34. The apparatus of claim 33, further comprising logic for initializing the tag column according to one or more of the following rules:

if the modification is an inserted row, creating a propagated row with values from the inserted tow and the tag value equal to +1,

if the modification is a deleted row, creating a propagated row with values from the deleted row and the tag value equal to −

1, and

if the modification is an updated row, decomposing the updated row into two propagated rows, wherein a first propagated row contains old values from the updated tow and the tag value equal to −

1, and a second propagated row contains new values from the updated row and the tag value equal to +1.

35. The apparatus of claim 34, wherein the base tables are referred to as Ti, the deleted rows are referred to as D(Ti), the inserted rows are referred to as I(Ti), and i=(1, 2, . . . , N).

36. The apparatus of claim 35, wherein each of the base tables may appear multiple times in a set {T1, T2, . . . , TN}.

37. The apparatus of claim 35, wherein a set of all updated rows for a base table Tj is a union of D(Tj) and I(Tj).

38. The apparatus of claim 37, wherein the set results from a plurality of modifications to the base table.

39. The apparatus of claim 37, wherein the set comprises a delta for the base table.

40. The apparatus of claim 39, wherein the logic for propagating comprises logic for deriving an output delta from an input delta for one or more relational operations used in generating the summary table.

41. The apparatus of claim 40, further comprising logic for propagating the tag values across the relational operation.

42. The apparatus of claim 41, wherein the relational operation comprises a selection operation and the logic for propagating comprises logic for:

applying zero or more predicates to one or more columns of the input delta to select the rows that will appear in the output delta; and

deriving the tag column of the output delta directly from the input delta tag column, wherein the tag values are not affected by the selection operation.

43. The apparatus of claim 41, wherein the relational operation comprises a projection operation and the logic for propagating comprises logic for:

selecting one or more columns that are required by the projection operation from the input delta to produce the output delta, and

deriving the output delta tag column directly from the input delta tag column without change to the tag values.

44. The apparatus of claim 41, wherein the relational operation comprises a union all operation and the logic for propagating comprises logic for:

pruning operands with no input delta from the union all operation,

if there is exactly one operand remaining (N=1) after pruning, then converting the union all operation to a selection operation without predicates, applying zero or mote predicates to one or more columns of the input delta to select the tows that will appear in the output delta, and deriving the tag column of the output delta directly from the input delta tag column, wherein the rag values are not affected by the selection operation; and

if there is more than one operand remaining (N>

1) after pruning, then deriving the output delta tag column by unioning together the tag columns of the input deltas, wherein the tag values are not changed by the union all operation.

45. The apparatus of claim 44, wherein the logic for pruning comprises logic for pruning operands that reference to a table function.

46. The apparatus of claim 44, wherein the logic for pruning comprises logic for pruning operands that reference a base table that has not been updated.

47. The apparatus of claim 41, wherein the relational operation comprises an inner join operation and the logic for propagating comprises logic for:

generating one or more join terms for the inner join operation,

adding an output delta tag column to each of the generated join terms, and

injecting a union operation tag includes the generated join terms as its operands into the propagating step, and then applying the following steps;

pruning operands with no input delta from the union operation,

if there is exactly one operand remaining (N=1) after pruning, then converting the union operation to a selection operation without predicates, applying zero or more predicates to one or more columns of the input delta to select the rows that will appear in the output delta, and deriving the tag column of the output delta directly from the input delta tag column, wherein the tag values are not affected by the selection operation; and

if there is mote than one operand remaining (N>

1) after pruning, then deriving the output delta tag column with the following rule;

for a given join term that contains K<

=M deltas with corresponding input tag columns input-tag₁, input-tag₂, . . . , input-tag_K;

output delta tag=input-tag₁*input-tag₂* . . . *input-tag_K*(−

1)**(K+1).

48. The apparatus of claim 47, further comprising logic for using repeatable read to access base table references in at least one join expression, unless there is an N-to-1 relationship from the join expression to the base table reference.

49. The apparatus of claim 47, further comprising logic for using cursor stability to access base table references in at least one join expression, when there is an N-to-1 relationship from the join expression to the base table reference.

50. The apparatus of claim 30, further comprising logic for computing a result set from at least one of the base tables and materializing the result set in the summary table.

51. The apparatus of claim 50, wherein the result set is an aggregated result set.

52. The apparatus of claim 50, wherein the result set is generated using join operations in the absence or presence of aggregation operations.

53. The apparatus of claim 50, wherein the result set is generated using union all operations with or without join operations in the presence of aggregation operations.

54. The apparatus of claim 30, wherein the summary table is a self-maintainable materialized view and the logic for propagating further comprises logic for maintaining the summary table in an incremental manner by processing only a set of updated rows without reference to the base tables.

55. The apparatus of claim 30, wherein the summary table satisfies one or more of the following criteria:

(1) the summary table is defied as an aggregate query,

(2) a FROM clause for the aggregate query contains only inner joins,

(3) a FROM clause for the aggregate query contains only a single table reference,

(4) the aggregate query does not contain a HAVING clause,

(5) aggregate functions in a SECT list of the query are self-maintainable with respect to insertions and deletions, and

(6) a SELECT DISTINCT operation is not allowed.

56. The apparatus of claim 30, wherein the summary table has a single table reference in a FROM clause and thus is self-maintainable.

57. The apparatus of claim 30, wherein the summary table that contains inner joins in a FROM clause and is nor self-maintainable.

58. The apparatus of claim 30, wherein the propagated modifications are performed on after images of the modified base tables.

59. An article of manufacture embodying logic for performing a method of incrementally maintaining a summary table derived from a plurality of base tables in a database stored on the computer, the method comprising:

(a) applying a plurality of modifications to the base tables; and

(b) propagating the applied modifications to the summary table, wherein the propagated modifications include an associated tag column contain a tag value, and the tag value indicates how many rows are to be added or deleted from the summary table.

60. The article of manufacture of claim 59, wherein the modifications comprise deltas.

61. The article of manufacture of claim 59, wherein the tag value indicates per row of the propagated modifications how many tows are to be added to or deleted from the summary table.

62. The article of manufacture of claim 61, wherein a tag value equal to −

n indicates that n rows are to be deleted from the summary table, and a tag value equal to +n indicates that n rows are to be inserted into the summary table.

63. The article of manufacture of claim 62, further comprising initializing the tag column according to one or more of the following rules:

if the modification is an inserted row, creating a propagated row with values from the inserted row and the tag value equal to +1,

if the modification is a deleted row, creating a propagated row with values from the deleted row and the tag value equal to −

1, and

if the modification is an updated row, decomposing the updated row into two propagated rows, wherein a first propagated row contains old values from the updated tow and the tag value equal to −

1, and a second propagated row contains new values from the updated row and the tag value equal to +1.

64. The article of manufacture of claim 63, wherein the base tables are referred to as Ti, the deleted rows are referred to as D(Ti), the inserted rows are referred to as I(Ti), and i=(1, 2, . . . , N).

65. The article of manufacture of claim 64, wherein each of the base tables may appear multiple times in a set {T1, T2, . . . , TN}.

66. The article of manufacture of claim 64, wherein a set of all updated rows for a base table Tj is a union of D(Tj) and I(Tj).

67. The article of manufacture of claim 66, wherein the set results from a plurality of modifications to the base table.

68. The article of manufacture of claim 66, wherein the set comprises a delta for the base table.

69. The article of manufacture of claim 68, wherein the propagating step comprises deriving an output delta from an input delta for one or more relationship operations used in generating the summary table.

70. The article of manufacture of claim 69, further comprising propagating the tag values across the relational operation.

71. The article of manufacture of claim 70, wherein the relational operation comprises a selection operation and the propagating step comprises:

applying zero or more predicates to one or more columns of the input delta to select the rows that will appear in the output delta; and

deriving the tag column of the output delta directly from the input delta tag column, wherein the tag values are not affected by the selection operation.

72. The article of manufacture of claim 70, wherein the relational operation comprises a projection operation and the propagating step comprises;

selecting one or more columns that are required by the projection operation from the input delta to produce the output delta, and

deriving the output delta tag column directly from the input delta tag column without change to the tag values.

73. The article of manufacture of claim 70, wherein the relational operation comprises a union all operation and the propagating step comprises:

pruning operands with no input delta from the union all operation,

if there is exactly one operand remaining (N=1) after pruning, then converting the union all operation to a selection operation without predicates, applying zero or more predicates to one or more columns of the input delta to select the rows that will appear in the output delta, and deriving the tag column of the output delta directly from the input delta tag column, wherein the tag values are not affected by the selection operation; and

if there is more than one operand remaining (N>

1) after pruning, then deriving the output delta tag column by unioning together the tag columns of the input deltas, wherein the tag values are not changed by the union all operation.

74. The article of manufacture of claim 73, wherein the pruning step comprises pruning operands that reference to a table function.

75. The article of manufacture of claim 73, wherein the pruning step comprises pruning operands that reference a base table that has not been updated.

76. The article of manufacture of claim 70, wherein the relational operation

comprises an inner join operation and the propagating step comprises:

generating one or more join terms for the inner join operation,

adding an output delta tag column to each of the generated join terms, and

injecting a union operation that includes the generated join terms as its operands into the propagating step, and then applying the following steps;

pruning operands with no input delta from the union operation,

if there is exactly one operand remaining (N=1) after pruning, then converting the union operation to a selection operation without predicates, applying zero or more predicates to one or more columns of the input delta to select the rows that will appear in the output delta, and deriving the tag column of the output delta directly from the input delta tag column, wherein the tag values are not affected by the selection operation; and

if there is more than one operand remaining (N>

1) after pruning, then deriving the output delta tag column with the following rule;

for a given join term that contains K<

=M deltas with corresponding input tag columns input-tag₁, input-tag₂, . . . , input-tag_K;

out delta tag=input-tag₁*input-tag₂* . . . *input-tag_K*(−

1)**(+1).

77. The article of manufacture of claim 76, further comprising using repeatable read to access base table references in at least one join expression, unless there is an N-to-1 relationship from the join expression to the base table reference.

78. The article of manufacture of claim 76, further comprising using cursor stability to access base table references in at least one join expression, when there is an N-to-1 relationship from die join expression to the base table reference.

79. The article of manufacture of claim 59, further comprising computing a result set from at least one of the base tables and materializing the result set in the summary table.

80. The article of manufacture of claim 79, wherein the result set is an aggregated result set.

81. The article of manufacture of claim 79, wherein the result set is generated using join operations in the absence or presence of aggregation operations.

82. The article of manufacture of claim 79, wherein the result set is generated using union all operations with or without join operations in the presence of aggregation operations.

83. The article of manufacture of claim 59, wherein the summary table is a self-maintainable materialized view and the propagating step further comprises maintaining the summary table in an incremental manner by processing only a set of updated rows without reference to the base tables.

84. The article of manufacture of claim 59, wherein the summary table satisfies one or more of the following criteria:

(1) the summary table is defined as an aggregate query,

(2) a FROM clause for the aggregate query contains only inner joins,

(3) a FROM clause for the aggregate query contains only a single table reference,

(4) the aggregate query does not contain a HAVING clause,

(5) aggregate functions in a SELECT list of the query are self-maintainable with respect to insertions and deletions, and

(6) a SELECT DISTINCT operation is not allowed.

85. The article of manufacture of claim 59, wherein the summary table has a single table reference in a FROM clause and thus is self-maintainable.

86. The article of manufacture of claim 59, wherein the summary table that contains inner joins in a FROM clause and is not self-maintainable.

87. The article of manufacture of claim 59, wherein the propagated modifications are performed on after images of the modified base tables.