{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T05:01:35Z","timestamp":1768107695050,"version":"3.49.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[1983,7,1]],"date-time":"1983-07-01T00:00:00Z","timestamp":425865600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1983,7]]},"DOI":"10.1145\/2402.322389","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:25:57Z","timestamp":1027769157000},"page":"479-513","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":545,"title":["On the Desirability of Acyclic Database Schemes"],"prefix":"10.1145","volume":"30","author":[{"given":"Catriel","family":"Beeri","sequence":"first","affiliation":[{"name":"The Hebrew University of Jerusalem, Jerusalem, Israel"}]},{"given":"Ronald","family":"Fagin","sequence":"additional","affiliation":[{"name":"IBM Research Laboratory K51\/281, 5600 Cottle Road, San Jose, CA"}]},{"given":"David","family":"Maier","sequence":"additional","affiliation":[{"name":"Oregon Graduate Center, 19600 NW Walker Road, Beaverton, OR"}]},{"given":"Mihalis","family":"Yannakakis","sequence":"additional","affiliation":[{"name":"Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ"}]}],"member":"320","published-online":{"date-parts":[[1983,7]]},"reference":[{"key":"e_1_2_1_1_2","doi-asserted-by":"publisher","DOI":"10.1145\/320083.320091"},{"key":"e_1_2_1_2_2","first-page":"580","volume-title":"North Holland","author":"ARMSTRONG W.W.","year":"1974","unstructured":"ARMSTRONG , W.W. Dependency structures of database relauonships. In Prec. IFIP 74 , North Holland , Amsterdam , 1974 , pp 580 -- 583 ARMSTRONG, W.W.Dependency structures of database relauonships. In Prec. IFIP 74, North Holland, Amsterdam, 1974, pp 580--583"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/1017466.1017467"},{"key":"e_1_2_1_4_2","volume-title":"Prec. 7th Int. Conf. on Graph-Theoretic Concepts in Computer Science","author":"BATI","year":"1981","unstructured":"BATI m, C., D'AT m, A., AND MOSCA m NI, M . Formal tools for top.down and bottom-up generation of acy~lic relational schemata . Prec. 7th Int. Conf. on Graph-Theoretic Concepts in Computer Science , Linz, Austria , 1981 . BATIm, C., D'ATm, A., AND MOSCAmNI, M. Formal tools for top.down and bottom-up generation of acy~lic relational schemata. Prec. 7th Int. Conf. on Graph-Theoretic Concepts in Computer Science, Linz, Austria, 1981."},{"key":"e_1_2_1_5_2","first-page":"47","volume-title":"Prec. Int. Conf. on Management of Data","author":"BEERI C.","year":"1977","unstructured":"BEERI , C. , F^ OIN , R , AND HOWARD , J.H. A complete axlomatization for functional and multivalued dependencies in database relations . In Prec. Int. Conf. on Management of Data ( Toronto, Ont., Can. , Aug. 3-5, 1977 ), ACM, New York, 1977, pp. 47 - 61 . 10.1145\/509404.509414 BEERI, C., F^OIN, R, AND HOWARD, J.H. A complete axlomatization for functional and multivalued dependencies in database relations. In Prec. Int. Conf. on Management of Data (Toronto, Ont., Can., Aug. 3-5, 1977), ACM, New York, 1977, pp. 47-61. 10.1145\/509404.509414"},{"key":"e_1_2_1_6_2","first-page":"355","volume-title":"ACM","author":"BI ERI","year":"1981","unstructured":"BI \/ ERI , C., FAGIN , g., MATER , D. , MENDELZON , A.O. , ULLMAN , J.D. , AND YANNAKAKIS , M. Properties of acyclic database schemes In Prec. 13th Ann. A CM Symt~. on Theory of Computing (Milwaukee, Wise, May ll-13, 1981) , ACM , New York , 1981 , pp 355 - 362 . 10.1145\/800076.802489 BI\/ERI, C., FAGIN, g., MATER, D., MENDELZON, A.O., ULLMAN, J.D., AND YANNAKAKIS, M. Properties of acyclic database schemes In Prec. 13th Ann. A CM Symt~. on Theory of Computing (Milwaukee, Wise, May ll-13, 1981), ACM, New York, 1981, pp 355-362. 10.1145\/800076.802489"},{"key":"e_1_2_1_7_2","first-page":"2","volume":"10","author":"BEERI C.","year":"1981","unstructured":"BEERI , C. , MENDELZON , A.O. , SAOI v, Y, AND ULLMAN , J.D. Equivalence of relational database schemes. SIAM J. Comput. 10 , 2 ( June 1981 ), 352-370. BEERI, C., MENDELZON, A.O., SAOIv, Y, AND ULLMAN, J.D. Equivalence of relational database schemes. SIAM J. Comput. 10, 2 (June 1981), 352-370.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_8_2","volume-title":"Calif.","author":"BEERI C.","year":"1980","unstructured":"BEERI , C. , AND RlSS ANEN , J. Faithful representation of relational database schemes Res. Pep. RJ2722, IBM Research Laboratory, San Jose , Calif. , 1980 . BEERI, C., AND RlSSANEN, J. Faithful representation of relational database schemes Res. Pep. RJ2722, IBM Research Laboratory, San Jose, Calif., 1980."},{"key":"e_1_2_1_9_2","first-page":"25","volume-title":"Advances in Database Theory, H Gallaire, J. Minker","author":"BEERI C.","year":"1981","unstructured":"BEERI , C. , AND VARDI , M Y . On the properties of join dependencies , in Advances in Database Theory, H Gallaire, J. Minker , and J-M. Nicolas, Eds, Plenum, N.Y ., 1981 , pp. 25 - 72 . BEERI, C., AND VARDI, M Y. On the properties of join dependencies, in Advances in Database Theory, H Gallaire, J. Minker, and J-M. Nicolas, Eds, Plenum, N.Y., 1981, pp. 25-72."},{"key":"e_1_2_1_10_2","unstructured":"BERGE C Graphs and Hypergraphs. North-Holland Amsterdam 1976.   BERGE C Graphs and Hypergraphs. North-Holland Amsterdam 1976."},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322238"},{"key":"e_1_2_1_12_2","first-page":"4","volume":"10","author":"RNS EIN","year":"1981","unstructured":"Bt RNS r EIN , P.A., AND GOODMAN , N The power of natural semijoins SIAM ~ Comput 10 , 4 ( Nov. 1981 ), 751-771. BtRNSrEIN, P.A., AND GOODMAN, N The power of natural semijoins SIAM ~ Comput 10, 4 (Nov. 1981), 751-771.","journal-title":"Comput"},{"key":"e_1_2_1_13_2","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0304-3975(80)90075-4","volume":"10","year":"1980","unstructured":"BlsKtre, J. Inferences of multivalued dependencies in fixed and undetermined universe. Theor Comput. Sci. 10 ( 1980 ), 93 - 105 . BlsKtre, J. Inferences of multivalued dependencies in fixed and undetermined universe. Theor Comput. Sci. 10 (1980), 93-105.","journal-title":"Theor Comput. Sci."},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/362384.362685"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/320557.320571"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322390"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/319732.319735"},{"key":"e_1_2_1_18_2","volume-title":"Algonthrmc Graph Theory and Perfect Graphs","author":"GOLUMBIC M.C.","year":"1980","unstructured":"GOLUMBIC , M.C. Algonthrmc Graph Theory and Perfect Graphs . Academic Press , New York , 1980 GOLUMBIC, M.C. Algonthrmc Graph Theory and Perfect Graphs. Academic Press, New York, 1980"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/319758.319775"},{"key":"e_1_2_1_21_2","volume-title":"Umv. of Toronto","author":"GRAHA","year":"1979","unstructured":"GRAHA m, M H. On the universal relaion Tech. Pep ., Umv. of Toronto , Toronto , Oat, Can , Sept. 1979 . GRAHAm, M H. On the universal relaion Tech. Pep., Umv. of Toronto, Toronto, Oat, Can, Sept. 1979."},{"key":"e_1_2_1_22_2","first-page":"2","volume":"8","author":"HAG AgA","year":"1979","unstructured":"HAG m AgA , K., ITO , M. , TANIGUCHI , K , AND Kxs Am, T . Decision problems for mulUvalued dependencies in relaUonal databases SIAM J Comput. 8 , 2 ( May 1979 ), 247-264. HAGmAgA, K., ITO, M., TANIGUCHI, K, AND KxsAm, T. Decision problems for mulUvalued dependencies in relaUonal databases SIAM J Comput. 8, 2 (May 1979), 247-264.","journal-title":"SIAM J Comput."},{"key":"e_1_2_1_24_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0020-0190(80)90111-8","volume":"10","author":"HONEYMAN P","year":"1980","unstructured":"HONEYMAN , P , LADNER , R.E , AN t> YANNAK AKIS , i Testing the universal instance assumption. Inf. Prec. Lett. 10 , 1 ( 1980 ), 14-19 HONEYMAN, P, LADNER, R.E, ANt> YANNAKAKIS, i Testing the universal instance assumption. Inf. Prec. Lett. 10, 1 (1980), 14-19","journal-title":"Inf. Prec. Lett."},{"key":"e_1_2_1_25_2","volume-title":"Proc XP1 Workshop, Stony Brook, N.Y.","author":"KORTFI H.F.","year":"1980","unstructured":"KORTFI , H.F. , AND ULLMAN , J.D. SYSTEM \/ U\" A database system based on the universal relation assumption . Proc XP1 Workshop, Stony Brook, N.Y. , June 1980 . KORTFI, H.F., AND ULLMAN, J.D. SYSTEM\/U\" A database system based on the universal relation assumption. Proc XP1 Workshop, Stony Brook, N.Y., June 1980."},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/322307.322311"},{"key":"e_1_2_1_27_2","first-page":"61","volume-title":"Proc 5th Int. Conf. on Very Large Data Bases (Rue de Janeiro, Brazil","author":"E.","year":"1979","unstructured":"LmN, Y. E. Multwalued dependencies wath null values m relational data bases . In Proc 5th Int. Conf. on Very Large Data Bases (Rue de Janeiro, Brazil , Oct. 3-5, 1979 ), ACM, New York , pp. 61 - 66 LmN, Y.E. Multwalued dependencies wath null values m relational data bases. In Proc 5th Int. Conf. on Very Large Data Bases (Rue de Janeiro, Brazil, Oct. 3-5, 1979), ACM, New York, pp. 61-66"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/319540.319546"},{"key":"e_1_2_1_29_2","volume-title":"Stony Brook, N.Y.","author":"MA","year":"1980","unstructured":"MA mg, D. Discarding the universal instance assumption Preliminary results Proc XPI Workshop , Stony Brook, N.Y. , June 1980 MAmg, D. Discarding the universal instance assumption Preliminary results Proc XPI Workshop, Stony Brook, N.Y., June 1980"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/322276.322280"},{"key":"e_1_2_1_31_2","first-page":"75","volume-title":"Prec. 5th int. Conf. on Very Large Data Bases (Rue de Janeiro, Brazil","author":"MENO~LZON A O","year":"1979","unstructured":"MENO~LZON , A O ., AND M^ IER , D. Generalized mutual dependencies and the decomposition of database relations , in Prec. 5th int. Conf. on Very Large Data Bases (Rue de Janeiro, Brazil , Oct 3-5, 1979 ), ACM, New York , pp. 75 - 82 MENO~LZON, A O., AND M^IER, D. Generalized mutual dependencies and the decomposition of database relations, in Prec. 5th int. Conf. on Very Large Data Bases (Rue de Janeiro, Brazil, Oct 3-5, 1979), ACM, New York, pp. 75-82"},{"key":"e_1_2_1_32_2","series-title":"Lecture Notes m Computer Science 64, J. Winkowskl, Ed","first-page":"537","volume-title":"Prec. 7th Symp on Mathematical Foundations of Computer Science","author":"RISSANEN","unstructured":"RISSANEN , J Theory of relations for databases~A tutorial survey , in Prec. 7th Symp on Mathematical Foundations of Computer Science , Lecture Notes m Computer Science 64, J. Winkowskl, Ed , Spnnger-Verlag , pp. 537 - 551 RISSANEN, J Theory of relations for databases~A tutorial survey, in Prec. 7th Symp on Mathematical Foundations of Computer Science, Lecture Notes m Computer Science 64, J. Winkowskl, Ed, Spnnger-Verlag, pp. 537-551"},{"key":"e_1_2_1_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/320576.320580"},{"key":"e_1_2_1_34_2","first-page":"26","volume-title":"Proc Ist A CM Conf on Princ~les of Database Systems","author":"RISSAN~'","year":"1982","unstructured":"RISSAN~' ,~, J. On equivalence of database schemes . In Proc Ist A CM Conf on Princ~les of Database Systems ( Los Angeles, Cahf. , Mar. 29-31, 1982 ), ACM, New York, 1982, pp. 23~- 26 . 10.1145\/588111.588116 RISSAN~',~, J.On equivalence of database schemes. In Proc Ist A CM Conf on Princ~les of Database Systems (Los Angeles, Cahf., Mar. 29-31, 1982), ACM, New York, 1982, pp. 23~-26. 10.1145\/588111.588116"},{"key":"e_1_2_1_35_2","volume-title":"E THE umversal instance and database design. Ph D. Dissertation","author":"SCIORE","year":"1980","unstructured":"SCIORE , E THE umversal instance and database design. Ph D. Dissertation , Princeton, Univ , Princeton, N.J. , 1980 . SCIORE, E THE umversal instance and database design. Ph D. Dissertation, Princeton, Univ, Princeton, N.J., 1980."},{"key":"e_1_2_1_36_2","unstructured":"SCIOtLE E.Some observations on real-world data dependencies Proc. XP1 Workshop Stony Brook N.Y June 1980.  SCIOtLE E.Some observations on real-world data dependencies Proc. XP1 Workshop Stony Brook N.Y June 1980."},{"key":"e_1_2_1_37_2","first-page":"121","volume-title":"E. Real-world MVDs. In Proc Int. Conf on Management of Data","author":"SC ORE","year":"1981","unstructured":"SC t ORE , E. Real-world MVDs. In Proc Int. Conf on Management of Data ( Ann Arbor, Mich., Apr. 29- May 1, 1981 ), ACM, New York, 1981, pp 121 - 132 . 10.1145\/582318.582337 SCtORE, E. Real-world MVDs. In Proc Int. Conf on Management of Data (Ann Arbor, Mich., Apr. 29-May 1, 1981), ACM, New York, 1981, pp 121-132. 10.1145\/582318.582337"},{"key":"e_1_2_1_38_2","volume-title":"Bell Laboratories","author":"TARSAN R.E.","year":"1982","unstructured":"TARSAN , R.E. , AND YANNAKAKIS , M. Strnple lmear-tmae algonthms to test ehordality of graphs, test acychcity of hypergraphs, and selecuvely reduce acychc hypergraphs. Teeh. Pep ., Bell Laboratories , Murray Hdl , N.J. , Mar. 1982 . TARSAN, R.E., AND YANNAKAKIS, M. Strnple lmear-tmae algonthms to test ehordality of graphs, test acychcity of hypergraphs, and selecuvely reduce acychc hypergraphs. Teeh. Pep., Bell Laboratories, Murray Hdl, N.J., Mar. 1982."},{"key":"e_1_2_1_39_2","volume-title":"Rehovot","author":"VARDI M.Y","year":"1980","unstructured":"VARDI , M.Y lnfemng multlvalued dependencies from funcUonal and join dependencies. Tech. Rep., Weizmann lnstttute , Rehovot , Israel , 1980 VARDI, M.Y lnfemng multlvalued dependencies from funcUonal and join dependencies. Tech. Rep., Weizmann lnstttute, Rehovot, Israel, 1980"},{"key":"e_1_2_1_40_2","first-page":"176","volume-title":"Proc. 23rd IEEE Syrup. on Foundations of Computer Science","author":"VARDI M.Y.","year":"1982","unstructured":"VARDI , M.Y. On decompositton of relational databases . In Proc. 23rd IEEE Syrup. on Foundations of Computer Science ( Chicago, I11. , Oct. 1982 ), IEEE, New York, 1982, pp 176 - 185 . VARDI, M.Y. On decompositton of relational databases. In Proc. 23rd IEEE Syrup. on Foundations of Computer Science (Chicago, I11., Oct. 1982), IEEE, New York, 1982, pp 176-185."},{"key":"e_1_2_1_41_2","first-page":"162","volume-title":"Proc. Int. Conf on Management of Data","author":"VASSLUOU","year":"1979","unstructured":"VASSLUOU , YNull values m database management--A denotadonal semantics approach . In Proc. Int. Conf on Management of Data ( Boston, Mass, May 30-june 1 , 1979 ), ACM, New York, pp 162 - 169 . 10.1145\/582095.582123 VASSLUOU, YNull values m database management--A denotadonal semantics approach. In Proc. Int. Conf on Management of Data (Boston, Mass, May 30-june 1, 1979), ACM, New York, pp 162-169. 10.1145\/582095.582123"},{"key":"e_1_2_1_42_2","volume-title":"Proc. XP1 Workshop, Stony Brook, N Y","author":"WALKER A","year":"1980","unstructured":"WALKER , A Time and space m a lathce of umversal relations with blank entries . Proc. XP1 Workshop, Stony Brook, N Y , June 1980 WALKER, A Time and space m a lathce of umversal relations with blank entries. Proc. XP1 Workshop, Stony Brook, N Y, June 1980"},{"key":"e_1_2_1_43_2","first-page":"82","volume-title":"Proc. 7th Int. Conf. on Very Large Data Bases","author":"YANNAKAKIS M.","year":"1981","unstructured":"YANNAKAKIS , M. Algorithms for acychc database schemes . In Proc. 7th Int. Conf. on Very Large Data Bases ( Cannes, France , Sept. 9-11, 1981 ), ACM, New York, 1981, pp. 82 -- 94 . YANNAKAKIS, M.Algorithms for acychc database schemes. In Proc. 7th Int. Conf. on Very Large Data Bases (Cannes, France, Sept. 9-11, 1981), ACM, New York, 1981, pp. 82--94."},{"key":"e_1_2_1_44_2","unstructured":"Yu C.T AND OZSOYO~LO M.Z An algorithm for tree-query membership of a distributed query Proc 1979 1EEE COMPSAC IEEE N.Y. 1979 pp 306-312  Yu C.T AND OZSOYO~LO M.Z An algorithm for tree-query membership of a distributed query Proc 1979 1EEE COMPSAC IEEE N.Y. 1979 pp 306-312"},{"key":"e_1_2_1_45_2","volume-title":"July","author":"ZANIOLO C.","year":"1976","unstructured":"ZANIOLO , C. Analysts and destgn of relatmnal schemata for database systems. Ph.D. Dissertation , Umv of Cahfornla at Los Angeles , July 1976 . Avadable as Tech. Rap UCLA-ENG- 7669. ZANIOLO, C.Analysts and destgn of relatmnal schemata for database systems. Ph.D. Dissertation, Umv of Cahfornla at Los Angeles, July 1976. Avadable as Tech. Rap UCLA-ENG-7669."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2402.322389","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2402.322389","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:48:11Z","timestamp":1750240091000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2402.322389"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,7]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1983,7]]}},"alternative-id":["10.1145\/2402.322389"],"URL":"https:\/\/doi.org\/10.1145\/2402.322389","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1983,7]]},"assertion":[{"value":"1983-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}