• Complete Yet Practical Search For Minimal Query Reformulations Under Constraints - Ioana Ileana

  • Abstract:
    We approach the topic of conjunctive query reformulation under constraints, which covers a range of problems such as query rewriting using views, physical access path selection, semantic query optimisation. We focus on completeness in this context – that is, on algorithms capable of finding all the minimal reformulations of a query. While completeness is a highly desirable feature, conventional wisdom has considered it to be a concept of mainly theoretical interest, incompatible with scalability and performance in practice. We challenge this conventional wisdom and show that completeness can be preserved at pratically relevant cost, by introducing a novel reformulation algorithm, the Provenance Aware Chase & Backchase (Prov C&B). Prov C&B revisits the Chase & Backchase (C&B) algorithm, transforming and dramatically speeding up its costly Backchase phase, by replacing the exponentially many chase sequences with a single, provenance-annotated chase phase. We thus introduce a novel chase flavor, the Provenance-Aware Chase, together with its underlying provenance-agnostic chase procedure, the Conservative Chase, and show how they guarantee the soundness and completeness of Prov C&B.We demonstrate the practical performance and impact of Prov C&B by exhibiting natural scenarios yielding speedups of over two orders of magnitude when compared to a sophisticated commercial DBMS in a view-based rewriting setting.


    By: Ioana Ileana (postdoc at INRIA and UCSD)