Cost-based maintenance of materialized views

• US 6,026,390 A
• Filed: 07/09/1997
• Issued: 02/15/2000
• Est. Priority Date: 05/29/1996
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.), Columbia University
• Original Assignee: AT&T Corporation (AT&T, Inc.), Columbia University
• Inventors: Srivastava, Divesh, Ross, Kenneth A., Sudarshan, Sundararajarao
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US08/890,194
• Time in Patent Office: 951 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 707/6, 707/7
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2393 Updating materialised views
• 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

Abstract

A method of incrementally maintaining a first materialized view of data in a database, by means of an additional materialized view, first determines whether a cost in time of incrementally maintaining the first materialized view with the additional materialized view is less than the cost of incrementally maintaining the first materialized view without the additional materialized view. The method creates the additional materialized view only if the cost in time is less therewith. Determining whether the cost of employing an additional materialized view is less includes using an expression directed acyclic graph that corresponds to the first materialized view. Another method of determining whether the cost is less includes pruning an expression directed acyclic graph to produce a single expression tree, and using the single expression tree to determine whether the cost is less. Both the expression directed acyclic graph and the single expression tree contain equivalence nodes. One or more possible materialized views are selected by marking the equivalence nodes, and materializing one or more views corresponding to the marked equivalence nodes. One or more possible materialized views are also selected by determining which of the views, if materialized, would result in a lowest cost of incrementally maintaining the first materialized view. The method is also used to reduce the cost in time of maintaining a first materialized view employed to check an integrity constraint of the database.

Claims

1. A method of incrementally maintaining a first materialized view of data in a database, the method employing an additional materialized view to maintain the first materialized view and the method comprising the steps of:

determining whether a first cost of incrementally maintaining the first materialized view with the additional materialized view is less than a second cost of incrementally maintaining the first materialized view without the additional materialized view; and

creating the additional materialized view only if the first cost is less than the second cost.

2. The method set forth in claim 1 wherein the step of determining whether the first cost is less comprises the steps of:

making an expression directed acyclic graph corresponding to a query which produces the first materialized view; and

using the expression directed acyclic graph to determine whether the first cost is less than the second cost.

3. The method set forth in claim 2 wherein the step of using the expression directed acyclic graph to determine whether the first cost is less includes the steps of:

pruning the expression directed acyclic graph to produce a single expression tree corresponding to the query; and

using the single expression tree to determine whether the first cost is less than the second cost.

4. The method set forth in claim 2 wherein the step of making an expression directed acyclic graph comprises the step of making an expression directed acyclic graph containing a plurality of equivalence nodes;

and

the method further comprising the steps of;

marking one or more of the plurality of equivalence nodes; and

selecting the additional materialized view from the marked equivalence nodes.

5. The method set forth in claim 3 wherein the pruning step comprises the step of producing a single expression tree containing a plurality of equivalence nodes;

and

the method further comprising the steps of;

marking one or more of the plurality of equivalence nodes; and

selecting the additional materialized view from the marked equivalence nodes.

6. The method set forth in any of claims 1-3 further including the steps of:

determining which of a plurality of additional materialized views results in a lowest cost of incrementally maintaining the first materialized view; and

creating the additional materialized view which results in the lowest cost.

7. The method set forth in claim 1 further comprising the step of:

employing the first materialized view to check an integrity constraint.

8. The method set forth in claim 2 wherein the step of using the expression directed acyclic graph to determine whether the first cost is less comprises the steps of:

identifying a subdag of the expression directed acyclic graph, the subdag containing a subdag node corresponding to the additional materialized view; and

using the subdag to determine the first cost, the first cost comprising a sum of a cost of computing updates to the subdag node and a cost of performing updates to the subdag node.

9. The method set forth in claim 2 wherein the step of using the expression directed acyclic graph to determine whether the first cost is less comprises the steps of:

selecting an update track in the expression directed acyclic graph, the update track containing a plurality of nodes for propagating an update transaction to the first materialized view; and

using the plurality of nodes for propagating to determine the first cost.

10. The method set forth in claim 9 wherein the step of using the plurality of nodes for propagating to determine the first cost comprises the steps of:

determining a cost of computing updates to the plurality of nodes for propagating; and

determining a cost of performing updates to the plurality of nodes for propagating.

11. The method of claim 9 further comprising the step of determining which of the plurality of nodes for propagating corresponds to an additional materialized view which results in a lowest cost of incrementally maintaining the first materialized view.

12. The method set forth in claim 6 wherein the step of determining which results in a lowest cost comprises the steps of:

determining a third cost of computing updates to the first materialized view with the plurality of additional materialized views;

determining a fourth cost of performing updates to the first materialized view with the plurality of additional materialized views; and

determining which of the plurality of additional materialized views results in a lowest total cost of incrementally maintaining the first materialized view, the lowest total cost comprising a sum of the third cost and the fourth cost.

13. The method set forth in claim 6 further including the steps of:

selecting an articulation node of the expression directed acyclic graph, the expression directed acyclic graph having a plurality of nodes, the plurality of nodes including the articulation node, a plurality of descendant nodes, and a plurality of remaining nodes, wherein the plurality of descendant nodes appear below the articulation node;

identifying a local expression directed acyclic graph comprising the articulation node and the plurality of descendant nodes;

using the local expression directed acyclic graph to determine a local cost of propagating updates to the first materialized view; and

determining the first cost by combining the local cost with a cost of propagating updates via the plurality of remaining codes.

14. A method for repeatedly executing an ad-hoc query in a database, the method employing a materialized view of data to execute the ad-hoc query, the method comprising the steps of:

determining whether a first query cost of repeatedly executing the ad-hoc query with the materialized view is less than a second query cost of repeatedly executing the ad-hoc query without the materialized view; and

creating the materialized view only if the first query cost is less than the second query cost.

15. The method set forth in claim 14 wherein the step of determining whether the first query cost is less comprises the steps of:

making an expression directed acyclic graph corresponding to the ad-hoc query; and

using the expression directed acyclic graph corresponding to the ad-hoc query to determine whether the first query cost is less than the second query cost.

16. The method set forth in claim 15 wherein the step of using the expression directed acyclic graph corresponding to the ad-hoc query includes the steps of:

pruning the expression directed acyclic graph to produce a single expression tree corresponding to the ad-hoc query; and

using the single expression tree corresponding to the ad-hoc query to determine whether the first query cost is less than the second query cost.

17. The method set forth in claim 15 wherein the step of making an expression directed acyclic graph corresponding to the ad-hoc query comprises the step of making an expression directed acyclic graph containing a plurality of equivalence nodes;

and

the method further comprising the steps of;

marking one or more of the plurality of equivalence nodes; and

selecting the materialized view from the marked equivalence nodes.

18. The method set forth in claim 16 wherein the pruning step comprises the step of producing a single expression tree containing a plurality of equivalence nodes;

and

the method further comprising the steps of;

marking one or more of the plurality of equivalence nodes; and

selecting the materialized view from the marked equivalence nodes.

19. The method set forth in any of claims 14-16 further including the steps of:

determining which of a plurality of materialized views results in a lowest cost of repeatedly executing the ad-hoc query; and

creating the materialized view which results in the lowest cost.

20. The method set forth in claim 15 wherein the step of using the expression directed acyclic graph corresponding to the ad-hoc query comprises the steps of:

identifying a subdag of the expression directed acyclic graph, the subdag containing a subdag node corresponding to the materialized view; and

using the subdag to determine the first query cost, the first query cost comprising a sum of a cost of computing updates to the subdag node and a cost of performing updates to the subdag node.

21. The method set forth in claim 15 wherein the step of using the expression directed acyclic graph corresponding to the ad-hoc query comprises the steps of:

selecting an update track in the expression directed acyclic graph, the update track containing a plurality of propagation nodes for updating the ad-hoc query; and

using the plurality of propagation nodes to determine the first query cost.

22. The method set forth in claim 21 wherein the step of using the plurality of propagation nodes to determine the first query cost comprises the steps of:

determining a cost of computing updates to the plurality of propagation nodes; and

determining a cost of performing updates to the plurality of propagation nodes.

23. The method of claim 21 further comprising the step of determining which of the plurality of propagation nodes corresponds to a materialized view which results in a lowest cost of repeatedly executing the ad-hoc query.

24. The method set forth in claim 19 wherein the step of determining which results in a lowest cost comprises the steps of:

determining a cost of computing updates to the ad-hoc query with the plurality of materialized views;

determining a cost of performing updates to the ad-hoc query with the plurality of materialized views;

determining which of the plurality of materialized views results in a lowest total cost of repeatedly executing the ad-hoc query, the lowest total cost comprising a sum of the cost of computing updates and the cost of performing updates.

25. The method set forth in claim 19 further including the steps of:

selecting an articulation node of the expression directed acyclic graph corresponding to the ad-hoc query, the expression directed acyclic graph having a plurality of nodes, the plurality of nodes including the articulation node, a plurality of descendant nodes, and a plurality of remaining nodes, wherein the plurality of descendant nodes appear below the articulation node;

identifying a second expression directed acyclic graph comprising the articulation node and the plurality of descendant nodes;

using the second expression directed acyclic graph to determine a local cost of propagating updates to the ad-hoc query; and

determining the first query cost by combining the local cost with a cost of propagating updates via the plurality of remaining nodes.