ACM SIGMOD Anthology VLDB dblp.uni-trier.de

A Sophisticate's Introduction to Database Normalization Theory.

Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124
@inproceedings{DBLP:conf/vldb/BeeriBG78,
  author    = {Catriel Beeri and
               Philip A. Bernstein and
               Nathan Goodman},
  editor    = {S. Bing Yao},
  title     = {A Sophisticate's Introduction to Database Normalization Theory},
  booktitle = {Fourth International Conference on Very Large Data Bases, September
               13-15, 1978, West Berlin, Germany},
  publisher = {IEEE Computer Society},
  year      = {1978},
  pages     = {113-124},
  ee        = {db/conf/vldb/BeeriBG78.html},
  crossref  = {DBLP:conf/vldb/78},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Formal database semantics has concentrated on dependency constraints, such as functional and multivalued dependencies, and on normal forms for relations. Unfortunately, much of this work has been inaccessible to researchers outside this field, due to the unfamiliar formalism in which the work is couched. In addition, the lack of a single set of definitions has confused the relationships among certain results. This paper is intended to serve the two-fold purpose of introducing the main issues and theorems of formal database semantics to the uninitiated, and to clarify the terminology of the field.

Copyright © 1978 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 ... BibTeX

Printed Edition

S. Bing Yao (Ed.): Fourth International Conference on Very Large Data Bases, September 13-15, 1978, West Berlin, Germany. IEEE Computer Society 1978
Contents BibTeX

References

[1]
Alfred V. Aho, Catriel Beeri, Jeffrey D. Ullman: The Theory of Joins in Relational Data Bases (Extended Abstract). FOCS 1977: 107-113 BibTeX
[2]
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
[3]
William Ward Armstrong: Dependency Structures of Data Base Relationships. IFIP Congress 1974: 580-583 BibTeX
[4]
...
[5]
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
[6]
Catriel Beeri, Ronald Fagin, John H. Howard: A Complete Axiomatization for Functional and Multivalued Dependencies in Database Relations. SIGMOD Conference 1977: 47-61 BibTeX
[7]
Philip A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Trans. Database Syst. 1(4): 277-298(1976) BibTeX
[8]
...
[9]
Philip A. Bernstein, J. Richard Swenson, Dennis Tsichritzis: A Unified Approach to Functional Dependencies and Relations. SIGMOD Conference 1975: 237-245 BibTeX
[10]
Jean-Marc Cadiou: On Semantic Issues in the Relational Model of Data. MFCS 1976: 23-38 BibTeX
[11]
C. Robert Carlson, Robert S. Kaplan: A Generalized Access Path Model and its Application to a Relational Data Base System. SIGMOD Conference 1976: 143-154 BibTeX
[12]
Peter P. Chen: The Entity-Relationship Model - Toward a Unified View of Data. ACM Trans. Database Syst. 1(1): 9-36(1976) BibTeX
[13]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[14]
...
[15]
E. F. Codd: Recent Investigations in Relational Data Base Systems. IFIP Congress 1974: 1017-1021 BibTeX
[16]
...
[17]
...
[18]
...
[19]
...
[20]
...
[21]
...
[22]
Raymond Fadous, John Forsyth: Finding Candidate Keys for Relational Data Bases. SIGMOD Conference 1975: 203-210 BibTeX
[23]
Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) BibTeX
[24]
Ronald Fagin: The Decomposition Versus Synthetic Approach to Relational Database Design. VLDB 1977: 441-446 BibTeX
[25]
...
[26]
Michael Hammer, Dennis McLeod: Semantic Integrity in a Relational Data Base System. VLDB 1975: 25-47 BibTeX
[27]
...
[28]
...
[29]
Alberto O. Mendelzon: On Axiomatizing Multivalued Dependencies in Relational Databases. J. ACM 26(1): 37-44(1979) BibTeX
[30]
Jean-Marie Nicolas: Mutual Dependencies and Some Results on Undecomposable Relations. VLDB 1978: 360-367 BibTeX
[31]
Jorma Rissanen: Independent Components of Relations. ACM Trans. Database Syst. 2(4): 317-325(1977) BibTeX
[32]
Jorma Rissanen: Theory of Relations for Databases - A Tutorial Survey. MFCS 1978: 536-551 BibTeX
[33]
...
[34]
Kathryn L. Schenk, James R. Pinkert: An Algorithm for Servicing Multi-Relational Queries. SIGMOD Conference 1977: 10-20 BibTeX
[35]
Hans Albrecht Schmid, J. Richard Swenson: On the Semantics of the Relational Data Model. SIGMOD Conference 1975: 211-223 BibTeX
[36]
John Miles Smith, Diane C. P. Smith: Database Abstractions: Aggregation and Generalization. ACM Trans. Database Syst. 2(2): 105-133(1977) BibTeX
[37]
Yuzuru Tanaka, Takao Tsuda: Decomposition and Composition of a Relational Database. VLDB 1977: 454-462 BibTeX
[38]
...
[39]
...
[40]
Clement T. Yu, D. T. Johnson: On the Complexity of Finding the Set of Candidate Keys for a Given Set of Functional Dependencies. Inf. Process. Lett. 5(4): 100-101(1976) BibTeX
[41]
...

Referenced by

  1. 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)
  2. Joseph Albert, Yannis E. Ioannidis, Raghu Ramakrishnan: Conjunctive Query Equivalence of Keyed Relational Schemas. PODS 1997: 44-50
  3. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  4. Kazimierz Subieta, Florian Matthes, Joachim W. Schmidt, Andreas Rudloff: Viewers: A Data-World Analogue of Procedure Calls. VLDB 1993: 268-277
  5. Marie Duzi: Semantic Information Connected with Data. ICDT 1992: 376-390
  6. Victor M. Markowitz: A Relation Merging Technique for Relational Databases. ICDE 1992: 428-437
  7. Tok Wang Ling, Cheng Hian Goh: Logical Database Design with Inclusion Dependencies. ICDE 1992: 642-649
  8. Héctor J. Hernández, Edward P. F. Chan: Constant-Time-Maintainable BCNF Database Schemes. ACM Trans. Database Syst. 16(4): 571-599(1991)
  9. Ke Wang: Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation. SIGMOD Conference 1990: 74-83
  10. Victor M. Markowitz, Arie Shoshani: On the Correctness of Representing Extended Entity-Relationship Structures in the Relational Model. SIGMOD Conference 1989: 430-439
  11. Lotfi Lakhal, Rosine Cicchetti, Serge Miranda: RTL - A Relation and Table Language for Statistical Databases. MFDBS 1989: 285-300
  12. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  13. Héctor J. Hernández, Edward P. F. Chan: A Characterization of Constant-time-mainteinability for BCNF Database Schemes. SIGMOD Conference 1988: 209-217
  14. Henryk Rybinski: On First-Order-Logic Databases. ACM Trans. Database Syst. 12(3): 325-349(1987)
  15. Z. Meral Özsoyoglu, Li-Yan Yuan: Reduced MVDs and Minimal Covers. ACM Trans. Database Syst. 12(3): 377-394(1987)
  16. Z. Meral Özsoyoglu, Li-Yan Yuan: A New Normal Form for Nested Relations. ACM Trans. Database Syst. 12(1): 111-136(1987)
  17. Georg Gottlob: Computing Covers for Embedded Functional Dependencies. PODS 1987: 58-69
  18. Joachim Biskup, Uwe Räsch: The Equivalence Problem For Relational Database Schemes. MFDBS 1987: 42-70
  19. Catriel Beeri, Michael Kifer: An Integrated Approach to Logical Design of Relational Database Schemes. ACM Trans. Database Syst. 11(2): 134-158(1986)
  20. 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)
  21. Carlo Batini, Maurizio Lenzerini, Shamkant B. Navathe: A Comparative Analysis of Methodologies for Database Schema Integration. ACM Comput. Surv. 18(4): 323-364(1986)
  22. Marc H. Graham, Ke Wang: Constant Time Maintenance or The Triumph of the fd. PODS 1986: 202-216
  23. Edward P. F. Chan, Héctor J. Hernández: On the Desirability of gamma-Acyclic BCNF Database Schemes. ICDT 1986: 105-122
  24. Gabriel M. Kuper, Moshe Y. Vardi: On the Expressive Power of the Logical Data Model (Preliminary Report). SIGMOD Conference 1985: 180-187
  25. Z. Meral Özsoyoglu, Li-Yan Yuan: A Normal Form for Nested Relations. PODS 1985: 251-260
  26. Alberto O. Mendelzon: Database States and Their Tableaux. ACM Trans. Database Syst. 9(2): 264-282(1984)
  27. 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)
  28. Richard Hull: Relative Information Capacity of Simple Relational Database Schemata. PODS 1984: 97-109
  29. Gösta Grahne, Kari-Jouko Räihä: Dependency Characterizations for Acyclic Database Schemes. PODS 1984: 9-18
  30. Alessandro D'Atri, Marina Moscarini: On the Recognition and Design of Acyclic Databases. PODS 1984: 1-8
  31. Jeffrey D. Ullman: On Kent's "Consequences of Assuming a Universal Relation". ACM Trans. Database Syst. 8(4): 637-643(1983)
  32. William Kent: The Universal Relation Revisited. ACM Trans. Database Syst. 8(4): 644-648(1983)
  33. Marc H. Graham: Functions in Databases. ACM Trans. Database Syst. 8(1): 81-109(1983)
  34. Joachim Biskup: A Foundation of Codd's Relational Maybe-Operations. ACM Trans. Database Syst. 8(4): 608-636(1983)
  35. Gösta Grahne, Kari-Jouko Räihä: Database Decomposition into Fourth Normal Form. VLDB 1983: 186-196
  36. Hiroshi Arisawa, Kunihiko Moriya, Takao Miura: Operations and the Properties on Non-First-Normal-Form Relational Databases. VLDB 1983: 197-204
  37. Edward Sciore: Improving Database Schemes by Adding Attributes. PODS 1983: 379-383
  38. Stephen J. Hegner: Algebraic Aspects of Relational Database Decomposition. PODS 1983: 400-413
  39. Stavros S. Cosmadakis, Christos H. Papadimitriou: Updates of Relational Views. PODS 1983: 317-331
  40. Marco A. Casanova, Vânia Maria Ponte Vidal: Towards a Sound View Integration Methodology. PODS 1983: 36-47
  41. Catriel Beeri, Michael Kifer: Elimination of Intersection Anomalies from Database Schemes. PODS 1983: 340-351
  42. Marco A. Casanova, Jose E. Amaral de Sa: Designing Entity-Relationship Schemes for Conventional Information Systems. ER 1983: 265-277
  43. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents
  44. 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)
  45. Carlo Zaniolo: A New Normal Form for the Design of Relational Database Schemata. ACM Trans. Database Syst. 7(3): 489-499(1982)
  46. Anthony C. Klug, Rod Price: Determining View Dependencies Using Tableaux. ACM Trans. Database Syst. 7(3): 361-380(1982)
  47. 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)
  48. Umeshwar Dayal, Philip A. Bernstein: On the Correct Translation of Update Operations on Relational Views. ACM Trans. Database Syst. 7(3): 381-416(1982)
  49. Tomasz Imielinski, Witold Lipski Jr.: A Technique for Translating States Between Database Schemata. SIGMOD Conference 1982: 61-68
  50. Jirun Dong, Richard Hull: Applying Approximate Order Dependency to Reduce Indexing Space. SIGMOD Conference 1982: 119-127
  51. Moshe Y. Vardi: The Implication and Finite Implication Problems for Typed Template Dependencies. PODS 1982: 230-238
  52. Jeffrey D. Ullman: The U. R. Strikes Back. PODS 1982: 10-22
  53. Nicolas Spyratos: An Operational Approach to Data Bases. PODS 1982: 212-220
  54. Marc H. Graham, Mihalis Yannakakis: Independent Database Schemas. PODS 1982: 199-204
  55. Marco A. Casanova: A Theory of Data Dependencies over Relational Expressions. PODS 1982: 189-198
  56. Catriel Beeri, Henry F. Korth: Compatible Attributes in a Universal Relation. PODS 1982: 55-62
  57. Carlo Zaniolo, Michel A. Melkanoff: On the Design of Relational Database Schemata. ACM Trans. Database Syst. 6(1): 1-47(1981)
  58. 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)
  59. Y. Edmund Lien: Hierarchical Schemata for Relational Databases. ACM Trans. Database Syst. 6(1): 48-69(1981)
  60. William Kent: Consequences of Assuming a Universal Relation. ACM Trans. Database Syst. 6(4): 539-556(1981)
  61. Billie S. Goldstein: Constraints on Null Values in Relational Databases. VLDB 1981: 101-110
  62. François Bancilhon, Nicolas Spyratos: Independent Components of Databases. VLDB 1981: 398-408
  63. Edward Sciore: Real-World MVD's. SIGMOD Conference 1981: 121-132
  64. Ilchoo Chung, Fumio Nakamura, Peter P. Chen: A Decomposition of Relations Using the Entity-Relationship Approach. ER 1981: 149-171
  65. Catriel Beeri: On the Membership Problem for Functional and Multivalued Dependencies in Relational Databases. ACM Trans. Database Syst. 5(3): 241-259(1980)
  66. Yannis Vassiliou: Functional Dependencies and Incomplete Information. VLDB 1980: 260-269
  67. Steven H. Spewak: A Pragmatic Approach to Database Design. VLDB 1980: 151-152
  68. K. K. Nambiar: Some Analytic Tools for the Design of Relational Database Systems. VLDB 1980: 417-428
  69. Philip A. Bernstein, Nathan Goodman: What does Boyce-Codd Normal Form Do? VLDB 1980: 245-259
  70. David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979)
  71. E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979)
  72. 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)
  73. Alfred V. Aho, Catriel Beeri, Jeffrey D. Ullman: The Theory of Joins in Relational Databases. ACM Trans. Database Syst. 4(3): 297-314(1979)
  74. Douglas Stott Parker Jr., Claude Delobel: Algorithmic Applications for a new Result on Multivalued Dependencies. VLDB 1979: 67-74
  75. Sylvia L. Osborn: Towards a Universal Relation Interface. VLDB 1979: 52-60
  76. Y. Edmund Lien: Multivalued Dependencies with Null Values in Relational Data Bases. VLDB 1979: 61-66
  77. Janis A. Bubenko Jr.: On the Role of `Understanding Models' in Conceptual Schema Design. VLDB 1979: 129-139
  78. Ronald Fagin: Normal Forms and Relational Database Operators. SIGMOD Conference 1979: 153-160
  79. Joachim Biskup, Umeshwar Dayal, Philip A. Bernstein: Synthesizing Independent Database Schemas. SIGMOD Conference 1979: 143-151
  80. A. Min Tjoa, Roland Wagner: Some Considerations on the Entity-Relationship Model. ER 1979: 145-154
  81. Y. Edmund Lien: On the Semantics of the Entity-Relationship Data Model. ER 1979: 155-168
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings (1977-1981): Copyright © by IEEE,
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:45:01 2009