{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:34:35Z","timestamp":1750221275534,"version":"3.41.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,9,1]],"date-time":"2017-09-01T00:00:00Z","timestamp":1504224000000},"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":[[2017,9]]},"abstract":"<jats:p>This paper reports on recent advances in semantic query optimization. We focus on the core class of conjunctive queries (CQs). Since CQ evaluation is NP-complete, a long line of research has concentrated on identifying fragments of CQs that can be efficiently evaluated. One of the most general such restrictions corresponds to bounded generalized hypertreewidth, which extends the notion of acyclicity. Here we discuss the problem of reformulating a CQ into one of bounded generalized hypertreewidth. Furthermore, we study whether knowing that such a reformulation exists alleviates the cost of CQ evaluation. In case a CQ cannot be reformulated as one of bounded generalized hypertreewidth, we discuss how it can be approximated in an optimal way. All the above issues are examined both for the constraint-free case, and the case where constraints, in fact, tuple-generating and equality-generating dependencies, are present<\/jats:p>","DOI":"10.1145\/3137586.3137588","type":"journal-article","created":{"date-parts":[[2017,9,5]],"date-time":"2017-09-05T12:23:34Z","timestamp":1504614214000},"page":"5-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Semantic Optimization in Tractable Classes of Conjunctive Queries"],"prefix":"10.1145","volume":"46","author":[{"given":"Pablo","family":"Barcel\u00f3","sequence":"first","affiliation":[{"name":"University of Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Pieris","sequence":"additional","affiliation":[{"name":"University of Edinburgh"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miguel","family":"Romero","sequence":"additional","affiliation":[{"name":"University of Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915213"},{"key":"e_1_2_1_2_1","volume-title":"Foundations of Databases","author":"Abiteboul Serge","year":"1995","unstructured":"Serge Abiteboul , Richard Hull , and Victor Vianu . Foundations of Databases . Addison-Wesley , 1995 . Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995."},{"key":"e_1_2_1_3_1","volume-title":"GYM: A multiround join algorithm in mapreduce. CoRR, abs\/1410.4156","author":"Afrati F.","year":"2014","unstructured":"F. Afrati , M. Joglekar , C. R\u00e9 , S. Salihoglu , and J. D. Ullman . GYM: A multiround join algorithm in mapreduce. CoRR, abs\/1410.4156 , 2014 . F. Afrati, M. Joglekar, C. R\u00e9, S. Salihoglu, and J. D. Ullman. GYM: A multiround join algorithm in mapreduce. CoRR, abs\/1410.4156, 2014."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2015.37"},{"issue":"10","key":"e_1_2_1_5_1","first-page":"968","article-title":"DBToaster: Higher-order delta processing for dynamic, frequently fresh views","volume":"5","author":"Amroun K.","year":"2012","unstructured":"K. Amroun , Z. Habbas , and W. Aggoune-Mtalaa . DBToaster: Higher-order delta processing for dynamic, frequently fresh views . VLDB , 5 ( 10 ): 968 -- 979 , 2012 . K. Amroun, Z. Habbas, and W. Aggoune-Mtalaa. DBToaster: Higher-order delta processing for dynamic, frequently fresh views. VLDB, 5(10):968--979, 2012.","journal-title":"VLDB"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742796"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902302"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/130911731"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745767"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1034714"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802489"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-10843-2_7"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/2591248.2591252"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2012.03.001"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.08.002"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/78922.78924"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214049"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00220-0"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/11564751_15"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46135-3_21"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502810"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1121995.1122010"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/319587.319592"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.033"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2933580"},{"key":"e_1_2_1_27_1","unstructured":"Diego Figueira 2017. Personal communication.  Diego Figueira 2017. Personal communication."},{"key":"e_1_2_1_28_1","volume-title":"General and fractional hypertree decompositions: Hard and easy cases. CoRR, abs\/1611.01090","author":"Fischl Wolfgang","year":"2016","unstructured":"Wolfgang Fischl , Georg Gottlob , and Reinhard Pichler . General and fractional hypertree decompositions: Hard and easy cases. CoRR, abs\/1611.01090 , 2016 . Wolfgang Fischl, Georg Gottlob, and Reinhard Pichler. General and fractional hypertree decompositions: Hard and easy cases. CoRR, abs\/1611.01090, 2016."},{"key":"e_1_2_1_29_1","volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","year":"2006","unstructured":"J\u00f6rg Flum and Martin Grohe . Parameterized Complexity Theory . Springer-Verlag , 2006 . J\u00f6rg Flum and Martin Grohe. Parameterized Complexity Theory. Springer-Verlag, 2006."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367849"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2064023"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/319758.319775"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902309"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382783"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2638546"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206036"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2636918"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90282-K"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90081-3"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-88074-1.50022-6"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543644"},{"key":"e_1_2_1_44_1","first-page":"1546","volume-title":"AAAI","author":"Lukasiewicz Thomas","year":"2015","unstructured":"Thomas Lukasiewicz , Maria Vanina Martinez , Andreas Pieris , and Gerardo I. Simari . From classical to consistent query answering under existential rules . In AAAI , pages 1546 -- 1552 , 2015 . Thomas Lukasiewicz, Maria Vanina Martinez, Andreas Pieris, and Gerardo I. Simari. From classical to consistent query answering under existential rules. In AAAI, pages 1546--1552, 2015."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320115"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536616.1536637"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1626"},{"key":"e_1_2_1_48_1","volume-title":"Handbook of Automated Reasoning","author":"Robinson A.","year":"2001","unstructured":"A. Robinson and A. Voronkov . Handbook of Automated Reasoning . The MIT Press , 2001 . A. Robinson and A. Voronkov. Handbook of Automated Reasoning. The MIT Press, 2001."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213035"},{"key":"e_1_2_1_50_1","first-page":"82","volume-title":"VLDB","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis . Algorithms for acyclic database schemes . In VLDB , pages 82 -- 94 , 1981 . Mihalis Yannakakis. Algorithms for acyclic database schemes. In VLDB, pages 82--94, 1981."}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3137586.3137588","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3137586.3137588","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:10Z","timestamp":1750212670000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3137586.3137588"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["10.1145\/3137586.3137588"],"URL":"https:\/\/doi.org\/10.1145\/3137586.3137588","relation":{},"ISSN":["0163-5808"],"issn-type":[{"type":"print","value":"0163-5808"}],"subject":[],"published":{"date-parts":[[2017,9]]},"assertion":[{"value":"2017-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}