View indexing in relational databases

ABSTRACT

The design and maintenance of a useful database system require efficient optimization of the logical access paths which demonstrate repetitive usage patterns. Views (classes of queries given by a query model) are an appropriate intermediate logical representation for database. Frequently accessed views of databases need to be supported by indexing to enhance retrieval. This paper investigates the problem of selecting an optimal index set of views and describes an efficient algorithm for this selection.

REFERENCES

• 1: Henry D. Anderson , P. Bruce Berra, Minimum cost selection of secondary indexes for formatted files, ACM Transactions on Database Systems (TODS), v.2 n.1, p.68-90, March 1977 [doi>10.1145/320521.320537]
• 2: M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin , K. P. Eswaran , J. N. Gray , P. P. Griffiths , W. F. King , R. A. Lorie , P. R. McJones , J. W. Mehl , G. R. Putzolu , I. L. Traiger , B. W. Wade , V. Watson, System R: relational approach to database management, ACM Transactions on Database Systems (TODS), v.1 n.2, p.97-137, June 1976 [doi>10.1145/320455.320457]
• 3: Alfonso F. Cárdenas, Analysis and performance of inverted data base structures, Communications of the ACM, v.18 n.5, p.253-263, May 1975 [doi>10.1145/360762.360766]
• 4: CHnNDY, K.M. Models of distributed systems. In Proc. 3rd Int. Conf. Very Large Databases, Tokyo, Japan, Oct. 6-8, ACM, New York, 1977, pp. 105-120.
• 5: CHANG, S.K. AND CHZNG, W.H. Database skeleton and its application to logical database synthesis. IEEE Trans. Softw. Eng. SE-U, 1 (Jan. 1978), 18-30.
• 6: FARLEY, J.H.G. ASP SCHUS~E~t, S.A. Query execution and index selection for relational data bases. Tech. Rep. CSRG-53, Univ. Toronto, Toronto, Ont., Canada, March 1975.
• 7: JACOBS, B.J. External to conceptual mapping construction using database logic, TR-1012, Dep. Computer Science, Univ. of Maryland, College Park, 1981.
• 8: KaRP, R.M. Reducibility among combinatorial problems. In Complexity of Computer Computations, R.E. Miller and J.W. Thatcher, Eds. pp. 85-104. Plenum, New York, 1972.
• 9: KINO, W.F. On the selection of indices for a file. IBM Research Rep. RJ1341, IBM, San Jose, Calif. 1974.
• 10: Salvatore T. March , Dennis G. Severance, A mathematical modeling approach to the automatic selection of database designs, Proceedings of the 1978 ACM SIGMOD international conference on management of data, May 31-June 02, 1978, Austin, Texas [doi>10.1145/509252.509272]
• 11: MYLOPOULOS, J., SCHUSTER, S., A~D TSICHRITZIS, D. A multi-level relational system. In Proc. 1975 Nat. Computer Conf., AFIPS Press, Arlington, Va.
• 12: Nils J. Nilsson, Problem-Solving Methods in Artificial Intelligence, McGraw-Hill Pub. Co., 1971
• 13: Nicholas D. Roussopoulos, A semantic network model of data bases., 1977
• 14: RoussoPouLos, N. CSDL: A language for conceptual schema design. IEEE Trans. Softw. Eng. SE-5, 5 (Sept. 1979), 481-496.
• 14a: RoussoPouLos, N. The logical access path schema of a database. IEEE Trans. Softw. Eng., to appear.
• 15: RoussoPOULOS, N. AND MYLOPOULOS, J. Using semantic networks for data base management. In Proc. Ist Int. Conf. Very Large Data Bases, Framingham, Mass., 1975, pp.144-172.
• 16: Sartaj Sahni, Approximate Algorithms for the 0/1 Knapsack Problem, Journal of the ACM (JACM), v.22 n.1, p.115-124, Jan. 1975 [doi>10.1145/321864.321873]
• 17: Mario Schkolnick, Secondary index optimization, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California [doi>10.1145/500080.500106]
• 18: SCHKOLNICK, M. Physical database design techniques. In Proc. NYU Syrup. Database Design, New York, 1978, pp. 99-109.
• 19: John Miles Smith , Diane C. P. Smith, Database abstractions: aggregation and generalization, ACM Transactions on Database Systems (TODS), v.2 n.2, p.105-133, June 1977 [doi>10.1145/320544.320546]
• 20: Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]

INDEX TERMS

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

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

General Terms:
Algorithms, Performance

Keywords:
index selection