Inference Rules for Functional and Inclusion Dependencies.

John C. Mitchell: Inference Rules for Functional and Inclusion Dependencies. PODS 1983: 58-69

@inproceedings{DBLP:conf/pods/Mitchell83,
  author    = {John C. Mitchell},
  title     = {Inference Rules for Functional and Inclusion Dependencies},
  booktitle = {Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, March 21-23, 1983, Colony Square Hotel,
               Atlanta, Georgia},
  publisher = {ACM},
  year      = {1983},
  isbn      = {0-89791-097-4},
  pages     = {58-69},
  ee        = {http://doi.acm.org/10.1145/588058.588067, db/conf/pods/Mitchell83.html},
  crossref  = {DBLP:conf/pods/83},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

A set Sigma of functional dependencies and inclusion dependencies implies a single dependency sigma if all databases (finite and infinite) which satisfy Sigma also satisfy sigma. This paper presents complete inference rules for deducing implications of inclusion and functional dependencies. The results of [5] suggest that the implication problem for functional and inclusion dependencies together has no simple axiomatization satisfying a natural set of conditions. Out of necessity, the inference rules presented here do not satisfy the conditions assumed in [5].

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

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/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. 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
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

BibTeX

Printed Edition

Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 21-23, 1983, Colony Square Hotel, Atlanta, Georgia. ACM 1983, ISBN 0-89791-097-4
Contents BibTeX

Online Edition: ACM Digital Library

References

[1]: ...
[2]: 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
[3]: Catriel Beeri, Ronald Fagin, John H. Howard: A Complete Axiomatization for Functional and Multivalued Dependencies in Database Relations. SIGMOD Conference 1977: 47-61 BibTeX
[4]: Catriel Beeri, Henry F. Korth: Compatible Attributes in a Universal Relation. PODS 1982: 55-62 BibTeX
[5]: Marco A. Casanova, Ronald Fagin, Christos H. Papadimitriou: Inclusion Dependencies and Their Interaction with Functional Dependencies. PODS 1982: 171-176 BibTeX
[6]: Peter P. Chen: The Entity-Relationship Model - Toward a Unified View of Data. ACM Trans. Database Syst. 1(1): 9-36(1976) BibTeX
[7]: E. F. Codd: Relational Completeness of Data Base Sublanguages. In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California : (1972) BibTeX
[8]: E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX
[9]: Ronald Fagin: A Normal Form for Relational Databases That Is Based on Domians and Keys. ACM Trans. Database Syst. 6(3): 387-415(1981) BibTeX
[10]: Ronald Fagin: Horn clauses and database dependencies. J. ACM 29(4): 952-985(1982) BibTeX
[11]: M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX
[12]: David S. Johnson, Anthony C. Klug: Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies. PODS 1982: 164-169 BibTeX
[13]: Paris C. Kanellakis, Stavros S. Cosmadakis, Moshe Y. Vardi: Unary Inclusion Dependencies have Polynomial Time Inference Problems (Extended Abstract). STOC 1983: 264-277 BibTeX
[14]: Moshe Y. Vardi: The Implication and Finite Implication Problems for Typed Template Dependencies. PODS 1982: 230-238 BibTeX
[15]: Mihalis Yannakakis, Christos H. Papadimitriou: Algebraic Dependencies (Extended Abstract). FOCS 1980: 328-332 BibTeX

Referenced by

Serge Abiteboul, Victor Vianu, Bradley S. Fordham, Yelena Yesha: Relational Transducers for Electronic Commerce. PODS 1998: 179-187
Xubo Zhang, Z. Meral Özsoyoglu: Implication and Referential Constraints: A New Formal Reasoning. IEEE Trans. Knowl. Data Eng. 9(6): 894-910(1997)
Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents
Tok Wang Ling, Cheng Hian Goh: Logical Database Design with Inclusion Dependencies. ICDE 1992: 642-649
Georg Gottlob, Michael Schrefl, Markus Stumptner: On the Interaction between Transitive Closure and Functional Dependencies. MFDBS 1989: 187-206
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents
James P. Delgrande: Formal Limits on the Automatic Generation and Maintenance of Integrity Constraints. PODS 1987: 190-196
Christopher N. G. Dampney: Specifying a Semantically Adequate Structure for Information Systems and Databases. ER 1987: 165-188
Robert Brown, Douglas Stott Parker Jr.: LAURA: A Formal Data Model and her Logical Design Methodology. VLDB 1983: 206-218

BibTeX

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