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

Logical Design of Relational Database Systems.

Li-Yan Yuan, Z. Meral Özsoyoglu: Logical Design of Relational Database Systems. PODS 1987: 38-47
@inproceedings{DBLP:conf/pods/YuanO87,
  author    = {Li-Yan Yuan and
               Z. Meral {\"O}zsoyoglu},
  title     = {Logical Design of Relational Database Systems},
  booktitle = {Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, March 23-25, 1987, San Diego,
               California},
  publisher = {ACM},
  year      = {1987},
  isbn      = {0-89791-223-3},
  pages     = {38-47},
  ee        = {http://doi.acm.org/10.1145/28659.28663, db/conf/pods/YuanO87.html},
  crossref  = {DBLP:conf/pods/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We define extended conflict free dependendencies in the context of functional and multivalued dependencies, and prove that there exists an acyclic, dependency preserving, 4NF database scheme if and only if the given set of dependencies has an extended conflict free cover. This condition can be checked in polynomial time. A polynomial time algorithm to obtain such a scheme for a given extended conflict free set of dependencies is also presented. The result is also applicable when the data dependencies consists of only functional dependencies, giving the necessary and sufficient condition for an acyclic, dependency preserving BCNF data- base scheme.

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.


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 Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 23-25, 1987, San Diego, California. ACM 1987, ISBN 0-89791-223-3
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: An Integrated Approach to Logical Design of Relational Database Schemes. ACM Trans. Database Syst. 11(2): 134-158(1986) 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]
Z. Meral Özsoyoglu, Li-Yan Yuan: Reduced MVDs and Minimal Covers. ACM Trans. Database Syst. 12(3): 377-394(1987) BibTeX
[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
[YO1]
Li-Yan Yuan, Z. Meral Özsoyoglu: Unifying Functional and Multivalued Dependencies for Relational Database Design. PODS 1986: 183-190 BibTeX
[YO2]
...

Referenced by

  1. Jyrki Nummenmaa, Peter Thanisch: Conjectures and Refutations in Database Design and Dependency Theory. ICDT 1990: 215-228
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:50 2009