{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:36:10Z","timestamp":1750221370155,"version":"3.41.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T00:00:00Z","timestamp":1521763200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61602023 and 61421003"],"award-info":[{"award-number":["61602023 and 61421003"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100012166","name":"973 Program","doi-asserted-by":"crossref","award":["2014CB340302"],"award-info":[{"award-number":["2014CB340302"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Shenzhen Peacock Program","award":["1105100030834361"],"award-info":[{"award-number":["1105100030834361"]}]},{"name":"Foundation for Innovative Research Groups of NSFC"},{"name":"Innovative Research Grants from Huawei Technologies"},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/M025268\/1"],"award-info":[{"award-number":["EP\/M025268\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"name":"ERC","award":["652976"],"award-info":[{"award-number":["652976"]}]},{"DOI":"10.13039\/501100015639","name":"Beijing Advanced Innovation Center for Big Data and Brain Computing","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100015639","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2018,3,31]]},"abstract":"<jats:p>\n            A query\n            <jats:italic>Q<\/jats:italic>\n            in a language\n            <jats:italic>L<\/jats:italic>\n            has a\n            <jats:italic>bounded rewriting<\/jats:italic>\n            using a set of L-definable views if there exists a query\n            <jats:italic>Q<\/jats:italic>\n            <jats:sup>\u2032<\/jats:sup>\n            in\n            <jats:italic>L<\/jats:italic>\n            such that given any dataset\n            <jats:italic>D<\/jats:italic>\n            ,\n            <jats:italic>Q<\/jats:italic>\n            (\n            <jats:italic>D<\/jats:italic>\n            ) can be computed by\n            <jats:italic>Q<\/jats:italic>\n            <jats:sub>\u2032<\/jats:sub>\n            that accesses only cached views and a small fraction\n            <jats:italic>D<\/jats:italic>\n            <jats:sub>\n              <jats:italic>Q<\/jats:italic>\n            <\/jats:sub>\n            of\n            <jats:italic>D<\/jats:italic>\n            . We consider datasets\n            <jats:italic>D<\/jats:italic>\n            that satisfy a set of access constraints, which are a combination of simple cardinality constraints and associated indices, such that the size |\n            <jats:italic>D<\/jats:italic>\n            <jats:sub>\n              <jats:italic>Q<\/jats:italic>\n            <\/jats:sub>\n            | of\n            <jats:italic>D<\/jats:italic>\n            <jats:sub>\n              <jats:italic>Q<\/jats:italic>\n            <\/jats:sub>\n            and the time to identify\n            <jats:italic>D<\/jats:italic>\n            <jats:sub>\n              <jats:italic>Q<\/jats:italic>\n            <\/jats:sub>\n            are independent of |\n            <jats:italic>D<\/jats:italic>\n            |, no matter how big\n            <jats:italic>D<\/jats:italic>\n            is.\n          <\/jats:p>\n          <jats:p>\n            In this article, we study the problem for deciding whether a query has a bounded rewriting given a set\n            <jats:italic>V<\/jats:italic>\n            of views and a set\n            <jats:italic>A<\/jats:italic>\n            of access constraints. We establish the complexity of the problem for various query languages\n            <jats:italic>L<\/jats:italic>\n            , from \u03a3\n            <jats:sub>3<\/jats:sub>\n            <jats:sup>p<\/jats:sup>\n            -complete for conjunctive queries (CQ) to undecidable for relational algebra (FO). We show that the intractability for CQ is rather robust even for acyclic CQ with fixed\n            <jats:italic>V<\/jats:italic>\n            and\n            <jats:italic>A<\/jats:italic>\n            , and characterize when the problem is in PTIME. To make practical use of bounded rewriting, we provide an effective syntax for FO queries that have a bounded rewriting. The syntax characterizes a key subclass of such queries without sacrificing the expressive power, and can be checked in PTIME. Finally, we investigate\n            <jats:italic>L<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            -to-\n            <jats:italic>L<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            bounded rewriting, when\n            <jats:italic>Q<\/jats:italic>\n            in\n            <jats:italic>L<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            is allowed to be rewritten into a query\n            <jats:italic>Q<\/jats:italic>\n            <jats:sup>\u2032<\/jats:sup>\n            in another language\n            <jats:italic>L<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            . We show that this relaxation does not simplify the analysis of bounded query rewriting using views.\n          <\/jats:p>","DOI":"10.1145\/3183673","type":"journal-article","created":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T12:29:49Z","timestamp":1521808189000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Bounded Query Rewriting Using Views"],"prefix":"10.1145","volume":"43","author":[{"given":"Yang","family":"Cao","sequence":"first","affiliation":[{"name":"University of Edinburgh, Edinburgh, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenfei","family":"Fan","sequence":"additional","affiliation":[{"name":"University of Edinburgh and Beihang University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Floris","family":"Geerts","sequence":"additional","affiliation":[{"name":"University of Antwerp, Antwerp, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ping","family":"Lu","sequence":"additional","affiliation":[{"name":"Beihang University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,3,23]]},"reference":[{"volume-title":"Foundations of Databases","author":"Abiteboul Serge","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_2_1_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_2_1","DOI":"10.1016\/j.tcs.2010.12.031"},{"doi-asserted-by":"publisher","key":"e_1_2_2_3_1","DOI":"10.1016\/j.jcss.2006.10.019"},{"doi-asserted-by":"publisher","key":"e_1_2_2_4_1","DOI":"10.1137\/0208017"},{"doi-asserted-by":"publisher","key":"e_1_2_2_5_1","DOI":"10.14778\/2078331.2078334"},{"key":"e_1_2_2_6_1","volume-title":"Proceedings of the 4th Biennial Conference on Innovative Data Systems Research (CIDR\u201909)","author":"Armbrust Michael","year":"2009","unstructured":"Michael Armbrust , Armando Fox , David A. Patterson , Nick Lanham , Beth Trushkowsky , Jesse Trutna , and Haruki Oh . 2009 . SCADS: Scale-independent storage for social computing applications . In Proceedings of the 4th Biennial Conference on Innovative Data Systems Research (CIDR\u201909) . Online Proceedings. Michael Armbrust, Armando Fox, David A. Patterson, Nick Lanham, Beth Trushkowsky, Jesse Trutna, and Haruki Oh. 2009. SCADS: Scale-independent storage for social computing applications. In Proceedings of the 4th Biennial Conference on Innovative Data Systems Research (CIDR\u201909). Online Proceedings."},{"doi-asserted-by":"publisher","key":"e_1_2_2_7_1","DOI":"10.1145\/2463676.2465333"},{"key":"e_1_2_2_8_1","volume-title":"Balder ten Cate, and Efthymia Tsamoura","author":"Benedikt Michael","year":"2016","unstructured":"Michael Benedikt , Julien Leblay , Balder ten Cate, and Efthymia Tsamoura . 2016 . Generating Plans from Proofs : The Interpolation-based Approach to Query Reformulation. Morgan 8 Claypool Publishers . Michael Benedikt, Julien Leblay, Balder ten Cate, and Efthymia Tsamoura. 2016. Generating Plans from Proofs: The Interpolation-based Approach to Query Reformulation. Morgan 8 Claypool Publishers."},{"doi-asserted-by":"publisher","key":"e_1_2_2_9_1","DOI":"10.1145\/2847523"},{"doi-asserted-by":"publisher","key":"e_1_2_2_10_1","DOI":"10.1109\/ICDE.2008.4497413"},{"doi-asserted-by":"publisher","key":"e_1_2_2_11_1","DOI":"10.1145\/2882903.2882942"},{"doi-asserted-by":"publisher","key":"e_1_2_2_12_1","DOI":"10.14778\/3099622.3099628"},{"doi-asserted-by":"publisher","key":"e_1_2_2_13_1","DOI":"10.1145\/2902251.2902294"},{"doi-asserted-by":"publisher","key":"e_1_2_2_14_1","DOI":"10.1109\/ICDE.2015.7113281"},{"doi-asserted-by":"publisher","key":"e_1_2_2_16_1","DOI":"10.14778\/2732977.2732996"},{"doi-asserted-by":"publisher","key":"e_1_2_2_17_1","DOI":"10.1145\/800105.803397"},{"doi-asserted-by":"publisher","key":"e_1_2_2_18_1","DOI":"10.1016\/S0304-3975(99)00220-0"},{"doi-asserted-by":"publisher","key":"e_1_2_2_19_1","DOI":"10.1145\/303976.303992"},{"doi-asserted-by":"publisher","key":"e_1_2_2_20_1","DOI":"10.1145\/2602136"},{"doi-asserted-by":"publisher","key":"e_1_2_2_21_1","DOI":"10.1016\/j.tcs.2006.11.008"},{"doi-asserted-by":"publisher","key":"e_1_2_2_22_1","DOI":"10.1145\/321510.321524"},{"unstructured":"Facebook. 2013. Introducing graph search. https:\/\/en-gb.facebook.com\/about\/graphsearch.  Facebook. 2013. Introducing graph search. https:\/\/en-gb.facebook.com\/about\/graphsearch.","key":"e_1_2_2_23_1"},{"unstructured":"Facebook. 2014. Constraints on the number of photos friends and tags. https:\/\/www.facebook.com\/help.  Facebook. 2014. Constraints on the number of photos friends and tags. https:\/\/www.facebook.com\/help.","key":"e_1_2_2_24_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_25_1","DOI":"10.1145\/2745754.2745771"},{"doi-asserted-by":"publisher","key":"e_1_2_2_26_1","DOI":"10.1145\/2594538.2594551"},{"volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey Michael","unstructured":"Michael Garey and David Johnson . 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman and Company . Michael Garey and David Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company.","key":"e_1_2_2_27_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_28_1","DOI":"10.1145\/114325.103712"},{"doi-asserted-by":"publisher","key":"e_1_2_2_29_1","DOI":"10.1145\/2902251.2902288"},{"doi-asserted-by":"publisher","key":"e_1_2_2_30_1","DOI":"10.1145\/303976.303979"},{"key":"e_1_2_2_31_1","volume-title":"ICT Innovations. Online Proceedings, 86--96","author":"Grujic Ivana","year":"2014","unstructured":"Ivana Grujic , Sanja Bogdanovic-Dinic , and Leonid Stoimenov . 2014 . Collecting and analyzing data from e-government Facebook pages . In ICT Innovations. Online Proceedings, 86--96 . Ivana Grujic, Sanja Bogdanovic-Dinic, and Leonid Stoimenov. 2014. Collecting and analyzing data from e-government Facebook pages. In ICT Innovations. Online Proceedings, 86--96."},{"doi-asserted-by":"publisher","key":"e_1_2_2_32_1","DOI":"10.1007\/s007780100054"},{"doi-asserted-by":"publisher","key":"e_1_2_2_33_1","DOI":"10.1093\/comjnl\/42.2.100"},{"key":"e_1_2_2_34_1","first-page":"139","article-title":"Precoloring extension with fixed color bound","volume":"62","author":"Kratochv\u00edl Jan","year":"1993","unstructured":"Jan Kratochv\u00edl . 1993 . Precoloring extension with fixed color bound . Acta Math. Univ. Comen. 62 (1993), 139 -- 153 . Jan Kratochv\u00edl. 1993. Precoloring extension with fixed color bound. Acta Math. Univ. Comen. 62 (1993), 139--153.","journal-title":"Acta Math. Univ. Comen."},{"doi-asserted-by":"publisher","key":"e_1_2_2_35_1","DOI":"10.1145\/543613.543644"},{"doi-asserted-by":"publisher","key":"e_1_2_2_36_1","DOI":"10.1145\/212433.220198"},{"doi-asserted-by":"publisher","key":"e_1_2_2_37_1","DOI":"10.1007\/s00778-002-0085-6"},{"doi-asserted-by":"publisher","key":"e_1_2_2_38_1","DOI":"10.1145\/320107.320115"},{"doi-asserted-by":"publisher","key":"e_1_2_2_39_1","DOI":"10.1145\/1055558.1055601"},{"doi-asserted-by":"publisher","key":"e_1_2_2_40_1","DOI":"10.1145\/1806907.1806913"},{"doi-asserted-by":"publisher","key":"e_1_2_2_41_1","DOI":"10.1145\/212433.220199"},{"volume-title":"Database Management Systems","author":"Ramakrishnan Raghu","unstructured":"Raghu Ramakrishnan and Johannes Gehrke . 2000. Database Management Systems . McGraw Hill . Raghu Ramakrishnan and Johannes Gehrke. 2000. Database Management Systems. McGraw Hill.","key":"e_1_2_2_42_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_43_1","DOI":"10.1145\/322217.322221"},{"doi-asserted-by":"publisher","key":"e_1_2_2_44_1","DOI":"10.1016\/0304-3975(76)90061-X"},{"doi-asserted-by":"publisher","key":"e_1_2_2_45_1","DOI":"10.1006\/inco.1999.2792"},{"key":"e_1_2_2_46_1","volume-title":"Principles of Database Systems","author":"Ullman Jeffrey D.","unstructured":"Jeffrey D. Ullman . 1982. Principles of Database Systems , 2 nd Edition. Computer Science Press . Jeffrey D. Ullman. 1982. Principles of Database Systems, 2nd Edition. Computer Science Press.","edition":"2"},{"doi-asserted-by":"publisher","key":"e_1_2_2_47_1","DOI":"10.1016\/0304-3975(87)90049-1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_48_1","DOI":"10.1109\/CMPSAC.1979.762509"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3183673","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3183673","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:32Z","timestamp":1750213592000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3183673"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,23]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,3,31]]}},"alternative-id":["10.1145\/3183673"],"URL":"https:\/\/doi.org\/10.1145\/3183673","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2018,3,23]]},"assertion":[{"value":"2016-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}