pegasus

Semantic query optimization (SQO) is the process of finding equivalent rewritings of an input query given constraints that hold in a database instance. We present a Chase & Backchase (C&B) algorithm strategy that generalizes and improves on well-known methods in the field. The implementation of our approach, the pegasus system, outperforms existing C&B systems an average by two orders of magnitude. This gain in performance is due to a combination of novel methods that lower the complexity in practical situations significantly.