Global query optimization

ABSTRACT

In some recently proposed extensions to relational database systems as well as in deductive databases, a database system is presented with a collection of queries to process instead of just one. It is an interesting problem then, to come up with algorithms that process these queries together instead of one query at a time. We examine the problem of multiple (global) query optimization in this paper. A hierarchy of algorithms that can be used for global query optimization is exhibited and analyzed. These algorithms range from an arbitrary serial execution without any sharing of common results among the queries to an exhaustive search of all possible ways to process all queries.

REFERENCES

• ASTR76: 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]
• CHAK82: Chakravarthy, U S and Mmker, J, "Processzng d#dtzpte Quemes zn Database Systems ": In Database D#g#neerz#, Vol (1), 1983
• CHAK84: U S Chakravarthy , D H Fishman , J Minker, Semantic query optimization in expert systems and database systems, Proceedings from the first international workshop on Expert database systems, p.659-674, January 1986, Kiawah Island, South Carolina, United States
• CHAK85: Chakravarthy, U S and Mmker,J, "Multzple Query Processzng zn l)eductzve Databases': University of Maryland, Technical Report TR-1554, August 1985
• FINK82: Sheldon Finkelstein, Common expression analysis in database applications, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582400]
• GALL78: Herve Gallaire , Jack Minker, Logic and Data Bases, Perseus Publishing, 1978
• GARE79: Garey, M R and Johnson, D S, "Computers and Intractatnlzt#/: W H Freeman and Co, San Francisco 1979
• GRAN80: Grant, J and Mmker, J, "On Optzmzzzng the Evaluatzon of a Set of E~-presszorcs ': Umvermty of Maryland, Techmcal Report TR-916, July 1980
• GRAN81: Grant, J and Mmker, J, "Optzmzzatzon zn De duc tzve and Conventzonal Relational Database Systems "" In Advances zn Data Base ?heory, vol 1, H Gallalre, J Mmker and J-M Nicolas, Eds, Plenum, New York
• GUTT84: Antonin Guttman, New features for a relational database system to support computer aided design, 1984
• HALL74: Hall, P V, "Common Subexpresszon Identzflcatton zn General Algebraic Systems': Tech Report UKSC 0060, IBM United Kingdom Scientific Centre, November 1974
• HALL76: Hall, P V, "Optzmzzatzon of a Single Relatzonal EcTresston zn a Relatzonal Data B#se System': IBM Journal of Research and Development, (20) 3, May 1976
• IOAN86: ioanmdm, Y, "'Processzng Recurs#on zn Databases", PhD Thesis, University of California, Berkeley (m preparation)
• JARK84a: Matthias Jarke , Jim Clifford , Yannis Vassiliou, An optimizing prolog front-end to a relational query system, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• JARK84b: Jarke, M, "Common Subexpresston Isolatzon zn Ma2tzple Query Optzmzzatzon': In Query Processzng zn Database Systems, W Kim, D Remer and D Batory, Eds, Sprmger-Verlag, New York
• KIM84: Kin# W, "Global 01atzmzzatzon of Relatzonal Quemes A First ,5#ep" In Query Processzng zn Database 2Pystems, W i#m, D Remer and D Batory, Eds, Sprmger-Verlag, New York
• KUNG84: R-M Kung , E Hanson , Y Ioannidis , T Sellis , L Shapiro , M Stonebraker, Heuristic search in database systems, Proceedings from the first international workshop on Expert database systems, p.537-548, January 1986, Kiawah Island, South Carolina, United States
• LARS85: Larson, P and Yang, H, "'Computing Quemes from 1)ertved Relatzons "" Proceedings of the l lth International Conference on Very Large Data Bases, Stockholm, August 1985
• RICH83: Elaine Rich, Artificial intelligence, McGraw-Hill, Inc., New York, NY, 1983
• ROUS82a: Nicholas Roussopoulos, View indexing in relational databases, ACM Transactions on Database Systems (TODS), v.7 n.2, p.258-290, June 1982 [doi>10.1145/319702.319729]
• ROUS82b: Roussopoulos, N, "The Logzcal Access Path Schema of a Database': IEEE Transactions on Software Engineering, (8) 6, November 1982
• RTI84: EQUEL/C User's Guzde, Version 2 1, Relational Technology, Inc, Berkeley, CA, July 1984
• SELI79: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• SELL85a: Timos K. Sellis , Leonard Shapiro, Optimization of extended database query languages, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.424-436, May 1985, Austin, Texas, United States
• SELL85b: Selhs, T, "Optzm#z#ng a Set of Relatzonal #k'presszons ': Manuscmpt, Umverslty of Cahforma, Berkeley, June 1985
• SELL86: Selhs, T, "Optzmzzatzon of Extended Relatzonal Database Systems': PhD Thems, Umverslty of Cahforma, Berkeley (m preparation)
• STON76: 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]
• STON85: Stonebraker, M et al, "The Deszgn of POSTGRES': Umvermty of Cahforma, Berkeley, November 1985 (subrratted for pubhcatlon)
• ULLM82: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• ULLM85: Jeffrey D. Ullman, Implementation of logiclal query languages for databases (abstract only), ACM SIGMOD Record, v.14 n.4, p.444, May 1985
• WONG76: 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]
• ZANI83: Carlo Zaniolo, The database language GEM, Proceedings of the 1983 ACM SIGMOD international conference on Management of data, May 23-26, 1983, San Jose, California

INDEX TERMS

Classification:
  E. Data
  E.5 FILES
      Subjects: Optimization**

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

General Terms:
Algorithms, Performance