{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T08:19:17Z","timestamp":1760170757202},"publisher-location":"Berlin, Heidelberg","reference-count":94,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540133452"},{"type":"electronic","value":"9783540388869"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1984]]},"DOI":"10.1007\/3-540-13345-3_1","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T18:01:41Z","timestamp":1330192901000},"page":"1-22","source":"Crossref","is-referenced-by-count":24,"title":["The theory of data dependencies \u2014 An overview"],"prefix":"10.1007","author":[{"given":"Ronald","family":"Fagin","sequence":"first","affiliation":[]},{"given":"Moshe Y.","family":"Vardi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"issue":"3","key":"1_CR1","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1145\/320083.320091","volume":"4","author":"A. V. Aho","year":"1979","unstructured":"A. V. Aho, C. Beeri, and J. D. Ullman, The theory of joins in relational data bases. ACM Trans. on Database Systems 4,3 (Sept. 1979), 297\u2013314.","journal-title":"ACM Trans. on Database Systems"},{"issue":"2","key":"1_CR2","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1137\/0208017","volume":"8","author":"A. V. Aho","year":"1979","unstructured":"A. V. Aho, Y. Sagiv, and J. D. Ullman, Equivalences among relational expressions. SIAM J. Computing 8,2 (May 1979), 218\u2013246.","journal-title":"SIAM J. Computing"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"W. W. Armstrong, Dependency structures of database relationships. Proc. IFIP 74, North Holland, 1974, 580\u2013583.","DOI":"10.1515\/9783110840308-026"},{"issue":"3","key":"1_CR4","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1145\/320613.320614","volume":"5","author":"C. Beeri","year":"1980","unstructured":"C. Beeri, On the membership problem for functional and multivalued dependencies in relational databases. ACM Trans. on Database Systems 5,3 (Sept. 1980), 241\u2013259.","journal-title":"ACM Trans. on Database Systems"},{"issue":"1","key":"1_CR5","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1145\/320064.320066","volume":"4","author":"C. Beeri","year":"1979","unstructured":"C. Beeri and P. A. Bernstein, Computational problems related to the design of normal form relational schemas. ACM Trans. on Database Systems 4,1 (March 1979), 30\u201359.","journal-title":"ACM Trans. on Database Systems"},{"key":"1_CR6","unstructured":"C. Beeri, P. A. Bernstein, and N. Goodman, A sophisticate's introduction to database normalization theory. Proc. Int. Conf. on Very Large Data Bases, 1978, Berlin, 113\u2013124."},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"C. Beeri, R. Fagin, and J.H. Howard, A complete axiomatization for functional and multivalued dependencies in database relations. Proc. ACM SIGMOD Conf. on Management of Data, 1977, Toronto, 47\u201361.","DOI":"10.1145\/509404.509414"},{"issue":"3","key":"1_CR8","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1145\/2402.322389","volume":"30","author":"C. Beeri","year":"1983","unstructured":"C. Beeri, R. Fagin, D. Maier, and M. Yannakakis, On the desirability of acyclic database schemes. J. ACM 30,3 (July 1983), 479\u2013513.","journal-title":"J. ACM"},{"issue":"3","key":"1_CR9","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1137\/0210048","volume":"10","author":"C. Beeri","year":"1981","unstructured":"C. Beeri and P. Honeyman, Preserving functional dependencies. SIAM J. Computing 10,3 (Aug. 1981), 647\u2013656.","journal-title":"SIAM J. Computing"},{"key":"1_CR10","unstructured":"C. Beeri and H. F. Korth, Proc. 1st ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, 1982, Los Angeles, 51\u201362."},{"issue":"2","key":"1_CR11","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1137\/0210025","volume":"10","author":"C. Beeri","year":"1981","unstructured":"C. Beeri, A. O. Mendelzon, Y. Sagiv, and J. D. Ullman, Equivalence of relational database schemes, SIAM J. Computing 10,2 (June 1981), 352\u2013370.","journal-title":"SIAM J. Computing"},{"key":"1_CR12","unstructured":"C. Beeri and J. Rissanen, Faithful representation of relational database schemes. IBM Research Report, San Jose, California, 1980."},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"C. Beeri and M. Y. Vardi, On the properties of join dependencies. In Advances in Database Theory (H. Gallaire, J. Minker, and J. M. Nicolas, Eds.), Plenum Press, 1981, 25\u201372.","DOI":"10.1007\/978-1-4615-8297-7_2"},{"key":"1_CR14","unstructured":"C. Beeri and M. Y. Vardi, A proof procedure for data dependencies. Hebrew University of Jerusalem Technical Report, Dec. 1980."},{"key":"1_CR15","unstructured":"C. Beeri and M. Y. Vardi, On the complexity of testing implications of data dependencies. Hebrew University of Jerusalem Technical Report, Dec. 1980."},{"issue":"1","key":"1_CR16","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1137\/0213006","volume":"13","author":"C. Beeri","year":"1984","unstructured":"C. Beeri and M. Y. Vardi, Formal systems for tuple and equality-generating dependencies. SIAM J. Computing 13,1 (Feb 1984), 76\u201398.","journal-title":"SIAM J. Computing"},{"key":"1_CR17","unstructured":"C. Beeri and M. Y. Vardi, Formal systems for join dependencies. Hebrew Univ. of Jerusalem Technical Report, 1981. To appear in Theoretical Computer Science."},{"key":"1_CR18","unstructured":"C. Beeri and M. Y. Vardi, The implication problem for data dependencies. Proc. XP1 Workshop on Relational Database Theoery, Stony Brook, NY, June 1980."},{"key":"1_CR19","doi-asserted-by":"crossref","unstructured":"C. Beeri and M. Y. Vardi, The implication problem for data dependencies. Proc. 8th Int. Colloq. on Languages Automata and Programming, 1981, Acre Israel. Appeared in: Lecture Notes in Computer Science-Vol. 115, Springer-Verlag, 1981, 73\u201385.","DOI":"10.1007\/3-540-10843-2_7"},{"issue":"4","key":"1_CR20","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1145\/320493.320489","volume":"1","author":"P. A. Bernstein","year":"1976","unstructured":"P. A. Bernstein, Synthesizing third normal form relations from functional dependencies. ACM Trans. on Database Systems 1,4 (Dec. 1976), 277\u2013298.","journal-title":"ACM Trans. on Database Systems"},{"key":"1_CR21","doi-asserted-by":"crossref","unstructured":"M. A. Casanova, R. Fagin, and C. Papadimitriou, Inclusion dependencies and their interaction with functional dependencies. Proc. 1st ACM SIGACT-SIGMOD Symp. on Principles of Database Systems (1982), Los Angeles, 171\u2013176. To appear in J. Computer and System Sciences.","DOI":"10.1145\/588111.588141"},{"key":"1_CR22","doi-asserted-by":"crossref","unstructured":"E. P. F. Chan and A. O. Mendelzon, Independent and separable database schemes. Proc. 2nd ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, 1983, Atlanta, 288\u2013296.","DOI":"10.1145\/588058.588091"},{"key":"1_CR23","doi-asserted-by":"crossref","unstructured":"A. K. Chandra, H. R. Lewis, and J. A. Makowsky, Embedded implicational dependencies and their inference problem. Proc. XP1 Workshop on Relational Database Theoery, Stony Brook, NY, June 1980.","DOI":"10.1145\/800076.802488"},{"key":"1_CR24","doi-asserted-by":"crossref","unstructured":"A. K. Chandra, H. R. Lewis, and J. A. Makowsky, Embedded implicational dependencies and their inference problem. Proc. 13th ACM Symp. on Theory of Computing, 1981, Milwaukee, 342\u2013354.","DOI":"10.1145\/800076.802488"},{"key":"1_CR25","unstructured":"A. K. Chandra and M. Y. Vardi, The implication problem for functional and inclusion dependencies is undecidable. IBM Research Report RC 9980, May 1983."},{"issue":"6","key":"1_CR26","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1145\/362384.362685","volume":"13","author":"E. F. Codd","year":"1970","unstructured":"E. F. Codd, A relational model of data for large shared data banks. Comm. ACM 13,6 (June 1970), 377\u2013387.","journal-title":"Comm. ACM"},{"key":"1_CR27","unstructured":"E. F. Codd, Further normalization of the data base relational model. Courant Computer Science Symposia 6: Data Base Systems, 1971, Prentice Hall, 33\u201364."},{"issue":"2","key":"1_CR28","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1145\/358396.358400","volume":"25","author":"E. F. Codd","year":"1982","unstructured":"E. F. Codd, Relational databases: a practical foundation for productivity. Comm. ACM 25,2 (1982), 109\u2013117.","journal-title":"Comm. ACM"},{"key":"1_CR29","doi-asserted-by":"crossref","unstructured":"P. De Bra and J. Paredaens, Conditional dependencies for horizontal decompositions. Proc. 10th Int. Colloq. on Languages Automata and Programming, 1981, Barcelona. Appeared in: Lecture Notes in Computer Science-Vol. 154, Springer-Verlag, 1983, 67\u201382.","DOI":"10.1007\/BFb0036898"},{"issue":"4","key":"1_CR30","doi-asserted-by":"crossref","first-page":"758","DOI":"10.1145\/322217.322228","volume":"27","author":"P. J. Downey","year":"1980","unstructured":"P. J. Downey, R. Sethi, and R. E. Tarjan, Variations on the common subexpression problem. J. ACM 27,4 (Oct. 1980), 758\u2013771.","journal-title":"J. ACM"},{"key":"1_CR31","unstructured":"B. S. Dreben and W. D. Goldfarb, The Decision Problem: Solvable Classes of Quantificational Formulas. Addison Wesley, 1979."},{"issue":"3","key":"1_CR32","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1145\/320557.320571","volume":"2","author":"R. Fagin","year":"1977","unstructured":"R. Fagin, Multivalued dependencies and a new normal form for relational databases. ACM Trans. on Database Systems 2,3 (Sept. 1977), 262\u2013278.","journal-title":"ACM Trans. on Database Systems"},{"issue":"3","key":"1_CR33","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1145\/319587.319592","volume":"6","author":"R. Fagin","year":"1981","unstructured":"R. Fagin, A normal form for relational databases that is based on domains and keys. ACM Trans. on Database Systems 6,3 (Sept. 1981), 387\u2013415.","journal-title":"ACM Trans. on Database Systems"},{"key":"1_CR34","unstructured":"R. Fagin, Armstrong databases. Proc. 7th IBM Symp. on Mathematical Foundations of Computer Science, Kanagawa, Japan, May 1982. Also appeared as IBM Research Report RJ3440 (April 1982), San Jose, California."},{"issue":"4","key":"1_CR35","doi-asserted-by":"crossref","first-page":"952","DOI":"10.1145\/322344.322347","volume":"29","author":"R. Fagin","year":"1982","unstructured":"R. Fagin, Horn clauses and database dependencies. J. ACM 29,4 (Oct. 1982), 952\u2013985.","journal-title":"J. ACM"},{"issue":"3","key":"1_CR36","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1145\/2402.322390","volume":"30","author":"R. Fagin","year":"1983","unstructured":"R. Fagin, Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM 30,3 (July 1983), 514\u2013550.","journal-title":"J. ACM"},{"issue":"3","key":"1_CR37","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1145\/319732.319735","volume":"7","author":"R. Fagin","year":"1982","unstructured":"R. Fagin, A. O. Mendelzon, and J. D. Ullman, A simplified universal relation assumption and its properties. ACM Trans. on Database Systems 7,3 (Sept. 1982), 343\u2013360.","journal-title":"ACM Trans. on Database Systems"},{"key":"1_CR38","unstructured":"P. C. Fischer and D.-M. Tsou, Whether a set of multivalued dependencies implies a join dependencies is NP-hard. To appear in Theoretical Computer Science."},{"issue":"1","key":"1_CR39","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1145\/322290.322296","volume":"29","author":"Z. Galil","year":"1982","unstructured":"Z. Galil, An almost linear-time algorithm for computing a dependency basis in a relational database. J. ACM 29,1 (Jan. 1982), 96\u2013102.","journal-title":"J. ACM"},{"key":"1_CR40","unstructured":"M. R. Garey and D. S. Johnson, Computers and Intractibility: A Guide to the Theory of NP-Completeness. Freeman, 1979."},{"issue":"4","key":"1_CR41","doi-asserted-by":"crossref","first-page":"678","DOI":"10.1145\/322326.322331","volume":"29","author":"S. Ginsburg","year":"1982","unstructured":"S. Ginsburg and S. M. Zaiddan, Properties of functional dependency families. J ACM 29,4 (July 1982), 678\u2013698.","journal-title":"J ACM"},{"key":"1_CR42","doi-asserted-by":"crossref","unstructured":"M. H. Graham, Path expressions in databases. Proc. 2nd ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, 1983, Atlanta, 366\u2013378.","DOI":"10.1145\/588058.588101"},{"issue":"1","key":"1_CR43","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1145\/319830.319835","volume":"8","author":"M. H. Graham","year":"1983","unstructured":"M. H. Graham, Functions in databases. ACM Trans. on Database Systems 8,1 (March 1983), 81\u2013109.","journal-title":"ACM Trans. on Database Systems"},{"key":"1_CR44","doi-asserted-by":"crossref","unstructured":"M. H. Graham and A. O. Mendelzon, Notions of dependency satisfaction. Proc. 1st ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, 1983, Los Angeles, 177\u2013188.","DOI":"10.21236\/ADA135303"},{"key":"1_CR45","doi-asserted-by":"crossref","unstructured":"M. H. Graham, A. O. Mendelzon, and M. Y. Vardi, Notions of dependency satisfaction. Stanford University Technical Report STAN-CS-83-979, Aug. 1983.","DOI":"10.21236\/ADA135303"},{"key":"1_CR46","doi-asserted-by":"crossref","unstructured":"M. H. Graham and M. Yannakakis, Independent database schemes. Proc. 1st ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, 1982, Los Angeles, 199\u2013204. To appear in J. Computer and Systems Sciences.","DOI":"10.1145\/588111.588144"},{"key":"1_CR47","doi-asserted-by":"crossref","unstructured":"J. Grant and B. E. Jacobs, On the family of generalized dependency constraints. J. ACM 29,4 (Oct. 1982).","DOI":"10.1145\/322344.322348"},{"key":"1_CR48","doi-asserted-by":"crossref","unstructured":"Y. Gurevich and H. R. Lewis, The inference problem for template dependencies. Proc. First ACM SIGACT-SIGMOD Principles of Database Systems (1982), Los Angeles, 221\u2013229.","DOI":"10.1145\/588111.588148"},{"issue":"2","key":"1_CR49","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1137\/0208018","volume":"8","author":"K. Hagihara","year":"1979","unstructured":"K. Hagihara, M. Ito, K. Taniguchi, and T. Kasami, Decision problems for multivalued dependencies in relational databases. SIAM J. Computing 8,2 (May 1979), 247\u2013264.","journal-title":"SIAM J. Computing"},{"key":"1_CR50","doi-asserted-by":"crossref","unstructured":"I. J. Heath, Unacceptable file operations in a relational data base. Proc. 1971 ACM-SIGFIDET Workshop on Data Description, Access, and Control, 1971, San Diego.","DOI":"10.1145\/1734714.1734717"},{"issue":"3","key":"1_CR51","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1145\/322326.322330","volume":"29","author":"P. Honeyman","year":"1982","unstructured":"P. Honeyman, Testing satisfaction of functional dependencies. J. ACM 29,3 (July 1982), 668\u2013677.","journal-title":"J. ACM"},{"issue":"1","key":"1_CR52","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/0020-0190(80)90114-3","volume":"10","author":"P. Honeyman","year":"1980","unstructured":"P. Honeyman, R. E. Ladner, and M. Yannakakis, Testing the universal instance assumption. Inf. Proc. Letters, 10,1 (1980), 14\u201319.","journal-title":"Inf. Proc. Letters"},{"key":"1_CR53","unstructured":"R. Hull, Finitely specifiable implicational dependency families. Univ. of Southern California Technical Report, 1981. To appear in J. ACM."},{"key":"1_CR54","doi-asserted-by":"crossref","unstructured":"D. S. Johnson and A. Klug, Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies. Proc. 1st ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, 1982, Los Angeles, 164\u2013169. To appear in J. Computer and Systems Sciences.","DOI":"10.1145\/588111.588138"},{"key":"1_CR55","doi-asserted-by":"crossref","unstructured":"P. C. Kannelakis, S. S. Cosmadakis, and M. Y. Vardi, Unary inclusion dependencies have polynomial-time inference problems. Proc. 15th ACM SIGACT Symp. on Theory of Computing, 1983, Boston, 264\u2013277.","DOI":"10.1145\/800061.808756"},{"key":"1_CR56","doi-asserted-by":"crossref","unstructured":"[LMG]K. Laver, A. O. Mendelzon, and M. H. Graham, Functional dependencies on cyclic database schemes. Proc. ACM SIGMOD Symp. on Management of Data, 1983, San Jose, 79\u201391.","DOI":"10.1145\/582192.582208"},{"issue":"3","key":"1_CR57","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0022-0000(80)90027-6","volume":"21","author":"H. Lewis","year":"1980","unstructured":"H. Lewis, Complexity results for classes of quantificational formulas. J. Computer and Systems Sciences 21,3 (Dec. 1980), 317\u2013353.","journal-title":"J. Computer and Systems Sciences"},{"issue":"2","key":"1_CR58","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0020-0190(80)90005-8","volume":"11","author":"L. Liu","year":"1980","unstructured":"L. Liu and A. Demers, An algorithm for testing lossless join property in relational databases. Information Processing Letters 11,2 (1980), 73\u201376.","journal-title":"Information Processing Letters"},{"key":"1_CR59","volume-title":"The Theory of Relational Databases","author":"D. Maier","year":"1983","unstructured":"D. Maier, The Theory of Relational Databases. Computer Science Press, Rockville, Maryland, 1983."},{"issue":"3","key":"1_CR60","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1016\/0022-0000(80)90029-X","volume":"21","author":"D. Maier","year":"1980","unstructured":"D. Maier, A. O. Mendelzon, F. Sadri, and J. D. Ullman, Adequacy of decompositions of relational databases. J. Computer and Systems Sciences 21,3 (Dec. 1980), 368\u2013379.","journal-title":"J. Computer and Systems Sciences"},{"issue":"4","key":"1_CR61","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1145\/320107.320115","volume":"4","author":"D. Maier","year":"1979","unstructured":"D. Maier, A. Mendelzon, and Y. Sagiv, Testing implications of data dependencies. ACM Trans. on Database Systems 4,4 (Dec. 1979), 455\u2013469.","journal-title":"ACM Trans. on Database Systems"},{"key":"1_CR62","doi-asserted-by":"crossref","unstructured":"D. Maier, D. Rozenshtein, and D. S. Warren, Windows on the world. Proc. ACM SIGMOD Symp. on Management of Data, 1983, San Jose, 68\u201378.","DOI":"10.1145\/582192.582207"},{"issue":"4","key":"1_CR63","doi-asserted-by":"crossref","first-page":"680","DOI":"10.1145\/322276.322280","volume":"28","author":"D. Maier","year":"1981","unstructured":"D. Maier, Y. Sagiv, and M. Yannakakis, On the complexity of testing implications of functional and join dependencies. J. ACM 28,4 (Oct. 1981), 680\u2013695.","journal-title":"J. ACM"},{"key":"1_CR64","doi-asserted-by":"crossref","unstructured":"D. Maier, J. D. Ullman, and M. Y. Vardi, The revenge of the JD. Proc. 2nd ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, 1983, Atlanta, 279\u2013287.","DOI":"10.1145\/588058.588090"},{"key":"1_CR65","unstructured":"A. Mendelzon, Database states and their tablueax. Proc. XP2 Workshop on Relational Database Theory, June 1981."},{"key":"1_CR66","doi-asserted-by":"crossref","unstructured":"Mendelzon, A. O. and D. Maier, Generalized mutual dependencies and the decomposition of database relations. Proc. Int. Conf. on Very Large Data Bases, (A. L. Furtado and H. L. Morgan, eds.), 1979, 75\u201382.","DOI":"10.1109\/VLDB.1979.718121"},{"key":"1_CR67","doi-asserted-by":"crossref","unstructured":"J. C. Mitchell, Inference rules for functional and inclusion dependencies. Proc. 2nd ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, 1983, Atlanta, 58\u201369.","DOI":"10.1145\/588058.588067"},{"key":"1_CR68","unstructured":"J. C. Mitchell, The implication problem for functional and inclusion dependencies. MIT Technical Report. To appear in Information and Control."},{"key":"1_CR69","doi-asserted-by":"crossref","unstructured":"J-M. Nicolas, First order logic formalization for functional, multivalued, and mutual dependencies. Proc. ACM SIGMOD Symp. on Management of Data, 1978, 40\u201346.","DOI":"10.1145\/509252.509269"},{"key":"1_CR70","unstructured":"J. Paredaens, Transitive dependencies in a database scheme. MBLE Research Report R387, 1979."},{"key":"1_CR71","doi-asserted-by":"crossref","unstructured":"J. Paredanes and D. Janssens, Decompositions of relations: a comprehensive approach. In Advances in Data Base Theory \u2014 Vol. 1 (H. Gallaire, J. Minker, and J-M. Nicolas, eds.), Plenum Press, 1981, 73\u2013100.","DOI":"10.1007\/978-1-4615-8297-7_3"},{"key":"1_CR72","doi-asserted-by":"crossref","unstructured":"D. S. Parker and K. Parsaye-Ghomi, Inference involving embedded multivalued dependencies and transitive dependencies. Proc. ACM SIGMOD Symp. on Management of Data, 1980, 52\u201357.","DOI":"10.1145\/582250.582259"},{"issue":"4","key":"1_CR73","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1145\/320576.320580","volume":"2","author":"J. Rissanen","year":"1977","unstructured":"J. Rissanen, Independent components of relations, ACM Trans. on Database Systems 2,4 (1977), 317\u2013325.","journal-title":"ACM Trans. on Database Systems"},{"key":"1_CR74","doi-asserted-by":"crossref","unstructured":"J. Rissanen, Theory of relations for databases \u2014 a tutorial survey. Proc. 7th Symp. on Math. Found. of Comp. Science, 1978, Lecture Notes in Computer Science \u2014 Vol. 64, Springer-Verlag, 537\u2013551.","DOI":"10.1007\/3-540-08921-7_102"},{"key":"1_CR75","doi-asserted-by":"crossref","unstructured":"J. Rissanen, On equivalence of database schemes. Proc. 1st ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, 1982, Los Angeles, 23\u201326.","DOI":"10.1145\/588111.588116"},{"key":"1_CR76","unstructured":"H. Rogers, Theory of Recursive Functions and \u00c8ffective Computability. McGraw-Hill, 1967."},{"issue":"2","key":"1_CR77","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1145\/322307.322312","volume":"29","author":"F. Sadri","year":"1981","unstructured":"F. Sadri and J. D. Ullman, Template dependencies: A large class of dependencies in relational databases and their complete axiomatization. J. ACM 29,2 (April 1981), 363\u2013372.","journal-title":"J. ACM"},{"issue":"2","key":"1_CR78","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1145\/322186.322190","volume":"27","author":"Y. Sagiv","year":"1980","unstructured":"Y. Sagiv, An algorithm for inferring multivalued dependencies with an application to propositional logic. J. ACM 27,2 (April 1980), 250\u2013262.","journal-title":"J. ACM"},{"key":"1_CR79","doi-asserted-by":"crossref","unstructured":"Y. Sagiv, Can we use the universal instance assumption without using nulls? Proc. ACM SIGMOD Symp. on Management of Data, 1981, 108\u2013120.","DOI":"10.1145\/582318.582336"},{"issue":"2","key":"1_CR80","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1145\/319983.319988","volume":"8","author":"Y. Sagiv","year":"1983","unstructured":"Y. Sagiv, A characterization of globally consistent databases and their correct access paths. ACM Trans. on Database Systems 8,2 (June 1983), 266\u2013286.","journal-title":"ACM Trans. on Database Systems"},{"issue":"1","key":"1_CR81","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1145\/322290.322297","volume":"29","author":"Y. Sagiv","year":"1982","unstructured":"Y. Sagiv and S. Walecka, Subset dependencies and a completeness result for a subclass of embedded multivalued dependencies. J. ACM 29,1 (Jan. 1982), 103\u2013117.","journal-title":"J. ACM"},{"issue":"1","key":"1_CR82","first-page":"12","volume":"14","author":"M. Schkolnick","year":"1982","unstructured":"M. Schkolnick and P. Sorenson, The effects of denormalization on database performance. The Australian Computer Journal 14,1 (Feb. 1982), 12\u201318.","journal-title":"The Australian Computer Journal"},{"key":"1_CR83","doi-asserted-by":"crossref","unstructured":"E. Sciore, Real-world MVDs. Proc. ACM SIGMOD Symp. on Management of Data, 1981, 121\u2013132.","DOI":"10.1145\/582335.582337"},{"key":"1_CR84","doi-asserted-by":"crossref","unstructured":"E. Sciore, Inclusion dependencies and the universal instance. Proc. 2nd ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, 1983, Atlanta, 48\u201357.","DOI":"10.1145\/588058.588066"},{"issue":"2","key":"1_CR85","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1145\/322307.322313","volume":"29","author":"E. Sciore","year":"1982","unstructured":"E. Sciore, A complete axiomatization of full join dependencies. J. ACM 29,2 (April 1982), 373\u2013393.","journal-title":"J. ACM"},{"key":"1_CR86","volume-title":"Principles of Database Systems","author":"J. D. Ullman","year":"1982","unstructured":"J. D. Ullman, Principles of Database Systems. Computer Science Press, Rockville, Maryland (1982)"},{"key":"1_CR87","unstructured":"M. Y. Vardi, The implication problem for data dependencies in relational databases. Ph.D. Dissertation (in Hebrew), The Hebrew University in Jerusalem, Sept. 1981."},{"key":"1_CR88","doi-asserted-by":"crossref","unstructured":"M. Y. Vardi, The implication and finite implication problems for typed template dependencies. Proc. 1st ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, 1982, Los Angeles, 230\u2013238. To appear in J. Computer and Systems Sciences.","DOI":"10.1145\/588111.588149"},{"key":"1_CR89","doi-asserted-by":"crossref","unstructured":"M. Y. Vardi, On decomposition of relational databases. Proc. 23rd IEEE Symp. on Foundation of Computer Science, Chicago, 1982, 176\u2013185.","DOI":"10.1109\/SFCS.1982.75"},{"key":"1_CR90","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1007\/BF00290729","volume":"19","author":"M. Y. Vardi","year":"1983","unstructured":"M. Y. Vardi, Inferring multivalued dependencies from functional and join dependencies. Acta Informatica, 19(1983), 305\u2013324.","journal-title":"Acta Informatica"},{"key":"1_CR91","unstructured":"M. Y. Vardi, A note on lossless database decompositions. To appear in Information Processing Letters."},{"key":"1_CR92","unstructured":"M. Yannakakis, Algorithms for acyclic database schemes. Proc. Int. Conf. on Very Large Data Bases, 1981, 82\u201394."},{"issue":"2","key":"1_CR93","first-page":"3","volume":"25","author":"M. Yannakakis","year":"1982","unstructured":"M. Yannakakis and C. Papadimitriou, Algebraic dependencies. J. Computer and System Sciences 25,2 (1982), 3\u201341.","journal-title":"J. Computer and System Sciences"},{"key":"1_CR94","unstructured":"C. Zaniolo, Analysis and design of relational schemata for database systems, Ph.D. Dissertation, Tech. Rep. UCLA-ENG-7669, UCLA, July 1976."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-13345-3_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:07:10Z","timestamp":1605643630000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-13345-3_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1984]]},"ISBN":["9783540133452","9783540388869"],"references-count":94,"URL":"https:\/\/doi.org\/10.1007\/3-540-13345-3_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1984]]}}}