ACM SIGMOD Anthology TODS dblp.uni-trier.de

Efficient Optimization of Simple Chase Join Expressions.

Paolo Atzeni, Edward P. F. Chan: Efficient Optimization of Simple Chase Join Expressions. ACM Trans. Database Syst. 14(2): 212-230(1989)
@article{DBLP:journals/tods/AtzeniC89,
  author    = {Paolo Atzeni and
               Edward P. F. Chan},
  title     = {Efficient Optimization of Simple Chase Join Expressions},
  journal   = {ACM Trans. Database Syst.},
  volume    = {14},
  number    = {2},
  year      = {1989},
  pages     = {212-230},
  ee        = {http://doi.acm.org/10.1145/63500.63520, db/journals/tods/AtzeniC89.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Simple chase join expressions are relational algebra expressions, involving only projection and join operators, defined on the basis of the functional dependencies associated with the database scheme. They are meaningful in the weak instance model, because for certain classes of schemes, including independent schemes, the total projections of the repesentative instance can be computed by means of unions of simple chase join expressions. We show how unions of simple chase join expressions can be optimized efficiently, without constructing and chasing the corresponding tableaux. We also present efficient algorithms for testing containment and equivalence, and for optimizing individual simple chase join expressions.

Copyright © 1989 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[1]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX
[2]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Optimization of a Class of Relational Expressions. ACM Trans. Database Syst. 4(4): 435-454(1979) BibTeX
[3]
Paolo Atzeni, Edward P. F. Chan: Efficient Query Answering in the Representative Instance Approach. PODS 1985: 181-188 BibTeX
[4]
Paolo Atzeni, Douglas Stott Parker Jr.: Assumptions in Relational Database Theory. PODS 1982: 1-9 BibTeX
[5]
Catriel Beeri, Philip A. Bernstein: Computational Problems Related to the Design of Normal Form Relational Schemas. ACM Trans. Database Syst. 4(1): 30-59(1979) BibTeX
[6]
...
[7]
Edward P. F. Chan, Paolo Atzeni: On the Properties and Characterization of Connection-tap-free Schemes. PODS 1986: 140-147 BibTeX
[8]
Edward P. F. Chan, Alberto O. Mendelzon: Answering queries on embedded-complete database schemes. J. ACM 34(2): 349-375(1987) BibTeX
[9]
Edward P. F. Chan, Alberto O. Mendelzon: Independent and Separable Database Schemes. SIAM J. Comput. 16(5): 841-851(1987) BibTeX
[10]
Peter J. Downey, Ravi Sethi, Robert Endre Tarjan: Variations on the Common Subexpression Problem. J. ACM 27(4): 758-771(1980) BibTeX
[11]
Marc H. Graham, Alberto O. Mendelzon: Strong Equivalence of Relational Wxpressions Under Dependencies. Inf. Process. Lett. 14(2): 57-62(1982) BibTeX
[12]
Marc H. Graham, Mihalis Yannakakis: Independent Database Schemas. J. Comput. Syst. Sci. 28(1): 121-141(1984) BibTeX
[13]
Peter Honeyman: Extension Joins. VLDB 1980: 239-244 BibTeX
[14]
Peter Honeyman: Testing satisfaction of functional dependencies. J. ACM 29(3): 668-677(1982) BibTeX
[15]
Minoru Ito, Motoaki Iwasaki, Tadao Kasami: Some Results on the Representative Instance in Relational Databases. SIAM J. Comput. 14(2): 334-354(1985) BibTeX
[16]
William Kent: Consequences of Assuming a Universal Relation. ACM Trans. Database Syst. 6(4): 539-556(1981) BibTeX
[17]
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX
[18]
David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX
[19]
David Maier, David Rozenshtein, David Scott Warren: Window Functions. Advances in Computing Research 3: 213-246(1986) BibTeX
[20]
David Maier, Jeffrey D. Ullman, Moshe Y. Vardi: On the Foundations of the Universal Relation Model. ACM Trans. Database Syst. 9(2): 283-308(1984) BibTeX
[21]
Alberto O. Mendelzon: Database States and Their Tableaux. ACM Trans. Database Syst. 9(2): 264-282(1984) BibTeX
[22]
Yehoshua Sagiv: Can We Use the Universal Instance Assumption Without Using Nulls? SIGMOD Conference 1981: 108-120 BibTeX
[23]
Yehoshua Sagiv: A Characterization of Globally Consistent Databases and Their Correct Access Paths. ACM Trans. Database Syst. 8(2): 266-286(1983) BibTeX
[24]
Yehoshua Sagiv: Evaluation of Queries in Independent Database Schemes. J. ACM 38(1): 120-161(1991) BibTeX
[25]
Yehoshua Sagiv: Quadratic Algorithms for Minimizing Joins in Restricted Relational Expressions. SIAM J. Comput. 12(2): 316-328(1983) BibTeX
[26]
Yehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655(1980) BibTeX
[27]
Jeffrey D. Ullman: The U. R. Strikes Back. PODS 1982: 10-22 BibTeX
[28]
Jeffrey D. Ullman: Universal Relation Interfaces for Database Systems. IFIP Congress 1983: 243-252 BibTeX
[29]
Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94 BibTeX
[30]
Mihalis Yannakakis: Querying Weak Instances. Advances in Computing Research 3: 185-211(1986) BibTeX

Referenced by

  1. Mark Levene, George Loizou: Database Design for Incomplete Relations. ACM Trans. Database Syst. 24(1): 80-125(1999)
  2. Paolo Atzeni, Riccardo Torlone: Efficient Updates to Independent Schemes in the Weak Instance Model. SIGMOD Conference 1990: 84-93
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:06 2008