A Polynomial Time Algorithm for Testing Implications of a Join Dependency and Embodied Functional Dependencies.

John H. Leuchner, Les Miller, Giora Slutzki: A Polynomial Time Algorithm for Testing Implications of a Join Dependency and Embodied Functional Dependencies. SIGMOD Conference 1988: 218-224

@inproceedings{DBLP:conf/sigmod/LeuchnerMS88,
  author    = {John H. Leuchner and
               Les Miller and
               Giora Slutzki},
  editor    = {Haran Boral and
               Per-{\AA}ke Larson},
  title     = {A Polynomial Time Algorithm for Testing Implications of a Join
               Dependency and Embodied Functional Dependencies},
  booktitle = {Proceedings of the 1988 ACM SIGMOD International Conference on
               Management of Data, Chicago, Illinois, June 1-3, 1988},
  publisher = {ACM Press},
  year      = {1988},
  pages     = {218-224},
  ee        = {http://doi.acm.org/10.1145/50202.50229, db/conf/sigmod/LeuchnerMS88.html},
  crossref  = {DBLP:conf/sigmod/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

The problem of deciding whether a full join dependency (JD) join [R] and a set of functional dependencies (FDs) F imply an embedded join dependency (EJD) join [S] is known to be NP-complete. We show that the problem can be decided in polynomial time if S <= R and F is embedded in R. Our work uses arguments based on an extension of complete intersection graphs rather than tableaus. This approach has facilitated our results and should prove useful for future research.

Copyright © 1988 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

Online Version (ACM WWW Account required): Full Text in PDF Format

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

DVD Version: Load ACM SIGMOD Anthology DVD 1" 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 DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

BibTeX

Printed Edition

Haran Boral, Per-Åke Larson (Eds.): Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, Chicago, Illinois, June 1-3, 1988. ACM Press 1988 BibTeX , SIGMOD Record 17(2), June 1988
Contents

Online Edition: ACM Digital Library

References

[B]: ...
[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) BibTeX
[FMUY]: Ronald Fagin, David Maier, Jeffrey D. Ullman, Mihalis Yannakakis: Tools for Template Dependencies. SIAM J. Comput. 12(1): 36-59(1983) BibTeX
[G]: Marc Gyssens: Embedded Join Dependencies as a Tool for Decomposing Full Join Dependencies. PODS 1985: 205-214 BibTeX
[GP]: Marc Gyssens, Jan Paredaens: A Decomposition Methodology for Cyclic Databases. Advances in Data Base Theory 1982: 85-122 BibTeX
[GS]: Nathan Goodman, Oded Shmueli: Syntactic Characterization of Tree Database Schemas. J. ACM 30(4): 767-786(1983) BibTeX
[M]: David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX
[MSY]: David Maier, Yehoshua Sagiv, Mihalis Yannakakis: On the Complexity of Testing Implications of Functional and Join Dependencies. J. ACM 28(4): 680-695(1981) BibTeX
[MLKL]: ...
[S]: Edward Sciore: A Complete Axiomatization of Full Join Dependencies. J. ACM 29(2): 373-393(1982) BibTeX
[TL]: ...
[U1]: Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[U2]: Jeffrey D. Ullman: The U. R. Strikes Back. PODS 1982: 10-22 BibTeX
[V]: ...

BibTeX

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