HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Complete Yet Practical Search for Minimal Query Reformulations Under Constraints

Abstract : We revisit the Chase&Backchase (C&B) algorithm for query refor-mulation under constraints, which provides a uniform solution to such particular-case problems as view-based rewriting under con-straints, semantic query optimization, and physical access path se-lection in query optimization. For an important class of queries and constraints, C&B has been shown to be complete, i.e. guaranteed to find all (join-)minimal reformulations under constraints. C&B is based on constructing a canonical rewriting candidate called a universal plan, then inspecting its exponentially many sub-queries in search for minimal reformulations, essentially removing redun-dant joins in all possible ways. This inspection involves chasing the subquery. Because of the resulting exponentially many chases, the conventional wisdom has held that completeness is a concept of mainly theoretical interest. We show that completeness can be preserved at practically rel-evant cost by introducing Prov C &B , a novel reformulation algo-rithm that instruments the chase to maintain provenance informa-tion connecting the joins added during the chase to the universal plan subqueries responsible for adding these joins. This allows it to directly "read off" the minimal reformulations from the result of a single chase of the universal plan, saving exponentially many chases of its subqueries. We exhibit natural scenarios yielding speedups of over two orders of magnitude between the execution of the best view-based rewriting found by a commercial query op-timizer and that of the best rewriting found by Prov C &B (which the optimizer misses because of limited reasoning about constraints).
Document type :
Conference papers
Complete list of metadata

Cited literature [33 references]  Display  Hide  Download

Contributor : Ioana Ileana Connect in order to contact the contributor
Submitted on : Monday, November 24, 2014 - 12:36:02 PM
Last modification on : Thursday, July 8, 2021 - 3:48:15 AM
Long-term archiving on: : Wednesday, February 25, 2015 - 10:45:52 AM


Files produced by the author(s)



Ioana Ileana, Bogdan Cautis, Alin Deutsch, Yannis Katsis. Complete Yet Practical Search for Minimal Query Reformulations Under Constraints. SIGMOD Conference 2014, Jun 2014, Snowbird, Utah, United States. ⟨10.1145/2588555.2593683⟩. ⟨hal-01086494⟩



Record views


Files downloads