Penn DB Group's logo
Constraints and optimization
Arrow; just used for page layout. People
Arrow, used for page layout Publications
Arrow, used for page layout Research
Arrow, used for page layout Classes
Arrow, used for page layout Seminar
Arrow, used for page layout Resources
Search this website

Constraints and optimization

Executive Summary

We study optimization methods motivated by logical redundancy and physical independence in mediator-like components.
We have identified classes of queries and constraints over complex values with dictionaries, generalizing the relational conjunctive queries and embedded dependencies, as well as many interesting examples of complex value and oodb queries and integrity constraints for which we can show that some important classical results on containment, dependency implication, and chasing extend and generalize.
Using high-level representations with the data structure of dictionaries (finite functions) we are able to represent the physical access structures as views over the integrated logical schema of the sources. Dictionaries reflect directly the efficiency of the representation and facilitate cost estimation.
We define and enumerate in a novel manner a search space for query plans that incorporate the physical access structures as views on the logical schema.
We capture the views through constraints (dependencies) and we use our previous work on the ``equational'' chase to rewrite with these constraints.
This makes our method easy to integrate in the important rule-based optimization paradigm, and easy to combine both with conventional techniques and with our previous approach to semantic optimization.

Project Members

Val Tannen   Alin Deutsch   Lucian Popa   Arnaud Sahuguet   


Levine Hall
3330 Walnut Street
Philadelphia, PA 19104

Last update: 08/02/11     Comments