dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

Algorithms for Acyclic Database Schemes.

Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94
@inproceedings{DBLP:conf/vldb/Yannakakis81,
  author    = {Mihalis Yannakakis},
  title     = {Algorithms for Acyclic Database Schemes},
  booktitle = {Very Large Data Bases, 7th International Conference, September
               9-11, 1981, Cannes, France, Proceedings},
  publisher = {IEEE Computer Society},
  year      = {1981},
  pages     = {82-94},
  ee        = {db/conf/vldb/Yannakakis81.html},
  crossref  = {DBLP:conf/vldb/81},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Many real-world situations can be captured by a set of functional dependencies and a single join dependency of a particular form called acyclic [B..]. The join dependency corresponds to a natural decomposition into meaningfull objects (an acyclic database scheme). 0ur purpose in this paper is to describe efficient algorithms in this setting for various problems, such as computing projections, minimizing joins, inferring dependencies, and testing for dependency satisfaction.

Copyright © 1981 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.


ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings. IEEE Computer Society 1981
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ASU1]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ba]
...
[Be]
Catriel Beeri: On the Membership Problem for Functional and Multivalued Dependencies in Relational Databases. ACM Trans. Database Syst. 5(3): 241-259(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BB]
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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[B..]
Catriel Beeri, Ronald Fagin, David Maier, Alberto O. Mendelzon, Jeffrey D. Ullman, Mihalis Yannakakis: Properties of Acyclic Database Schemes. STOC 1981: 355-362 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BV]
Catriel Beeri, Moshe Y. Vardi: On the Properties of Join Dependencies. Advances in Data Base Theory 1979: 25-71 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ber]
Philip A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Trans. Database Syst. 1(4): 277-298(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BG]
...
[Bg]
...
[C]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[F]
Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[H]
Peter Honeyman: Testing satisfaction of functional dependencies. J. ACM 29(3): 668-677(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HLY]
Peter Honeyman, Richard E. Ladner, Mihalis Yannakakis: Testing the Universal Instance Assumption. Inf. Process. Lett. 10(1): 14-19(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[L]
Y. Edmund Lien: On the Equivalence of Database Models. J. ACM 29(2): 333-362(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[M]
...
[MMS]
David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MSY]
David Maier, Yehoshua Sagiv, Mihalis Yannakakis: On the Complexity of Testing Implications of Functional and Join Dependencies. J. ACM 28(4): 680-695(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[R]
Jorma Rissanen: Theory of Relations for Databases - A Tutorial Survey. MFCS 1978: 536-551 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SU]
Fereidoon Sadri, Jeffrey D. Ullman: A Complete Axiomatization for a Large Class of Dependencies in Relational Databases. STOC 1980: 117-122 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sa]
Yehoshua Sagiv: Can We Use the Universal Instance Assumption Without Using Nulls? SIGMOD Conference 1981: 108-120 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SY]
Yehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[S]
Edward Sciore: Real-World MVD's. SIGMOD Conference 1981: 121-132 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[U]
Jeffrey D. Ullman: Principles of Database Systems, 1st Edition. Computer Science Press 1980
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[V]
Moshe Y. Vardi: Inferring Multivalued Dependencies From Functional and Join Dependencies. Acta Inf. 19: 305-324(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[W]
...
[Z]
...

Last update Mon Sep 17 22:00:36 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page