Relational database systems became the predominant technology for storing, handling, and querying data only after a great improvement in the efficiency of query evaluation in such systems. The key factor in this improvement was the introduction and development of query optimization techniques. In the late 1970's and early 1980's, researchers recognized that the semantics of the database could be exploited for further query optimization, and developed a new set of techniques called semantic query optimization (SQO). SQO uses integrity constraints associated with the database to improve the efficiency of query evaluation. Although several different techniques for SQO have been developed, only simple prototypes have been built and no commercial implementations of SQO exist today.

This project has two goals. First, we develop, implement and test exisiting SQO techniques within the DB2 query optimizer developed by IBM. Second, we develop new SQO techniques that would allow automatic extraction of semantic information from stored data for the purpose of query optimization. We plan to develop efficient algorithms for discovering such semantic information, develop mechanisms for its maintenance, and develop efficient algorithms for within the optimizer that can effectively use it for SQO rewrites.

This project is supported by IBM and NSERC.

• Jarek Gryz
• Parke Godfrey
• Dongming Liang

Alumni:

• Jerry Zheng
• Linqi Liu
• Xiaoyan Qian

• Parke Godfrey, Jarek Gryz, Calisto Zuzarte, Exploiting Constraint-Like Data Characterizations in Query Optimization. In Proceedings of SIGMOD, Santa Barbara, CA, 2001.
• Jarek Gryz, Berni Schiefer, Jian Zheng, and Calisto Zuzarte, Discovery and Application of Check Constraints in DB2. In Proceedings of the 17th ICDE, Heidelberg, Germany, April 2001.
  
• Jeff Edmonds, Jarek Gryz, Dongming Liang, and Renée J. Miller, Mining for Empty Rectangles in Large Data Sets. In Proceedings of the 8th ICDT, London, UK, January 2001.
• Qi Cheng, Jarek Gryz, Fred Koo, Cliff Leung, Linqi Liu, Xiaoyan Qian, and Berni Schiefer, Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database. In Proceedings of the 25th VLDB, Edinburgh, Scotland, September 1999.
  
• Jarek Gryz, Linqi Liu, Xiaoyan Qian, Semantic Query Optimization Techniques in IBM DB2: Initial Results . Technical Report CS-1999-01, York University, February 19, 1999