Updating derived relations: detecting irrelevant and autonomously computable updates

ABSTRACT

Consider a database containing not only base relations but also stored derived relations (also called materialized or concrete views). When a base relation is updated, it may also be necessary to update some of the derived relations. This paper gives sufficient and necessary conditions for detecting when an update of a base relation cannot affect a derived relation (an irrelevant update), and for detecting when a derived relation can be correctly updated using no data other than the derived relation itself and the given update operation (an autonomously computable update). The class of derived relations considered is restricted to those defined by PSJ-expressions, that is, any relational algebra expressions constructed from an arbitrary number of project, select and join operations (but containing no self-joins). The class of update operations consists of insertions, deletions, and modifications, where the set of tuples to be deleted or modified is specified by a selection condition on attributes of the relation being updated.

REFERENCES

• 1: ADIBA, M. E., AND LINDSAY, B.G. Database snapshots. In Proceedings of the 6th international Conference on Very Large Data Bases (Montreal, 1980), 86-91.
• 2: D. S. Batory, Modeling the storage architectures of commercial database systems, ACM Transactions on Database Systems (TODS), v.10 n.4, p.463-528, Dec. 1985 [doi>10.1145/4879.5392]
• 3: BERNSTEIN, P. A., AND BLAUSTEIN, B.T. A simplification algorithm for integrity assertions and concrete views. In Proceedings COMPSAC 81 (Chicago, 1981), 90-99.
• 4: J. A. Balkeley Perez, Updating materialized database views, University of Waterloo, Waterloo, Ont., Canada, 1987
• 5: José A. Blakeley , Neil Coburn , Per-Åke Larson, Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates, Proceedings of the 12th International Conference on Very Large Data Bases, p.457-466, August 25-28, 1986
• 6: BLAKELEY, J. A., COBURN, N., AND LARSON, P.-/~. Updating derived relations: Detecting irrelevant and autonomously computable updates. Tech. Rep. 235, Computer Science Dept., Indiana Univ., 1987.
• 7: Jose A. Blakeley , Per-Ake Larson , Frank Wm Tompa, Efficiently updating materialized views, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.61-71, May 28-30, 1986, Washington, D.C., United States
• 8: 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]
• 9: Neil Coburn, Updating derived relations, University of Waterloo, Waterloo, Ont., Canada, 1988
• 10: U. Dayal , B. Blaustein , A. Buchmann , U. Chakravarthy , M. Hsu , R. Ledin , D. McCarthy , A. Rosenthal , S. Sarin , M. J. Carey , M. Livny , R. Jauhari, The HiPAC project: combining active databases and timing constraints, ACM SIGMOD Record, v.17 n.1, p.51-70, March, 1988 [doi>10.1145/44203.44208]
• 11: Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
• 12: GARDARIN, G., SIMON, E., AND VERLAINE, L. Querying real time relational data bases. In IEEE-ICC International Conference (Amsterdam, 1984), 757-761.
• 13: 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]
• 14: LARSON, P.-/k., AND YANG, H.Z. Computing queries from derived relations. In Proceedings of the 11th International Conference on Very Large Data Bases (Stockholm, 1985), 259-269.
• 15: Bruce Lindsay , Laura Haas , C. Mohan , Hamid Pirahesh , Paul Wilms, A snapshot differential refresh algorithm, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.53-60, May 28-30, 1986, Washington, D.C., United States
• 16: David Maier, Theory of Relational Databases, Computer Science Pr, 1983
• 17: David Maier , Jeffrey D. Ullman, Fragments of relations, Proceedings of the 1983 ACM SIGMOD international conference on Management of data, May 23-26, 1983, San Jose, California
• 18: ROSENKRANTZ, D. J., AND HUNT, H. B., III. Processing conjunctive predicates and queries. In Proceedings of the 6th International Conference on Very Large Data Bases (Montreal, 1980), 64-72.
• 19: Michael Stonebraker , Jeff Anton , Eric Hanson, Extending a database system with procedures, ACM Transactions on Database Systems (TODS), v.12 n.3, p.350-376, Sept. 1987 [doi>10.1145/27629.27631]
• 20: Hongzhi Yang, Query transformation, 1987
• 21: H. Z. Yang , Per-Åke Larson, Query Transformation for PSJ-Queries, Proceedings of the 13th International Conference on Very Large Data Bases, p.245-254, September 01-04, 1987

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema
      H.2.2 Physical Design
          Subjects: Access methods
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Design, Performance, Theory