Optimizing Multiset Relational Algebra Queries Using Weak-Equivalent Rewrite Rules

Relational query languages rely heavily on costly join operations to combine tuples from multiple tables into a single resulting tuple. In many cases, the cost of query evaluation can be reduced by manually optimizing (parts of) queries to use cheaper semi-joins instead of joins. Unfortunately, existing database products can only apply such optimizations automatically in rather limited cases.To improve on this situation, we propose a framework …