ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Unifying Functional and Multivalued Dependencies for Relational Database Design.

Li-Yan Yuan, Z. Meral Özsoyoglu: Unifying Functional and Multivalued Dependencies for Relational Database Design. PODS 1986: 183-190
@inproceedings{DBLP:conf/pods/YuanO86,
  author    = {Li-Yan Yuan and
               Z. Meral {\"O}zsoyoglu},
  title     = {Unifying Functional and Multivalued Dependencies for Relational
               Database Design},
  booktitle = {Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, March 24-26, 1986, Cambridge, Massachusetts},
  publisher = {ACM},
  year      = {1986},
  isbn      = {0-89791-179-2},
  pages     = {183-190},
  ee        = {http://doi.acm.org/10.1145/6012.15414, db/conf/pods/YuanO86.html},
  crossref  = {DBLP:conf/pods/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We consider the problem of unifying functional dependencies (FDs) and multivalued dependencies (MVDs) in designing relational database schemes. Given a set D of dependencies (MVDs and FDs) over a universal scheme U, we define a different set of MVDs over U, called the envelope set for D, so that a database scheme with respect to D can be designed by considering only the MVDs in the envelope set for D, instead of treating MVDs and FDs in D separately. We show that a database scheme is in 4NF with respect to D (BCNF if D consists of only FDs) if it is 4NF with respect to the envelope set for D.

By utilizing the envelope set of dependencies we extend the conflict free property of sets of MVDs to apply to sets of FDs and MVDs. We show that if a set D of dependencies is extended conflict free then there exists an acyclic, join lossless 4NF decomposition (BCNF) with respect to D which is also dependency preserving. Except for the case where D is a set of MVDs only, this was an open problem in the literature. We also show that for a set M of MVDs, an acyclic join lossless 4NF decomposition exists if M does not split its keys.

Given a set of dependencies D, obtaining the envelope set for D, determining whether D is extended conflict free, and if D is extended conflict free then obtaining a dependency preserving, acyclic, join lossless, 4NF decomposition can be done in time polynomial in the size of D.

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


Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 24-26, 1986, Cambridge, Massachusetts. ACM 1986, ISBN 0-89791-179-2
Contents BibTeX

Online Edition: ACM Digital Library


References

[BB]
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
[Be]
Philip A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Trans. Database Syst. 1(4): 277-298(1976) BibTeX
[BFMY]
Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis: On the Desirability of Acyclic Database Schemes. J. ACM 30(3): 479-513(1983) BibTeX
[BK]
Catriel Beeri, Michael Kifer: Comprehensive Approach to the Design of Relational Database Schemes. VLDB 1984: 196-207 BibTeX
[Fa]
Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) BibTeX
[Ga]
Zvi Galil: An Almost Linear-Time Algorithm for Computing a Dependency Basis in a Relational Database. J. ACM 29(1): 96-102(1982) BibTeX
[GR]
Gösta Grahne, Kari-Jouko Räihä: Database Decomposition into Fourth Normal Form. VLDB 1983: 186-196 BibTeX
[Ka]
Hirofumi Katsuno: An Extension of Conflict-Free Multivalued Dependency Sets. ACM Trans. Database Syst. 9(2): 309-326(1984) BibTeX
[L1]
Y. Edmund Lien: Hierarchical Schemata for Relational Databases. ACM Trans. Database Syst. 6(1): 48-69(1981) BibTeX
[L2]
Y. Edmund Lien: On the Equivalence of Database Models. J. ACM 29(2): 333-362(1982) BibTeX
[OY1]
...
[OY2]
Z. Meral Özsoyoglu, Li-Yan Yuan: A Normal Form for Nested Relations. PODS 1985: 251-260 BibTeX
[Ul]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[YO]
...

Referenced by

  1. Jyrki Nummenmaa, Peter Thanisch: Conjectures and Refutations in Database Design and Dependency Theory. ICDT 1990: 215-228
  2. Z. Meral Özsoyoglu, Li-Yan Yuan: Reduced MVDs and Minimal Covers. ACM Trans. Database Syst. 12(3): 377-394(1987)
  3. Z. Meral Özsoyoglu, Li-Yan Yuan: A New Normal Form for Nested Relations. ACM Trans. Database Syst. 12(1): 111-136(1987)
  4. Mark A. Roth, Henry F. Korth: The Design of ¬1NF Relational Databases into Nested Normal Form. SIGMOD Conference 1987: 143-159
  5. Li-Yan Yuan, Z. Meral Özsoyoglu: Logical Design of Relational Database Systems. PODS 1987: 38-47
  6. Detlev Ruland, Dietmar Seipel: Designing Alpha-Acyclic BCNF-Database Schemes. MFDBS 1987: 197-209
  7. Z. Meral Özsoyoglu, Li-Yan Yuan: A Design Method for Nested Relational Databases. ICDE 1987: 599-608
  8. Dirk Van Gucht: Interaction-Free Multivalued Dependency Sets. ICDT 1986: 409-420
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
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:33:49 2009