Timos K. Sellis
Abstract
Some recently proposed extensions to relational database systems, as well as to deductive database systems, require support for multiple-query processing. For example, in a database system enhanced with inference capabilities, a simple query involving a rule with multiple definitions may expand to more than one actual query that has to be run over the database. It is an interesting problem then to come up with algorithms that process these queries together instead of one query at a time. The main motivation for performing such an interquery optimization lies in the fact that queries may share common data. We examine the problem of multiple-query optimization in this paper. The first major contribution of the paper is a systematic look at the problem, along with the presentation and analysis of algorithms that can be used for multiple-query optimization. The second contribution lies in the presentation of experimental results. Our results show that using multiple-query processing algorithms may reduce execution cost considerably.
- 1 ASTRAHAN, M. ET AL. System R: A relational approach to database management. ACM Trans. Database Syst. 1, 2 (June 1976), 97-137. Google Scholar
- 2 CHAKRAVARTH~, V. S., FISHMAN, D. H., AND MINKER, J. Semantic query optimization in expert systems and database systems. In Expert Database Systems: Proceedings From the 1st International Workshop, L. Kershberg, Ed. Benjamin/Cummings, Menlo Park, Calif. 1986, 659-674. Google Scholar
- 3 CHAKRAVARTHY, U. S., AND MINKER, J. Processing multiple queries in database systems. Database Eng. 5, 3 (Sept. 1982), 38-44.Google Scholar
- 4 CHAKRAVARTHY, U. S., AND MINKER, J. Multiple query processing in deductive databases. Tech. Rep. TR-1554, Dept. of Computer Science, Univ. of Maryland, College Park, Md., Aug. 1985.Google Scholar
- 5 CHAKRAVARTHY, U. S., MINKER, J., AND GRANT, J. Semantic query optimization: additional constraints and control strategies. In Proceedings of the 1st International Conference on Expert Database Systems (Charleston, S. C., April 1986). Institute of Information Management and Policy, Univ. of South Carolina, Apr. 1986, 259-270.Google Scholar
- 6 CLOCKSIN, W., AND MELLISH, C. Programming in PROLOG. Springer-Verlag, New York, 1981. Google Scholar
- 7 FINKELSTEIN, S. Common expression analysis in database applicaitons. In procdeeings of the ACM-SIGMOD International Conference on the Management of Data (Orlando, Fla., June 1982) ACM, New York, 1982, 235-245. Google Scholar
- 8 GALLAIRE, H., AND MINKER, J. Logic and Data Bases. Plenum Press, New York, 1978 Google Scholar
- 9 GRANT, J., AND MINKER, J. On optimizing the evaluation of a set of expressions. Tech. Rep. TR-916, Univ. of Maryland, College Park, Md., July 1980.Google Scholar
- 10 GRANT, J., AND MINKER, J. Optimization in deductive and conventional relational database systems. In Advances in Data Base Theory, Vol. 1, H. Gallaire, J. Minker, and J.-M. Nicolas, Eds. Plenum Press, New York, 1981, 195-234.Google Scholar
- 11 GU2"rMAN, A. New features for relational database systems to support CAD applications. Ph.D. dissertation, Computer Science Div., Univ. of California, Berkeley, June 1984.Google Scholar
- 12 HALL, P. V. Common subexpression identification in general algebraic systems, Tech. Rep. UKSC 0060, IBM United Kingdom Scientific Centre, Nov. 1974.Google Scholar
- 13 HALL, P.V. Optimization of a single relational expression in a relational data base system. IBM J. Res. Dev. 20, 3 (May 1976), 244-257.Google Scholar
- 14 IOANNIDIS, Y. Processing recursion in deductive database systems. Ph.D. dissertation, Univ. of California, Berkeley, July 1986.Google Scholar
- 15 JARKE, S., CLIFFORD, J., AND VASSILIOU, Y. An optimizing PROLOG front-end to a relational query system. In Proceedings o/ACM-SIGMOD International Con/erence on the Management o/ Data (Boston, Mass., June 18-21, 1984). ACM, New York 1984, 296-306 Google Scholar
- 16 JARKE, M. Common subexpression isolation in multiple query optimization. In Query Processing in Database Systems, W. Kim, D. Reiner, and D. Batory, Eds. Springer-Verlag, New York, 1984, 191-205.Google Scholar
- 17 KIM, W. Global optimization of relational queries: a first step. In Query Processing in Database Systems, W. Kim, D. Reiner, and D. Batory, Eds. Springer-Verlag, New York, 1984, 206-216.Google Scholar
- 18 KUNG, R., HANSON, E., IOANNIDIS, Y., SELLIS, T., SHAPIRO, L., AND STONEBRAKER, M. Heuristic search in data base systems. In Expert Database Systems: Proceedings From the 1st International Workshop, L. Kershberg, Ed. Benjamin/Cummings, Menlo Park, Calif., 1986, 537-548. Google Scholar
- 19 LARSON, P., AND YANG, H. Computing queries from derived relations. In Proceedings of International Conference on Very Large Data Bases (Stockholm, Aug. 1985), 259-269.Google Scholar
- 20 NAQVI, S., AND HENSCHEIN, L. On compiling queries in recursive first order datbases. J. ACM 31, 1 (Jan. 1984), 47-85. Google Scholar
- 21 NmSSON, N.J. Principles of Artificial Intelligence. Tioga, Palo Alto, Calif., 1980. Google Scholar
- 22 RELATIONAL TECHNOLOGY, INC. EQUEL/C User's Guide. Version 2.1, Relational Technology, Inc., Berkeley, Calif., July 1984.Google Scholar
- 23 ROSENKRANTZ, D. J., AND HUNT, H. B. Processing conjunctive predicates and queries. In Proceedings of the International Conference on Very Large Data Bases (Montreal, Oct. 1980), 64-72.Google Scholar
- 24 ROUSSOPOULOS, N. View indexing in relational databases. ACM Trans. Database Syst. 7, 2 (June 1982), 258-290. Google Scholar
- 25 I~OUSSOPOULOS, N. The logical access path schema of a database. IEEE "l'rans. Softw. Eng. SE-8, 6 (Nov. 1982), 563-573.Google Scholar
- 26 SELLZS, T., AND SHAPZRO, L. Optimization of extended database languages. In Proceedings of May 1985), ACM, New York, 1985, 424-436. Google Scholar
- 27 STONEBRAKER, M., AND ROWE, L. The design of POSTGRES. In Proceedings of the ACM- SIGMOD International Conference on the Management of Data (Washin~on D. C., May 28-30, 1986). ACM, New York, 1986, 340-355. Google Scholar
- 28 STONEBRAKER, M., WONG, E., KREPS, P., AND HELD, G. The design and implementation of INGRES. ACM Trans. Database Syst. 1, 3 (Sept. 1976), 189-222. Google Scholar
- 29 ULLMAN, J. Implementation of logical query languages for data bases. ACM Trans. Database Syst. 10, 3 (Sept. 1985), 289-321. Google Scholar
- 30 WONG, E., AND YOUSSEFI, K. Decomposition: A strategy for query processing. ACM Trans. Database Syst. 1, 3 (Sept. 1976), 223-241. Google Scholar
- 31 ZANIOLO, C. The database language GEM. In Proceedings of the ACM-SIGMOD International Conference on the Management of Data (San Jose, Calif., May, 1983). ACM, New York, 1983, 207-218. Google Scholar
Index Terms
- Multiple-query optimization
Recommendations
Query Optimization for Ontology-Mediated Query Answering
WWW '24: Proceedings of the ACM on Web Conference 2024Ontology-mediated query answering (OMQA) consists in asking database queries on knowledge bases (KBs); a KB is a set of facts called the KB's database, which is described by domain knowledge called the KB's ontology. A widely-investigated OMQA technique ...
Synopses for query optimization: A space-complexity perspective
Special Issue: SIGMOD/PODS 2004Database systems use precomputed synopses of data to estimate the cost of alternative plans during query optimization. A number of alternative synopsis structures have been proposed, but histograms are by far the most commonly used. While histograms ...
Reviews
Edward Sava-Segal
Given a set of queries that are supposed to share some tasks, a considerable reduction of execution time may be achieved by avoiding redundant page access. Sharing common temporary results among queries is cheaper than serial execution. This is the main reason for performing multiple-query analysis. The author's concern is building an optimal access plan, given a set of queries and a set of common subexpressions found previously. Two architectures for systems with a multiple-query processing facility are considered. One is based on a plan merger interleaving the results of the locally optimal access plans of each query. A second more sophisticated one is based on a global optimizer. In the second case the optimization problem is formulated as a state space search problem, and an admissible algorithm is used for that problem. Compared to previous work, a better estimation function is defined in this paper. It penalizes plans that cannot coexist in the final state, thus enabling the algorithm to converge to the final solution faster. Some restrictions are made in building the algorithm, but a way to avoid them using the same framework is discussed. An overview of previous research in the area is presented, and a full section describes experimental results, which the author claims to be publishing for the first time. Experiments proved the usefulness of the given algorithms in various contexts, producing a decrease of 20–50 percent in both I/O and CPU time, even in the presence of fast access paths for relations. Algorithms are clearly described and exemplified. No previous background, except some acquaintance with heuristic search algorithms, is needed to fully understand this interesting paper. Everyone concerned with building database and rule-based systems should read it.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments