{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:56:07Z","timestamp":1725663367016},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540127277"},{"type":"electronic","value":"9783540387145"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1983]]},"DOI":"10.1007\/3-540-12727-5_3","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:55:28Z","timestamp":1330192528000},"page":"65-89","source":"Crossref","is-referenced-by-count":11,"title":["Acyclic database schemes (of various degrees): A painless introduction"],"prefix":"10.1007","author":[{"given":"Ronald","family":"Fagin","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,29]]},"reference":[{"issue":"3","key":"3_CR1","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1145\/320083.320091","volume":"4","author":"A. V. Aho","year":"1979","unstructured":"Aho, A. V., C. Beeri, and J. D. Ullman, \"The theory of joins in relational databases,\" ACM Trans. on Database Systems 4,3 (1979), 297\u2013314.","journal-title":"ACM Trans. on Database Systems"},{"key":"3_CR2","unstructured":"Ausiello, G., A. d'Atri, and M. Moscarini, \"Minimal coverings of acyclic database schemata\", Proc. ONERA-CERT Toulouse Workshop on Logical Bases for Data Bases (Dec. 1982)."},{"key":"3_CR3","unstructured":"Batini, C., A. D'Atri, and M. Moscarini, \"Formal tools for top-down and bottom-up generation of acyclic relational schemata\", Proc. 7th Int. Conf. on Graph-Theoretic Concepts in Computer Science, Linz (1981)."},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"Beeri, C., R. Fagin, D. Maier, A. O. Mendelzon, J. D. Ullman, and M. Yannakakis, \"Properties of acyclic database schemes,\" Proc. Thirteenth Annual ACM Symposium on the Theory of Computing, 355\u2013362 (1981).","DOI":"10.1145\/800076.802489"},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"Beeri, C., R. Fagin, D. Maier, and M. Yannakakis, \"On the desirability of acyclic database schemes,\" J. ACM, to appear.","DOI":"10.1145\/2402.322389"},{"issue":"1","key":"3_CR6","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1145\/322234.322238","volume":"28","author":"P. A. Bernstein","year":"1981","unstructured":"Bernstein, P. A. and D. W. Chiu, \"Using semi-joins to solve relational queries\", J. ACM 28, 1 (Jan. 1981), 25\u201340.","journal-title":"J. ACM"},{"issue":"4","key":"3_CR7","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1137\/0210059","volume":"10","author":"P. A. Bernstein","year":"1981","unstructured":"Bernstein, P. A. and N. Goodman, \"The power of natural semijoins\" SIAM J. Computing 10,4 (Nov. 1981), 751\u2013771.","journal-title":"SIAM J. Computing"},{"key":"3_CR8","unstructured":"Biskup, J. and H. H. Bruggemann, \"Towards designing acyclic database schemas\", Proc. ONERA-CERT Toulouse Workshop on Logical Bases for Data Bases (Dec. 1982)."},{"issue":"6","key":"3_CR9","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1147\/rd.206.0560","volume":"20","author":"D. D. Chamberlin","year":"1976","unstructured":"Chamberlin, D.D., M. M. Astrahan, K. P. Eswaran, P. P. Griffiths, R. A. Lorie, J. W. Mehl, P. Reisner, and B. W. Wade, \"SEQUEL 2: A unified approach to data definition, manipulation, and control,\" IBM J. of Research and Development 20,6 (Nov. 1976), 560\u2013575.","journal-title":"IBM J. of Research and Development"},{"key":"3_CR10","unstructured":"Chase, K., \"Join graphs and acyclic data base schemes\", Proc. 1981 Very Large Data Bases Conf., 95\u2013100."},{"issue":"6","key":"3_CR11","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1145\/362384.362685","volume":"13","author":"E. F. Codd","year":"1970","unstructured":"Codd, E. F., \"A relational model for large shared data banks,\" Comm. ACM 13,6 (1970), 377\u2013387.","journal-title":"Comm. ACM"},{"key":"3_CR12","unstructured":"Codd, E. F., \"Further normalization of the database relational model,\" Courant Computer Science Symposia 6: Data Base Systems, (May 24\u201325, 1971), Prentice-Hall, 65\u201398."},{"key":"3_CR13","unstructured":"D'Atri, A. and M. Moscarini, \"Acyclic hypergraphs: their recognition and top-down vs bottom-up generation,\" Consiglio Nazionale Delle Ricerche, Istituto di Analisi dei Sistemi ed Informatica, R.29 (1982)."},{"issue":"3","key":"3_CR14","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1145\/320557.320571","volume":"2","author":"R. Fagin","year":"1977","unstructured":"Fagin, R., \"Multivalued dependencies and a new normal form for relational databases,\" ACM Trans. on Database Systems 2,3 (1977), 262\u2013278.","journal-title":"ACM Trans. on Database Systems"},{"issue":"3","key":"3_CR15","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1145\/319587.319592","volume":"6","author":"R. Fagin","year":"1981","unstructured":"Fagin, R., \"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":"3_CR16","doi-asserted-by":"crossref","unstructured":"Fagin, R., \"Degrees of acyclicity for hypergraphs and relational database schemes\". To appear, J. ACM.","DOI":"10.1145\/2402.322390"},{"issue":"3","key":"3_CR17","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1145\/319732.319735","volume":"7","author":"R. Fagin","year":"1982","unstructured":"Fagin, R., 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":"3_CR18","unstructured":"Finkelstein, S., private communication."},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"Goodman, N., and O. Shmueli, \"The tree property is fundamental for query processing\", Proc. First ACM SIGACT-SIGMOD Principles of Database Systems (1982), Los Angeles, 40\u201348.","DOI":"10.1145\/588111.588119"},{"key":"3_CR20","doi-asserted-by":"crossref","unstructured":"Goodman, N., and O. Shmueli, \"Transforming cyclic schemas into trees\", Proc. First ACM SIGACT-SIGMOD Principles of Database Systems (1982), Los Angeles, 49\u201354.","DOI":"10.1145\/588111.588120"},{"issue":"4","key":"3_CR21","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/319758.319775","volume":"7","author":"N. Goodman","year":"1982","unstructured":"Goodman, N., and O. Shmueli, \"Tree queries: a simple class of queries,\" ACM Trans. on Database Systems 7,4 (Dec. 1982), 653\u2013677.","journal-title":"ACM Trans. on Database Systems"},{"key":"3_CR22","doi-asserted-by":"crossref","unstructured":"Goodman, N., O. Shmueli, and Y. C. Tay, \"GYO reductions, canonical connections, and cyclic schemas and tree projections\", Proc. Second ACM SIGACT-SIGMOD Principles of Database Systems (1983), Atlanta, 267\u2013278.","DOI":"10.1145\/588058.588089"},{"key":"3_CR23","unstructured":"Graham, M. H., \"On the universal relation,\" Technical Report, Univ. of Toronto (Sept. 1979)."},{"key":"3_CR24","unstructured":"Gyssens, M. and J. Paredaens, \"A decomposition methodology for cyclic databases\", Proc. ONERA-CERT Toulouse Workshop on Logical Bases for Data Bases (Dec. 1982)."},{"key":"3_CR25","unstructured":"Hanatani, Y., \"Eliminating cyclies in database schemas\", Proc. ONERA-CERT Toulouse Workshop on Logical Bases for Data Bases (Dec. 1982)."},{"issue":"1","key":"3_CR26","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/0020-0190(80)90114-3","volume":"10","author":"P. Honeyman","year":"1980","unstructured":"Honeyman, P., 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":"3_CR27","unstructured":"Hull, R., \"Acyclic join dependency and database projections,\" USC Technical Report (June 1981)."},{"issue":"4","key":"3_CR28","doi-asserted-by":"publisher","first-page":"680","DOI":"10.1145\/322276.322280","volume":"28","author":"D. Maier","year":"1981","unstructured":"Maier, D., 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":"3_CR29","doi-asserted-by":"crossref","unstructured":"Maier, D. and J. D. Ullman, \"Connections in acyclic hypergraphs,\" Proc. First ACM SIGACT-SIGMOD Principles of Database Systems (1982), Los Angeles, 34\u201339.","DOI":"10.1145\/588111.588118"},{"issue":"2","key":"3_CR30","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1145\/320544.320553","volume":"2","author":"E. A. Ozkarahan","year":"1977","unstructured":"Ozkarahan, E. A., S. A. Schuster, and K. C. Sevick, \"Performance evaluation of a relational associative processor\", ACM Trans. on Database Systems 2,2 (June 1977), 175\u2013196.","journal-title":"ACM Trans. on Database Systems"},{"key":"3_CR31","first-page":"537","volume":"64","author":"J. Rissanen","year":"1978","unstructured":"Rissanen, J., \"Theory of relations for databases \u2014 a tutorial survey.\" Proc. 7th Symp. on Math. Found. of Comp. Science, Lecture Notes in Comp. Science, 64 (1978), Springer-Verlag, 537\u2013551.","journal-title":"Proc. 7th Symp. on Math. Found. of Comp. Science, Lecture Notes in Comp. Science"},{"issue":"1","key":"3_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/320128.320129","volume":"5","author":"J. B. Rothnie Jr.","year":"1980","unstructured":"Rothnie, J. B. Jr., P. A. Bernstein, S. Fox, N. Goodman, M. Hammer, T. A. Landers, C. Reeve, D. W. Shipman, and E. Wong, \"Introduction to a system for distributed databases (SDD-1)\", ACM Trans. on Database Systems 5,1 (Mar. 1980), 1\u201317.","journal-title":"ACM Trans. on Database Systems"},{"key":"3_CR33","doi-asserted-by":"crossref","unstructured":"Sacca, D., \"On the recognition of coverings of acyclic database hypergraphs\", Proc. Second ACM SIGACT-SIGMOD Principles of Database Systems (1983), Atlanta, 297\u2013304.","DOI":"10.1145\/588058.588092"},{"key":"3_CR34","volume-title":"\"Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs\", Bell Labs Technical Report","author":"R. E. Tarjan","year":"1982","unstructured":"Tarjan, R. E., and Yannakakis, M., \"Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs\", Bell Labs Technical Report (March 1982), Murray Hill, New Jersey."},{"key":"3_CR35","doi-asserted-by":"crossref","unstructured":"Ullman, J. D., \"The U.R. strikes back,\" Proc. First ACM SIGACT-SIGMOD Principles of Database Systems (1982), Los Angeles, 10\u201322.","DOI":"10.1145\/588111.588114"},{"key":"3_CR36","unstructured":"Yannakakis, M., \"Algorithms for acyclic database schemes,\" Proc. 1981 Very Large Data Bases Conf., 82\u201394."},{"key":"3_CR37","unstructured":"Yu, C.T. and M.Z. Ozsoyoglu, \"An algorithm for tree-query membership of a distributed query\", Proc. 1979 IEEE COMPSAC, 306\u2013312."},{"key":"3_CR38","unstructured":"Zaniolo, C., 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","CAAP'83"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-12727-5_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T20:50:55Z","timestamp":1619556655000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-12727-5_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983]]},"ISBN":["9783540127277","9783540387145"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/3-540-12727-5_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1983]]}}}