Reduced MVDs and Minimal Covers.

Z. Meral Özsoyoglu, Li-Yan Yuan: Reduced MVDs and Minimal Covers. ACM Trans. Database Syst. 12(3): 377-394(1987)

@article{DBLP:journals/tods/OzsoyogluY87a,
  author    = {Z. Meral {\"O}zsoyoglu and
               Li-Yan Yuan},
  title     = {Reduced MVDs and Minimal Covers},
  journal   = {ACM Trans. Database Syst.},
  volume    = {12},
  number    = {3},
  year      = {1987},
  pages     = {377-394},
  ee        = {http://doi.acm.org/10.1145/27629.214286, db/journals/tods/OzsoyogluY87a.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

Multivalued dependencies (MVDs) are data dependencies that appear frequently in the "real world" and play an important role in designing relational database schemes. Given a set of MVDs to constrain a database scheme, it is desirable to obtain an equivalent set of MVDs that do not have any redundancies. In this paper we define such a set of MVDs, called reduced MVDs, and present an algorithm to obtain reduced MVDs. We also define a minimal cover of a set of MVDs, which is a set of reduced MVDs, and give an efficient method to find such a minimal cover. The significance and properties of reduced MVDs are also discussed in the context of database design (e.g., 4NF decomposition) and conflict-free MVDs.

Copyright © 1987 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 ...

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/An3-1 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

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/aDVD2 or /dvd

BibTeX

References

[1]: 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
[2]: Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124 BibTeX
[3]: Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis: On the Desirability of Acyclic Database Schemes. J. ACM 30(3): 479-513(1983) BibTeX
[4]: Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) BibTeX
[5]: Zvi Galil: An Almost Linear-Time Algorithm for Computing a Dependency Basis in a Relational Database. J. ACM 29(1): 96-102(1982) BibTeX
[6]: ...
[7]: Gösta Grahne, Kari-Jouko Räihä: Database Decomposition into Fourth Normal Form. VLDB 1983: 186-196 BibTeX
[8]: Kenichi Hagihara, Minoru Ito, Kenichi Taniguchi, Tadao Kasami: Decision Problems for Multivalued Dependencies in Relational Databases. SIAM J. Comput. 8(2): 247-264(1979) BibTeX
[9]: Y. Edmund Lien: Hierarchical Schemata for Relational Databases. ACM Trans. Database Syst. 6(1): 48-69(1981) BibTeX
[10]: Y. Edmund Lien: On the Equivalence of Database Models. J. ACM 29(2): 333-362(1982) BibTeX
[11]: David Maier: Minimum Covers in Relational Database Model. J. ACM 27(4): 664-674(1980) BibTeX
[12]: Z. Meral Özsoyoglu, Li-Yan Yuan: A New Normal Form for Nested Relations. ACM Trans. Database Syst. 12(1): 111-136(1987) BibTeX
[13]: Edward Sciore: Real-World MVD's. SIGMOD Conference 1981: 121-132 BibTeX
[14]: Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[15]: Li-Yan Yuan, Z. Meral Özsoyoglu: Unifying Functional and Multivalued Dependencies for Relational Database Design. PODS 1986: 183-190 BibTeX
[16]: Carlo Zaniolo, Michel A. Melkanoff: On the Design of Relational Database Schemata. ACM Trans. Database Syst. 6(1): 1-47(1981) BibTeX

Referenced by

Li-Yan Yuan, Z. Meral Özsoyoglu: Logical Design of Relational Database Systems. PODS 1987: 38-47
Z. Meral Özsoyoglu, Li-Yan Yuan: A Design Method for Nested Relational Databases. ICDE 1987: 599-608

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]