乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:39:39Z","timestamp":1740134379032,"version":"3.37.3"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"name":"Royal Society in the context of the project \u201cRAISON DATA\u201d","award":["RP\/R1\/201074"]},{"name":"EPSRC Programme","award":["EP\/M025268\/VADA"]},{"name":"Millennium Institute for Foundational Research on Data"},{"name":"Fondecyt","award":["1170109"]},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/S003800\/1 EQUID"],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"name":"ANR project QUID","award":["ANR-18-CE40-0031"]},{"name":"ANR project D\u00e9LTA","award":["ANR-16-CE40-0007"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2020,12,31]]},"abstract":"\n This work deals with the problem of semantic optimization of the central class of conjunctive queries (CQs). Since CQ evaluation is NP-complete, a long line of research has focussed on identifying fragments of CQs that can be efficiently evaluated. One of the most general restrictions corresponds to generalized hypetreewidth bounded by a fixed constant\n k<\/jats:italic>\n \u2265 1; the associated fragment is denoted GHW\n \n k<\/jats:italic>\n <\/jats:sub>\n . A CQ is semantically in GHW\n \n k<\/jats:italic>\n <\/jats:sub>\n if it is equivalent to a CQ in GHW\n \n k<\/jats:italic>\n <\/jats:sub>\n . The problem of checking whether a CQ is semantically in GHW\n \n k<\/jats:italic>\n <\/jats:sub>\n has been studied in the constraint-free case, and it has been shown to be NP-complete. However, in case the database is subject to constraints such as tuple-generating dependencies (TGDs) that can express, e.g., inclusion dependencies, or equality-generating dependencies (EGDs) that capture, e.g., key dependencies, a CQ may turn out to be semantically in GHW\n \n k<\/jats:italic>\n <\/jats:sub>\n under the constraints, while not being semantically in GHW\n \n k<\/jats:italic>\n <\/jats:sub>\n without the constraints. This opens avenues to new query optimization techniques. In this article, we initiate and develop the theory of semantic optimization of CQs under constraints. More precisely, we study the following natural problem: Given a CQ and a set of constraints, is the query semantically in GHW\n \n k<\/jats:italic>\n <\/jats:sub>\n , for a fixed\n k<\/jats:italic>\n \u2265 1, under the constraints, or, in other words, is the query equivalent to one that belongs to GHW\n \n k<\/jats:italic>\n <\/jats:sub>\n over all those databases that satisfy the constraints? We show that, contrary to what one might expect, decidability of CQ containment is a necessary but not a sufficient condition for the decidability of the problem in question. In particular, we show that checking whether a CQ is semantically in GHW\n 1<\/jats:sub>\n is undecidable in the presence of full TGDs (i.e., Datalog rules) or EGDs. In view of the above negative results, we focus on the main classes of TGDs for which CQ containment is decidable and that do not capture the class of full TGDs, i.e., guarded, non-recursive, and sticky sets of TGDs, and show that the problem in question is decidable, while its complexity coincides with the complexity of CQ containment. We also consider key dependencies over unary and binary relations, and we show that the problem in question is decidable in elementary time. Furthermore, we investigate whether being semantically in GHW\n \n k<\/jats:italic>\n <\/jats:sub>\n alleviates the cost of query evaluation. Finally, in case a CQ is not semantically in GHW\n \n k<\/jats:italic>\n <\/jats:sub>\n , we discuss how it can be approximated via a CQ that falls in GHW\n \n k<\/jats:italic>\n <\/jats:sub>\n in an optimal way. Such approximations might help finding \u201cquick\u201d answers to the input query when exact evaluation is intractable.\n <\/jats:p>","DOI":"10.1145\/3424908","type":"journal-article","created":{"date-parts":[[2020,10,29]],"date-time":"2020-10-29T10:05:36Z","timestamp":1603965936000},"page":"1-60","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Semantic Optimization of Conjunctive Queries"],"prefix":"10.1145","volume":"67","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2293-2653","authenticated-orcid":false,"given":"Pablo","family":"Barcel\u00f3","sequence":"first","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile, Chile and IMFD Chile, Chile, IMFD Chile"}]},{"given":"Diego","family":"Figueira","sequence":"additional","affiliation":[{"name":"University of Bordeaux, CNRS, Bordeaux INP, LaBRI, France"}]},{"given":"Georg","family":"Gottlob","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Oxford, UK"}]},{"given":"Andreas","family":"Pieris","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, UK"}]}],"member":"320","published-online":{"date-parts":[[2020,10,29]]},"reference":[{"volume-title":"Foundations of Databases","author":"Abiteboul Serge","key":"e_1_2_1_1_1","unstructured":"Serge Abiteboul , Richard Hull , and Victor Vianu . 1995. Foundations of Databases . Addison-Wesley . Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the IJCAI. 712--717","author":"Baget Jean-Fran\u00e7ois","year":"2011","unstructured":"Jean-Fran\u00e7ois Baget , Marie-Laure Mugnier , Sebastian Rudolph , and Micha\u00ebl Thomazo . 2011 . Walking the complexity lines for generalized guarded existential rules . In Proceedings of the IJCAI. 712--717 . Jean-Fran\u00e7ois Baget, Marie-Laure Mugnier, Sebastian Rudolph, and Micha\u00ebl Thomazo. 2011. Walking the complexity lines for generalized guarded existential rules. In Proceedings of the IJCAI. 712--717."},{"key":"e_1_2_1_3_1","volume-title":"Querying the guarded fragment. Logic. Methods Comput. Sci. 10, 2","author":"B\u00e1r\u00e1ny Vince","year":"2014","unstructured":"Vince B\u00e1r\u00e1ny , Georg Gottlob , and Martin Otto . 2014. Querying the guarded fragment. Logic. Methods Comput. Sci. 10, 2 ( 2014 ). Vince B\u00e1r\u00e1ny, Georg Gottlob, and Martin Otto. 2014. Querying the guarded fragment. Logic. Methods Comput. Sci. 10, 2 (2014)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2019.8785823"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902302"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/130911731"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745767"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1034714"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802489"},{"key":"e_1_2_1_10_1","volume-title":"Vardi","author":"Beeri Catriel","year":"1981","unstructured":"Catriel Beeri and Moshe Y . Vardi . 1981 . The implication problem for data dependencies. In Proceedings of the ICALP. 73--85. Catriel Beeri and Moshe Y. Vardi. 1981. The implication problem for data dependencies. In Proceedings of the ICALP. 73--85."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2591248.2591252"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2012.03.001"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.08.002"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773179"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1352582.1352590"},{"key":"e_1_2_1_16_1","volume-title":"Merlin","author":"Chandra Ashok K.","year":"1977","unstructured":"Ashok K. Chandra and Philip M . Merlin . 1977 . Optimal implementation of conjunctive queries in relational data bases. In Proceedings of the STOC. 77--90. Ashok K. Chandra and Philip M. Merlin. 1977. Optimal implementation of conjunctive queries in relational data bases. In Proceedings of the STOC. 77--90."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11564751_15"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02088013"},{"key":"e_1_2_1_19_1","volume-title":"Vardi","author":"Dalmau V\u00edctor","year":"2002","unstructured":"V\u00edctor Dalmau , Phokion G. Kolaitis , and Moshe Y . Vardi . 2002 . Constraint satisfaction, bounded treewidth, and finite-variable logics. In Proceedings of the CP. 310--326. V\u00edctor Dalmau, Phokion G. Kolaitis, and Moshe Y. Vardi. 2002. Constraint satisfaction, bounded treewidth, and finite-variable logics. In Proceedings of the CP. 310--326."},{"key":"e_1_2_1_20_1","volume-title":"Remmel","author":"Deutsch Alin","year":"2008","unstructured":"Alin Deutsch , Alan Nash , and Jeff B . Remmel . 2008 . The chase revisisted. In Proceedings of the PODS. 149--158. Alin Deutsch, Alan Nash, and Jeff B. Remmel. 2008. The chase revisisted. In Proceedings of the PODS. 149--158."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/319587.319592"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1085304.1085309"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2933580"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196962"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.08.001"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/319758.319775"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902309"},{"volume-title":"Graph Theory, Computational Intelligence and Thought","author":"Gottlob Georg","key":"e_1_2_1_28_1","unstructured":"Georg Gottlob , Gianluigi Greco , and Bruno Marnette . 2009. HyperConsistency width for constraint satisfaction: Algorithms and complexity results . In Graph Theory, Computational Intelligence and Thought . Springer , Berlin , 87--99. Georg Gottlob, Gianluigi Greco, and Bruno Marnette. 2009. HyperConsistency width for constraint satisfaction: Algorithms and complexity results. In Graph Theory, Computational Intelligence and Thought. Springer, Berlin, 87--99."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568320"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2638546"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Pavol Hell and Jaroslav Ne\u0161et\u0159il. 2004. Graphs and Homomorphisms. Oxford University Press. Pavol Hell and Jaroslav Ne\u0161et\u0159il. 2004. Graphs and Homomorphisms. Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90081-3"},{"volume-title":"Elements of Finite Model Theory","author":"Libkin Leonid","key":"e_1_2_1_34_1","unstructured":"Leonid Libkin . 2004. Elements of Finite Model Theory . Springer . Leonid Libkin. 2004. Elements of Finite Model Theory. Springer."},{"key":"e_1_2_1_35_1","volume-title":"Andreas Pieris, and Gerardo I. Simari.","author":"Lukasiewicz Thomas","year":"2015","unstructured":"Thomas Lukasiewicz , Maria Vanina Martinez , Andreas Pieris, and Gerardo I. Simari. 2015 . From classical to consistent query answering under existential rules. In Proceedings of the AAAI. 1546--1552. Thomas Lukasiewicz, Maria Vanina Martinez, Andreas Pieris, and Gerardo I. Simari. 2015. From classical to consistent query answering under existential rules. In Proceedings of the AAAI. 1546--1552."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320115"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1626"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.04.011"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322221"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90054-P"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213035"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the VLDB. 82--94","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis . 1981 . Algorithms for acyclic database schemes . In Proceedings of the VLDB. 82--94 . Mihalis Yannakakis. 1981. Algorithms for acyclic database schemes. In Proceedings of the VLDB. 82--94."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3424908","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T18:32:36Z","timestamp":1672597956000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3424908"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,29]]},"references-count":42,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,12,31]]}},"alternative-id":["10.1145\/3424908"],"URL":"https:\/\/doi.org\/10.1145\/3424908","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2020,10,29]]},"assertion":[{"value":"2018-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-10-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}