Functional Dependencies on Cyclic Database Schemes.

@inproceedings{DBLP:conf/sigmod/LaverMG83,
  author    = {Kent Laver and
               Alberto O. Mendelzon and
               Marc H. Graham},
  editor    = {David J. DeWitt and
               Georges Gardarin},
  title     = {Functional Dependencies on Cyclic Database Schemes},
  booktitle = {SIGMOD'83, Proceedings of Annual Meeting, San Jose, California,
               May 23-26, 1983},
  publisher = {ACM Press},
  year      = {1983},
  pages     = {79-91},
  ee        = {http://doi.acm.org/10.1145/582192.582208, db/conf/sigmod/LaverMG83.html},
  crossref  = {DBLP:conf/sigmod/83},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We study how functional dependencies affect the cyclicity of a database scheme; in particular, when does a set of functional dependencies make a cyclic database scheme behave like an acyclic one.

A database scheme is fd-acyclic if every pairwise-consistent database state that satisfies the fd's is join-consistent. We give a simple characterization of fd-acyclicity over a restricted class of database schemes. We then give a tableau-based characterization for the general case that leads to an algorithm for testing fd-acyclicity. This algorithm actually solves the more general problem of query equivalence under functional dependencies and typed inclusion dependencies.

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.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" 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
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/smod7592 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
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[ASU]

Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979)

[B+]

Catriel Beeri, Ronald Fagin, David Maier, Alberto O. Mendelzon, Jeffrey D. Ullman, Mihalis Yannakakis: Properties of Acyclic Database Schemes. STOC 1981: 355-362

[BFMY]

Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis: On the Desirability of Acyclic Database Schemes. J. ACM 30(3): 479-513(1983)

[BG]

Philip A. Bernstein, Nathan Goodman: Power of Natural Semijoins. SIAM J. Comput. 10(4): 751-771(1981)

[CFP]

Marco A. Casanova, Ronald Fagin, Christos H. Papadimitriou: Inclusion Dependencies and Their Interaction with Functional Dependencies. PODS 1982: 171-176

[CM]

Edward P. F. Chan, Alberto O. Mendelzon: Independent and Separable Database Schemes. PODS 1983: 288-296

[F1]

Ronald Fagin: Horn clauses and database dependencies. J. ACM 29(4): 952-985(1982)

[F2]

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

[FMU]

Ronald Fagin, Alberto O. Mendelzon, Jeffrey D. Ullman: A Simplified Universal Relation Assumption and Its Properties. ACM Trans. Database Syst. 7(3): 343-360(1982)

[G]

...

[GM]

Marc H. Graham, Alberto O. Mendelzon: Strong Equivalence of Relational Wxpressions Under Dependencies. Inf. Process. Lett. 14(2): 57-62(1982)

[GS1]

Nathan Goodman, Oded Shmueli: Tree Queries: A Simple Class of Relational Queries. ACM Trans. Database Syst. 7(4): 653-677(1982)

[GS2]

Nathan Goodman, Oded Shmueli: Limitations of the Chase. Inf. Process. Lett. 13(4/5): 154-156(1981)

[GY]

Marc H. Graham, Mihalis Yannakakis: Independent Database Schemas. PODS 1982: 199-204

[H]

Peter Honeyman: Testing satisfaction of functional dependencies. J. ACM 29(3): 668-677(1982)

[JK]

David S. Johnson, Anthony C. Klug: Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies. PODS 1982: 164-169

[K]

...

[L]

...

[MMS]

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

[S]

Yehoshua Sagiv: Can We Use the Universal Instance Assumption Without Using Nulls? SIGMOD Conference 1981: 108-120

[U]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6

[V]

...

Referenced by

1. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
   Contents
2. Yehoshua Sagiv, Oded Shmueli: Solving Queries by Tree Projections. ACM Trans. Database Syst. 18(3): 487-511(1993)
3. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
   Contents
4. Yehoshua Sagiv, Oded Shmueli: On Finite FD-Acyclicity. PODS 1986: 173-182
5. Yehoshua Sagiv, Oded Shmueli: The Equivalence of Solving Queries and Production Tree Projections. PODS 1986: 160-172
6. Domenico Saccà, F. Manfredi, A. Mecchia: Properties of Database Schemata with Functional Dependencies. PODS 1984: 19-28
7. Alessandro D'Atri, Marina Moscarini: On the Recognition and Design of Acyclic Databases. PODS 1984: 1-8
8. Stavros S. Cosmadakis, Paris C. Kanellakis: Functional and Inclusion Dependencies: A Graph Theoretic Approach. PODS 1984: 29-37

Last update Fri May 25 08:38:20 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page