{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T11:47:35Z","timestamp":1763466455747,"version":"3.41.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2005,9,1]],"date-time":"2005-09-01T00:00:00Z","timestamp":1125532800000},"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":["SIGMOD Rec."],"published-print":{"date-parts":[[2005,9]]},"abstract":"<jats:p>We review the notion of hypertree width, a measure of the degree of cyclicity of hypergraphs that is useful for identifying and solving efficiently easy instances of hard problems, by exploiting their structural properties. Indeed, a number of relevant problems from different areas, such as database theory, artificial intelligence, and game theory, are tractable when their underlying hypergraphs have small (i.e., bounded by some fixed constant) hypertree width. In particular, we describe how this notion may be used for identifying tractable classes of database queries and answering such queries in an efficient way.<\/jats:p>","DOI":"10.1145\/1084805.1084827","type":"journal-article","created":{"date-parts":[[2005,11,9]],"date-time":"2005-11-09T22:23:27Z","timestamp":1131575007000},"page":"91-99","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Query answering exploiting structural properties"],"prefix":"10.1145","volume":"34","author":[{"given":"Francesco","family":"Scarcello","sequence":"first","affiliation":[{"name":"DEIS, Universit\u00e0 della Calabria, Italy"}]}],"member":"320","published-online":{"date-parts":[[2005,9]]},"reference":[{"volume-title":"Addison-Wesley","year":"1995","author":"Abiteboul S.","key":"e_1_2_1_1_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/275487.275516"},{"volume-title":"Proc. of EuroComb'05","year":"2005","author":"Adler I.","key":"e_1_2_1_3_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1145\/2402.322389"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1137\/0210059"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1145\/800105.803397"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1016\/S0304-3975(99)00220-0"},{"unstructured":"R. Dechter. Constraint Processing. Morgan Kaufmann 2003.]]   R. Dechter. Constraint Processing. Morgan Kaufmann 2003.]]","key":"e_1_2_1_8_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1145\/319732.319735"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/602220.602222"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/4221.4225"},{"volume-title":"Prentice Hall","year":"2000","author":"Garcia-Molina H.","key":"e_1_2_1_12_1"},{"unstructured":"Y. E. Ioannidis. Query Optimization. The Computer Science and Engineering Handbook pp. 1038--1057 1997.]]  Y. E. Ioannidis. Query Optimization. The Computer Science and Engineering Handbook pp. 1038--1057 1997.]]","key":"e_1_2_1_13_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1145\/319758.319775"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1016\/S0004-3702(00)00078-3"},{"key":"e_1_2_1_16_1","first-page":"167","volume-title":"Proc. of the Conference on Software Engineering and Knowledge Engineering (SEKE'00)","author":"Gottlob Georg","year":"2000"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1145\/382780.382783"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.5555\/645730.668191"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1006\/jcss.2001.1809"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1016\/S0304-3975(01)00108-6"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1016\/S0022-0000(03)00030-8"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1007\/11604686_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.2307\/2586808"},{"key":"e_1_2_1_24_1","first-page":"552","volume-title":"Proc. of FOCS'03","author":"Grohe M.","year":"2003"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1145\/380752.380867"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1016\/0004-3702(94)90003-5"},{"doi-asserted-by":"crossref","unstructured":"D. S. Johnson. A Catalog of Complexity Classes Handbook of Theoretical Computer Science Volume A: Algorithms and Complexity pp. 67--161 1990.]]   D. S. Johnson. A Catalog of Complexity Classes Handbook of Theoretical Computer Science Volume A: Algorithms and Complexity pp. 67--161 1990.]]","key":"e_1_2_1_27_1","DOI":"10.1016\/B978-0-444-88071-0.50007-2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1006\/jcss.2000.1713"},{"volume-title":"Vienna University of Technology","year":"2003","author":"Korimort T.","key":"e_1_2_1_29_1"},{"unstructured":"D. Maier. The Theory of Relational Databases. Computer Science Press. 1986.]]   D. Maier. The Theory of Relational Databases. Computer Science Press. 1986.]]","key":"e_1_2_1_30_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1007\/978-3-540-24741-8_26"},{"volume-title":"TU Vienna","year":"2004","author":"McMahan B.","key":"e_1_2_1_32_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1145\/263661.263664"},{"doi-asserted-by":"crossref","unstructured":"O. Reingold. Undirected ST-Connectivity in Log-Space manuscript 2004 currently available at http:\/\/www.wisdom.weizmann.ac.il\/~reingold\/publications\/sl.ps]]  O. Reingold. Undirected ST-Connectivity in Log-Space manuscript 2004 currently available at http:\/\/www.wisdom.weizmann.ac.il\/~reingold\/publications\/sl.ps]]","key":"e_1_2_1_34_1","DOI":"10.1145\/1060590.1060647"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1016\/0196-6774(86)90023-4"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1016\/0022-0000(80)90036-7"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.1145\/4221.4997"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.1006\/jctb.1993.1027"},{"unstructured":"Francesco Scarcello and Alfredo Mazzitelli. The hypertree decompositions homepage since 2002. http:\/\/wwwinfo.deis.unical.it\/~frank\/Hypertrees\/]]  Francesco Scarcello and Alfredo Mazzitelli. The hypertree decompositions homepage since 2002. http:\/\/wwwinfo.deis.unical.it\/~frank\/Hypertrees\/]]","key":"e_1_2_1_40_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_41_1","DOI":"10.1145\/1055558.1055587"},{"doi-asserted-by":"publisher","key":"e_1_2_1_42_1","DOI":"10.1137\/0213035"},{"unstructured":"J. D. Ullman. Principles of Database and Knowledge Base Systems. Computer Science Press 1989.]]   J. D. Ullman. Principles of Database and Knowledge Base Systems. Computer Science Press 1989.]]","key":"e_1_2_1_43_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_44_1","DOI":"10.1145\/223784.223803"},{"volume-title":"University of Amsterdam","year":"1997","author":"Benthem J. Van","key":"e_1_2_1_45_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_46_1","DOI":"10.1145\/800070.802186"},{"doi-asserted-by":"publisher","key":"e_1_2_1_47_1","DOI":"10.1145\/335168.335209"},{"key":"e_1_2_1_48_1","first-page":"82","volume-title":"Proc. of VLDB'81","author":"Yannakakis M.","year":"1981"},{"issue":"3","key":"e_1_2_1_49_1","first-page":"261","article-title":"On determining tree-query membership of a distributed query","volume":"22","author":"Yu C. T.","year":"1984","journal-title":"Infor"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1084805.1084827","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1084805.1084827","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:24Z","timestamp":1750262904000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1084805.1084827"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,9]]},"references-count":48,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2005,9]]}},"alternative-id":["10.1145\/1084805.1084827"],"URL":"https:\/\/doi.org\/10.1145\/1084805.1084827","relation":{},"ISSN":["0163-5808"],"issn-type":[{"type":"print","value":"0163-5808"}],"subject":[],"published":{"date-parts":[[2005,9]]},"assertion":[{"value":"2005-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}