Optimizing the performance of a relational algebra database interface

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimizing the performance of a relational algebra database interface

Full text

Pdf (1.14 MB)

Source

Communications of the ACM archive
Volume 18 , Issue 10 (October 1975) table of contents

Pages: 568 - 579

Year of Publication: 1975

ISSN:0001-0782

Authors

John Miles Smith	Univ. of Utah, Salt Lake City
Philip Yen-Tang Chang	Univ. of Utah, Salt Lake City

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 16, Downloads (12 Months): 63, Citation Count: 81

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/361020.361025 What is a DOI?

ABSTRACT

An approach for implementing a “smart” interface to support a relational view of data is proposed. The basic idea is to employ automatic programming techniques so that the interface analyzes and efficiently refines the high level query specification supplied by the user. A relational algebra interface, called SQUIRAL, which was designed using this approach, is described in detail. SQUIRAL seeks to minimize query response time and space utilization by: (1) performing global query optimization, (2) exploiting disjoint and pipelined concurrency, (3) coordinating sort orders in temporary relations, (4) employing directory analysis, and (5) maintaining locality in page references. Algorithms for implementing the operators of E. F. Codd's relational algebra are presented, and a methodology for composing them to optimize the performance of a particular user query is described.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	M. M. Astrahan , D. D. Chamberlin, Implementation of a structured English query language, Communications of the ACM, v.18 n.10, p.580-588, Oct. 1975 [doi>10.1145/361020.361215]
	2	Bjorner, D., Codd, E.F., Deckert, K.L., and Traiger, I.L. The Gamma-0 n-ary relational data base interface: Specifications of objects and operations. Res. Rep. RJI200, IBM Research Laboratory, San Jose, Calif., April 1973.
	3	Donald D. Chamberlin , Raymond F. Boyce, SEQUEL: A structured English query language, Proceedings of the 1974 ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control, p.249-264, May 01-03, 1974, Ann Arbor, Michigan [doi>10.1145/800296.811515]
	4	Chang, P.Y. A design for a relational data base system. U. of Utah Tech. Rep.
	5	E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
	6	Codd, E.F. Relational completeness of data base sublanguages. In Courant Computer Science Symposia 6: Data Base Systems, Prentice-Hall, Englewood Cliffs, N.J., May 1971, pp. 65-98.
	7	Lorie, R.A., and Symonds, A.J. A relational access method for interactive applications. In Courant Computer Science Symposia 6: Data Base Systems, Prentice-Hall, Englewood Cliffs, N.J., May 1971, pp. 99-124.
	8	Lorie, R.A. XRM--an extended (n-ary) relational memory. Tech. Rep. 320-2096, IBM Scientific Center, Cambridge, Mass., Jan. 1964.
	9	James B. Rothnie, Jr., An approach to implementing a relational data management system, Proceedings of the 1974 ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control, p.277-294, May 01-03, 1974, Ann Arbor, Michigan [doi>10.1145/800296.811517]

CITED BY 81

	Paul J. Sadowski , S. A. Schuster, Exploiting parallelism in a Relational Associative Processor, Proceedings of the fourth workshop on Computer architecture for non-numeric processing, p.99-109, August 01-04, 1978, Blue Mountain Lake, New York, United States
	Chyuan Shiun Lin , Diane C. P. Smith , John Miles Smith, The design of a rotating associative memory for relational database applications, ACM Transactions on Database Systems (TODS), v.1 n.1, p.53-65, March 1976
	Haran Boral , David J. DeWitt, Processor allocation strategies for multiprocessor database machines, ACM Transactions on Database Systems (TODS), v.6 n.2, p.227-254, June 1981
	Matthias Jarke , Jurgen Koch, Query Optimization in Database Systems, ACM Computing Surveys (CSUR), v.16 n.2, p.111-152, June 1984
	N. Derrett , M.-C. Shan, Rule-based query optimization in IRIS, Proceedings of the 17th conference on ACM Annual Computer Science Conference, p.78-86, February 21-23, 1989, Louisville, Kentucky
	Ann S. Michaels , Benjamin Mittman , C. Robert Carlson, A Comparison of the Relational and CODASYL Approaches to Data-Base Management, ACM Computing Surveys (CSUR), v.8 n.1, p.125-151, March 1976
	Won Kim, Relational Database Systemsr, ACM Computing Surveys (CSUR), v.11 n.3, p.187-211, Sept. 1979
	Francois Bry, Towards an efficient evaluation of general queries: quantifier and disjunction processing revisited, ACM SIGMOD Record, v.18 n.2, p.193-204, June 1989
	Won Kim, On optimizing an SQL-like nested query, ACM Transactions on Database Systems (TODS), v.7 n.3, p.443-469, Sept. 1982
	Philip A. Bernstein , Dah-Ming W. Chiu, Using Semi-Joins to Solve Relational Queries, Journal of the ACM (JACM), v.28 n.1, p.25-40, Jan. 1981
	Yehoshua Sagiv , Mihalis Yannakakis, Equivalences Among Relational Expressions with the Union and Difference Operators, Journal of the ACM (JACM), v.27 n.4, p.633-655, Oct. 1980
	Ted M. Sparr, A language for a scientific and engineering database system, Proceedings of the 19th conference on Design automation, p.865-871, January 1982
	Bharat Bhasker , Csaba J. Egyhazy , Konstantinos P. Triantis, The architecture of a heterogeneous distributed database management system: the distributed access view integrated database (DAVID), Proceedings of the 1992 ACM annual conference on Communications, p.173-179, March 03-05, 1992, Kansas City, Missouri, United States
	S. Ceri , G. Pelagatti, Correctness of query execution strategies in distributed databases, ACM Transactions on Database Systems (TODS), v.8 n.4, p.577-607, Dec. 1983
	Goetz Graefe , Richard L. Cole, Fast algorithms for universal quantification in large databases, ACM Transactions on Database Systems (TODS), v.20 n.2, p.187-236, June 1995
	Peter Buneman , Robert E. Frankel , Rishiyur Nikhil, An implementation technique for database query languages, ACM Transactions on Database Systems (TODS), v.7 n.2, p.164-186, June 1982
	S. Bing Yao , David DeJong, Evaluation of database access paths, Proceedings of the 1978 ACM SIGMOD international conference on management of data, May 31-June 02, 1978, Austin, Texas
	Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993
	M. Negri , G. Pelagatti , L. Sbattella, Formal semantics of SQL queries, ACM Transactions on Database Systems (TODS), v.16 n.3, p.513-534, Sept. 1991
	J. Slonim , E. A. Unger , P. S. Fisher, Data base management system environments present and future, ACM SIGSMALL Newsletter, v.5 n.2, p.75-83, April 1979
	Bogdan Czejdo , Marek> Rusinkiewioz, Query transformation in an instructional database management system, ACM SIGCSE Bulletin, v.16 n.1, p.217-223, February 1984
	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
	M. Muralikrishna , David J. DeWitt, Optimization of multiple-relation multiple-disjunct queries, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.263-275, March 1988, Austin, Texas, United States
	Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States
	Ryohei Nakano, Translation with optimization from relational calculus to relational algebra having aggregate functions, ACM Transactions on Database Systems (TODS), v.15 n.4, p.518-557, Dec. 1990
	S. Bing Yao, Optimization of query evaluation algorithms, ACM Transactions on Database Systems (TODS), v.4 n.2, p.133-155, June 1979
	E. Babb, Joined normal form: a storage encoding for relational databasess, ACM Transactions on Database Systems (TODS), v.7 n.4, p.588-614, Dec. 1982
	Stanley Y. W. Su , Herman Lam , Der Her Lo, Transformation of data traversals and operations in application programs to account for semantic changes of databases, ACM Transactions on Database Systems (TODS), v.6 n.2, p.255-294, June 1981
	Philip Y. Chang, Parallel processing and data driven implementation of a relational data base system, Proceedings of the annual conference, p.314-318, October 20-22, 1976, Houston, Texas, United States
	Edwin McKenzie , Richard Snodgrass, Extending the relational algebra to support transaction time, ACM SIGMOD Record, v.16 n.3, p.467-478, Dec. 1987
	Richard Snodgrass, A relational approach to monitoring complex systems, ACM Transactions on Computer Systems (TOCS), v.6 n.2, p.157-195, May 1988
	L. Edwin McKenzie, Jr. , Richard Thomas Snodgrass, Evaluation of relational algebras incorporating the time dimension in databases, ACM Computing Surveys (CSUR), v.23 n.4, p.501-543, Dec. 1991
	Kyu-Young Whang , Ravi Krishnamurthy, Query optimization in a memory-resident domain relational calculus database system, ACM Transactions on Database Systems (TODS), v.15 n.1, p.67-95, March 1990
	Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas
	K. Seo , A. Minematsu , H. Aiso , N. Kamibayashi, A look-ahead data staging architecture for relational data base machines, Proceedings of the 8th annual symposium on Computer Architecture, p.389-406, May 12-14, 1981, Minneapolis, Minnesota, United States
	Goetz Graefe , David J. DeWitt, The EXODUS optimizer generator, ACM SIGMOD Record, v.16 n.3, p.160-172, Dec. 1987
	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
	M. Negri , G. Pelagatti, Distributive join: a new algorithm for joining relations, ACM Transactions on Database Systems (TODS), v.16 n.4, p.655-669, Dec. 1991
	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
	Matthias Jarke , Jürgen Koch, Range nesting: a fast method to evaluate quantified queries, ACM SIGMOD Record, v.13 n.4, May 1983
	Won Kim, A new way to compute the product and join of relations, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, May 14-16, 1980, Santa Monica, California
	G. Pelagatti , F. A. Schreiber, Evaluation of transmission requirements in distributed database access, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts
	Lars Bækgaard , Leo Mark, Incremental Computation of Set Difference Views, IEEE Transactions on Knowledge and Data Engineering, v.9 n.2, p.251-261, March 1997
	Paul J. Sadowski , S. A. Schuster, Exploiting parallelism in a Relational Associative Processor, ACM SIGMOD Record, v.10 n.1, August 1978
	K. P. Mikkilineni , S. Y. W. Su, An Evaluation of Relational Join Algorithms in a Pipelined Query Processing Environment, IEEE Transactions on Software Engineering, v.14 n.6, p.838-848, June 1988
	Bharat Bhasker , Csaba J. Egyhazy , Konstantinos P. Triantis, Non-parametric estimation techniques in support of query decomposition strategies for heterogeneous distributed database management systems, Proceedings of the 30th annual Southeast regional conference, April 08-10, 1992, Raleigh, North Carolina
	Shashi K. Gadia , Sunil S. Nair, Algebraic Identities and Query Optimization in a Parametric Model for Relational Temporal Databases, IEEE Transactions on Knowledge and Data Engineering, v.10 n.5, p.793-807, September 1998
	Mario Jino , Jane W. S. Liu, Intelligent magnetic bubble memories, Proceedings of the 5th annual symposium on Computer architecture, p.166-174, April 03-05, 1978
	Joseph D. Brownsmith, A simulation model of the MICRONET computer system during join processing, Proceedings of the 14th annual symposium on Simulation, p.1-16, March 17-20, 1981, Tampa, Florida, United States
	Timo Niemi , Kalervo Järvelin, Prolog-Based Meta-rules for Relational Database Representation and Manipulation, IEEE Transactions on Software Engineering, v.17 n.8, p.762-788, August 1991
	Antonio L. Furtado , Larry Kerschberg, An algebra of quotient relations, Proceedings of the 1977 ACM SIGMOD international conference on Management of data, August 03-05, 1977, Toronto, Ontario, Canada
	L. M. Haas , W. Chang , G. M. Lohman , J. McPherson , P. F. Wilms , G. Lapis , B. Lindsay , H. Pirahesh , M. J. Carey , E. Shekita, Starburst Mid-Flight: As the Dust Clears, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.143-160, March 1990
	K. P. Mikkilineni , Y. C. Chow , S. Y. W. Su, Petri-Net-Based Modeling and Evaluation of Pipelined Processing of Concurrent Database Queries, IEEE Transactions on Software Engineering, v.14 n.11, p.1656-1667, November 1988
	Ralf Rantzau , Leonard D. Shapiro , Bernhard Mitschang , Quan Wang, Algorithms and applications for universal quantification in relational databases, Information Systems, v.28 n.1-2, p.3-32, 01 March 2003
	Paolo Ciaccia , Maria Rita Scalas, Optimization Strategies for Relational Queries, IEEE Transactions on Software Engineering, v.15 n.10, p.1217-1235, October 1989
	Lars Baekgaard , Leo Mark, Incremental computation of nested relational query expressions, ACM Transactions on Database Systems (TODS), v.20 n.2, p.111-148, June 1995
	Haran Boral , David J. DeWitt, Design considerations for data-flow database machines, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, May 14-16, 1980, Santa Monica, California
	Christian S. Jensen , Leo Mark , Nick Roussopoulos , Timos Sellis, Using differential techniques to efficiently support transaction time, The VLDB Journal — The International Journal on Very Large Data Bases, v.2 n.1, p.75-116, January 1993
	Lars Bækgaard , Leo Mark, Incremental Computation of Time-Varying Query Expressions, IEEE Transactions on Knowledge and Data Engineering, v.7 n.4, p.583-590, August 1995
	Won Kim , Daniel Gajski , David J. Kuck, A parallel pipelined relational query processor, ACM Transactions on Database Systems (TODS), v.9 n.2, p.214-235, June 1984
	Hongjun Lu , Michael J. Carey, Some experimental results on distributed join algorithms in a local network, Proceedings of the 11th international conference on Very Large Data Bases, p.292-304, August 21-23, 1985, Stockholm, Sweden
	Kazuhiro Satoh , Masashi Tsuchida , Fumio Nakamura , Kazuhiko Oomachi, Local and global query optimization mechanisms for relational databases, Proceedings of the 11th international conference on Very Large Data Bases, p.405-417, August 21-23, 1985, Stockholm, Sweden
	Yehoshua Sagiv , Mihalis Yannakakis, Equivalence among relational expressions with the union and difference operation, Proceedings of the fourth international conference on Very Large Data Bases, p.535-548, September 13-15, 1978, West Berlin, Germany
	Robert Demolombe, Estimation of the number of tuples satisfying a query expressed in predicate calculus language, Proceedings of the sixth international conference on Very Large Data Bases, p.55-63, October 01-03, 1980, Montreal, Quebec, Canada
	Michel E. Adiba , Jean-Claude Chupin , Robert Demolombe , Georges Gardarin , Jean Le Bihan, Issues in distributed data base management systems: a technical overview, Proceedings of the fourth international conference on Very Large Data Bases, p.89-110, September 13-15, 1978, West Berlin, Germany
	Stanley Y. W. Su , Stefan Lupkiewicz , Chang-jung Lee , Der Her Lo , Keith L. Doty, MICRONET: a microcomputer network system for managing distributed relational databases, Proceedings of the fourth international conference on Very Large Data Bases, p.288-298, September 13-15, 1978, West Berlin, Germany
	Kyu-Young Whang , Gio Wiederhold , Daniel Sagalowicz, Separability - an approach to physical data base design, Proceedings of the seventh international conference on Very Large Data Bases, p.320-332, September 09-11, 1981, Cannes, France
	Akifumi Makinouchi , Masayoshi Tezuka , Hajime Kitakami , S. Adachi, The optimization strategy for query evaluation in RDB/V1, Proceedings of the seventh international conference on Very Large Data Bases, p.518-529, September 09-11, 1981, Cannes, France
	Sylvia L. Osborn, Towards a universal relation interface, Proceedings of the fifth international conference on Very Large Data Bases, p.52-60, October 03-05, 1979, Rio de Janeiro, Brazil
	T. H. Merrett , Ekow J. Otoo, Distribution models of relations, Proceedings of the fifth international conference on Very Large Data Bases, p.418-425, October 03-05, 1979, Rio de Janeiro, Brazil
	David K. Hsiao , Stuart E. Madnick, Database machine architecture in the context of information technology evolution, Proceedings of the third international conference on Very large data bases, p.63-84, October 06-08, 1977, Tokyo, Japan
	Michael Stonebraker , Lawrence A. Rowe, Observations on data manipulation languages and their embedding in general purpose programming languages, Proceedings of the third international conference on Very large data bases, p.128-143, October 06-08, 1977, Tokyo, Japan
	Theo Härder, A scan-driven sort facility for a relational database system, Proceedings of the third international conference on Very large data bases, p.236-244, October 06-08, 1977, Tokyo, Japan
	Arnon Rosenthal , David S. Reiner, Extending the Algebraic Framework of Query Processing to Handle Outerjoins, Proceedings of the 10th International Conference on Very Large Data Bases, p.334-343, August 27-31, 1984
	Shashi Shekhar , Jaideep Srivastava , Soumitra Dutta, A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization, Proceedings of the 14th International Conference on Very Large Data Bases, p.457-467, August 29-September 01, 1988
	Alexander Brodsky , Joxan Jaffar , Michael J. Maher, Toward Practical Constraint Databases, Proceedings of the 19th International Conference on Very Large Data Bases, p.567-580, August 24-27, 1993
	Alexander Brodsky , Joxan Jaffar , Michael J. Maher, Toward Practical Query Evaluation for Constraint Databases, Constraints, v.2 n.3-4, p.279-304, 1997
	Stephen Todd, PRTV, an efficient implementation for large relational data bases, Proceedings of the 1st International Conference on Very Large Data Bases, September 22-24, 1975, Framingham, Massachusetts
	Shurug Al-Khalifa , Bin Liu , H. V. Jagadish, Evaluating Universal Quantification in XML, IEEE Transactions on Knowledge and Data Engineering, v.19 n.11, p.1494-1507, November 2007
	Bogdan Czejdo , Marek Rusinkiewicz, REQUEST: a testbed relational database management system for instructional and research purposes, Proceedings of the July 9-12, 1984, national computer conference and exposition, July 09-12, 1984, Las Vegas, Nevada
	Noriyuki Kamibayashi , Kazuo Seo, Spirit-III: an advanced relational database machine introducing a novel data-staging architecture with Tuple Stream Filters to preprocess relational algebra, Proceedings of the June 7-10, 1982, national computer conference, June 07-10, 1982, Houston, Texas