Query Optimization by Quantifier Elimination

                              Christoph Koch

                 École Polytechnique Fédérale de Lausanne



  Abstract. Many of us who teach database query languages have seen
  creative students who lack a training in formal logic come up with sur-
  prising ways of using aggregation for expressing challenging queries in
  SQL – ways that do not feel natural to those trained in logic but which
  nevertheless exact admiration. In this talk, I show how quantifier elimina-
  tion can be used to optimize SQL queries in surprising ways – ways whose
  results coincide with and generalize these apparently creative tricks. The
  new query optimization technique, apart from being potentially useful for
  practical query engines, suggests a particular way in which the logically
  untrained mind synthesizes queries (not quantifier elimination, though)
  – an observation at best based on an amateur’s understanding of brain
  science, but potentially still useful for teaching databases.