ACM SIGMOD Anthology TODS dblp.uni-trier.de

Computational Problems Related to the Design of Normal Form Relational Schemas.

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)
@article{DBLP:journals/tods/BeeriB79,
  author    = {Catriel Beeri and
               Philip A. Bernstein},
  title     = {Computational Problems Related to the Design of Normal Form Relational
               Schemas},
  journal   = {ACM Trans. Database Syst.},
  volume    = {4},
  number    = {1},
  year      = {1979},
  pages     = {30-59},
  ee        = {http://doi.acm.org/10.1145/320064.320066, db/journals/tods/BeeriB79.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Problems related to functional dependencies and the algorithmic design of relational schemas are examined. Specifically, the following results are presented: (1) a tree model of derivations of functional dependencies from other functional dependencies; (2) a linear-time algorithm to test if a functional dependency is in the closure of a set of functional dependencies; (3) a quadratic-time implementation of Bernstein's third normal form schema synthesis algorithm.

Copyright © 1979 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, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX
[2]
William Ward Armstrong: Dependency Structures of Data Base Relationships. IFIP Congress 1974: 580-583 BibTeX
[3]
...
[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]
...
[7]
...
[8]
Philip A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Trans. Database Syst. 1(4): 277-298(1976) BibTeX
[9]
...
[10]
Philip A. Bernstein, J. Richard Swenson, Dennis Tsichritzis: A Unified Approach to Functional Dependencies and Relations. SIGMOD Conference 1975: 237-245 BibTeX
[11]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[12]
E. F. Codd: Further Normalization of the Data Base Relational Model. IBM Research Report, San Jose, California RJ909: (1971) BibTeX
[13]
E. F. Codd: Recent Investigations in Relational Data Base Systems. IFIP Congress 1974: 1017-1021 BibTeX
[14]
...
[15]
...
[16]
...
[17]
Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) BibTeX
[18]
...
[19]
Ronald Fagin: The Decomposition Versus Synthetic Approach to Relational Database Design. VLDB 1977: 441-446 BibTeX
[20]
...
[21]
...
[22]
Claudio L. Lucchesi, Sylvia L. Osborn: Candidate Keys for Relations. J. Comput. Syst. Sci. 17(2): 270-279(1978) BibTeX
[23]
...
[24]
Jorma Rissanen: Independent Components of Relations. ACM Trans. Database Syst. 2(4): 317-325(1977) BibTeX
[25]
...
[26]
Hans Albrecht Schmid, J. Richard Swenson: On the Semantics of the Relational Data Model. SIGMOD Conference 1975: 211-223 BibTeX
[27]
...

Referenced by

  1. Noel Novelli, Rosine Cicchetti: FUN: An Efficient Algorithm for Mining Functional and Embedded Dependencies. ICDT 2001: 189-203
  2. Mark Levene, George Loizou: Database Design for Incomplete Relations. ACM Trans. Database Syst. 24(1): 80-125(1999)
  3. Zahir Tari, John Stokes, Stefano Spaccapietra: Object Normal Forms and Dependency Constraints for Object-Oriented Schemata. ACM Trans. Database Syst. 22(4): 513-569(1997)
  4. David E. Simmen, Eugene J. Shekita, Timothy Malkemus: Fundamental Techniques for Order Optimization. SIGMOD Conference 1996: 57-67
  5. Dimitri Theodoratos: Deductive Object Oriented Schemas. ER 1996: 58-72
  6. David E. Simmen, Eugene J. Shekita, Timothy Malkemus: Fundamental Techniques for Order Optimization. EDBT 1996: 625-628
  7. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  8. Martha Escobar-Molano, Richard Hull, Dean Jacobs: Safety and Translation of Calculus Queries with Scalar Functions. PODS 1993: 253-264
  9. Grant E. Weddell: Reasoning about Functional Dependencies Generalized for Semantic Data Models. ACM Trans. Database Syst. 17(1): 32-64(1992)
  10. Ke Wang, Marc H. Graham: Constant-Time Maintainability: A Generalization of Independence. ACM Trans. Database Syst. 17(2): 201-246(1992)
  11. Paolo Atzeni, Riccardo Torlone: Updating Relational Databases Through Weak Instance Interfaces. ACM Trans. Database Syst. 17(4): 718-745(1992)
  12. Héctor J. Hernández, Edward P. F. Chan: Constant-Time-Maintainable BCNF Database Schemes. ACM Trans. Database Syst. 16(4): 571-599(1991)
  13. Dimitri Theodoratos: Monadic Databases with Equality. MFDBS 1991: 74-88
  14. Ke Wang: Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation. SIGMOD Conference 1990: 74-83
  15. Paolo Atzeni, Edward P. F. Chan: Efficient Optimization of Simple Chase Join Expressions. ACM Trans. Database Syst. 14(2): 212-230(1989)
  16. Ke Wang: Can Constant-time Maintainability Be More Practical? PODS 1989: 120-127
  17. Jürgen M. Janas: Covers for Functional Independencies. MFDBS 1989: 254-268
  18. Dina Bitton, Jeffrey Millman, Solveig Torgersen: A Feasibility and Performance Study of Dependency Inference. ICDE 1989: 635-641
  19. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  20. K. V. S. V. N. Raju, Arun K. Majumdar: Fuzzy Functional Dependencies and Lossless Join Decomposition of Fuzzy Relational Database Systems. ACM Trans. Database Syst. 13(2): 129-166(1988)
  21. Jim Diederich, Jack Milton: New Methods and Fast Algorithms for Database Normalization. ACM Trans. Database Syst. 13(3): 339-365(1988)
  22. Héctor J. Hernández, Edward P. F. Chan: A Characterization of Constant-time-mainteinability for BCNF Database Schemes. SIGMOD Conference 1988: 209-217
  23. Michael Kifer, Raghu Ramakrishnan, Abraham Silberschatz: An Axiomatic Approach to Deciding Query Safety in Deductive Databases. PODS 1988: 52-60
  24. Z. Meral Özsoyoglu, Li-Yan Yuan: Reduced MVDs and Minimal Covers. ACM Trans. Database Syst. 12(3): 377-394(1987)
  25. Li-Yan Yuan, Z. Meral Özsoyoglu: Logical Design of Relational Database Systems. PODS 1987: 38-47
  26. Jeffrey D. Ullman: Database Theory: Past and Future. PODS 1987: 1-10
  27. Georg Gottlob: Computing Covers for Embedded Functional Dependencies. PODS 1987: 58-69
  28. Paul De Bra: Functional Dependency Implications, Inducing Horizontal Decompositions. MFDBS 1987: 80-98
  29. Catriel Beeri, Michael Kifer: An Integrated Approach to Logical Design of Relational Database Schemes. ACM Trans. Database Syst. 11(2): 134-158(1986)
  30. Hiroshi Arisawa, Takao Miura: On the Properties of Extended Inclusion Dependencies. VLDB 1986: 449-456
  31. Li-Yan Yuan, Z. Meral Özsoyoglu: Unifying Functional and Multivalued Dependencies for Relational Database Design. PODS 1986: 183-190
  32. Edward P. F. Chan, Héctor J. Hernández: On the Desirability of gamma-Acyclic BCNF Database Schemes. ICDT 1986: 105-122
  33. Paul De Bra: Horizontal Decompositions Based on Functional-Dependency-Set-Implications. ICDT 1986: 157-170
  34. David S. Reiner, Gretchen Brown, Mark Friedell, John Lehman, Richard McKee, Penny Rheingans, Arnon Rosenthal: A Database Designer's Workbench. ER 1986: 347-360
  35. Mokrane Bouzeghoub, Georges Gardarin, Elisabeth Métais: Database Design Tools: An Expert System Approach. VLDB 1985: 82-95
  36. Jacob Stein, David Maier: Relaxing the Universal Relation Scheme Assumption. PODS 1985: 76-84
  37. Yehoshua Sagiv: On Computing Restricted Projections of Representative Instances. PODS 1985: 171-180
  38. Sukhamay Kundu: An Improved Algorithm for Finding a Key of a Relation. PODS 1985: 189-192
  39. Alessandro D'Atri, Domenico Saccà: Equivalence and Mapping of Database Schemes. VLDB 1984: 187-195
  40. Yehoshua Sagiv: A Characterization of Globally Consistent Databases and Their Correct Access Paths. ACM Trans. Database Syst. 8(2): 266-286(1983)
  41. Gösta Grahne, Kari-Jouko Räihä: Database Decomposition into Fourth Normal Form. VLDB 1983: 186-196
  42. Peter Honeyman, Edward Sciore: A New Characterization of Independence. SIGMOD Conference 1983: 92-96
  43. Domenico Saccà: On the Recognition of Coverings of Acyclic Database Hypergraphs. PODS 1983: 297-304
  44. John C. Mitchell: Inference Rules for Functional and Inclusion Dependencies. PODS 1983: 58-69
  45. Seymour Ginsburg, Richard Hull: Sort Sets in the Relational Model. PODS 1983: 332-339
  46. Stavros S. Cosmadakis, Christos H. Papadimitriou: Updates of Relational Views. PODS 1983: 317-331
  47. Catriel Beeri, Michael Kifer: Elimination of Intersection Anomalies from Database Schemes. PODS 1983: 340-351
  48. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents
  49. Carlo Zaniolo, Michel A. Melkanoff: A Formal Approach to the Definition and the Design of Conceptual Schemata for Database Systems. ACM Trans. Database Syst. 7(1): 24-59(1982)
  50. Carlo Zaniolo: A New Normal Form for the Design of Relational Database Schemata. ACM Trans. Database Syst. 7(3): 489-499(1982)
  51. Umeshwar Dayal, Philip A. Bernstein: On the Correct Translation of Update Operations on Relational Views. ACM Trans. Database Syst. 7(3): 381-416(1982)
  52. Carol Helfgott LeDoux, Douglas Stott Parker Jr.: Reflections on Boyce-Codd Normal Form. VLDB 1982: 131-141
  53. Sharon McCure Kuck, Yehoshua Sagiv: A Universal Relation Database System Implemented via the Network Model. PODS 1982: 147-157
  54. Marco A. Casanova, Ronald Fagin, Christos H. Papadimitriou: Inclusion Dependencies and Their Interaction with Functional Dependencies. PODS 1982: 171-176
  55. Carlo Zaniolo, Michel A. Melkanoff: On the Design of Relational Database Schemata. ACM Trans. Database Syst. 6(1): 1-47(1981)
  56. Tok Wang Ling, Frank Wm. Tompa, Tiko Kameda: An Improved Third Normal Form for Relational Databases. ACM Trans. Database Syst. 6(2): 329-346(1981)
  57. Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94
  58. Yehoshua Sagiv: Can We Use the Universal Instance Assumption Without Using Nulls? SIGMOD Conference 1981: 108-120
  59. Catriel Beeri: On the Membership Problem for Functional and Multivalued Dependencies in Relational Databases. ACM Trans. Database Syst. 5(3): 241-259(1980)
  60. Peter Honeyman: Extension Joins. VLDB 1980: 239-244
  61. Philip A. Bernstein: Errata: Computational Problems Related to the Design of Normal Form Relational Schemas. ACM Trans. Database Syst. 4(3): 396(1979)
  62. Douglas Stott Parker Jr., Claude Delobel: Algorithmic Applications for a new Result on Multivalued Dependencies. VLDB 1979: 67-74
  63. Joachim Biskup, Umeshwar Dayal, Philip A. Bernstein: Synthesizing Independent Database Schemas. SIGMOD Conference 1979: 143-151
  64. A. Min Tjoa, Roland Wagner: Some Considerations on the Entity-Relationship Model. ER 1979: 145-154
  65. Peter A. Ng, J. F. Paul: A Formal Definition of Entity-Relationship Models. ER 1979: 211-230
  66. Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124
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:38:39 2008