Efficiently updating materialized views

ABSTRACT

Query processing can be sped up by keeping frequently accessed users' views materialized. However, the need to access base relations in response to queries can be avoided only if the materialized view is adequately maintained. We propose a method in which all database updates to base relations are first filtered to remove from consideration those that cannot possibly affect the view. The conditions given for the detection of updates of this type, called irrelevant updates, are necessary and sufficient and are independent of the database state. For the remaining database updates, a differential algorithm can be applied to re-evaluate the view expression. The algorithm proposed exploits the knowledge provided by both the view definition expression and the database update operations.

REFERENCES

• AL80: Adlba, Michel, and Bruce G Lmdsay, "Database Snapshots," Proc oF the 6#h International Conference on Very Large Databases, 1980, Pages 86-91
• ASU79: A. V. Aho , Y. Sagiv , J. D. Ullman, Efficient optimization of a class of relational expressions, ACM Transactions on Database Systems (TODS), v.4 n.4, p.435-454, Dec. 1979 [doi>10.1145/320107.320112]
• BC79: O. Peter Buneman , Eric K. Clemons, Efficiently monitoring relational databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.368-382, Sept. 1979 [doi>10.1145/320083.320099]
• F62: Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
• GSV84: Gardann, G, E Simon, L Verlalne, #Querylng Real Time Relational Data Ba#es," IEEE-IUC International Conference (Amsterdam), May 1984, Pages 757- 761
• HS78: Michael Hammer , Sunil K. Sarin, Efficient monitoring of database assertions, Proceedings of the 1978 ACM SIGMOD international conference on management of data, May 31-June 02, 1978, Austin, Texas [doi>10.1145/509252.509290]
• HT85: Susan Horwitz , Tim Teitelbaum, Relations and attributes: A symbiotic basis for editing environments, Proceedings of the ACM SIGPLAN 85 symposium on Language issues in programming environments, p.93-106, June 25-28, 1985, Seattle, Washington, United States
• K80: Klug, A, "On Inequahty Tableaux," US Technical Report 403, Umverslty of Wlsconsm, Madison, Wl, November 1980
• KP81: Koenig, Shaye, and Robert Patge, #A T#ansformatlonai Framework for the Automatic Control of Derived Data," Proc of the 7th Internatlonal Conference on Very Large Data Bases, 1981, Pages 306- 318
• L85: Lindsay, Bruce G, Personal communlcatlon
• M83: Mater, Davtd, The Theory of Relatmnal Databases, Computer Science Press, 1983
• RH80: Rosenkrantz, Daniel J, and Harry B Hunt III, "Processing Conjunctive Predicates and Queries,# Proc of the 6th Inter. national Conference on Very Large Data Bases, 1980, Pages 64-72
• SI84: Oded Shmueli , Alon Itai, Maintenance of views, ACM SIGMOD Record, v.14 n.2, June 1984
• WY76: Eugene Wong , Karel Youssefi, Decomposition—a strategy for query processing, ACM Transactions on Database Systems (TODS), v.1 n.3, p.223-241, Sept. 1976 [doi>10.1145/320473.320479]

INDEX TERMS

Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Viewing algorithms

General Terms:
Algorithms, Verification