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

Inclusion Dependencies and Their Interaction with Functional Dependencies.

Marco A. Casanova, Ronald Fagin, Christos H. Papadimitriou: Inclusion Dependencies and Their Interaction with Functional Dependencies. PODS 1982: 171-176
@inproceedings{DBLP:conf/pods/CasanovaFP82,
  author    = {Marco A. Casanova and
               Ronald Fagin and
               Christos H. Papadimitriou},
  title     = {Inclusion Dependencies and Their Interaction with Functional
               Dependencies},
  booktitle = {Proceedings of the ACM Symposium on Principles of Database Systems,
               March 29-31, 1982, Los Angeles, California},
  publisher = {ACM},
  year      = {1982},
  pages     = {171-176},
  ee        = {http://doi.acm.org/10.1145/588111.588141, db/conf/pods/CasanovaFP82.html},
  crossref  = {DBLP:conf/pods/82},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Inclusion dependencies, or INDs (which can say, for example, that every manager is an employee) are studied, including their interaction with functional dependencies, or FDs. A simple complete axiomatization for INDs is presented, and the decision problem for INDs is shown to be PSPACE-complete. (The decision problem for INDs is the problem of determining whether or not Sigma logically implies sigma, given a set Sigma of INDs and a single IND sigma). It is shown that finite implication (implication over databases with a finite number of tuples) is the same as unrestricted implications for INDs, although finite implication and unrestricted implication are distinct for FDs and INDs taken together. It is shown that, although there are simple complete axiomatizations for FDs alone and for INDs alone, there is no complete axiomatization for FDs and INDs taken together, in which every rule is k-ary for some fixed k (and in particular, there is no finite complete axiomatization.) This is true whether we consider finite implication or unrestricted implication, and is true even if no relation scheme has more than three attributes. The nonexistence of a k-ary complete axiomatization for FDs and INDs taken together is proven by giving a condition which is necessary and sufficient in general for the existence of a k-ary complete axiomatization.

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.


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 ACM Symposium on Principles of Database Systems, March 29-31, 1982, Los Angeles, California. ACM 1982
Contents BibTeX

Online Edition: ACM Digital Library


References

[ABU]
Alfred V. Aho, Catriel Beeri, Jeffrey D. Ullman: The Theory of Joins in Relational Databases. ACM Trans. Database Syst. 4(3): 297-314(1979) BibTeX
[Ar]
William Ward Armstrong: Dependency Structures of Data Base Relationships. IFIP Congress 1974: 580-583 BibTeX
[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
[BFH]
Catriel Beeri, Ronald Fagin, John H. Howard: A Complete Axiomatization for Functional and Multivalued Dependencies in Database Relations. SIGMOD Conference 1977: 47-61 BibTeX
[BK]
Catriel Beeri, Henry F. Korth: Compatible Attributes in a Universal Relation. PODS 1982: 55-62 BibTeX
[BV]
Catriel Beeri, Moshe Y. Vardi: Formal Systems for Tuple and Equality Generating Dependencies. SIAM J. Comput. 13(1): 76-98(1984) BibTeX
[BG]
Philip A. Bernstein, Nathan Goodman: What does Boyce-Codd Normal Form Do? VLDB 1980: 245-259 BibTeX
[CFP]
...
[Ch]
Peter P. Chen: The Entity-Relationship Model - Toward a Unified View of Data. ACM Trans. Database Syst. 1(1): 9-36(1976) BibTeX
[Co1]
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
[Co2]
E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX
[Fa1]
Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) BibTeX
[Fa2]
...
[Fa3]
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
[Fa4]
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
[FV]
Ronald Fagin, Moshe Y. Vardi: Armstrong Databases for Functional and Inclusion Dependencies. Inf. Process. Lett. 16(1): 13-19(1983) BibTeX
[GJ]
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
[JK]
David S. Johnson, Anthony C. Klug: Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies. PODS 1982: 164-169 BibTeX
[Ke]
William Kent: Consequences of Assuming a Universal Relation. ACM Trans. Database Syst. 6(4): 539-556(1981) BibTeX
[Kl]
Anthony C. Klug: Entity-Relationship Views over Uninterpreted Enterprise Schemas. ER 1979: 39-60 BibTeX
[LP]
...
[Li]
...
[Sa]
Walter J. Savitch: Relationships Between Nondeterministic and Deterministic Tape Complexities. J. Comput. Syst. Sci. 4(2): 177-192(1970) BibTeX
[SU]
Fereidoon Sadri, Jeffrey D. Ullman: A Complete Axiomatization for a Large Class of Dependencies in Relational Databases. STOC 1980: 117-122 BibTeX
[SW]
Yehoshua Sagiv, Scott F. Walecka: Subset Dependencies and a Completeness Result for a Subclass of Embedded Multivalued Dependencies. J. ACM 29(1): 103-117(1982) BibTeX
[SS]
John Miles Smith, Diane C. P. Smith: Database Abstractions: Aggregation. Commun. ACM 20(6): 405-413(1977) BibTeX
[WM]
Gio Wiederhold, Ramez Elmasri: The Structural Model for Database Design. ER 1979: 237-258 BibTeX
[YP]
Mihalis Yannakakis, Christos H. Papadimitriou: Algebraic Dependencies (Extended Abstract). FOCS 1980: 328-332 BibTeX
[Za]
Carlo Zaniolo: Design of Relational Views over Network Schemas. SIGMOD Conference 1979: 179-190 BibTeX

Referenced by

  1. Nicole Bidoit, Sandra de Amo: A First Step Towards Implementing Dynamic Algebraic Dependencies. ICDT 1995: 308-321
  2. Tok Wang Ling, Cheng Hian Goh: Logical Database Design with Inclusion Dependencies. ICDE 1992: 642-649
  3. Paul Johannesson, Katalin Kalman: A Method for Translating Relational Schemas into Conceptual Schemas. ER 1989: 271-285
  4. Peter Lyngbæk, Victor Vianu: Mapping a Semantic Database Model to the Relational Model. SIGMOD Conference 1987: 132-142
  5. Joachim Biskup, Uwe Räsch: The Equivalence Problem For Relational Database Schemes. MFDBS 1987: 42-70
  6. Hiroshi Arisawa, Takao Miura: On the Properties of Extended Inclusion Dependencies. VLDB 1986: 449-456
  7. Joachim Biskup, Bernhard Convent: A Formal View Integration Method. SIGMOD Conference 1986: 398-407
  8. Bernhard Convent: Unsolvable Problems Related To The View Integration Approach. ICDT 1986: 141-156
  9. Arthur M. Keller: Algorithms for Translating View Updates to Database Updates for Views Involving Selections, Projections, and Joins. PODS 1985: 154-163
  10. Matthias Jarke, James Clifford, Yannis Vassiliou: An Optimizing Prolog Front-End to a Relational Query System. SIGMOD Conference 1984: 296-306
  11. Tomasz Imielinski, Nicolas Spyratos: On Lossless Transformation of Database Schemes not Necessarily Satisfying Universal Instance Assumption. PODS 1984: 258-265
  12. Stavros S. Cosmadakis, Paris C. Kanellakis: Functional and Inclusion Dependencies: A Graph Theoretic Approach. PODS 1984: 29-37
  13. David Maier, David Rozenshtein, Jacob Stein: Representing Roles in Universal Scheme Interfaces. ICDE 1984: 133-142
  14. Ulrich Schiel: An Abstract Introduction to the Temporal-Hierarchic Data Model (THM). VLDB 1983: 322-330
  15. Robert Brown, Douglas Stott Parker Jr.: LAURA: A Formal Data Model and her Logical Design Methodology. VLDB 1983: 206-218
  16. Kent Laver, Alberto O. Mendelzon, Marc H. Graham: Functional Dependencies on Cyclic Database Schemes. SIGMOD Conference 1983: 79-91
  17. Edward Sciore: Inclusion Dependencies and the Universal Instance. PODS 1983: 48-57
  18. John C. Mitchell: Inference Rules for Functional and Inclusion Dependencies. PODS 1983: 58-69
  19. Stephen J. Hegner: Algebraic Aspects of Relational Database Decomposition. PODS 1983: 400-413
  20. Seymour Ginsburg, Richard Hull: Sort Sets in the Relational Model. PODS 1983: 332-339
  21. Marco A. Casanova, Vânia Maria Ponte Vidal: Towards a Sound View Integration Methodology. PODS 1983: 36-47
  22. Marco A. Casanova, Jose E. Amaral de Sa: Designing Entity-Relationship Schemes for Conventional Information Systems. ER 1983: 265-277
  23. David S. Johnson, Anthony C. Klug: Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies. PODS 1982: 164-169
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:40 2009