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

Publications

• A Chase Too Far? [.pdf] 
  Proceedings of ACM SIGMOD International Conference on Management of Data (SIGMOD) (2000)
  Lucian Popa   Alin Deutsch   Arnaud Sahuguet   Val Tannen   
  

• A Chase Too Far? [.pdf] 
  Technical Report MS-CIS-99-28 (1999)
  Lucian Popa   Alin Deutsch   Arnaud Sahuguet   Val Tannen   
  

• Optimization for Physical Independence in Information Integration Components [abstract] [.ps] 
  Technical Report (1999)
  Alin Deutsch   Lucian Popa   Val Tannen   
  

• Physical Data Independence, Constraints and Optimization with Universal Plans [abstract] [.ps] [.pdf] 
  International Conference on Very Large Databases (VLDB) (1999)
  Alin Deutsch   Lucian Popa   Val Tannen   
  

• An Equational Chase for Path-Conjunctive Queries, Constraints, and Views [abstract] [.ps] [.pdf] 
  International Conference on Database Theory (ICDT) (1999)
  Lucian Popa   Val Tannen   
  

• Chase and axioms for PC queries and dependencies [.ps] 
  Technical Report MS-CIS-98-34 (1998)
  Lucian Popa   Val Tannen