For the relational data model there exists a rich and interesting theory of conjunctive queries and of the containment-expressing constraints corresponding to them. Query containment under constraints was studied during the classical times of relational database theory using the constraints as rewrite rules in a technique called chase. Query reformulation, in particular certain forms of very useful optimization can also be handled under constraints, using a new chase-and-backchase algorithm that we have developed.
It turns out that this relational tool can also be used to solve the containment and reformulation problems for XML “conjunctive” queries.
Joint work with Alin Deutsch (UC San Diego) and Lucian Popa (IBM Almaden).