Abstract
The optimization of relational expressions concerning the elimination of “redundant” operations has been dealt with sofar for a limited class of expressions that puts restrictions on the selection operators involved. We propose a solution for the case of arbitrary selection criteria.
Zusammenfassung
Anfragen in relationalen Datenbanken können sogenannte redundante Operationen enthalten, d. h. Operationen, auf die zur Erledigung der Anfrage verzichtet werden kann. Besonders für kostenintensive Operationen, wie Join und Cartesisches Produkt, ist es interessant herauszufinden, ob sie in einem relationalen Ausdruck redundant vorkommen. In dieser Arbeit wird eine Tableauxmethode angewandt, um solche Redundanzen in relationalen Anfragen mit beliebigen Selektionsoperatoren erkennen zu können.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Aho, A. V., Sagiv, Y., Ullman, J. D.: Equivalences among relational expressions. SIAM J. Comp.8, 218–246 (1979).
Aho, A. V., Sagiv, Y., Ullman, J. D.: Efficient optimization of a class of relational expressions. ACM Trans. Database Systems4, 435–454 (1979).
Aho, A. V., Beeri, C., Ullman, J. D.: Theory of joins in relational databases. ACM Trans. Database Syst. Y,3, 297–314 (1979).
Chandra, A. K., Merlin, P. M.: Optimal implementations of conjunctive queries in relational databases. Proc. 1st Ann. ACM Symp. on Theory of Computing, Boulder, Colo., 1977, 77–90.
Codd, E. F.: A relational model of data for large shared data banks. Comm. of the ACM13, 377–387 (1970).
Codd, E. F.: Further normalization of the database relational model. In: Database Systems (Rustin, R., ed.), Englewood Cliffs, N. J.: Prentice-Hall.
Klug, Antony: Locking expressions for increased database concurrency. J. ACM30, 36–54 (1983).
Majster-Cederbaum, M. E.: Conjunctive queries with selection operators. Submitted for publication.
Ott, N., Horlaender, K.: Removing rendundant join operations in queries involving views. TR 82.03.003, Technical Report, IBM Scientific Center Heidelberg, 1982.
Ott, N.: On the problem of removing redundant join operations, TR 80.01.002, IBM Scientific Center, Heidelberg 1980.
Pecherer, R. M.: Efficient evaluation of expressions in relational algebra. Proc. ACM Pacific Conf., San Francisco, 1975, 44–49.
Sagiv, Y.: Optimization of queries in relational data bases. Ph. D. Thesis, Dept. of Electr. Engineering and Computer Science, Princeton University, 1978.
Sagiv, Y., Yonnakakis, M.: Equivalences among relational expressions with the union and difference operators. ACM27, 633–655 (1980).
Smith, J. M., Chang, P. Y.: Optimizing the performance of a relational algebra database interface. Comm. ACM18, 569–579 (1975).
Ullman, J. D.: Principles of Database Systems. Computer Science Press 1980.
Wong, E., Youssefi, K.: Decomposition — a strategy for query processing. ACM Trans. Database Syst.1, 223–241 (1976).
Zloof, M.: Query by example: the invocation and definition of tables and forms. Proc. ACM Int. Conf. on Very Large Data Bases, 1975.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Majster-Cederbaum, M.E. Elimination of redundant operations in relational queries with general selection operators. Computing 34, 303–323 (1985). https://doi.org/10.1007/BF02251832
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02251832