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

Computing Covers for Embedded Functional Dependencies.

Georg Gottlob: Computing Covers for Embedded Functional Dependencies. PODS 1987: 58-69
@inproceedings{DBLP:conf/pods/Gottlob87,
  author    = {Georg Gottlob},
  title     = {Computing Covers for Embedded Functional Dependencies},
  booktitle = {Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, March 23-25, 1987, San Diego,
               California},
  publisher = {ACM},
  year      = {1987},
  isbn      = {0-89791-223-3},
  pages     = {58-69},
  ee        = {http://doi.acm.org/10.1145/28659.28665, db/conf/pods/Gottlob87.html},
  crossref  = {DBLP:conf/pods/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

This paper deals with the problem of computing covers for the functional dependencies embedded in a subset of a given relation schema. We show how this problem can be simplified and present a new and efficient algorithm "Reduction By Resolution" (RBR) for its solution. Though the problem of computing covers for embedded dependencies is inherently exponential, our algorithm behaves polynomially for several classes of inputs. RBR can be used for the solution of some related problems in the theory of database design, such as deciding whether a given database scheme is in Boyce-Codd Normal Form or decomposing a scheme into Boyce-Codd Normal Form.

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

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 23-25, 1987, San Diego, California. ACM 1987, ISBN 0-89791-223-3
Contents BibTeX

Online Edition: ACM Digital Library

References

[1]
...
[2]
William Ward Armstrong, Claude Delobel: Decomposition and Functional Dependencies in Relations. ACM Trans. Database Syst. 5(4): 404-430(1980) BibTeX
[3]
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
[4]
Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124 BibTeX
[5]
Catriel Beeri, Ronald Fagin, John H. Howard: A Complete Axiomatization for Functional and Multivalued Dependencies in Database Relations. SIGMOD Conference 1977: 47-61 BibTeX
[6]
Catriel Beeri, Peter Honeyman: Preserving Functional Dependencies. SIAM J. Comput. 10(3): 647-656(1981) BibTeX
[7]
Philip A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Trans. Database Syst. 1(4): 277-298(1976) BibTeX
[8]
Stefano Ceri, Georg Gottlob: Normalization of Relations and PROLOG. Commun. ACM 29(6): 524-544(1986) BibTeX
[9]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[10]
E. F. Codd: Normalized Data Structure: A Brief Tutorial. SIGFIDET Workshop 1971: 1-17 BibTeX
[11]
...
[12]
...
[13]
...
[14]
...
[15]
Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) BibTeX
[16]
Patrick C. Fischer, Jiann H. Jou, Don-Min Tsou: Succinctness in Dependency Systems. Theor. Comput. Sci. 24: 323-329(1983) BibTeX
[17]
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX
[18]
...
[19]
Jiann H. Jou, Patrick C. Fischer: The Complexity of Recognizing 3NF Relation Schemes. Inf. Process. Lett. 14(4): 187-190(1982) BibTeX
[20]
Carol Helfgott LeDoux, Douglas Stott Parker Jr.: Reflections on Boyce-Codd Normal Form. VLDB 1982: 131-141 BibTeX
[21]
Claudio L. Lucchesi, Sylvia L. Osborn: Candidate Keys for Relations. J. Comput. Syst. Sci. 17(2): 270-279(1978) BibTeX
[22]
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX
[23]
Sylvia L. Osborn: Testing for Existence of a Covering Boyce-Codd normal Form. Inf. Process. Lett. 8(1): 11-14(1979) BibTeX
[24]
Jorma Rissanen: Independent Components of Relations. ACM Trans. Database Syst. 2(4): 317-325(1977) BibTeX
[25]
John Alan Robinson: A Machine-Oriented Logic Based on the Resolution Principle. J. ACM 12(1): 23-41(1965) BibTeX
[26]
...
[27]
...
[28]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[29]
Abraham Silberschatz, Henry F. Korth: Database System Concepts, 1st Edition. McGraw-Hill Book Company 1986, ISBN 0-07-100529-3
BibTeX

Referenced by

  1. Noel Novelli, Rosine Cicchetti: FUN: An Efficient Algorithm for Mining Functional and Embedded Dependencies. ICDT 2001: 189-203
  2. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  3. Ke Wang, Marc H. Graham: Constant-Time Maintainability: A Generalization of Independence. ACM Trans. Database Syst. 17(2): 201-246(1992)
  4. János Demetrovics, Leonid Libkin, Ilya B. Muchnik: Functional Dependencies and the Semilattice of Closed Classes. MFDBS 1989: 136-147
  5. Dina Bitton, Jeffrey Millman, Solveig Torgersen: A Feasibility and Performance Study of Dependency Inference. ICDE 1989: 635-641
  6. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
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:33:50 2009