article

Free Access

Query Optimization in Database Systems

Authors:
Matthias Jarke

Graduate School of Business Administration, New York University, New York, New York

Graduate School of Business Administration, New York University, New York, New York
View Profile

,
Jurgen Koch

Fachbereich Informatik, Johann Wolfgang Goethe-Universität, 6000 Frankfurt 1, West Germany

Fachbereich Informatik, Johann Wolfgang Goethe-Universität, 6000 Frankfurt 1, West Germany
View Profile

Authors Info & Claims

ACM Computing Surveys Volume 16 Issue 2pp 111–152https://doi.org/10.1145/356924.356928

Published:01 June 1984Publication History

ACM Computing Surveys

References

AnD, A. V., BEERI, C., AND ULLMAN, J. D. 1979a. The theory of joins in relational databases. ACM Trar~g. Database Syst. 4, 3 (Sept.), 297-314. Google Scholar
AHO, A. V., SAC, IV, Y., AND ULLMAN, J. D. 1979b. Efficient optimization of a class of reIational expressions. ACM Trans. Database Syst. 4, 4 (Dec.), 435-454. Google ScholarDigital Library
AHO, A. V., SAC, lV, Y., AND ULLMAN, J. D. 1979c. Equivalences among relational expressions. SIAM J. Comput. 8, 2, 218-246.Google ScholarDigital Library
ANDLER, S., DING, I., ESWARAN, K., HAUSER, C., K{M, W., MEHL, J., AND WILLIAMS, R. 1982. System D: A distributed system for availability. In Proceedings of the 8th International Conference on Very Large Data Bases (Mexico City). VLDB Endowment, Saratoga, Calif., pp. 33-44. Google Scholar
APERS, P. M. G., HEVNER, A. R., AND YAO, S. B. 1983. Optimization algorithms for distributed queries. {EEE Trans. So{tw. Eng. SE-9, 1, 57-68.Google Scholar
ASTRAHAN, M. M., AND CHAMBERLIN, D. D. 1975. Implementation of a structured English query language. Commun. ACM 18, 10 (Oct.), 580-588. Google ScholarDigital Library
ASTRAHAN, M. M., AND GHOSH, S. P. 1974. A search path selection algorithm for the Data Independent Accessing Model (DIAM). In Proceedings o/ the A CM-SIGMOD Workshop on Data Description, Access and Control (Ann Arbor, Mich., May 1-3). ACM, New York, pp. 367-388. Google Scholar
ASTRAHAN, ML M., SCHKOLNWK, M., AND K{M, W. 1980. Performance of the System R access path selection algorithm. In Information Processing 80. Elsevier North-Holland, New York, pp. 487-491.Google Scholar
BANCILHON, F., RICSARO, P., AND SCHOLL, M. 1982. On line processing of compacted relations. In Proceedings of the 8th International Conference on Very Large Data Bases (Mexico City). VLDB Endowment, Saratoga, Calif., pp. 263-269. Google Scholar
BANERJEE, J., AND HSIAO, D. K. 1979. DBC--A database computer for very large databases. IEEE Trans. Comput. C-28, 6, 414-429.Google ScholarDigital Library
BATORY, D. S. 1982. Index selection. In Principles of Database Design, S. B. Yao, Ed. Springer, New York.Google Scholar
BAYER, R., AND MCCREIGHT, E. 1972. Organization and maintenance of large ordered indexes. Acta Inf. t, 173-189.Google Scholar
BAYER, R., ELHAROT, K., KIESSLING, W., AND KIL- tAR, D. 1984. Verteilte Datenbanksysteme. Inf. Spektrum 7, 1, 1-19.Google Scholar
BENTLEY, J. L., AND FRIEDMAN, J. H. 1979. Data structures for range searching. ACM Comput. Surv. 11, 4 (Dec.), 397-409. Google ScholarDigital Library
BrRNAOAT, P. 1983. Decomposition et ~valuation de questions dans une machine base de donn$es relationnelles. Th~se IlIme cycle, D~partment d'Informatique, Universit~ de Paris VI, Paris, France.Google Scholar
BERNSTr~IN, P. A., AND CHIU, D. M. W. 1981. Using semi-joins to solve relational queries. J. ACM 28, 1 (Jan.), 25-40. Google Scholar
BERNSTEIN, P. A., AND GOODMAN, N. 1981a. The power of natural semijoins. SIAM J. Comput. 10, 4, 751-771.Google ScholarDigital Library
BERNSTE{N, P. A., AND GOODMAN, N. 1981b. The power of inequality semijoins. Inf. Syst. 6, 4, 255- 265.Google ScholarCross Ref
BERNSTEIN, P. A., AND GOODMAN, N. 1981c. Concurrency control in distributed database systems. ACM Comput. Surv. 13, 2 (June), 185-221. Google ScholarDigital Library
BERNSTEIN, P. A., BLAUSTEIN, B. T., AND CLARKE, E. M. 1980. Fast maintenance of semantic integrity assertions using redundant aggregate data. In Proceedings of the 6th International Conference on Very Large Data Bases (Montreal, Oct. 1-3). IEEE, New York, pp. 126-136.Google Scholar
BERNSTEIN, P. A., GOODMAN, N., WONG, E., REEVE, C. L., AND RownNm, J. B., JR. 1981. Query processing in a system for distributed databases (SDD-1). ACM Trans. Database Syst. 6, 4 (Dec.), 602-625. Google ScholarDigital Library
BEaaA, B., AND OLIVER, E. 1979. The role of associative array processors in database machine architectures. IEEE Comput. 12, 3, 53-61.Google ScholarDigital Library
BITTON, D., BORAL, H., DEWiT~r, D., AND WILKIN- SON, W. K. 1983. Parallel algorithms for the execution of relational database operations. ACM Trans. Database Syst. 8, 3 (Sept.), 324-353. Google ScholarDigital Library
BLASC, EN, M. W., AND ESWARAN, K. P. 1976. On the evaluation of queries in a relational data base system. IBM Res. Rep. RJ 1745, IBM Research Laboratories, San Jose, Calif.Google Scholar
BLASGEN, M. W., AND ESWARAN, K. P. 1977. Storage and access in relational databases. IBM Syst. J. 16, 363-377.Google ScholarDigital Library
BOLOUR, A. 1981. Optimal retrieval for small range queries. SIAM J. Comput. 10, 4, 721-741.Google ScholarCross Ref
BREITBART, Y., AND REITER, A. 1975. Algorithms for fast evaluation of Boolean expressions. Acta Inf. 4, 107-116.Google ScholarDigital Library
BRODIE, M., MYLOPOULOS, J., AND SCHMIDT, J. W., Eds. 1984. On Conceptual Modelling. Perspectides from Artificial Intelligence, Databases, and Programming Languages. Springer, New York.Google Scholar
BUNEMAN, P. 1979. The problem of multiple paths in a database schema. In Proceedings of the 5th International Conference on Very Large Data Bases (Rio de Janeiro, Oct. 3-5). IEEE, New York, pp. 368-372.Google Scholar
CARDENAS, A. F. 1975. Analysis and performance of inverted data base structures. Commun. ACM 18, 5 (May), 253-263. Google ScholarDigital Library
CARLIS, J. V., MARCH, S. T., AND DICKSON, G. W. 1981. Physical database design: A DSS approach. In Proceedings of the 2nd International Conference on Information Systems (Boston, Mass.). ACM, New York, pp. 153-172.Google Scholar
CARLSON, C. R., AND KAPLAN, R. S. 1976. A generalized access path model and its application to a relational data base system, in Proceedings of the A CM-SIGMOD International Conference on Management of Data (Washington, D.C., June 2- 4). ACM, New York, pp. 143-154. Google Scholar
CER}, S., AND PELAGATTI, G. 1982. Allocation of operations in distributed database access. IEEE Trans. Comput. C-31, 2, 119-128.Google ScholarDigital Library
CHAMBERLIN, D. D., ASTRAHAN, M. M., FaNC, W. F., Loam, R. A., MeaL, J. W., PRICE, T. G., SCHKOLNICK, M., SELINCER, P. G., SLUTZ, D. R., WAOE, B. W., AND YOST, R. A. 1981. Support for repetitive transactions and ad hoc queries in System R. A CM Trans. Database Syst. 6, 1 (Mar.), 70-94. Google ScholarDigital Library
CHAN, A., AND NIAMIR, B. 1982. On estimating cost of accessing records in blocked database organizations. Comput. J. 25, 3, 368-374.Google ScholarCross Ref
CHAN, A., DAYAL, U., FOX, $., GOODMAN, N., RIES, D. D., AND SKEEN, D. 1983. Overview of an Ada compatible distributed database manager. In SIGMOD 83, Proceedings of the Annual Meeting (San Jose, Calif., May 23-26). ACM, New York, pp. 228-237. Google Scholar
CHANDRA, A. K., AND HAREL, D. 1982a. Structure and complexity of relational queries. J. Comput. Syst. Sci. 25, 99-128.Google ScholarCross Ref
CHANORA, A. K., AND HAREL, D. 1982b. Horn clauses and the fixpoint query hierarchy. In Proceedings of the A CM Symposium on Principles of Database Systems (Los Angeles, Calif., Mar. 29- 31). ACM, New York, pp. 158-163. Google Scholar
CHANDRA, A. K., AND MERLIN, P. M. 1977. Optimal implementation of conjunctive queries in relational data bases. In Proceedings of the 9th Annual A CM Symposium on Theory of Computation (Boulder, Colo., May 24). ACM, New York, pp. 77-90. Google Scholar
CHANC,, C. L. 1978. DEDUCE 2: Further investigations of deduction in relational databases. In Logic and Databases, H. Gallaire and J. Minker, Eds. Plenum, New York, pp. 210-236.Google Scholar
CHAt~G, C. L. 1979. On evaluation of queries containing derived relations in a relational data base. IBM Res. Rep. RJ2667, IBM Research Laboratories, San Jose, Calif.Google Scholar
CHANG, J.-M. 1982. A heuristic approach to distributed query processing. In Proceedings o{ the 8th International Conference on Very Large Data Bases (Mexico City). VLDB Endowment, Saratoga, Calif., pp. 54-61. Google Scholar
CnEN, P. P. S., AND AKOKA, J. 1980. Optimal design of distributed information systems. IEEE Trans. Comput. C-29, 12, 1068-1080.Google Scholar
CHESNAm, A., GELENSE, E., ^NO MITRANI, I. 1983. On the modeling of parallel access to shared data. Commun. ACM 26, 3 (Mar.), 196-202. Google Scholar
CHEUNG, T.-Y. 1982a. A method for equijoin queries in distributed relations} databases. IEEE Trans. Comput. 6'-31, 8, 746-751. Google ScholarDigital Library
CU~UNG, T.-Y. 1982b. Estimating block accesses and number of records in file management. Commun. ACM 25, 7 (July), 484-487. Google Scholar
CHIu, D. M., AND HO, Y. C. 1980. A methodology for interpreting tree queries into optima} semijoin expressions. In Proceedings of the A CM-- SIGMOD International Conference on Management of Data (Santa Monica, CaliL, May 14-16). ACM, New York, pp. 169-178. Google Scholar
Cmu, D. M., BERNSTEIN, P. A., AND HO, Y. C. 1981. Optimizing chain queries in a distributed database system. Tech. Rep. TR-01-81, Computer Science Dept., Harvard University, Cambridge, Mass.Google Scholar
CHRISTODOULAKIS, S. 1981. Estimating selectivities in data bases. Tech. Rep. CSRG-136, Computer Science Dept., University of Toronto, Toronto, Canada.Google Scholar
CHRISTODOULAKI8, S. 1983. Estimating block transfers and join sizes. In SIGMOD 83, Proceedings o{ the Annual Meeting (San Jose, Calif., May 23- 26). ACM, New York. pp. 40-54. Google Scholar
CHU, W. W., AND HURLEY, P. 1982. Optimal query processing for distributed database systems. IEEE Trans. Comput. C-3I, 9, 835-850.Google ScholarDigital Library
CLAUSRN, S. E. 1980. Optimizing the evaluation of calculus expressions in a relational database system. Inf. Syst. 5, 1, 41-54.Google ScholarCross Ref
Cooo, E. F. 1971. A database sublanguage founded on the relational calculus. In Proceedings of the A CM-SIGFIDET Workshop, Data Description, Access, and Control (San Diego, Calif., Nov. 11- 12). ACM, New York, pp. 35-68.Google Scholar
Cooo, E. F. 1972. Relational completeness of data base sublanguages. In Courant Computer Science Symposia No. 6: Data Base Systems. Prentice- Hall, New York, pp. 67-101.Google Scholar
DA~;I~.LS, D. 1982. Query compilation in a distributed database system. IBM Res. Rep. RJ3423, IBM Research Laboratories, San Jose, Calif.Google Scholar
DANIELB, D., SELINGER, S., HAAS, L., LINDSAY, B., MOHAN, J., WALKER, A., AND WILM$, P. 1982. An introduction to distributed query compilation in R*. In Proceedings of the 2nd Symposium on Distributed Databases (Berlin, FRG). Elsevier North-Holland, New York.Google Scholar
DAvis, H. W., AND WINSLOW, L. E. 1982. Computational power in query languages. SIAM j. Comput. 11, 3, 547-554.Google Scholar
Davis, L. S., aND KONIg, T. L. 1982. Pattern databases. In Data Base Design Techniques II, S. B. Yao and T. L. Kunii, F_As. Springer, New York, pp. 357-399. Google Scholar
DAYAL, U. 1983a. Evaluating queries with quantitiers: A horticultural approach. In Proceedings of the ACM Symposium on Principles of Database Systems (Atlanta, Ga.). ACM, New York, pp. 125-136. Google Scholar
DAYAL, U. 1983b. Processing queries over generalization hierarchies in a multi-database system. In Proceedings of the 9th International Conference on Very Large Data Bases (Florence, Italy). VLDB Endowment, Saratoga, Calif., pp. 342-353. Google Scholar
DAYAL, U., AND GOODMAN, N. 1982. Query optimization for CODASYL database systems. In Proceedings o/ the A CM-SIGMOD {nternational Conference on Management of Data (Orlando, Fla., June 2-4). ACM, New York, pp. 138-150. Google Scholar
DAYAL, U., GOODMAN, N., LANDERS, T. A., OLSON, K., SMiTh, J. M., aND YEDWAS, L. 1981. Local query optimization in Multibase--A system for heterogeneous distributed databases. Tech. Rep. CCA-81-11, Computer Corporation of America, Cambridge, Mass.Google Scholar
DEMOLOMBE, R. 1980. Estimation of the number of tuples satisfying a query expressed in predicate calculus language. In Proceedings o/the 6th Conference on Very Large Data Bases (Montreal, Oct. 1-3). IEEE, New York, pp. 55-63.Google Scholar
Dv. WITT, D. J. 1979. Query execution in DIRECT. In Proceedings of the A CM-SIGMOD International Conference on Management of Data (Boston, Mass., May 30-June 1). ACM, New York, pp. 13-22. Google Scholar
DOWNEY, P. J., Sr. Tm, R., AND TAItJAN, R. E. 1980. Variations on the common subexpression problem. J. ACM 27, 4 (Oct.), 758~771. Google ScholarDigital Library
EG~ERS, S. J., AND SHOSUANI, A. 1980. Efficient access of compressed data. In Proceedings of the 6th International Conference on Very Large Data Bases (Montreal, Oct. 1-3). IEEE, New York, pp. 205-211.Google Scholar
EPSTEIN, R., AND STONEBRAKER, M. 1980. Analysis of distributed data base processing strategies. In Proceedings of the 6th International Conference on Very Large Data Bases (Montreal, Oct. 1-3). IEEE, New York, pp. 92-101.Google Scholar
EPSTEIN, R., STONEBRAKER, M., AND WONG, E. 1978. Distributed query processing in a relational data base system, in Proceedings of the A CM-SIGMOD International Conference on Management of Data (Austin, Tex., May 31-.June 2). ACM, New York, pp. 169-180. Google Scholar
ESCUUER, C., AND CLORiEUX, A. M. 1979. The SIR- IUS-DELTA distributed DBMS. In Proceedings of the International Conference on Entity-Reintionship Approach, P. Chen, Ed. Elsevier North- Holland, New York, pp. 543-551. Google Scholar
ESWARAN, K. P., GRAY, J. N., Loam, R. A., AND TRAIGER, I. L. 1976. The notions of consistency and predicate locks in a database system. Commun. ACM 19, 11 (Nov.), 624-633. Google ScholarDigital Library
FINKr. LSTEIN, S. 1982. Common expression analysis in database applications. In Proceedings of the A CM-SIGMOD International Conference on Management of Data (Orlando, Fla., June 2-4). ACM, New York, pp. 235-245. Google Scholar
FORKER, H. J. 1982. Algebraical and operational methods for the optimization of query processing in distributed relational database management systems. In Proceedings of the 2nd International Symposium on Distributed Databases (Berlin, FRG). Elsevier North-Holland, New York, pp. 39-59.Google Scholar
GARDARIN, G., VALDURIEZ, P., AND VIEMONT, Y. 1984. Predicate trees: An approach to optimize relational query operations. In Proceedings of the IEEE COMPDEC Conference (Los Angeles, Calif.). IEEE, New York. Google Scholar
GAWSH, B., AND SEC, EV, A. 1982. Query optimization in distributed computer systems. In Management of Distributed Data Processing, J. Akoka, Ed. Elsevier North.Holland, New York, pp. 233-252.Google Scholar
GAriSH, B., AND SEGEV, A. 1983. Set query optimization in horizontally partitioned distributed databases. Working Paper QM8304, Graduate School of Management, University of Rochester, Rochester, N.Y.Google Scholar
GELENBE, E., AND GARDY, }{}). 1982. The size of projections of relations satisfying a functional dependency. In Proceedings of the 8th international Conference on Very Large Data Bases (Mexico City). VLDB Endowment, Saratoga, Calif., pp. 325-333. Google Scholar
GILLES, J. H., AND SCHUSTER, S. A. 1975. Query execution and index selection for relational data bases. Tech. Rep. CSRG~53, Computer Science Dept., University of Toronto, Toronto, Ontario.Google Scholar
GOODMAN, N., AND SHMUELI, O. 1980. Nonreducible database states for cyclic queries. Tech. Rep. TR-15-SO, Computer Science Dept., Harvard University, Cambridge, Mass.Google Scholar
GOODMAN, N., AND SHMUELI, O. 1982. Tree queries: A simple class of relational queries. A CM Trans. Database Syst. 7, 4 (Dec.), 653-677. Google ScholarDigital Library
GOTLmB, L. R. 1975. Computing joins of relations. In Proceedings of the ACM-SIGMOD International Conference on Management of Data (San Jose, Calif., May 14-16). ACM, New York, pp. 55-63. Google Scholar
GOUDA, U. G., AND DAYAL, U, 1981. Optimal semijoin schedules for query processing in local distributed database systems. In Proceedings of the A CM-SIGMOD International Conference on Management of Data (Ann Arbor, Mich., Apr. 29- May 1). ACM, New York, pp. 164-175. Google Scholar
GRANT, J., AND MINKER, J. 1981. Optimization in deductive and conventional relational database systems. In Advances in Database Theory, H. Gallaire, J. Minker, and J.-M. Nicolas, Eds. Plenum, New York, pp. 195-234.Google Scholar
GRAY, P. M. D. 1981. Use of automatic programming and simulation to facilitate operations on CO- DASYL databases. In Database, M. P~ Atkinson, Ed. Pergamon Infotech, London, pp. 315-369.Google Scholar
GaAY, P. M. D. 1984. Implementing the join operation on CODASYL DBMS. In Databases: Role and Structure, P. M. Stocker, Ed. Cambridge University Press, Cambridge, England.Google Scholar
G~tIEs, D. 1971. Compiler Construction for Digital Computers. Wiley, New York. Google Scholar
GRIFFETH, N. D. 1978. Nonprocedural query processing for databases with access paths. In Proceedings of the ACM-SfGMOD International Conference on Management of Data (Austin, Tex., May 31-June 2). ACM, New York, pp. 160-168. Google Scholar
GRIrFITHS, P. G., AND WADE, B. W. 1976. An authorization mechanism for a relational database system. ACM Trans. Database Syst. 1, 3 (Sept.), 242-255. Google Scholar
GR)SnMAN, R. 1978. The simplification of retrieval requests generated by question-answering systems. In Proceedings of the 4th International Conference on Very Large Data Bases (West Berlin, FRG, Sept. 13-15). IEEE, New York, pp. 400- 406.Google Scholar
GUDES, E., AND REITER, A. 1973. On evaluating Boolean expressions. Softw. Pract. Exper. 3, 345- 350.Google ScholarDigital Library
HALL, P. A. V. 1974. Common subexpression identification in general algebraic systems. Tech. Rep. UKSC 0060, IBM UK Scientific Center, Peterlee, England.Google Scholar
HALL, P. A. V. 1976. Optimization of single expressions in a relational data base system. IBM J. Res. Devel. 20, 3, 244-257.Google ScholarDigital Library
HAMMER, M., AND NIAMIR, B. 1979. A heuristic approachto attribute partitioning. In Proceedings of the A CM-SIGMOD International Conference on Management of Data (Boston, Mass., May 30- June 1). ACM, New York, pp. 93-101. Google Scholar
HAMMER, M., A~O ZOONm, S. B., JR. 1980. Knowledge-based query processing. In Proceedings of the 6th International Conference on Very Large Data Bases (Montreal, Oct. 1-3). IEEE, New York, pp. 137-147.Google Scholar
HANANJ, M. Z. 1977. An optimal evaluation of Boolean expressions in an online query system. Commun. ACM 20, 5 (May), 344-347. Google Scholar
HAWTHORN, P, 1982. Microprocessor assisted tuple access, decompression, and assembly for statistical database systems. In Proceedings of the 8th International Conference on Very Large Data Bases (Mexico City). VLDB Endowment, Saratoga, Calif., pp. 223-233. Google Scholar
HENSCHEN, L. J., ANO NAQV~, S. A. 1984. On compiling queries in recursive first-order databases. J. ACM 31, 1 (Jan.), 47-85. Google ScholarDigital Library
HEVNER, A. R. 1979. The optimization of query processing on distributed database systems. Ph.D. dissertation, Computer Science Dept., Purdue University, West Lafayette, Ind. Google Scholar
HEVNER, A. R., A~o YAO, S. B. 1979. Query processing on a distributed database. IEEE Trans. So{tw. Eng. SE-5, 3, 177-187.Google ScholarDigital Library
HEVNER, A. R., AND ~AO, S. B. 1981. Transaction optimization on a distributed database system. Tech. Rep. HR-81-257, Honeywell Corporate Computer Center, Bloomington, Minn.Google Scholar
HSlAO, D. K. 1979. Database machines are coming, database machines are coming. IEEE Comput. 12, 3, 7-9.Google ScholarDigital Library
IBM COFtrORATIO~ 1966. Introduction to IBM direct-access storage devices and organization methods. Programming manual GC 20-1649-06,Google Scholar
IEEE 1982. Special issue on query optimization. IEEE Databa~se Eng. 5, 3 (Sept.).Google Scholar
JARKE, M. 1984, Common subexpression isolation in multiple query optimization. In Query Processing in Database Systems, W. Kim, D. Reiner, and D. Batory, Eds. Springer, New York.Google Scholar
JARKE, M., AND Koch, J, 1983. Range nesting: A fast method to evaluate quantified queries. In SiGMOD 83, Proceedings of Annual Meeting (San Jose, Calif., May 23-26). ACM, New York, pp. 196-206. Google Scholar
JARKE, M., ANO SCHMmT, J. W. 1981. Evaluation of first-order relational expressions. Tech. Rep. 78, Fachbereich Informatik, Universitaet Hamburg, Hamburg, FRG.Google Scholar
JARKE, M., AND SCHMIDT, J. W. 1982. Query processing strategies in the PASCAL/R relational database management system. In Proceedings of the A CM-SIGMOD International Conference on Management of Data (Orlando, Fla., June 2-4). ACM, New York, pp. 256-264. Google Scholar
JAaKE, M., AHD VASSmIOU, Y. 1984. Coupling expert systems with database management systems. In Artificial Intelligence Applications for Business, W. Reitman, Ed. Ablex, Norwood, N.J., pp. 65- 85.Google Scholar
JARKE, M., CLIFFORD, J., AND VASSlLIOU, Y. 1984. An optimizing Prolog front-end to a relational query system, in SIGMOD 84, Proceedings of Annual Meeting (Boston, Mass., June 18-21). ACM, New York, pp, 296-306. Google Scholar
JOHNSON, D. S., AND KLUG, A. 1982. Testing containment of conjunctive queries under functional and inclusion dependencies. In Proceedings of the A CM Symposium on Principles of Database Systems (Los Angeles, Calif., Mar. 29-31). ACM, New York, pp. 164-169. Google Scholar
JOHNSON, D. S., AND KLUG, A. 1983. Optimizing conjunctive queries that contain untyped variables. SIAM J. Comput. 12, 4, 616-640.Google ScholarCross Ref
JOHNSTON, H. R., SCHWrgTZER, J. E., AND WARKE~- TINE, E. R. 1983. A DBMS facility for handling structured engineering entities. In Proceedings of the Database Week Engineering Design Applications Conference (San Jose, Calif.). ACM, New York, pp. 3-12.Google Scholar
KAMBAYASHI, Y., AND YOSHIKAWA, M. 1983. Query processing utilizing dependencies and horizontal decomposition. In SIGMOD 83 Proceedings of the Annual Meeting (San Jose, Calif., May 23-26). ACM, New York, pp. 55-67. Google Scholar
KAMBAYASHI, Y., YOSHIKAWA, M., AND YAJIMA, S. 1982. Query processing for distributed databases using generalized semi-joins. In Proceedings of the ACM-SIGMOD International Conference on Management of Data (Orlando, Fla., June 2- 4). ACM, New York, pp. 151-160. Google Scholar
KATZ, R. H., AHD WONG, E. 1982. Decompiling CO- DASYL DML into relational queries. ACM Trans. Databo~ve Syst. 7, 1 (Mar.), 1-23. Google ScholarDigital Library
KELLOGC,, C. 1982. A practical amalgam of knowledge and data base technology. In Proceedings of the National Conference on Artificial Intelligence (Pittsburgh, Pa.). AAAI, Menlo Park, Calif.Google Scholar
K~.aSCnSERC, L., TING, P. D., AND YAO, S. B. 1982. Query optimization in star computer networks. ACM Trans. Database Syst. 7, 4 (Dec.), 678-711. Google Scholar
KIM, W. 1980. A new way to compute the product and join of relations. In Proceedings of the ACM- SIGMOD International Conference on Managernent of Data (Santa Monica, (Calif., May 14-16). ACM, New York, pp. 179-187. Google Scholar
KIM, W. 1981. Query optimization for relational database systems. IBM Res. Rep. RJ3081, IBM Research Laboratories, San Jose, Calif.Google Scholar
KIM, W. 1982. On optimizing an SQL-!ike nested query. ACM Trans. Database Syst. 7, 3 (Sept.), pp. 443-469. Google ScholarDigital Library
KIM, W. 1984. Global optimization of relational queries: A first step. In Query Processing in Database Systems, W. Kim, D. Reiner, and D. Batory, Eds. Springer, New York.Google Scholar
KIM, W., KUCK, D. J., AND GARSKI, D. 1981. A bitserial/tuple-parallel relational query processor. IBM Res. Rep. RJ3194, IBM Research Laboratories, San Jose, Calif.Google Scholar
KING, J. J. 1979. Exploring the use of domain knowledge for query processing efficiency. Tech. Rep. STAN-CS-79-781, Computer Science Dept., Stanford University, Stanford, Calif. Google Scholar
KiHc., J. J. 1981. QUIST: A system for semantic query optimization in relational databases. In Proceedings of the 7th International Conference on Very Large Dam Bases (Cannes, Sept. 9-11). IEEE, New York, pp. 510-517.Google Scholar
KLUG, A. 1980. Calculating constraints on relational expressions. ACM Trans. Database Syst. 5, 3 (Sept.), 260-290. Google ScholarDigital Library
KLUC., A. 1982a. Equivalence of relational algebra and relational calculus query languages having aggregate functions. J. ACM 29, 3 (July), 699- 717. Google Scholar
KLUG, A. 1982b. Access paths in the "ABE" statistical query facility. In Proceedings o/the ACM- SIGMOD International Conference on Management of Data (Orlando, Fla., June 2-4). ACM, New York, pp. 161-173. Google Scholar
KLUO, A. 1983. Locking expressions for increased database concurrency. J. ACM 30, I (Jan.), 36- 54. Google ScholarDigital Library
KOCH, J., SCHMIDT, J. W., AND WUNDERLICH, V. 1981. Type derivation for first-order relational expressions. Teeh. Rep. no. 79, Fachbereich Informatik, Universitfit Hamburg, Hamburg, FRG.Google Scholar
KOWALSKL R. 1981. Logic as a database language. Unpublished manuscript, Computer Science Dept., Imperial College, London.Google Scholar
KIJNWUJI, S., AND YOKOTA, H. 1982. Prolog and relational databases for Fifth Generation Computer Systems. In Proceedings o/the Workshop on Logical Bases for Data Bases (Toulouse, France). ONERA-CERT, Toulouse, France.Google Scholar
L^MERSDORF, W. 1984. Recursive data models for non-conventional database applications. In Proceedings of the IEEE COMPDEC Conference (Los Angeles, Calif.). IEEE, New York. Google Scholar
LANG, T., WOOD, C., AND FERNANDEZ, I. B. 1977. Database buffer paging in virtual storage systems. ACM Trans. Database Syst. 2, 4 (Dec.), 339-351. Google ScholarDigital Library
LANGDON, G. G. 1979. Database machines: an introduction. IEEE Trans. Comput. C-28, 6, 381-383.Google ScholarDigital Library
LEILtCH, H.-O., STIEGE, G., A~D ZEIDLER, H. C. 1978. A search processor for data base management systems. In Proceedings of the 4th Internstional Conference on Very Large Data Bases (West Berlin, FRG, Sept. 13-15). 1EEE, New York, pp. 280-287.Google Scholar
,IN, C. S., SMITH, D. C. P., AND SMITH, J. M. 1976. The design of a rotating associative memory for relational database applications. ACM Trans. Database Syst. I, I (Mar.), 53-65. Google Scholar
Liu, J. W. S. 1976. Algorithms for parsing search queries in systems with inverted file organizations. ACM Trans. Database Syst. 1, 4 (Dec.), 299-316. Google Scholar
LUK, W. S. 1983. On estimating block accesses in database organizations. Commun. A CM 26, 11 (Nov.), 945-947. Google ScholarDigital Library
MA~P;AWA, M. 1982. Parallel join and sorting algorithms. In Data Base Design Techniques II, S. B. Y ao and T. L. Kunii, Eds. Springer, New York, pp. 266-296. Google Scholar
MAUMOUO, S. A., RIORDON, J. S., ANO TOT}{, K. C. 1979. Database partitioning and query processing. In Proceedings of the IFIP Working Conference on Database Architecture. Elsevier North- Holland, New York, pp. 3-21.Google Scholar
MATER, D. 1983. The Theory of Relational Databases. Computer Science Press, Rockville, Md. Google Scholar
MAIER, D., AND ULLMAN, J. D. 1983. Fragments of relations. In SiGMOD 83, Proceedings of the Annual Meeting (San Jose, Calif., May 23-26). ACM, New York, pp. 15-22. Google Scholar
MAIER, D., AND WARREN, D. S. 1981. Incorporating computed relations in relational databases. In Proceedings of the A CM-SIGMOD International Conference on Management of Data (Ann Arbor, Mich., Apr. 29-May 1). ACM, New York, pp. 176-187. Google Scholar
MAKtNOVCHI, A., TEZUKA, M., KITAKAMI, H., AND ADACH{, S. 1981. The optimization strategy for query evaluation in RDB/V1. In Proceedings of the 7th InteraatLonal Conference on Very Large Data Bases (Cannes, Sept. 9-11). IEEE, New York, pp. 518-529.Google Scholar
MALL, M., REIM!~R, M., ^ND SCHMIDT, J. W. 1984. Data selection, sharing and access control in a relational scenario. In On Conceptual Modeling. Perspectives from Artificial Intelligence, Databases, and Programming Languages, M. Brodie, J. Mylopoulos, and J. W. Schmidt, Eds. Springer, New York, pp. 411-436.Google Scholar
MARBURGER, H., AND NEBEL, B. 1983. Natuerlichsprachlicher Datenbankzugang mit HAM- ANS: Syntaktische Korespondenz, natuerlichsprachliche Quantifizierung und semantisches Modell des Diskursbereichs. In Sprachen fuer Datenbanken, J. W. Schmidt, Ed. Springer-Vetlag, Berlin, pp. 26-41. Google Scholar
MARCH, S. T. 1983. A mathematical programming approach to the selection of access paths for large multiuser data bases. Decision Sci. 14, 4, 564-587.Google ScholarCross Ref
MARYANSKI, F. J. 1980. Backend database systems. ACM Comput. Surv. 12, 1 (Mar.), 3-25. Google ScholarDigital Library
MENON, M. J., ANO HSIAO, D. K. 1981. Design and analysis of a relational join operation for VLSI. In Proceedings of the 7th International Conference on Very Large Data Bases (Cannes, Sept. 9-11). IEEE, New York, pp. 44-55.Google Scholar
MERREqrV, T. H. 1977. Database cost analysis: A topdown approach. In Proceedings of the ACM-SIG- MOD International Conference on Management of Data (Toronto, Canada, Aug. 3-5). ACM, New York, pp. 135-143. Google Scholar
MERRETT, T. H. 1981. Why sort-merge gives the best implementation of the natural join. SIG- MOD Rec. 13, 2, 39-51. Google ScholarDigital Library
MERR~.TT, T. H., KAMBAYASHt, Y., AND YASUURA, H. 1981. Scheduling of page-fetches in join operations. In Proceedings of the 7th International Conference on Very Large Data Bases (Cannes, Sept. 9-11). IEEE, New York, pp. 488-498.Google Scholar
MINKER, J. 1975. Performing inferences over relation data bases. In Proceedings of the A CM- SiGMOD International Conference on Management of Data (San Jose, CaliL, May 14-16). ACM, New York, pp. 79-91. Google Scholar
M{NKER, J. 1978. Search strategy and selection function for an inferential relational system. ACM Trans. Database Syst. 3, 1 (Mar.), 1-31. Google ScholarDigital Library
MINKER, J., AND NICOLAS, J.-M. 1983. On recursive axioms in deductive databases. Inf. Syst. 8, 1, 1- 13.Google ScholarCross Ref
MISSIgOFF, M., A~O SCHOLL, M. 1983. Relational queries in domain based DBMS. In SIGMOD 83, Proceedings of Annual Meeting (San Jose, Calif., May 23-26). ACM, New York, pp. 219-227. Google Scholar
MONTGOMERY, A. I., o'SOUZA, D. J., AND LEE, S. B. 1983. The cost of relational algebraic operations in skewed data: Estimates and experiments. In Information Processing 83. Elsevier North-Holland, New York, pp. 235-241.Google Scholar
Mu~z, R. R. 1979. Gross architecture of the distributed database system. VDN. In Proceedings of the IFIP Working Conference on Database Architecture. Elsevier North-Holland, New York, pp. 23- 34.Google Scholar
Mv~z, R. R., SCn~EII)ER, H.-J., A~o STa~~R, F. 1979. Application of sub-predicate tests in database systems. In Proceedings of the 5th International Con/erence on Very Large Data Bases (Rio de Janeiro, Oct. 3-5). IEEE, New York, pp. 426-435.Google Scholar
MUTHUSWAMY, B., AND KERSCHBERG, r. 1983. Distributed query optimization using detailed database statistics. Unpublished manuscript, Computer Science Dept., University of South Carolina.Google Scholar
NAU, D. 1983. Expert computer systems. IEEE Cornput. 16, 2 (Feb.), 63-85.Google Scholar
NEUHOLD, E. J., AND BILLER, It. 1977. POREL: A distributed data base on an inhomogeneous computer network. In Proceedings of the 3rd International Conference on Very Large Data Bases (Tokyo, Oct. 6-8). IEEE, New York, pp. 380-395. No,, P. 1982. Distributed compilation and recompilation of distributed queries. IBM ties. Rep. RJ3375, IBM Research Laboratories, San Jose, Calif.Google Scholar
NIEBUHR, K. E., AND SMITH, S. E. 1976. N-aryjoins for processing Query by Example. IBM Tech. Disclosure Bull. 19, 6, 2377-2381.Google Scholar
NIEsunI~, K. E., SCUOLZ, K. W., ANn SMITe, S. E. 1976. Algorithm for processing Query by Example. IBM Tech. Disclosure Bull. 19, 2,736-741.Google Scholar
NIEVERGELT, J., HINTERBERGER, H., AND SEVCIK, K. C. 1984. The grid file: An adaptable, symmetric multikey file structure. A CM Trans. Database Syst. 9, I (Mar.), 38-71. Google Scholar
N~LSSON, N. 1982. Principles of Artificial Intelligence. Springer, New York. O~r, N. 1977. Interpretation of questions with quantifiers and negation in the USL system. IBM Tech. Rep. TR-77.10.005, IBM Scientific Center, Heidelberg, FRG. Google Scholar
OTT, N., AND HORLAENDER, K. 1982. Removing redundant join operations in queries involving views, iBM Tech. Rep. TR-82.03.003, IBM Scientific Center, Heidelberg, FRG.Google Scholar
OZgA~tAHAN, E. A. 1982. Database machine/computer based distributed databases. In Proceedings of the 2nd International Symposium on DistribuWd Databases (Berlin, FRG). Elsevier North- Holland, New York, pp. 61-80.Google Scholar
OzsoYOGLU, M. Z., AND OZSOYOGLU, G. 1983. An extension of relational algebra for summary tables. In Proceedings o/the 2nd Statistical Data~ base Workshop (Berkeley, Calif.). University of California, Berkeley. Google Scholar
OZSOYOaLU, M., ANO Yu, C. T. 1980. On identifying a class of database queries that can be processed efficiently. In Proceedings o/the IEEE COMP- SAC Conference. IEEE, New York, pp. 453-461.Google Scholar
PalcE, R. 1982. Applications of finite differencing to database integrity control and query/transaction optimization. In Proceedings of the Workshop on Logical Bases for Data Bases (Toulouse, France). ONERA-CERT, Toulouse, France.Google Scholar
PALERMO, F. P. 1972. A data base search problem. In Proceedings of the 4th Symposium on Computer and Information Science (Miami Beach, Fla.). AFIPS Press, Reston, Va., pp. 67-101.Google Scholar
PARSAYE, K. 1983. Database management, knowledge base management, and expert system development in PROLOG. In Proceedings of the Database Week Conference on Engineering Applications of Databases (San Jose, Calif.). ACM, New York, pp. 159-178. Google Scholar
PECHER~.~t, R. M. 1975. Efficient evaluation of expressions in a relational algebra. In Proceedings of the ACM Pacific 75 Conference (San Francisco, Calif., May 14-16). ACM, New York, pp. 44-49.Google Scholar
PECUERER, R. M. 1976. Efficient exploration of product spaces. In Proceedings of the ACM-SIG- MOD international Conference on Management of Data (Washington, D.C., June 2-4). ACM, New York, pp. i69-177.Google Scholar
Pmoa-rE, A. 1979. Findamental and secondary issues in the design of non-procedural relational languages. In Proceedings of the 5th International Conference on Very Large Data Bases (Rio de Janeiro, Oct. 3-5). IEEE, New York, pp. 239-250.Google Scholar
PUTKONr~N, A. 1979. On the selection of the access path in inverted database organizations, In/. Syst. 4, 4, 219-225.Google Scholar
REIMZR, M. 1983. Solving the phantom problem by predicative optimistic concurrency control. In Proceedings of the 9th International Conference on Very Large Data Bases (Florence, Italy). VLDB Endowment, Saratoga, Calif., pp. 81-88. Google Scholar
R~.ITEa, R. 1978. Deductive question-answering on relational data bases. In Logic and Databases, H. Gallaire and J. Minker, Eds: Plenum, New York, pp. 149-178.Google Scholar
R~CH^RD, P. 1981. Evaluation of the size of a query expressed in relational algebra. In Proceedings of the A CM-SIGMOD International Conference on Management of Data (Ann Arbor, Mich., Apr. 29- May 1). ACM, New York, pp. 155-163. Google Scholar
ROSENKRANTZ, D. J., AND HUNT, H. B. III. 1980. Processing conjunctive predicates and queries. In Proceedings of the 6th international Conference on Very Large Data Bases (Montreal, Oct. 1-3). IEEE, New York, pp. 64-72.Google Scholar
ROSENTHAL, A., AND REINER, D. 1982. An architecture for query optimization. In Proceedings of the A CM-SIGMOD International Conference on Management of Data (Orlando, Fla., June 2-4). ACM, New York, pp. 246-255. Google Scholar
ROSENTHaL, A., ANO REINER, D. 1984. Querying relational views of networks. In Query Processing in Database Systems, W. Kim, D. Reiner, and D. Batory, Eds. Springer, New York.Google Scholar
ROTHNIE, J. B. 1974. An approach to implementing a relational data management system. In Proceedings of the ACM-SIGMOD Workshop on Data Description, Access, and Control (Ann Arbor, Mich., May 1-3). ACM, New York, pp. 277-294. Google Scholar
ROTHNtE, J. B., JR. 1975. Evaluating inter-entry retrieval expressions in a relational data base management system. In Proceedings of the National Computer Conference (Anaheim, Calif., May 19-22), vol. 44. AFIPS Press, Reston, Va., pp. 417-423.Google Scholar
ROTHNI~., J. B., ANO GOOOMaN, N. 1977. A survey of research and development in distributed database management. In Proceedings of the 3rd International Conference on Very Large Data Bases (Tokyo, Oct. 6-8). IEEE, New York, pp. 48-62.Google Scholar
ROUSSOPOULOS, N. 1982a. View indexing in relational databases. A CM Trans. Database Syst. 7, 2 (June), 258-290. Google ScholarDigital Library
ROUSSOPOULOS, N. 1982b. The logical access path schema of a database. IEEE Tran~. Softw. Eng. SE-8, 6, 563-573.Google ScholarDigital Library
SACCO, G. M., aND SCnKOLNWK, M. 1982. A mechanism for managing the buffer pool in a relational database system using the hot set model. In Pro. ceedings of the 8th International Conference on Very Large Data Bases (Mexico City). VLDB Endowment, Saratoga, Calif., pp. 257-262. Google Scholar
SACCO, G. M., AND YAO, S. B. 1982. Query optimization in distributed database systems. In Advances in Computers, vol. 21. Academic Press, New York, pp. 225-273.Google Scholar
SAGALOWmZ, D. 1977. iDA: An intelligent data access program. In Proceedings of the 3rd International Conference on Very Large Data Bases (Tokyo, Oct. 6-8). IEEE, New York, pp. 293-302.Google Scholar
SaGlv, Y. 1981. Optimization of Queries in Relational Databases. UMI Research Press, Ann Arbor, Michigan.Google Scholar
SAG~V, Y. 1983. Quadratic algorithms for minimizing joins in restricted relational expressions. SlAM J. Comput. 12, 2, 316-328.Google ScholarCross Ref
SAGIV, Y., aND YANNAKAKIS, M. 1980. Equivalences among relational expressions with the union and difference operators. J. ACM 27, 4 (Oct.) 633- 655. Google ScholarDigital Library
SALTON, G., AND WON(J, A. 1978. Generation and search of clustered files. A CM Trans. Database Syst. 3, 4 (Dec.) 321-346. Google ScholarDigital Library
SCHEK, H.-J., AND PISTOR, P. 1982. Data structures for an integrated database management and information retrieval system. In Proceedings of the 8th International Conference on Very Large Data Bases (Mexico City). VLDB Endowment, Saratoga, Calif., pp. 197-207. Google Scholar
SCHENK, K. L., AND PINKERT, J. R. 1977. An algorithm for servicing multi-relational queries. In Proceedings of the A CM-SIGMOD International Conference on Management of Data (Toronto, Canada, Aug. 3-5). ACM, New York, pp. 10-20. Google Scholar
SCaKOLNICg, M. 1975. The optimal selection of indexes for files. Inf. Syst. 1, 4, 141-146.Google ScholarCross Ref
SCHKOLNICK, M. 1982. Physical database design techniques. In Data Base Design Techniques 1I, S. B. Yao and T. L. Kunii, Eds. Springer, New York, pp. 229-252. Google Scholar
SCHMIOT, J. W. 1977. Some high level language constructs for data of type relation. A CM Trans. Database Syst. 2, 3 (Sept.), 247-261. Google Scholar
SCHMIOT, J. W. 1979. Parallel processing of relations: A single-assignment appxoach. In Proceedings of the 5th International Conference on Very Large Data Bases (Rio de Janeiro, Oct. 3-5). IEEE, New York, pp. 398-408.Google Scholar
SCHMJDT, J. W. 1984. Database programming: Lan. guage constructs and execution models. In Programmiersprachen und Programmentwicklung, U. Ammann, Ed. Springer-Verlag, Berlin, pp. 1-26. Google Scholar
SELINOER, P. G., AND AOmA, M. 1980. Access path selection in distributed database systems. IBM Res. Rep. RJ2283, IBM Research Laboratories, San Jose, Calif.Google Scholar
SELINGER, P. G., ASTRAHAN, M. M., CHAMBERLIN, D. D., Lomg, R. A., ^ND PRICE, T. G. 1979. Access path selection in a relational database management system. In Proceedings of the ACM-SiGMOD International Conference on Management of Data (Boston, Mass., May 30-June 1). ACM, New York, pp. 23~34. Google Scholar
SEV~RANCg, D. G., AND CARUS, J. V. 1977. A practical approach to selecting record access paths. ACM Comput. Surv. 9, 4 (Dec.) 259-272. Google Scholar
SaMUF. LI, O. 1981. The fundamental role of tree schemas in relational query processing. Ph.D. thesis, Computer Science Dept., Harvard Univ., Cambridge, Mass.Google Scholar
SHNEIDERMAN, B. 1977. Reduced combined indexes for efficient multiple attribute retrieval Inf. Syst. 2, 4, 149-154.Google ScholarCross Ref
SHNEIDERMAN, B., AND GOODMAN, V. 1976. Batched searching of sequential and tree structured files. A CM Trans. Database Syst. I, 3 (Sept.), 268-275. Google Scholar
SHOSHANI, A. 1982. Statistical database: Characteristics, problems, and some solutions. In Proceedings of the 8th International Conference on Very Large Data Bases (Mexico City). VLDB Endowment, Saratoga, Calif., pp. 208-222. Google Scholar
SHULTZ, R. K., aND Z~NGO, R. J. 1984. Response time analysis of multiprocessor computers for database support. A CM Trans. Database Syst. 9, 1 (Mar.), 100-132. Google Scholar
SMITH, J. M., AND CHANG, P. Y. T. 1975. Optimizing the performance of a relational algebra database interface. Commun. ACM I8, 10 (Oct.), 568-579. Google Scholar
SMITH, J. M., BERNSTEIN, P. A., DAYAL, U., GOOD- MAN, N., LANDERS, T., LIN, K. W. T., AND WONG, E. 1981. MULTIBASE--Integrating heterogeneous distributed database systems. In Proceedings of the AFIPS National Computer Conference (Chicago, May 4-7), vol. 50. AFIPS Press, Reston, Vs., pp. 487-499.Google Scholar
SOCKUT, G. H., AND GOLOBERG, R. P. 1979. Database reorganization--Principles and practice. ACM Comput. Surv. 1t, 4 (Dec.) 371-395. Google ScholarDigital Library
STONgBRAKER, M. 1975. Implementation of integrity constraints and views by query modification. In Proceedings of the A CM-SIGMOD Internstional Conference on Management of Data (San Jose, Calif., May 14-16). ACM, New York, pp. 65-78. Google Scholar
STONEBRAKER, M., AND NEUHOLD, E. 1977. A distributed database version of INGRES. In Proceedings of the 2nd Berkeley Workshop on Distributed Data Management and Computer Networks (Berkeley, Calif.). University of California, Berkeley.Google Scholar
STONEBRAKER, M., WONG, E., KREPS, P., AND HELD, G. 1976. The design and implementation of INGRES.ACM Trans. Database Syst. 1, 3 (Sept.), 189-222. Google ScholarDigital Library
STROET, J. W. M., AND ENGMANN, R. 1979. Manipulation of expressions in a relational algebra. Inf. Syst. 4, 4, 195-203.Google ScholarCross Ref
Su, S. Y. W. 1979. Cellular-logic devices: Concepts and applications. IEEE Comput. 12, 3, 11-25.Google ScholarDigital Library
Su, S. Y. W., AND LIPKOVSKI, G. 1975. CASSM: A cellular system for very large databases. In Proceedings o{ the 1st International Conference on Very Large Data Bases (Framingham, Mass., Sept. 22-24). ACM, New York, pp. 456-472.Google Scholar
Su, S. Y. W., AND MIKKILINENI, K. P. 1982. Parallel algorithms and their implementation in MICRO- NET. In Proceedings of the 8th International Conference on Very Large Data Bases (Mexico City). VLDB Endowment, Saratoga, Calif., pp. 310~324. Google Scholar
TANENBAUM, A. 1981. Computer Networks. Prentice-Hall, New York. Google Scholar
TEORE~, T. J., ANO FRY, J. P. 1982. Design of Detabase Structures. Prentice-Hall, New York. Google Scholar
TOAD, S. 1974. Implementing the join operator in relational data bases. IBM Scientific Center Tech. Note 15, IBM UK Scientific Center, Peterlee, England.Google Scholar
TSlCHRITZlS, D. 1976. LSL: A link and selector language. In Proceedings of the A CM-SIGMOD International Con{erence on Management o{ Data (Washington, D.C., June 2-4). ACM, New York, pp. 123-133. Google Scholar
ULLMAN, J. D. 1982. Principles of Databc~se Systems. Computer Science Press, Rockville, Md. Google Scholar
VALOUmEZ, P. 1982. Semi-join algorithms for multiprocessor systems. In Proceedings of the A CM- SIGMOD International Conference on Manage. ment of Data (Orlando, Fla., June 2-4). ACM, New York, pp. 225-233. Google Scholar
VALDURIEZ, P., AND GARDARIN, G. 1984. Join and semijoin algorithms for a multiprocessor database machine. ACM Trans. Database Syst. 9, i (Mar.), 133-161. Google ScholarDigital Library
v^~ OE Rmw, R. P., W^SS~RMAN, A. I., KERSTEN, M. L., AND DE JONGE, W. 1981. High-level programming features for improving the efficiency of a relational database system. ACM Trans. Database Syst. 6, 3 (Sept.), 464-485. Google Scholar
VASSIL{OU, Y., AND JARKE, M. 1984. Query languages--A taxonomy. In Human Factors and Interactive Computer Systems, Y. Vassiliou, Ed. Ablex, Norwood, N.J.Google Scholar
VASSILIOU, Y., AND LOC~OVSKY, F. 1980. DBMS transaction translation. In Proceedings of the IEEE COMPSAC Conference. IEEE, New York, pp. 89-96.Google Scholar
VASSILIOU, Y., CLIFFORD, J., AND JARKE, M. 1984. Access to specific declarative knowledge in expert systems: The impact of logic programming. Decision Support Syst. 1, 1.Google Scholar
VER~OFSTAO, J. S. M. 1978. Recovery techniques for database systems. ACM Comput. Surv. 10, 2 (June), 167-195. Google Scholar
WALKER, A. 1980. On retrieval from a small version of a large data base. In Proceedings of the 6th International Conference on Very Large Data Basses (Montreal, Oct. 1-3). IEEE, New York, pp. 47-54.Google Scholar
W^RREN, D. H. D. 1981. Efficient processing of interactive relational database queries expressed in logic. In Proceedings of the 7th International Conference on Very Large Data Bases (Cannes, Sept. 9-11). IEEE, New York, pp. 272-281.Google Scholar
WgLCH, J. W., ANO GRASAM, J. W. 1976. Retrieval using ordered lists in inverted and multilist files. In Proceedings of the ACM-SIGMOD Interneti~mal Conference on Management of Data (Wash~ ington, D.C., June 2-4). ACM, New York, pp. 21- 29. Google Scholar
WaANa, K.-Y., WIEOERHOLD, G., AND SAGALOWICZ, D. 1983. Estimating block accesses in database organizations: A closed noniterarive formula. Commun. ACM 26, 11 (Nov.), 940-944. Google Scholar
WILHAMS, R., DANIELS, D., HAAS, L., LAPI8, G., LINDSAY, B., NG, P., OBERMARCK, R., SEL{NGER, P., WALKER, A., WILMS, P., AND Y OaT, R. 1982. R*: An overview of the architecture. In Proceedings of the International Conference on Database Systems (Jerusalem, Israel).Google Scholar
WANG, E. 1977. Retrieving dispersed data from SDD-I: A system for distributed databases. In Proceedings of the Second Berkeley Workshop on Distributed Data Management and Computer Networks (Berkeley, Calif.), pp. 217-235.Google Scholar
WONa, E. 1983. Dynamic rematerialization: Processing distributed queries using redundant data. IEEE Trans. So{tw. Eng. SE-9, 3, 228~232.Google Scholar
WONO, E., AND KATZ, R. H. 1983. Distributing a database for parallelism. In S{GMOD 83, Proceedings of the Annual Meeting (San Jose, Calif., May 23-26). ACM, New York, pp. 23-29. Google Scholar
WANG, E., AND YOUSSEFI, K. 1976. Decomposition--A strategy for query processing. ACM Trans. Database Syst. 1, 3 (Sept.), 223-241. Google Scholar
Xu, G. D. 1983. Search control in semantic query optimization. Tech. Rep.//83-09, Computer and Information Science Dept., University of Massachusetts, Amherst, Mass.Google Scholar
YAN(~, C.-S. 1977. Avoiding redundant accesses in unsorted multilist file organizations. Inf. Syst. 2, 4, 155-158.Google ScholarCross Ref
YAO, S. B. 1977a. Approximating block accesses in database organizations. Commun. A CM 20, 4 (Apr.), 260~261. Google ScholarDigital Library
YAO, S. B. 1977b. An attribute based model for database access cost analysis. ACM Trans. Database Syst. 2, 1 (Mar.), 45-67. Google ScholarDigital Library
YAO, S. B. 1979. Optimization of query evaluation algorithms. A CM Trans. Database Syst. 4, 2 (June), 133~155. Google ScholarDigital Library
YAO, S. B., AND DEJONG, D. 1978. Evaluation of database access paths. In Proceedings of the A CM-SIGMOD International Conference on Management of Data (Austin, Tex., May 31-June 2). ACM, New York, pp. 66-77. Google Scholar
YOUSSEFI, K., AND WANG, E. 1979. Query processing in a relational database management system. In Proceedings of the 5th International Conference on Very Large Data Bases (Rio de Janeiro, Oct. 3-5). IEEE, New York, pp. 409-417.Google Scholar
YU, C. T., AND CHANG, C. C. 1983. On the design of a query processing strategy in a distributed database environment. In S.rGMOD 83, Proceedings el the Annual Meeting (San Jose, Calif., May 23- 26). ACM, New York, pp. 30-39. Google Scholar
Yu, C. T., ANO OZSOYOGLU, M. 1979. An algorithm for tree query membership of a distributed query. In Proceedings of the IEEE COMPSAC Conference. IEEE, New York, pp. 306-312.Google Scholar
Yu, C. T., LUK, W. $., AND SIu, M. K. 1978. On the estimation of the number of desired records with respect to a given query. ACM Trans. Database Syst. 3, 1 (Mar.), 41-56. Google Scholar
ZANIOLO, C. 1979. Design of relational views over network schemas. In Proceedings of the A CM- SIGMOD International Conference on Management of Data (Boston, Mass., May 30-June 1). ACM, New York, pp. 179-190. Google Scholar

Index Terms

Query Optimization in Database Systems

Recommendations

Query optimization in multidatabase systems
CASCON '92: Proceedings of the 1992 conference of the Centre for Advanced Studies on Collaborative research - Volume 2

A multidatabase system (MDBS) integrates information from autonomous local databases managed by heterogeneous database management systems (DBMS) in a distributed environment. For a query involving more than one database, global query optimization should ...
Read More
Query optimization for object-relational database systems
Read More
Query processing and optimization in temporal database systems
Read More

Comments

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Published in
ACM Computing Surveys Volume 16, Issue 2
June 1984
161 pages
ISSN:0360-0300
EISSN:1557-7341
DOI:10.1145/356924
Editor:
Adele Goldberg
Issue’s Table of Contents
Copyright © 1984 ACM
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
- Published: 1 June 1984
Published in csur Volume 16, Issue 2

Permissions
Request permissions about this article.
Request Permissions

Check for updates
Qualifiers
- article
Conference
Funding Sources
Other Metrics
View Article Metrics

Article Metrics
- 490
  Total Citations
  View Citations
- 10,791
  Total Downloads
- Downloads (Last 12 months)957
- Downloads (Last 6 weeks)149
Other Metrics
View Author Metrics
Cited By
View all

PDF Format

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Query Optimization in Database Systems

ACM Computing Surveys

References

Cited By

Index Terms

Recommendations

Query optimization in multidatabase systems

Query optimization for object-relational database systems

Query processing and optimization in temporal database systems

Comments

Login options

Full Access

Published in

Sponsors

In-Cooperation

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Conference

Funding Sources

Other Metrics

Article Metrics

Other Metrics

Cited By

PDF Format

eReader

Digital Edition

Caption

Query Optimization in Database Systems

ACM Computing Surveys

References

Cited By

Index Terms

Recommendations

Query optimization in multidatabase systems

Query optimization for object-relational database systems

Query processing and optimization in temporal database systems

Comments

Login options

Full Access

Published in

Sponsors

In-Cooperation

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Conference

Funding Sources

Article Metrics

Other Metrics

PDF Format

eReader

Digital Edition

Share this Publication link

Share on Social Media