Physical Data Independence, Constraints and Optimization with Universal Plans

	Alin Deutsch   Lucian Popa   Val Tannen   


We present an optimization method and algorithm designed for three
objectives: physical data independence, semantic optimization, and
generalized tableau minimization. The method relies on generalized
forms of chase and ``backchase'' with constraints (dependencies). By
using dictionaries (finite functions) in physical schemas we can
capture with constraints useful access structures such as
indexes, materialized views, source capabilities, access support
relations, gmaps, etc.

The search space for query plans is defined and enumerated in a novel
manner: the chase phase rewrites the original query into a
``universal'' plan that integrates all the access structures and
alternative pathways that are allowed by applicable constraints.
Then, the backchase phase produces optimal plans by eliminating
various combinations of redundancies, again according to constraints.

This method is applicable (sound) to a large class of queries,
physical access structures, and semantic constraints. We prove that it
is in fact complete for ``path-conjunctive'' queries and views with
complex objects, classes and dictionaries, going beyond previous
theoretical work on processing queries using materialized views.