{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,5]],"date-time":"2026-11-05T05:37:01Z","timestamp":1793857021068,"version":"4.6.1"},"reference-count":16,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,8]]},"abstract":"<jats:p>The implication problem for a class of dependencies is the following: given a finite set of dependencies, determine if they logically imply another dependency. We show that the implication problem is undecidable for the class of functional and inclusion dependencies. This holds true even if the inclusion dependencies are restricted to be binary. It may be noted that the implication problem is known to be decidable for functional and unary inclusion dependencies and also for inclusion dependencies without functional dependencies.<\/jats:p>","DOI":"10.1137\/0214049","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"671-677","source":"Crossref","is-referenced-by-count":113,"title":["The Implication Problem for Functional and Inclusion Dependencies is Undecidable"],"prefix":"10.1137","volume":"14","author":[{"given":"Ashok K.","family":"Chandra","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Moshe Y.","family":"Vardi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,2]]},"reference":[{"key":"R1","first-page":"580","volume-title":"Information processing 74 (Proc. IFIP Congress, Stockholm, 1974)","author":"Armstrong W. W.","year":"1974"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/320064.320066"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/320493.320489"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/0213006"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90075-8"},{"key":"R6","first-page":"33","volume-title":"Data Base Systems","author":"Codd E. F.","year":"1972"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/319587.319592"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90005-4"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.2307\/2274101"},{"key":"R10","first-page":"25","volume":"5","author":"Gurevich Y.","year":"1966","journal-title":"Algebra i Logika Sem."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90081-3"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"P. C. Kanellakis, S. S. Cosmadakis, M. Y. Vardi,  Unary inclusion dependencies have polynomial time inference problems,  Proc.15th ACM Symposium on Theory of Computing, Boston,  1983,  264\u2013277, April","DOI":"10.1145\/800061.808756"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"J. Mitchell,  The implication problem for functional and inclusion dependencies,  Proc. 2nd ACM Symposium on Principles of Database Systems, Atlanta,  1983,  58\u201369","DOI":"10.1145\/588058.588067"},{"key":"R14","unstructured":"John C. Mitchell,  The implication problem for functional and inclusion dependencies, Tech. Rep., MIT\/LCS\/TM-235, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge,  1983, Feb."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.2307\/2267170"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90074-6"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214049","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:14Z","timestamp":1787337554000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214049"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,8]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1985,8]]}},"alternative-id":["10.1137\/0214049"],"URL":"https:\/\/doi.org\/10.1137\/0214049","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,8]]}}}