{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:27:08Z","timestamp":1787387228524,"version":"build-2736575974"},"reference-count":26,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1983,2]]},"abstract":"<jats:p>Template dependencies (TD\u2019s) are a class of data dependencies that include multivalued and join dependencies and embedded versions of these. A collection of techniques, examples and results about TD\u2019s are presented. The principal results are: 1) Finite implication (implication over relations with a finite number of tuples) is distinct from unrestricted implication for TD\u2019s. 2) There are, for TD\u2019s over three or more attributes, infinite chains of increasingly weaker and increasingly stronger full TD\u2019s. 3) However, there are weakest (nontrivial) and strongest full TD\u2019s over any given set of attributes. 4) Over two attributes, there are only three distinct TD\u2019s. 5) There is no weakest (not necessarily full) TD over any set of three or more attributes. 6) There is a finite relation that obeys every strictly partial TD but no full TD. 7) The conjunction of each finite set of full TD\u2019s is equivalent to a single full TD. However, the conjunction of a finite set of (not necessarily full) TD\u2019s is not necessarily equivalent to a single TD and the disjunction of a finite set of full TD\u2019s is not necessarily equivalent to a single TD. 8) There is a finite set of TD\u2019s with an infinite Armstrong relation but no finite Armstrong relation. 9) A necessary and sufficient condition for the existence of finite Armstrong relations for sets of TD\u2019s can be formulated in terms of the implication structure of TD\u2019s.<\/jats:p>","DOI":"10.1137\/0212003","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:05:53Z","timestamp":1109225153000},"page":"36-59","source":"Crossref","is-referenced-by-count":11,"title":["Tools for Template Dependencies"],"prefix":"10.1137","volume":"12","author":[{"given":"Ronald","family":"Fagin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Maier","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeffrey D.","family":"Ullman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mihalis","family":"Yannakakis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"C. Beeri, R. Fagin, D. Maier, A. O. Mendelzon, J. D. Ullman, M. Yannakakis,  Properties of acyclic database schemes,  Proc. Thirteenth Annual ACM Symposium on the Theory of Computing,  1981,  355\u2013362","DOI":"10.1145\/800076.802489"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322389"},{"key":"R3","unstructured":"C. Beeri, M. Y. Vardi,  A proof procedure for data dependencies, Technical Report, Hebrew Univ. of Jerusalem,  1980, August"},{"key":"R4","unstructured":"C. Beeri, M. Y. Vardi,  Formal systems for tuple and equality generating dependencies, Technical Report, Hebrew Univ. of Jerusalem,  1981, April"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"C. Beeri, M. Y. Vardi,  The implication problem for data dependencies,  Proc. 8th ICALP, Acre, Israel, July 1981, Lecture Notes in Computer Science, Vol. 115, Springer-Verlag, New York,  1981,  73\u201385","DOI":"10.1007\/3-540-10843-2_7"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"M. A. Casanova, R. Fagin, C. Papadimitriou,  Inclusion dependencies and their interaction with functional dependencies,  Proc. First ACM SIGACT-SIGMOD Principles of Database Systems,  1982,  171\u2013176","DOI":"10.1145\/588111.588141"},{"key":"R7","first-page":"33","volume-title":"Courant Computer Science Symposia 6: Data Base Systems, May 24\u201325, 1971","author":"Codd E. F.","year":"1971"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/320263.320271"},{"key":"R9","volume-title":"A mathematical introduction to logic","author":"Enderton Herbert B.","year":"1972"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1017\/S0022481200051756"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1145\/320557.320571"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1145\/322344.322347"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/319732.319735"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/322326.322331"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Y. Gurevich, H. R. Lewis,  The inference problem for template dependencies,  Proc. First ACM SIGACT-SIGMOD Principles of Database Systems,  1982,  221\u2013229","DOI":"10.1145\/588111.588148"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320115"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"A. Mendelzon, D. Maier,  Generalized mutual dependencies,  Proc. Very large Data Bases Conference,  1979,  75\u201382","DOI":"10.1109\/VLDB.1979.718121"},{"key":"R18","unstructured":"J.M. Nicolas,  Mutual dependencies and some results on undecomposable relations,  Proc. Very Large Data Bases Conference,  1978,  360\u2013367"},{"key":"R19","volume-title":"Formal Bases for Databases","author":"Paradaens J.","year":"1978"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-08921-7_102"},{"key":"R21","unstructured":"F. Sadri, Personal communication"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1145\/322307.322312"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1145\/322290.322297"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"M. Y. Vardi,  The implication and finite implication problems for typed template dependencies,  Proc. First ACM SIGACT-SIGMOD Principles of Database Systems,  1982,  230\u2013238","DOI":"10.1145\/588111.588149"},{"key":"R25","unstructured":"M. Y. Vardi,  1981, Personal communication, Oct."},{"key":"R26","doi-asserted-by":"crossref","unstructured":"M. Yannakakis, C. Papadimitriou,  Algebraic dependencies,  Proc. IEEE Symposium on Foundations of Computer Science,  1980,  328\u2013332","DOI":"10.1109\/SFCS.1980.10"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0212003","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:40:55Z","timestamp":1787337655000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0212003"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,2]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1983,2]]}},"alternative-id":["10.1137\/0212003"],"URL":"https:\/\/doi.org\/10.1137\/0212003","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1983,2]]}}}