Optimizing multiset relational algebra queries using weak-equivalent rewrite rules (Q2103917)

The paper improves usual approaches to automatic query optimization for queries written in SQL. Particularly, evaluation of joins is considered, using semi-joins instead of joins. This approach is used in practice with a manual approach that leads to cheaper joins. On the other hand, its automatic version is used in practice only in limited cases. The authors propose automatic optimization via weak-equivalent rules for a multiset relational algebra which forms the background of core SQL. In practice, this means to use the WHERE\dots IN\dots\ clauses supporting a use of semi-joins. The rules guarantee that the original subquery and its rewritten version evaluate to the same result up to duplicate elimination. Section 1 presents an SQL example with real input relations and results documenting advantages of the approach, i.e., that the evaluation of rewritten queries is significantly faster. After the preliminaries introduced in Section 2, the authors present in Section 3 a meaningful formal approach based on the multiset relational algebra (including deduplication) extended with semi-joins, max-union and attribute introduction. The core Section 4 is devoted to possible optimizations within the scope of projection and deduplication operations. Associated is weak-equivalency, where weak-equivalent expressions yield the same results up to duplicate elimination. An extension of the approach, considering keys and functional dependencies, is described in Section 5. The somewhat confusing short Section 6 then provides a detailed rewriting of the queries exhibited in the paper. In conclusion, the authors offer a number of challenges, both theoretical and practical ones. The former involve taking features like aggregation and recursive queries into account when optimizing queries, the latter are about implementing the approach to confirm its power. For the entire collection see [Zbl 1499.68028].