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