Algorithmic Applications for a new Result on Multivalued Dependencies.

Douglas Stott Parker Jr., Claude Delobel: Algorithmic Applications for a new Result on Multivalued Dependencies. VLDB 1979: 67-74
  author    = {Douglas Stott Parker Jr. and
               Claude Delobel},
  editor    = {Antonio L. Furtado and
               Howard L. Morgan},
  title     = {Algorithmic Applications for a new Result on Multivalued Dependencies},
  booktitle = {Fifth International Conference on Very Large Data Bases, October
               3-5, 1979, Rio de Janeiro, Brazil, Proceedings},
  publisher = {IEEE Computer Society},
  year      = {1979},
  pages     = {67-74},
  ee        = {db/conf/vldb/ParkerD79.html},
  crossref  = {DBLP:conf/vldb/79},
  bibsource = {DBLP,}


Recently Delobel and Parker have shown that Multivalued dependencies (MVDS) may be represented as Boolean switching functions, in much the same way as Functional dependencies (FDs) can be represented as Boolean implications. This permits all FD and MVD inferences to be made as logical (Boolean) inferences, a significant plus because the FD/MVD inference axioms are fairly complex. This paper reviews some of the basic implications of this result and outlines new applications in FD/MVD membership testing, generation of dependency closure, cover, and keys, and testing for lossless and independent decompositions.

Copyright © 1979 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

Antonio L. Furtado, Howard L. Morgan (Eds.): Fifth International Conference on Very Large Data Bases, October 3-5, 1979, Rio de Janeiro, Brazil, Proceedings. IEEE Computer Society 1979
Contents BibTeX


[ABU 77]
Alfred V. Aho, Catriel Beeri, Jeffrey D. Ullman: The Theory of Joins in Relational Data Bases (Extended Abstract). FOCS 1977: 107-113 BibTeX
[BBG 78]
Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124 BibTeX
[BFH 77]
Catriel Beeri, Ronald Fagin, John H. Howard: A Complete Axiomatization for Functional and Multivalued Dependencies in Database Relations. SIGMOD Conference 1977: 47-61 BibTeX
[Ber 76]
Philip A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Trans. Database Syst. 1(4): 277-298(1976) BibTeX
[BB 79]
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
[BST 75]
Philip A. Bernstein, J. Richard Swenson, Dennis Tsichritzis: A Unified Approach to Functional Dependencies and Relations. SIGMOD Conference 1975: 237-245 BibTeX
[BRK 74]
Ramachendra P. Batni, Jeffrey D. Russell, Charles R. Kime: An Efficient Algorithm for Finding an Irredundant Set Cover. J. ACM 21(3): 351-355(1974) BibTeX
[Cha 76]
[Cur 77]
[Dat 78]
[Del 72]
[Del 78]
Claude Delobel: Normalization and Hierarchical Dependencies in the Relational Data Model. ACM Trans. Database Syst. 3(3): 201-222(1978) BibTeX
[DC 73]
[DP 78]
[Dem 78]
János Demetrovics: On the Number of Candidate Keys. Inf. Process. Lett. 7(6): 266-269(1978) BibTeX
[Fag 77a]
[Fag 77b]
Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) BibTeX
[Fag 77c]
Ronald Fagin: The Decomposition Versus Synthetic Approach to Relational Database Design. VLDB 1977: 441-446 BibTeX
[HCO 74]
[HW 75]
[Men 79]
Alberto O. Mendelzon: On Axiomatizing Multivalued Dependencies in Relational Databases. J. ACM 26(1): 37-44(1979) BibTeX
[Mil 65]
[Nic 78]
Jean-Marie Nicolas: Mutual Dependencies and Some Results on Undecomposable Relations. VLDB 1978: 360-367 BibTeX
[RNMP 77]
[Ris 77]
Jorma Rissanen: Independent Components of Relations. ACM Trans. Database Syst. 2(4): 317-325(1977) BibTeX
[Rob 65]
[Zan 76]
[ZM 78]

Referenced by

  1. Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984)
  2. Carol Helfgott LeDoux, Douglas Stott Parker Jr.: Reflections on Boyce-Codd Normal Form. VLDB 1982: 131-141
  3. Hervé Gallaire: Impacts of Logic and Databases (Invited Paper). VLDB 1981: 248-259
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings (1977-1981): Copyright © by IEEE,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:05 2009