Some properties of relational expressions

ABSTRACT

We obtain certain results concerning the power of expressions in relational (calculus and algebra) database sublanguages. Our main results state the undecidability of the equivalence and finite equivalence problems for relational expressions. We also observe that the type of join used in a relational algebra affects the complexity of problems for that algebra. For example, using equi-joins instead of natural joins leads to unnecessarily complex expressions. We relate these results to the problems of query optimization and concurrency control.

REFERENCES

• 1: Sagiv, Y., and Yannakakis, M., "Equivalence Among Relational Expressions with the Union and Difference Operations," Proceedings of the ACM Very Large Data Base Conference, Sept. 1978, pp. 535-548.
• 2: Manaster, A. B., Completeness, Compactness, and Undecidability: An Introduction to Mathematical Logic, Prentice-Hall, Inc., Englewood Cliffs, N. J., 1975.
• 3: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 4: A. V. Aho , Y. Sagiv , J. D. Ullman, Efficient optimization of a class of relational expressions, ACM Transactions on Database Systems (TODS), v.4 n.4, p.435-454, Dec. 1979 [doi>10.1145/320107.320112]
• 5: K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976 [doi>10.1145/360363.360369]
• 6: Aho, A. V., Sagiv, Y., Ullman, J. D., "Equivalence Among Relational Expressions," submitted to SIAM Journal of Computing.
• 7: Codd, E. F., "Relational Completeness of Data Base sublanguages," in Date Base Systems (R. Rustin, ed.), Prentice-Hall, Englewood Cliffs, N. J., 1972, pp. 65-98.
• 8: Lewis, H. R., "Complexity of Solvable Cases of the Decision Problem for the Predicate Calculus," 1978 Nineteenth Annual Symposium on Foundations of Computer Science, pp. 35-47,
• 9: Shelab, S., "Decidability of a Portion of the Predicate Calculus," Israel Journal of Mathematics, Vol. 28, No. 1-2, 1977, pp. 32-44.
• 10: Ackermann, W., Solvable Cases of the Decision Problem, North-Holland Publishing Company, Amsterdam, The Netherlands, 1954.

INDEX TERMS

Keywords:
Concurrency, equi-join, natural join, predicate calculus, predicate lock, query optimization, relational algebra, relational calculus, undecidability