ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions.

Edward P. F. Chan: Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions. SIGMOD Conference 1984: 149-163
@inproceedings{DBLP:conf/sigmod/Chan84,
  author    = {Edward P. F. Chan},
  editor    = {Beatrice Yormark},
  title     = {Optimal Computation of Total Projections with Unions of Simple
               Chase Join Expressions},
  booktitle = {SIGMOD'84, Proceedings of Annual Meeting, Boston, Massachusetts,
               June 18-21, 1984},
  publisher = {ACM Press},
  year      = {1984},
  pages     = {149-163},
  ee        = {http://doi.acm.org/10.1145/602259.602280, db/conf/sigmod/Chan84.html},
  crossref  = {DBLP:conf/sigmod/84},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The representative instance has been proposed as a query answering device in systems using the Universal Relation Interface. One approach is to use the total projections of the representative instance to generate the answer for a query. Associated with this approach is the problem of how to generate the total projections of the representative instance efficiently. We propose a generalization of extension joins, called chase join expressions, as a means to compute the total projections when functional dependencies are given as constraints. In particular, we identify an important subclass of chase join expressions called simple chase join expressions and show that the total projections with respect to a set of functional dependencies can be computed by unions of simple chase join expressions when an independent scheme is assumed. We also find a simple and efficient algorithm that minimizes the number of join operations in a union of simple chase join expressions.

Copyright © 1984 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.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Beatrice Yormark (Ed.): SIGMOD'84, Proceedings of Annual Meeting, Boston, Massachusetts, June 18-21, 1984. ACM Press 1984 BibTeX , SIGMOD Record 14(2)
Contents

Online Edition: ACM Digital Library


References

[ABU]
Alfred V. Aho, Catriel Beeri, Jeffrey D. Ullman: The Theory of Joins in Relational Databases. ACM Trans. Database Syst. 4(3): 297-314(1979) BibTeX
[AK]
...
[ASSU]
Alfred V. Aho, Yehoshua Sagiv, Thomas G. Szymanski, Jeffrey D. Ullman: Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions. SIAM J. Comput. 10(3): 405-421(1981) BibTeX
[ASU1]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX
[ASU2]
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
[BMSU]
Catriel Beeri, Alberto O. Mendelzon, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalence of Relational Database Schemes. SIAM J. Comput. 10(2): 352-370(1981) BibTeX
[BV]
Catriel Beeri, Moshe Y. Vardi: The Implication Problem for Data Dependencies. ICALP 1981: 73-85 BibTeX
[CK]
C. Robert Carlson, Robert S. Kaplan: A Generalized Access Path Model and its Application to a Relational Data Base System. SIGMOD Conference 1976: 143-154 BibTeX
[C]
...
[CM]
Edward P. F. Chan, Alberto O. Mendelzon: Independent and Separable Database Schemes. PODS 1983: 288-296 BibTeX
[Co]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[F]
Ronald Fagin: Horn clauses and database dependencies. J. ACM 29(4): 952-985(1982) BibTeX
[FMU]
Ronald Fagin, Alberto O. Mendelzon, Jeffrey D. Ullman: A Simplified Universal Relation Assumption and Its Properties. ACM Trans. Database Syst. 7(3): 343-360(1982) BibTeX
[GM1]
Marc H. Graham, Alberto O. Mendelzon: Strong Equivalence of Relational Wxpressions Under Dependencies. Inf. Process. Lett. 14(2): 57-62(1982) BibTeX
[GM2]
...
[GMV]
Marc H. Graham, Alberto O. Mendelzon, Moshe Y. Vardi: Notions of dependency satisfaction. J. ACM 33(1): 105-129(1986) BibTeX
[GY]
Marc H. Graham, Mihalis Yannakakis: Independent Database Schemas. PODS 1982: 199-204 BibTeX
[H1]
Peter Honeyman: Extension Joins. VLDB 1980: 239-244 BibTeX
[H2]
Peter Honeyman: Testing satisfaction of functional dependencies. J. ACM 29(3): 668-677(1982) BibTeX
[KU]
Henry F. Korth, Gabriel M. Kuper, Joan Feigenbaum, Allen Van Gelder, Jeffrey D. Ullman: System/U: A Database System Based on the Universal Relation Assumption. ACM Trans. Database Syst. 9(3): 331-347(1984) BibTeX
[L]
...
[MMS]
David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX
[MRW]
David Maier, David Rozenshtein, David Scott Warren: Windows on the World. SIGMOD Conference 1983: 68-78 BibTeX
[MU]
David Maier, Jeffrey D. Ullman: Maximal Objects and the Semantics of Universal Relation Databases. ACM Trans. Database Syst. 8(1): 1-14(1983) BibTeX
[MUV]
David Maier, Jeffrey D. Ullman, Moshe Y. Vardi: The Revenge of the JD. PODS 1983: 279-287 BibTeX
[MW]
David Maier, David Scott Warren: Specifying Connections for a Universal Relation Scheme Database. SIGMOD Conference 1982: 1-7 BibTeX
[O]
Sylvia L. Osborn: Towards a Universal Relation Interface. VLDB 1979: 52-60 BibTeX
[S1]
Yehoshua Sagiv: Can We Use the Universal Instance Assumption Without Using Nulls? SIGMOD Conference 1981: 108-120 BibTeX
[S2]
Yehoshua Sagiv: A Characterization of Globally Consistent Databases and Their Correct Access Paths. ACM Trans. Database Syst. 8(2): 266-286(1983) BibTeX
[S3]
Yehoshua Sagiv: Quadratic Algorithms for Minimizing Joins in Restricted Relational Expressions. SIAM J. Comput. 12(2): 316-328(1983) BibTeX
[SY]
Yehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655(1980) BibTeX
[SP]
Kathryn L. Schenk, James R. Pinkert: An Algorithm for Servicing Multi-Relational Queries. SIGMOD Conference 1977: 10-20 BibTeX
[U]
Jeffrey D. Ullman: The U. R. Strikes Back. PODS 1982: 10-22 BibTeX
[V]
...
[Y1]
Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94 BibTeX
[Y2]
Mihalis Yannakakis: Querying Weak Instances. PODS 1984: 275-280 BibTeX

Referenced by

  1. Paolo Atzeni, Riccardo Torlone: Updating Relational Databases Through Weak Instance Interfaces. ACM Trans. Database Syst. 17(4): 718-745(1992)
  2. Héctor J. Hernández, Edward P. F. Chan: Constant-Time-Maintainable BCNF Database Schemes. ACM Trans. Database Syst. 16(4): 571-599(1991)
  3. Paolo Atzeni, Riccardo Torlone: Efficient Updates to Independent Schemes in the Weak Instance Model. SIGMOD Conference 1990: 84-93
  4. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  5. Edward P. F. Chan, Héctor J. Hernández: Independence-reducible Database Schemes. PODS 1988: 163-173
  6. Edward P. F. Chan, Héctor J. Hernández: On Designing Database Schemes Bounded or Constant-time-maintainable with respect to Functional Dependencies. PODS 1987: 48-57
  7. Paolo Atzeni, Maria Cristina De Bernardis: A New Basis for the Weak Instance Model. PODS 1987: 79-86
  8. Edward P. F. Chan, Héctor J. Hernández: On the Desirability of gamma-Acyclic BCNF Database Schemes. ICDT 1986: 105-122
  9. Paolo Atzeni, Edward P. F. Chan: Efficient Query Answering in the Representative Instance Approach. PODS 1985: 181-188
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:39:38 2009