Won Kim
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.
- 1 ASTRAHAN, M.M., AND CHAMBERLIN, D.D. Implementation of a structured English query language. Comrnun. ACM 18, 10(Oct. I975), 580-588. Google Scholar
Digital Library
- 2 ASTRAHAN, M.M., ET AL. System R: Relational approach to database management. ACM Trans. Database Syst. 1, 2(June 1976), 97-137. Google ScholarDigital Library
- 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.Google Scholar
- 4 BLASGEN, M.W., AND ESWARAN, K.P. Storage and access in relational data bases. IBM Syst. J. 16, 4, 1977, 363-377.Google ScholarDigital Library
- 5 BOYCE, R.F., AND CHAMBERLIN, D.D. SEQUEL: A structured English query language. In Proc. ACM SIGMOD Workshop Data Description, Access and Control (Ann Arbor, Mich., May 1-3), ACM, New York, 1974, pp. 249-264. Google ScholarDigital Library
- 6 CHAbIBERLIN, D.D., ET AL. SEQUEL2: A unified approach to data definition, manipulation, and control. IBM J. Res. Dev. (Nov. 1976), 560-575.Google Scholar
- 7 CODD, E.F. A relational model of data for large shared data banks. Commun. ACM 13, 6(June 1970), 377-387. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 12 DATE, C.J. An Introduction to Database Systems (2nd ed.). Addison-Wesley, Reading, Mass., 1977. Google ScholarDigital Library
- 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.Google Scholar
- 14 LIEN, Y.E. Design and imp|ementation of a relational database on a minicomputer. In Proc. ACM Annual Conf. (Seattle, Oct. 16-19), ACM, New York, 1977, pp. 16-22. Google ScholarDigital Library
- 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.Google Scholar
- 16 PALERMO, F.P. A data base search problem. IBM Res. Rep. RJ1072, San Jose, Calif., July 1972.Google Scholar
- 17 ROTHNIE, J.B. An approach to implementing a relational data base management system. In Proc. A CM SIGMOD Workshop Data Description, Access and Control. (Ann Arbor, Mich., May 1-3), ACM, New York, 1974, pp. 277-294. Google ScholarDigital Library
- 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.Google Scholar
- 19 SELINGER, P.G., ET AL. Access path selection in a relational database system. In Proc. Inter. Conf. Management of Data (ACM) (Boston, Mass., May 1979), 23-34. Google ScholarDigital Library
- 20 SMITH, J.M., AND CHANG, P.Y. Optimizing the performance of a relational algebra database interface. Commun. ACM 18, 10(Oct. 1975), 568-579. Google ScholarDigital Library
- 21 Stonebraker, M., Tong, E., Kreps, P., and Held, G. The design and implementation of INGRES. ACM Trans. Database Syst. 1, 3 (Sept. 1976), 189-222. Google ScholarDigital Library
- 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.Google Scholar
- 23 WEiss, H.M. The ORACLE data base management system. Mini-Micro Syst. (Aug. 1980), 111-114.Google Scholar
- 24 TONG, E., AND YOUSSEFI, K. Decomposition--A strategy for query processing. A CM Trans. Database Syst. 1, 3(Sept. 1976}, 223-241. Google ScholarDigital Library
Index Terms
- On optimizing an SQL-like nested query
Recommendations
SQL query optimization through nested relational algebra
Most research work on optimization of nested queries focuses on aggregate subqueries. In this article, we show that existing approaches are not adequate for nonaggregate subqueries, especially for those having multiple subqueries and certain comparison ...
The use of Hints in SQL-Nested query optimization
The query optimization phase in query processing plays a crucial role in choosing the most efficient strategy for executing a query. In this paper, we study an optimization technique for SQL-Nested queries using Hints. Hints are additional comments that ...
SkyCube-tree based query processing in OLAP skyline cubes
IMCOM '17: Proceedings of the 11th International Conference on Ubiquitous Information Management and CommunicationSkyline Cube (SC) has been proposed as an extension of Data Cube by using the skyline operator. Although both range queries and group-by queries are useful for decision making support, they impose much burdens upon a query processing system. To cope ...
Comments