{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,18]],"date-time":"2024-06-18T11:17:34Z","timestamp":1718709454372},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"14","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2014,10]]},"abstract":"<jats:p>\n            We are interested in scalable data integration and data exchange under constraints\/dependencies. In data exchange the problem is how to materialize a target database instance, satisfying the source-to-target and target dependencies, that provides the certain answers. In data integration, the problem is how to rewrite a query over the target schema into a query over the source schemas that provides the certain answers. In both these problems we make use of the chase algorithm, the main tool to reason with dependencies. Our first contribution is to introduce the\n            <jats:italic>frugal<\/jats:italic>\n            chase, which produces smaller universal solutions than the standard chase, still remaining polynomial in data complexity. Our second contribution is to use the frugal chase to scale up query answering using views under LAV weakly acyclic target constraints, a useful language capturing RDF\/S. The latter problem can be reduced to query rewriting using views without constraints by chasing the source-to-target mappings with the target constraints. We construct a compact graph-based representation of the mappings and the constraints and develop an efficient algorithm to run the frugal chase on this representation. We show experimentally that our approach scales to large problems, speeding up the compilation of the dependencies into the mappings by close to 2 and 3 orders of magnitude, compared to the standard and the core chase, respectively. Compared to the standard chase, we improve online query rewriting time by a factor of 3, while producing equivalent, but smaller, rewritings of the original query.\n          <\/jats:p>","DOI":"10.14778\/2733085.2733093","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"1869-1880","source":"Crossref","is-referenced-by-count":7,"title":["Optimizing the chase"],"prefix":"10.14778","volume":"7","author":[{"given":"George","family":"Konstantinidis","sequence":"first","affiliation":[{"name":"University of Southern California, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9 Luis","family":"Ambite","sequence":"additional","affiliation":[{"name":"University of Southern California, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2009.08.002"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514899"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453886"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1734953.1734954"},{"key":"e_1_2_1_5_1","volume-title":"AAAI'06","author":"Arvelo Y.","year":"2006","unstructured":"Y. Arvelo , B. Bonet , and M. E. Vidal . Compilation of query-rewriting problems into tractable fragments of propositional logic . In AAAI'06 , pgs 225--230, 2006 . Y. Arvelo, B. Bonet, and M. E. Vidal. Compilation of query-rewriting problems into tractable fragments of propositional logic. In AAAI'06, pgs 225--230, 2006."},{"key":"e_1_2_1_6_1","first-page":"73","volume-title":"Languages & Programming","author":"Beeri C.","year":"1981","unstructured":"C. Beeri & M. Vardi . The implication problem for data dependencies. Automata , Languages & Programming , Springer , pages 73 -- 85 , 1981 . C. Beeri & M. Vardi. The implication problem for data dependencies. Automata, Languages & Programming, Springer, pages 73--85, 1981."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2591248.2591252"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24206-9_20"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376938"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1121995.1122010"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(99)00025-4"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061323"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1O16\/j.tcs.2004.10.033"},{"key":"e_1_2_1_15_1","first-page":"67","volume-title":"AAAI","author":"Friedman M.","year":"1999","unstructured":"M. Friedman , A. Y. Levy , and T. D. Millstein . Navigational plans for data integration . In AAAI , pages 67 -- 73 , 1999 . M. Friedman, A. Y. Levy, and T. D. Millstein. Navigational plans for data integration. In AAAI, pages 67--73, 1999."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065187"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1346330.1346334"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2371185"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0306-4379(99)00034-4"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780100054"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1966385.1966392"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90081-3"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1218702.1218704"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989335"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484712.2484716"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543644"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.220198"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559799"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559914"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/767141.767146"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687741"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2733085.2733093","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:16:08Z","timestamp":1672226168000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2733085.2733093"}},"subtitle":["scalable data integration under constraints"],"short-title":[],"issued":{"date-parts":[[2014,10]]},"references-count":31,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2014,10]]}},"alternative-id":["10.14778\/2733085.2733093"],"URL":"https:\/\/doi.org\/10.14778\/2733085.2733093","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2014,10]]}}}