{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:14:18Z","timestamp":1750306458642,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,2,3]],"date-time":"2016-02-03T00:00:00Z","timestamp":1454457600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/H017690\/1 and EP\/M005852\/1"],"award-info":[{"award-number":["EP\/H017690\/1 and EP\/M005852\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council UK","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000266","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":[[2016,2,3]]},"abstract":"<jats:p>\n            We present algorithms for answering queries making use of information about source integrity constraints, access restrictions, and access costs. Our method can exploit the integrity constraints to find plans even when there is no direct access to relations appearing in the query. We look at different kinds of plans, depending on the kind of relational operators that are permitted within their commands. To each type of plan, we associate a semantic property that is necessary for having a plan of that type. The key idea of our method is to move from a search for a plan to a search for a proof of the corresponding semantic property, and then\n            <jats:italic>generate a plan from a proof<\/jats:italic>\n            . We provide algorithms for converting proofs to plans and show that they will find a plan of the desired type whenever such a plan exists. We show that while discovery of one proof allows us to find a single plan that answers the query, we can explore alternative proofs to find lower-cost plans.\n          <\/jats:p>","DOI":"10.1145\/2847523","type":"journal-article","created":{"date-parts":[[2016,2,3]],"date-time":"2016-02-03T16:29:01Z","timestamp":1454516941000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Generating Plans from Proofs"],"prefix":"10.1145","volume":"40","author":[{"given":"Michael","family":"Benedikt","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Balder","family":"Ten Cate","sequence":"additional","affiliation":[{"name":"LogicBlox and UC-Santa Cruz, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Efthymia","family":"Tsamoura","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,2,3]]},"reference":[{"volume-title":"Foundations of Databases","author":"Abiteboul Serbe","key":"e_1_2_2_1_1"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.12.031"},{"key":"e_1_2_2_3_1","doi-asserted-by":"crossref","unstructured":"Vince B\u00e1r\u00e1ny Michael Benedikt and Pierre Bourhis. 2013. Access restrictions and integrity constraints revisited. In ICDT.  Vince B\u00e1r\u00e1ny Michael Benedikt and Pierre Bourhis. 2013. Access restrictions and integrity constraints revisited. In ICDT.","DOI":"10.1145\/2448496.2448522"},{"key":"e_1_2_2_4_1","doi-asserted-by":"crossref","unstructured":"Vince B\u00e1r\u00e1ny Georg Gottlob and Martin Otto. 2010. Querying the guarded fragment. In LICS.  Vince B\u00e1r\u00e1ny Georg Gottlob and Martin Otto. 2010. Querying the guarded fragment. In LICS.","DOI":"10.1109\/LICS.2010.26"},{"volume-title":"Balder ten Cate, and Luc Segoufin","year":"2011","author":"B\u00e1r\u00e1ny Vince","key":"e_1_2_2_5_1"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733028"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735703.2735708"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594550"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.2307\/2963593"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.11.008"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376938"},{"key":"e_1_2_2_12_1","unstructured":"Alin Deutsch Lucian Popa and Val Tannen. 1999. Physical data independence constraints and optimization with universal plans. In VLDB.   Alin Deutsch Lucian Popa and Val Tannen. 1999. Physical data independence constraints and optimization with universal plans. In VLDB."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1121995.1122010"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(99)00025-4"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1O16\/j.tcs.2004.10.033"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304210"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593683"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-002-0085-6"},{"key":"e_1_2_2_19_1","unstructured":"Chen Li and Edward Chang. 2000. Query planning with limited source capabilities. In ICDE.  Chen Li and Edward Chang. 2000. Query planning with limited source capabilities. In ICDE."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/502030.502032"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320115"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0333-y"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055601"},{"key":"e_1_2_2_24_1","doi-asserted-by":"crossref","unstructured":"Alan Nash and Bertram Lud\u00e4scher. 2004b. Processing union of conjunctive queries with negation under limited access patterns. In EDBT.  Alan Nash and Bertram Lud\u00e4scher. 2004b. Processing union of conjunctive queries with negation under limited access patterns. In EDBT.","DOI":"10.1007\/978-3-540-24741-8_25"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806907.1806913"},{"key":"e_1_2_2_26_1","unstructured":"Adrian Onet. 2013. The chase procedure and its applications in data exchange. In Data Exchange Integration and Streams.  Adrian Onet. 2013. The chase procedure and its applications in data exchange. In Data Exchange Integration and Streams."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.2307\/420966"},{"key":"e_1_2_2_28_1","unstructured":"Lucian Popa. 2000. Object\/Relational Query Optimization with Chase and Backchase. Ph.D. Dissertation. University of Pennsylvania.   Lucian Popa. 2000. Object\/Relational Query Optimization with Chase and Backchase. Ph.D. Dissertation. University of Pennsylvania."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.220199"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065174"},{"key":"e_1_2_2_31_1","doi-asserted-by":"crossref","unstructured":"David Toman and Grant Weddell. 2011. Fundamentals of Physical Design and Query Compilation. Morgan Claypool.   David Toman and Grant Weddell. 2011. Fundamentals of Physical Design and Query Compilation. Morgan Claypool.","DOI":"10.1007\/978-3-031-01881-7"},{"key":"e_1_2_2_32_1","unstructured":"Jeffrey D. Ullman. 1989. Principles of Database and Knowledge-Base Systems V2. Computer Science Press.  Jeffrey D. Ullman. 1989. Principles of Database and Knowledge-Base Systems V2. Computer Science Press."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2847523","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2847523","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:43:27Z","timestamp":1750225407000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2847523"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,3]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,2,3]]}},"alternative-id":["10.1145\/2847523"],"URL":"https:\/\/doi.org\/10.1145\/2847523","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2016,2,3]]},"assertion":[{"value":"2015-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-02-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}