Reflections on Boyce-Codd Normal Form.

@inproceedings{DBLP:conf/vldb/LeDouxP82,
  author    = {Carol Helfgott LeDoux and
               Douglas Stott Parker Jr.},
  title     = {Reflections on Boyce-Codd Normal Form},
  booktitle = {Eigth International Conference on Very Large Data Bases, September
               8-10, 1982, Mexico City, Mexico, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1982},
  isbn      = {0-934613-14-1},
  pages     = {131-141},
  ee        = {db/conf/vldb/LeDouxP82.html},
  crossref  = {DBLP:conf/vldb/82},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The usefulness of Boyce-Codd Normal Form (BCNF) has been questioned by various researchers. A recent study showed that under common assumptions, BCNF no longer guaran- tees freedom from various 'anomalies', one of its purported virtues. Second, a BCNF covering is sometimes unattainable, i.e., some sets of FDs have no corresponding BCNF schema. Third, it is difficult to determine whether a given schema violates BCNF (doing so is known to be NP- complete).

This paper reviews the intent of the normal form, and suggests that these arguments may be discounted. We show that

• BCNF still provides a useful design criterion when such assumptions as the Universal Instance Assumption are dropped (although BCNF can be improved upon by taking into consideration the dynamic use of the database);
• even in schemata where BCNF is 'unattain- able', BCNF can be attained by unconven- tional means, typically by renaming or adding attributes to better capture the semantic content of the data;
• testing violation of BCNF seems to require exponential time only in the w,orst case where the set of 'interesting' dependencies (nontrivial dependencies in minimal form) in the dependency closure grows exponentially large. Such situations do not seem to typify the 'real world': We investi- gate a model of FD schemata, called the FD hierarchy model, similar to many other data models proposed in recent years. For this model the FD closure is always small, and testing violation of BCNF is not only not NP-complete, it is linear in the size of the input. We also point out a relationship between keys, FDs which violate BCNF, and FD closures.

Copyright © 1982 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/vldb7588 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

References

[Atzeni & Parker 1982]

Paolo Atzeni, Douglas Stott Parker Jr.: Assumptions in Relational Database Theory. PODS 1982: 1-9 BibTeX

[Beeri & Bernstein 1979]

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

[Bernstein & Goodman 1980]

Philip A. Bernstein, Nathan Goodman: What does Boyce-Codd Normal Form Do? VLDB 1980: 245-259 BibTeX

[Biskup et al.1979]

Joachim Biskup, Umeshwar Dayal, Philip A. Bernstein: Synthesizing Independent Database Schemas. SIGMOD Conference 1979: 143-151 BibTeX

[Codd 1972]

E. F. Codd: Further Normalization of the Data Base Relational Model. IBM Research Report, San Jose, California RJ909: (1971) BibTeX

[Date 1981]

...

[Delobel & Casey 1973]

...

[Fagin 1977]

...

[Kent 1978]

...

[Lien 1981]

Y. Edmund Lien: Hierarchical Schemata for Relational Databases. ACM Trans. Database Syst. 6(1): 48-69(1981) BibTeX

[Osborn 1979]

Sylvia L. Osborn: Testing for Existence of a Covering Boyce-Codd normal Form. Inf. Process. Lett. 8(1): 11-14(1979) BibTeX

[Parker & Delobel 1979]

Douglas Stott Parker Jr., Claude Delobel: Algorithmic Applications for a new Result on Multivalued Dependencies. VLDB 1979: 67-74 BibTeX

[Sagiv et al.1981]

Yehoshua Sagiv, Claude Delobel, Douglas Stott Parker Jr., Ronald Fagin: An Equivalence Between Relational Database Dependencies and a Fragment of Propositional Logic. J. ACM 28(3): 435-453(1981) BibTeX

[Sciore 1982]

Edward Sciore: Improving Database Schemes by Adding Attributes. PODS 1983: 379-383 BibTeX

[Ullman 1980]

Jeffrey D. Ullman: Principles of Database Systems, 1st Edition. Computer Science Press 1980
BibTeX

Referenced by

1. Héctor J. Hernández, Edward P. F. Chan: Constant-Time-Maintainable BCNF Database Schemes. ACM Trans. Database Syst. 16(4): 571-599(1991)
2. Héctor J. Hernández, Edward P. F. Chan: A Characterization of Constant-time-mainteinability for BCNF Database Schemes. SIGMOD Conference 1988: 209-217
3. Georg Gottlob: Computing Covers for Embedded Functional Dependencies. PODS 1987: 58-69
4. Edward P. F. Chan, Héctor J. Hernández: On the Desirability of gamma-Acyclic BCNF Database Schemes. ICDT 1986: 105-122
5. Robert Brown, Douglas Stott Parker Jr.: LAURA: A Formal Data Model and her Logical Design Methodology. VLDB 1983: 206-218
6. Edward Sciore: Inclusion Dependencies and the Universal Instance. PODS 1983: 48-57