dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

On Finite FD-Acyclicity.

Yehoshua Sagiv, Oded Shmueli: On Finite FD-Acyclicity. PODS 1986: 173-182
@inproceedings{DBLP:conf/pods/SagivS86a,
  author    = {Yehoshua Sagiv and
               Oded Shmueli},
  title     = {On Finite FD-Acyclicity},
  booktitle = {Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, March 25-27, 1985, Portland, Oregon, USA},
  publisher = {ACM},
  year      = {1986},
  isbn      = {0-89791-153-9},
  pages     = {173-182},
  ee        = {http://doi.acm.org/10.1145/6012.15422, db/conf/pods/SagivS86a.html},
  crossref  = {DBLP:conf/pods/85},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Database schemes with functional dependencies are considered. The satisfying states of these schemes are those having representative instances that satisfy all the functional dependencies. All states are assumed to be finite. A database scheme is fd-acyclic if all its pairwise consistent satisfying states are also join consistent. If the relation schemes of a database scheme are closed under the functional dependencies, then the database scheme is fd-acyclic if and only if it is acyclic (i.e., its corresponding hypergraph is acyclic). If a cover of the functional dependencies is embedded in the database scheme, then fd-acyclicity can be tested in polynomial time.

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

Printed Edition

Avi Silberschatz (Ed.): Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 24-26, 1986, Cambridge, Massachusetts, USA. ACM 1986, ISBN 0-89791-179-2
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition: ACM Digital Library

Journal Version

Yehoshua Sagiv, Oded Shmueli: A Characterization of Finite fd-Acyclicity. J. Comput. Syst. Sci. 38(2): 380-404(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[Aho, Sagiv, Ullman 1979]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bernstein, Chiu 1981]
Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Beeri, Fagin, Maier, Mendelzon, Ullman, Yannakakis 1981]
Catriel Beeri, Ronald Fagin, David Maier, Alberto O. Mendelzon, Jeffrey D. Ullman, Mihalis Yannakakis: Properties of Acyclic Database Schemes. STOC 1981: 355-362 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Beeri, Fagin, Maier, Yannakakis 1983]
Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis: On the Desirability of Acyclic Database Schemes. J. ACM 30(3): 479-513(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Beeri, Kifer 1984]
Catriel Beeri, Michael Kifer: Comprehensive Approach to the Design of Relational Database Schemes. VLDB 1984: 196-207 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Casanova, Fagin, Papadimitriou 1984]
Marco A. Casanova, Ronald Fagin, Christos H. Papadimitriou: Inclusion Dependencies and Their Interaction with Functional Dependencies. J. Comput. Syst. Sci. 28(1): 29-59(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Fagin, mendelzon, Ullman, 1982]
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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Graham 1979]
...
[Goodman, Shmueli 1982]
Nathan Goodman, Oded Shmueli: Tree Queries: A Simple Class of Relational Queries. ACM Trans. Database Syst. 7(4): 653-677(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Goodman, Shmueli 1983]
Nathan Goodman, Oded Shmueli: Syntactic Characterization of Tree Database Schemas. J. ACM 30(4): 767-786(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Honeyman 1982]
Peter Honeyman: Testing satisfaction of functional dependencies. J. ACM 29(3): 668-677(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hull 1983]
Richard Hull: Acyclic Join Dependency and Data Base Projections. J. Comput. Syst. Sci. 27(3): 331-349(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Johnson, Klug 1984]
David S. Johnson, Anthony C. Klug: Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies. J. Comput. Syst. Sci. 28(1): 167-189(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Katsumo 1984]
Hirofumi Katsuno: An Extension of Conflict-Free Multivalued Dependency Sets. ACM Trans. Database Syst. 9(2): 309-326(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Laver, Mendelzon, Graham 1983]
Kent Laver, Alberto O. Mendelzon, Marc H. Graham: Functional Dependencies on Cyclic Database Schemes. SIGMOD Conference 1983: 79-91 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Laver 1984]
...
[Maier, Mendelzon, Sagiv 1979]
David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sacca, Manfredi, Mecchia 1984]
Domenico Saccà, F. Manfredi, A. Mecchia: Properties of Database Schemata with Functional Dependencies. PODS 1984: 19-28 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Tarjan, Yannakakis 1984]
Robert Endre Tarjan, Mihalis Yannakakis: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs. SIAM J. Comput. 13(3): 566-579(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ullman 1983]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Yannakakis 1981]
Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Yu, Ozsoyoglu 1979]
...

Last update Fri Sep 14 17:28:25 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page