Several important query rewriting problems such as semantic
optimization, minimization, rewriting using views, equivalent
query reformulation in data publishing and integration, are
particular instances of the problem of query reformulation
under constraints.

However, these rewriting problems were historically tackled
by distinct database research groups in isolation, which led
to the development of apparently unrelated solution techniques.
Their combination within the same database management system
is at best tricky and inefficient, tending to miss opportunities
for synergy (such as enabling a rewriting of type A by applying
a rewriting of type B).

In this talk, I will briefly survey the above rewriting problems,
then present the Chase&Backchase (C&B) algorithm for finding
reformulations of a conjunctive query in the presence of
constraints expressed as embedded dependencies (these capture all
prevalent integrity constraints such as keys, foreign keys, etc.).

The C&B thus provides a uniform solution to the above rewriting
problems (for the class of queries and constraints considered).
Moreover, as opposed to some of the prior particular case
solutions, the C&B method is complete, i.e. all equivalent
reformulations are found.

As it turns out, the C&B is applicabile also to object-oriented
and XML settings. An online demo of the Chase&Backchase method
can be found at http://cb.ucsd.edu (thanks to Nicola Onose and
Emiran Curtmola).

This will be an informal whiteboard presentation.