ACM SIGMOD Anthology TODS dblp.uni-trier.de

Synthesizing Third Normal Form Relations from Functional Dependencies.

Philip A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Trans. Database Syst. 1(4): 277-298(1976)
@article{DBLP:journals/tods/Bernstein76,
  author    = {Philip A. Bernstein},
  title     = {Synthesizing Third Normal Form Relations from Functional Dependencies},
  journal   = {ACM Trans. Database Syst.},
  volume    = {1},
  number    = {4},
  year      = {1976},
  pages     = {277-298},
  ee        = {http://doi.acm.org/10.1145/320493.320489, db/journals/tods/Bernstein76.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

It has been proposed that the description of a relational database can be formulated as a set of functional relationships among database attributes. These functional relationships can then be used to synthesize algorithmically a relational schema. It is the purpose of this paper to present an effective procedure for performing such a synthesis. The schema that results from this procedure is proved to be in Codd's third normal form and to contain the fewest possible number of relations. Problems with earlier attempts to construct such a procedure are also discussed.

Copyright © 1976 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]
William Ward Armstrong: Dependency Structures of Data Base Relationships. IFIP Congress 1974: 580-583 BibTeX
[2]
...
[3]
Philip A. Bernstein, J. Richard Swenson, Dennis Tsichritzis: A Unified Approach to Functional Dependencies and Relations. SIGMOD Conference 1975: 237-245 BibTeX
[4]
...
[5]
...
[6]
...
[7]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[8]
E. F. Codd: Further Normalization of the Data Base Relational Model. IBM Research Report, San Jose, California RJ909: (1971) BibTeX
[9]
...
[10]
...
[11]
...
[12]
...

Referenced by

  1. Sin Yeung Lee, Mong-Li Lee, Tok Wang Ling, Leonid A. Kalinichenko: Designing Good Semi-Structured Databases and Conceptual Modeling. ER 1999: 131-145
  2. Richard T. Snodgrass, Hector Garcia-Molina, Tomasz Imielinski, David Maier, Patricia G. Selinger, Jeffrey D. Ullman: Reminiscences on Influential Papers. SIGMOD Record 27(3): 33-35(1998)
  3. Gultekin Özsoyoglu, Veli Hakkoymaz, Joel Kraft: Automating the Assembly of Presentations from Multimedia Databases. ICDE 1996: 593-601
  4. Sudha Ram: Deriving Functional Dependencies from the Entity-Relationship Model. Commun. ACM 38(9): 95-107(1995)
  5. John L. Knapp: Uniqueness Conditions for ER Representations. OOER 1995: 296-307
  6. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  7. Dominique Laurent, Nicolas Spyratos: A Partition Model Approach to Updating Universal Scheme Interfaces. IEEE Trans. Knowl. Data Eng. 6(2): 316-330(1994)
  8. Roger H. L. Chiang, Terence M. Barron, Veda C. Storey: Performance Evaluation of Reverse Engineering Relational Databases into Extended Entity-Relationship Models. ER 1993: 352-363
  9. Tok Wang Ling, Cheng Hian Goh: Logical Database Design with Inclusion Dependencies. ICDE 1992: 642-649
  10. Ke Wang: Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation. SIGMOD Conference 1990: 74-83
  11. Jürgen M. Janas: Covers for Functional Independencies. MFDBS 1989: 254-268
  12. Margareta Dina Draghici: An Extended View on Data Base Conceptual Design. MFDBS 1989: 148-171
  13. Paul Johannesson, Katalin Kalman: A Method for Translating Relational Schemas into Conceptual Schemas. ER 1989: 271-285
  14. David W. Embley, Tok Wang Ling: Synergistic Database Design with an Extended Entity-Relationship Model. ER 1989: 111-128
  15. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  16. Jim Diederich, Jack Milton: New Methods and Fast Algorithms for Database Normalization. ACM Trans. Database Syst. 13(3): 339-365(1988)
  17. Li-Yan Yuan, Z. Meral Özsoyoglu: Logical Design of Relational Database Systems. PODS 1987: 38-47
  18. Jeffrey D. Ullman: Database Theory: Past and Future. PODS 1987: 1-10
  19. Georg Gottlob: Computing Covers for Embedded Functional Dependencies. PODS 1987: 58-69
  20. Detlev Ruland, Dietmar Seipel: Designing Alpha-Acyclic BCNF-Database Schemes. MFDBS 1987: 197-209
  21. Hans Janssens: A Theory of Reference Graphs in Relational Databases. MFDBS 1987: 159-180
  22. Paul C. Gilmore: A Foundation for the Entity Relationship Approach: How and Why. ER 1987: 95-113
  23. Catriel Beeri, Michael Kifer: An Integrated Approach to Logical Design of Relational Database Schemes. ACM Trans. Database Syst. 11(2): 134-158(1986)
  24. Toby J. Teorey, Dongqing Yang, James P. Fry: A Logical Design Methodology for Relational Databases Using the Extended Entity-Relationship Model. ACM Comput. Surv. 18(2): 197-222(1986)
  25. Carlo Batini, Maurizio Lenzerini, Shamkant B. Navathe: A Comparative Analysis of Methodologies for Database Schema Integration. ACM Comput. Surv. 18(4): 323-364(1986)
  26. Li-Yan Yuan, Z. Meral Özsoyoglu: Unifying Functional and Multivalued Dependencies for Relational Database Design. PODS 1986: 183-190
  27. Detlev Ruland, Dietmar Seipel: Alpha-Acyclic Decompositions of Relational Database Schemes. PODS 1986: 191-201
  28. Joachim Biskup, Hans Hermann Brüggemann, L. Schnetgöke, M. Kramer: One Flavor Assumption and Gamma-Acyclicity for Universal Relation Views. PODS 1986: 148-159
  29. André Flory, Salvatore T. March: SCRABBLE: A Local Database Management System. ER 1986: 271-286
  30. Sukhamay Kundu: An Improved Algorithm for Finding a Key of a Relation. PODS 1985: 189-192
  31. Tok Wang Ling: A Normal Form For Entity-Relationship Diagrams. ER 1985: 24-35
  32. Lynette I. Brady: A Universal Relation Assumption Based on Entities and Relationships. ER 1985: 208-215
  33. David Maier, Jeffrey D. Ullman, Moshe Y. Vardi: On the Foundations of the Universal Relation Model. ACM Trans. Database Syst. 9(2): 283-308(1984)
  34. 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)
  35. Hirofumi Katsuno: An Extension of Conflict-Free Multivalued Dependency Sets. ACM Trans. Database Syst. 9(2): 309-326(1984)
  36. Shamkant B. Navathe, T. Sashidhar, Ramez Elmasri: Relationship Merging in Schema Integration. VLDB 1984: 78-90
  37. Catriel Beeri, Michael Kifer: Comprehensive Approach to the Design of Relational Database Schemes. VLDB 1984: 196-207
  38. Richard Hull: Relative Information Capacity of Simple Relational Database Schemata. PODS 1984: 97-109
  39. Ramez Elmasri, Shamkant B. Navathe: Object Integration in Logical Database Design. ICDE 1984: 426-433
  40. Jeffrey D. Ullman: On Kent's "Consequences of Assuming a Universal Relation". ACM Trans. Database Syst. 8(4): 637-643(1983)
  41. Yehoshua Sagiv: A Characterization of Globally Consistent Databases and Their Correct Access Paths. ACM Trans. Database Syst. 8(2): 266-286(1983)
  42. Marc H. Graham: Functions in Databases. ACM Trans. Database Syst. 8(1): 81-109(1983)
  43. Hiroshi Arisawa, Kunihiko Moriya, Takao Miura: Operations and the Properties on Non-First-Normal-Form Relational Databases. VLDB 1983: 197-204
  44. David Maier, David Rozenshtein, David Scott Warren: Windows on the World. SIGMOD Conference 1983: 68-78
  45. Sharon McCure Kuck, Yehoshua Sagiv: Designing Globally Consistent Network Schemas. SIGMOD Conference 1983: 185-195
  46. David Maier, Jeffrey D. Ullman, Moshe Y. Vardi: The Revenge of the JD. PODS 1983: 279-287
  47. Catriel Beeri, Michael Kifer: Elimination of Intersection Anomalies from Database Schemes. PODS 1983: 340-351
  48. William Kent: Fact-Based Data Analysis and Design. ER 1983: 3-53
  49. C. Robert Carlson, Adarsh K. Arora: UPM: A Formal Tool for Expressing Database Update Semantics. ER 1983: 517-525
  50. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents
  51. 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)
  52. Carlo Zaniolo: A New Normal Form for the Design of Relational Database Schemata. ACM Trans. Database Syst. 7(3): 489-499(1982)
  53. Anthony C. Klug, Rod Price: Determining View Dependencies Using Tableaux. ACM Trans. Database Syst. 7(3): 361-380(1982)
  54. 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)
  55. Tomasz Imielinski, Witold Lipski Jr.: A Technique for Translating States Between Database Schemata. SIGMOD Conference 1982: 61-68
  56. Tomasz Imielinski, Witold Lipski Jr.: A Systematic Approach to Relational Database Theory. SIGMOD Conference 1982: 8-14
  57. Moshe Y. Vardi: The Implication and Finite Implication Problems for Typed Template Dependencies. PODS 1982: 230-238
  58. Jeffrey D. Ullman: The U. R. Strikes Back. PODS 1982: 10-22
  59. Sharon McCure Kuck, Yehoshua Sagiv: A Universal Relation Database System Implemented via the Network Model. PODS 1982: 147-157
  60. Paolo Atzeni, Douglas Stott Parker Jr.: Assumptions in Relational Database Theory. PODS 1982: 1-9
  61. Carlo Zaniolo, Michel A. Melkanoff: On the Design of Relational Database Schemata. ACM Trans. Database Syst. 6(1): 1-47(1981)
  62. 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)
  63. Y. Edmund Lien: Hierarchical Schemata for Relational Databases. ACM Trans. Database Syst. 6(1): 48-69(1981)
  64. Ronald Fagin: A Normal Form for Relational Databases That Is Based on Domians and Keys. ACM Trans. Database Syst. 6(3): 387-415(1981)
  65. Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94
  66. Yehoshua Sagiv: Can We Use the Universal Instance Assumption Without Using Nulls? SIGMOD Conference 1981: 108-120
  67. Asuman Dogac, Peter P. Chen: Entity-Relationship Model in the ANSI/SPARC Framework. ER 1981: 357-374
  68. Anthony C. Klug: Calculating Constraints on Relational Expressions. ACM Trans. Database Syst. 5(3): 260-290(1980)
  69. Catriel Beeri: On the Membership Problem for Functional and Multivalued Dependencies in Relational Databases. ACM Trans. Database Syst. 5(3): 241-259(1980)
  70. William Ward Armstrong, Claude Delobel: Decomposition and Functional Dependencies in Relations. ACM Trans. Database Syst. 5(4): 404-430(1980)
  71. Steven H. Spewak: A Pragmatic Approach to Database Design. VLDB 1980: 151-152
  72. Peter Honeyman: Extension Joins. VLDB 1980: 239-244
  73. Philip A. Bernstein, Nathan Goodman: What does Boyce-Codd Normal Form Do? VLDB 1980: 245-259
  74. David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979)
  75. 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)
  76. Alfred V. Aho, Catriel Beeri, Jeffrey D. Ullman: The Theory of Joins in Relational Databases. ACM Trans. Database Syst. 4(3): 297-314(1979)
  77. Douglas Stott Parker Jr., Claude Delobel: Algorithmic Applications for a new Result on Multivalued Dependencies. VLDB 1979: 67-74
  78. Sylvia L. Osborn: Towards a Universal Relation Interface. VLDB 1979: 52-60
  79. Barron C. Housel, Vance E. Waddle, S. Bing Yao: The Functional Dependency Model for Logical Database Design. VLDB 1979: 194-208
  80. Edward Sciore: Improving Semantic Specification in a Relational Database. SIGMOD Conference 1979: 170-178
  81. Ronald Fagin: Normal Forms and Relational Database Operators. SIGMOD Conference 1979: 153-160
  82. Joachim Biskup, Umeshwar Dayal, Philip A. Bernstein: Synthesizing Independent Database Schemas. SIGMOD Conference 1979: 143-151
  83. Eugene Wong, Randy H. Katz: Logical Design and Schema Conversion for Relational and DBTG Databases. ER 1979: 311-322
  84. A. Min Tjoa, Roland Wagner: Some Considerations on the Entity-Relationship Model. ER 1979: 145-154
  85. Peter A. Ng, J. F. Paul: A Formal Definition of Entity-Relationship Models. ER 1979: 211-230
  86. H. Hsu, Nick Roussopoulos: Database Conceptual Modelling. ER 1979: 259-276
  87. Claude Delobel: Normalization and Hierarchical Dependencies in the Relational Data Model. ACM Trans. Database Syst. 3(3): 201-222(1978)
  88. K. C. Toth, Samy A. Mahmoud, J. Spruce Riordon, O. Sherif: The ADD System: An Architecture for Distributed Databases. VLDB 1978: 462-471
  89. John Miles Smith: A Normal Form for Abstract Syntax. VLDB 1978: 156-162
  90. Jean-Marie Nicolas: Mutual Dependencies and Some Results on Undecomposable Relations. VLDB 1978: 360-367
  91. Odile Foucaut, Colette Rolland: Concepts for Design of an Information System Conceptual Schema and its Utilization in the REMORA Project. VLDB 1978: 342-350
  92. Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124
  93. Adarsh K. Arora, C. Robert Carlson: The Information Preserving Properties of Relational Database Transformations. VLDB 1978: 352-359
  94. Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977)
  95. Yuzuru Tanaka, Takao Tsuda: Decomposition and Composition of a Relational Database. VLDB 1977: 454-462
  96. Yahiko Kambayashi, Katsumi Tanaka, Shuzo Yajima: A Relational Data Language with Simplified Binary Relation Handling Capability. VLDB 1977: 338-350
  97. Ronald Fagin: The Decomposition Versus Synthetic Approach to Relational Database Design. VLDB 1977: 441-446
  98. Peter P. Chen, S. Bing Yao: Design and Performance Tools for Data Base Systems. VLDB 1977: 3-15
  99. Catriel Beeri, Ronald Fagin, John H. Howard: A Complete Axiomatization for Functional and Multivalued Dependencies in Database Relations. SIGMOD Conference 1977: 47-61
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:36 2008