The Implication and Finite Implication Problems for Typed Template Dependencies.

@inproceedings{DBLP:conf/pods/Vardi82,
  author    = {Moshe Y. Vardi},
  title     = {The Implication and Finite Implication Problems for Typed Template
               Dependencies},
  booktitle = {Proceedings of the ACM Symposium on Principles of Database Systems,
               March 29-31, 1982, Los Angeles, California},
  publisher = {ACM},
  year      = {1982},
  pages     = {230-238},
  ee        = {http://doi.acm.org/10.1145/588111.588149, db/conf/pods/Vardi82.html},
  crossref  = {DBLP:conf/pods/82},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The class of typed template dependencies is a class of data dependencies that includes embedded multivalued and join dependencies. We show that the implication and the finite implication problems for this class are unsolvable. An immediate corollary is that this class has no formal system for finite implication. We also show how to construct a finite set of typed template dependencies whose implication and finite implication problems are unsolvable.

The class of simple template dependencies is a proper subclass of the above class, and it generalizes slightly embedded join dependencies. It is shown that the implication and the finite implication problems for this class are also unsolvable. An immediate corollary is that this class has no formal system for either implication or finite implication.

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

• 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
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• 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
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[Bern]

Philip A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Trans. Database Syst. 1(4): 277-298(1976) BibTeX

[BMSU]

Catriel Beeri, Alberto O. Mendelzon, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalence of Relational Database Schemes. SIAM J. Comput. 10(2): 352-370(1981) BibTeX

[BR]

...

[BBG]

Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124 BibTeX

[BV1]

Catriel Beeri, Moshe Y. Vardi: The Implication Problem for Data Dependencies. ICALP 1981: 73-85 BibTeX

[BV2]

Catriel Beeri, Moshe Y. Vardi: A Proof Procedure for Data Dependencies. J. ACM 31(4): 718-741(1984) BibTeX

[BV3]

Catriel Beeri, Moshe Y. Vardi: Formal Systems for Tuple and Equality Generating Dependencies. SIAM J. Comput. 13(1): 76-98(1984) BibTeX

[CLM]

Ashok K. Chandra, Harry R. Lewis, Johann A. Makowsky: Embedded Implicational Dependencies and their Inference Problem. STOC 1981: 342-354 BibTeX

[Codd1]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX

[Codd2]

...

[Codd3]

E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX

[Fag1]

Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) BibTeX

[Fag2]

Ronald Fagin: Horn Clauses and Database Dependencies (Extended Abstract). STOC 1980: 123-134 BibTeX

[FMUY]

Ronald Fagin, David Maier, Jeffrey D. Ullman, Mihalis Yannakakis: Tools for Template Dependencies. SIAM J. Comput. 12(1): 36-59(1983) BibTeX

[GL]

Yuri Gurevich, Harry R. Lewis: The Inference Problem for Template Dependencies. PODS 1982: 221-229 BibTeX

[Gu]

...

[MMS]

David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX

[Po]

...

[SU]

Fereidoon Sadri, Jeffrey D. Ullman: A Complete Axiomatization for a Large Class of Dependencies in Relational Databases. STOC 1980: 117-122 BibTeX

[YP]

Mihalis Yannakakis, Christos H. Papadimitriou: Algebraic Dependencies (Extended Abstract). FOCS 1980: 328-332 BibTeX

[Zan]

...

Referenced by

1. Marc Gyssens: Embedded Join Dependencies as a Tool for Decomposing Full Join Dependencies. PODS 1985: 205-214
2. John C. Mitchell: Inference Rules for Functional and Inclusion Dependencies. PODS 1983: 58-69
3. Yuri Gurevich, Harry R. Lewis: The Inference Problem for Template Dependencies. PODS 1982: 221-229