On optimizing an SQL-like nested query

ABSTRACT

SQL is a high-level nonprocedural data language which has received wide recognition in relational databases. One of the most interesting features of SQL is the nesting of query blocks to an arbitrary depth. An SQL-like query nested to an arbitrary depth is shown to be composed of five basic types of nesting. Four of them have not been well understood and more work needs to be done to improve their execution efficiency. Algorithms are developed that transform queries involving these basic types of nesting into semantically equivalent queries that are amenable to efficient processing by existing query-processing subsystems. These algorithms are then combined into a coherent strategy for processing a general nested query of arbitrary complexity.

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	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	BLASGBN, M.W., AND ESWARAN, K.P. On the evaluation of queries in relational data base systems. IBM Res. Rep. RJ1745, IBM Research, San Jose, Calif., April 1976.
	4	BLASGEN, M.W., AND ESWARAN, K.P. Storage and access in relational data bases. IBM Syst. J. 16, 4, 1977, 363-377.
	5	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]
	6	CHAbIBERLIN, D.D., ET AL. SEQUEL2: A unified approach to data definition, manipulation, and control. IBM J. Res. Dev. (Nov. 1976), 560-575.
	7	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]
	8	CODD, E.F. A database sublanguage founded on the relational calculus. In Proc. ACM SIGFI- DET Workshop on Data Description, Access and Control (San Diego, Nov. 11-12), ACM, New York, 1971, pp. 35-68.
	9	CODD, E.F. Further normalization of the data base relational model. In Data Base Systems, Courant Computer Science Symposia, Vol. 6, Prentice-Hall, Englewood Cliffs, N.J., 1971.
	10	CODD, E.F. Relational completeness of data base sublanguages. In Data Base Systems, Courant Computer Science Symposia, Vol. 6, Prentice-Hall, Englewood Cliffs, N.J., 1971.
	11	CZARNIK, B., SCHUSTER, S., AND TSICHRITZIS, D. ZETA: A relational data base management system. In Proc. ACM Pacific Regional Conf. (San Francisco, April 17-18), ACM, New York, 1975, pp. 21-25.
	12	C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	13	EPSTEIN, R. Techniques for processing of aggregates in relational database systems. ERL/UCB Memo M79/8, Electronics Research Laboratory, Univ. California, Berkeley, Feb. 1979.
	14	Y. E. Lien, Design and implementation of a relational database on a minicomputer, Proceedings of the 1977 annual conference, p.16-22, January 1977 [doi>10.1145/800179.810175]
	15	MYLOPOULOS, J., SCHUSTER, S., AND TSICHRITZIS, D. A multi-level relational system. In Proc. 1975 AFIPS Nat. Computer Conf., Vol. 44. AFIPS Press, Arlington, Va., pp. 403-408.
	16	PALERMO, F.P. A data base search problem. IBM Res. Rep. RJ1072, San Jose, Calif., July 1972.
	17	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]
	18	ROTHNIE, J.B. Evaluating inter-entry retrieval expressions in a relational data base management system, in Proc. 1975 AFIPS Nat. Computer Conf., Vol. 44. AFIPS Press, Arlington, Va., pp. 417-423.
	19	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]
	20	John Miles Smith , Philip Yen-Tang Chang, Optimizing the performance of a relational algebra database interface, Communications of the ACM, v.18 n.10, p.568-579, Oct. 1975 [doi>10.1145/361020.361025]
	21	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]
	22	WEELDREYER, J.A., AND FRIESEN, O.D. Multics relational data store: An implementation of a relational data base manager. In Proc. llth Hawaii Int. Conf. Systems Science, 1978, pp. 52-66.
	23	WEiss, H.M. The ORACLE data base management system. Mini-Micro Syst. (Aug. 1980), 111-114.
	24	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]