Anthony Klug
Abstract
Conjunctive queries are generalized so that inequality comparisons can be made between elements of the query. Algorithms for containment and equivalence of such “inequality queries” are given, under the assumption that the data domains are dense and totally ordered. In general, containment does not imply the existence of homomorphisms (containment mappings), but the homomorphism property does exist for subclasses of inequality queries. A minimization algorithm is defined using the equivalence algorithm. It is first shown that the constants appearing in a query can be divided into “essential” and “nonessential” subgroups. The minimum query can be nondeterministically guessed using only the essential constants of the original query.
- 1 AHO, A. V., SAGIV, Y., AND ULLMAN, J. D. Efficient optimization of a class of relational expressions. ACM Trans. Database Syst. 4, 4 (Dec. 1979), 435-454. Google Scholar
- 2 AHO, A. V., SAGIV, Y., AND ULLMAN, J.O. Equivalences among relational expressions. SIAM J. Comput. 8, 2 (May 1979), 218-246.Google Scholar
- 3 ASTRAHAN, M. M., BLASGEN, M. W., CHAMBERLIN, D. D., ESWARAN, K. P., GRAY, J. N., GRIFFITHS, P. P., KING, W. F., LORIE, R. A., MCJONES, P. R., MEHL, J. W., PUTZOLU, G. R., TRAIGER, I. L., WADE, B. W., AND WATSON, V. System R: Relational approach to database management. ACM Trans. Database Syst. 1, 2 (June 1976), 97-137. Google Scholar
- 4 BEERI, C., BERNSTEIN, P., AND GOODMAN, N. A sophistieate's introduction to database normalization theory. In Proceedings of the 1978 VLDB Conference (West Berlin). 1978.Google Scholar
- 5 CHANDRA, A. K., AND MERLIN, P.M. Optimal implementation of conjunctive queries in relational databases. In Proceedings of the 9th Annual ACM Symposium on Theory of Computing. ACM, New York, 1976, pp. 77-90. Google Scholar
- 6 CODD, E.F. Relational completeness of data base sublanguages. In Data Base Systems, R. Rustin, Ed. Prentice-Hall, Englewood Cliffs, N.J., 1972.Google Scholar
- 7 DAYAL, U., Gt~DraAN, N., AND KATZ, R. An extended relational algebra with control over duplicate elimination. In Proceedings of the ACM Symposium on Principles of Database Systems. ACM, New York, 1982, pp. 117-123. Google Scholar
- 8 JOHNSON, D., AND KLUG, A. Optimizing conjunctive queries that contain untyped variables. SIAMJ. Comput. 12, 4 (Nov. 1983), 616-640.Google Scholar
- 9 JOHNSON, D., AND KLUG, A. Testing containment of conjunctive queries under functional and inclusion dependencies. J. Comput. Syst. Sci. 28, 1 (Feb. 1984), 167-189.Google Scholar
- 10 SAGIV, Y. Quadratic algorithms for minimizing joins in restricted relational expressions. Tech. Rep. UIUCDCS-R-79-992. Computer Science Dept., Univ. of Illinois, Urbana, I11., 1979.Google Scholar
- 11 SAGIV, Y., AND YANNAKAKIS, M. Equivalences among relational expressions with the union and difference operators. J. ACM 27, 4 (Oct. 1980), 633-655. Google Scholar
- 12 SHOVNFIELD, J.R. Mathematical Logic. Addison-Wesley, Reading, Mass., 1967.Google Scholar
- 13 SOLOMON, M.K. Some properties of relational expressions. In Proceedings of the ACM Southeast Regional Conference. ACM, New York, 1979, pp. 111-116. Google Scholar
- 14 STON~.nRAK~R, 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
- 15 ULLMAN, J. D. A view of directions in relational database theory. Rep. STAN-CS-81-852. Computer Science Dept., Stanford Univ., Stanford, Calif., 1981.Google Scholar
- 16 YANNAKAKIS, M., AND PAPADIMITRIOU, C. Algebraic dependencies. J. Comput. Syst. Sci. 25, 1 (1982), 2--41.Google Scholar
Index Terms
- On conjunctive queries containing inequalities
Recommendations
Answering Conjunctive Queries with Inequalities
In this paper, we study the complexity of answering conjunctive queries (CQ) with inequalities (ź). In particular, we are interested in comparing the complexity of the query with and without inequalities. The main contribution of our work is a novel ...
Equivalence and minimization of conjunctive queries under combined semantics
ICDT '12: Proceedings of the 15th International Conference on Database TheoryThe problems of query containment, equivalence, and minimization are fundamental problems in the context of query processing and optimization. In their classic work [2] published in 1977, Chandra and Merlin solved the three problems for the language of ...
Combined-semantics equivalence of conjunctive queries
Query containment and equivalence are fundamental problems in the context of query processing and optimization. In this paper, we consider combined-semantics equivalence of conjunctive (CQ) queries. The combined-semantics formalism 10,11 generalizes the ...
Reviews
Kazem Taghva
Conjunctive queries are a subset of domain calculus expressions built from relational atomic formulas using the logical connective and. In the database setting, the connective and is interpreted as the join operator. Since the join is one of the most expensive operations to perform, the optimization problem for conjunctive queries must deal with minimizing the number of joins. Thus, one must find a query with a minimum number of joins that is equivalent to the original conjunctive query. Chandra and Merlin have shown that the optimization problem for conjunctive queries is NP-complete [1]. In this paper, the author investigates the optimization problem for conjunctive queries containing inequalities. The optimization problem is closely related to the query equivalence and query containment problems. The equivalence problem is to determine whether two queries produce the same output when they are evaluated against the same database. The containment problem is defined similarly. The author has shown that the containment problems for left and right semi-interval queries (in left semi-interval queries, all inequalities are of the form x&thgr; c, where x is a variable, c is a constant, and &thgr; is one of ?<,=) are in NP. The general containment problem is left open. The paper is well written and the proofs are mathematically sound. It is essential reading for people interested in the query optimization problem.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments