Whether a Set of Multivalued Dependencies Implies a Join Dependency is NP-hard

Abstract

Previous article Next article Whether a Set of Multivalued Dependencies Implies a Join Dependency is NP-hardPatrick C. Fischer and Don-Min TsouPatrick C. Fischer and Don-Min Tsouhttps://doi.org/10.1137/0212015PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstractThe problem of determining, given a set of multivalued dependencies, whether or not they logically imply a given join dependency is shown to be computationally intractable.[1] A. V. Aho, , C. Beeri and , J. D. Ullman, The theory of joins in relational databases, ACM Trans. Database Systems, 4 (1979), 297–314 10.1145/320083.320091 CrossrefGoogle Scholar[2] A. V. Aho, , Y. Sagiv and , J. D. Ullman, Efficient optimization of a class of relational expressions, ACM Trans. Database Systems, 4 (1979), 435–454 10.1145/320107.320112 CrossrefGoogle Scholar[3] W. W. Armstrong, Dependency structures of data base relationshipsInformation processing 74 (Proc. IFIP Congress, Stockholm, 1974), North-Holland, Amsterdam, 1974, 580–583 54:9126 0296.68038 Google Scholar[4] C. Beeri, On the membership problem for function and multivalued dependencies in relational databases, ACM Trans. Database Systems, 5 (1980), 241–259 10.1145/320613.320614 0441.68118 CrossrefGoogle Scholar[5] C. Beeri and , P. A. Bernstein, Computational problems related to the design of normal form relational schemes, ACM Trans. Database Systems, 4 (1979), 30–59 10.1145/320064.320066 CrossrefGoogle Scholar[6] C. Beeri, , R. Fagin and , J. Howard, A complete axiomatization for functional and multivalued dependencies, Proc. ACM SIGMOD Conference, 1977, 47–61 Google Scholar[7] C. Beeri, , R. Fagin, , D. Maier, , A. Mendelzon, , J. Ullman and , M. Yannakakis, Properties of acyclic database schemes, Proc. Thirteenth Annual ACM Symposium on Theory of Computing, 1981, 355–362 Google Scholar[8] E. F. Codd, A relational model of data for large shared data banks, Comm. ACM, 13 (1970), 377–387 10.1145/362384.362685 0207.18003 CrossrefISIGoogle Scholar[9] R. Fagin, Multivalued dependencies and a new normal form for relational databases, ACM Trans. Database Systems, 2 (1977), 262–278 10.1145/320557.320571 CrossrefGoogle Scholar[10] K. Hagihara, , M. Ito and , K. Taniguchi, Decision problems for multivalued dependencies in relational databases, SIAM J. Comput., 8 (1979), 247–264 10.1137/0208018 80c:68021 0408.68025 LinkISIGoogle Scholar[11] Richard M. Karp, Reducibility among combinatorial problemsComplexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), Plenum, New York, 1972, 85–103 51:14644 CrossrefGoogle Scholar[12] D. Maier, , A. O. Mendelzon and , Y. Sagiv, Testing implications of data dependencies, ACM Trans. Database Systems, 4 (1979), 455–469 10.1145/320107.320115 CrossrefGoogle Scholar[13] David Maier, , Yehoshua Sagiv and , Mihalis Yannakakis, On the complexity of testing implications of functional and join dependencies, J. Assoc. Comput. Mach., 28 (1981), 680–695 10.1145/322276.322280 84g:68030 0481.68094 CrossrefISIGoogle Scholar[14] D.-M. Tsou, Analysis of the logical design in relational databases, Technical Rep., CS-80-11, Vanderbilt University, Nashville, TN, 1980 Google Scholar[15] J. D. Ullman, Principles of Database Systems, Computer Science Press, Potomac, MD, 1979 Google Scholar[16] M. Y. Vardi, Inferring multivalued dependencies from functional and join dependencies, Technical Rep., Weizmann Institute of Science, Rehovot, Israel, 1980 Google Scholar[17] C. Beeri and , M. Y. Vardi, On the complexity of testing implications of data dependencies, Technical Rep., Hebrew University, Jerusalem, Israel, 1980 Google ScholarKeywordsrelational databasedependency theorymultivalued dependencyjoin dependency Previous article Next article FiguresRelatedReferencesCited ByDetails Testing Dependencies and Inference Rules in DatabasesModeling and Analysis of Information Systems, Vol. 29, No. 3 | 25 September 2022 Cross Ref I/O-efficient join dependency testing, Loomis–Whitney join, and triangle enumerationJournal of Computer and System Sciences, Vol. 82, No. 8 | 1 Dec 2016 Cross Ref Join Dependency Testing, Loomis-Whitney Join, and Triangle EnumerationProceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems | 20 May 2015 Cross Ref Conditions for lossless joinInternational Journal of Computer Mathematics, Vol. 78, No. 4 | 1 Jan 2001 Cross Ref Compact scheme forests in nested normal formInternational Journal of Computer Mathematics, Vol. 45, No. 1-2 | 1 Jan 1992 Cross Ref A polynomial-time join dependency implication algorithm for unary multi-valued dependenciesICDT '86 | 2 June 2005 Cross Ref Volume 12, Issue 2| 1983SIAM Journal on Computing215-410 History Submitted:15 March 1982Published online:31 July 2006 InformationCopyright © 1983 © Society for Industrial and Applied MathematicsKeywordsrelational databasedependency theorymultivalued dependencyjoin dependencyPDF Download Article & Publication DataArticle DOI:10.1137/0212015Article page range:pp. 259-266ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics