Semantic Query Optimization: Correctness and Control
Pongtawat Chippimolchai*, Kiyoshi Akama**, and Vilas Wuwongse*
*Computer Science and Information Management Program, Asian Institute of Technology, Km. 42, Paholyothin Highway, Klong Luang, Pathumthani 12120, Thailand
**Division of Large-Scale Computational Systems Information Initiative Center, Hokkaido University, Kita 11 Nishi 5, Kita-ku, Sapporo, Hokkaido 060-0811, Japan
We developed a semantic query optimization framework for deductive databases based on equivalent transformation (ET) rules. ET rules, prepared from the semantic knowledge of databases, such as integrity constraints, transform given queries into syntactically different but semantically equivalent and more efficient forms. We formally prove the correctness of query transformations by ET rules. For efficiency, we propose a two-phase heuristic-based strategy to guide query transformations and introduce a condition-based control strategy to prevent unwanted, unnecessary transformations. We give examples demonstrating the possible optimization.
-  K. Akama, Y. Kawaguchi, and E. Miyamoto, “Equivalent Transformation for Member Constriants on Term Domain,” Journal of Japanese Society for Artificial Intelligence, 13(2), pp. 274-282, 1998.
-  K. Akama, Y. Shigeta, and E. Miyamoto, “Solving Problems by Equivalent Transformation of Logic Programs,” Journal of Japanese Society for Artificial Intelligence, 12(2), pp. 266-275, 1997.
-  K. Akama, E. Nantajeewarawat, and H. Koike, “A Class of Rewriting Rules and Reverse transformation for Rule-Based Equivalent Transformation,” Electronic Notes in Theoretical Computer Science, 59(4), pp. 1-16, 2001.
-  K. Akama, E. Nantajeewarawat, and H. Koike, “Program Synthesis Based on the Equivalent Transformation Computation Model,” In Proc. 12th International Workshop on Logic Based Program Development and Transformation (LOPSTR 2002), pp. 285-304, Madrid, Spain, 2002.
-  U. S. Chakravarthy, J. Grant, and J. Minker, “Foundations of Semantic Query Optimization for Deductive Databases,” Foundations of Deductive Databases and Logic Programming, 1987.
-  U. S. Chakravarthy, J. Grant, and J. Minker, “Logic-Based Approach to Semantic Query Optimization,” ACM Transactions on Database Systems, 15, pp. 162-207, 1990.
-  P. Godfrey, J. Grant, J. Gryz, and J. Minker, “Integrity Constraints: Semantics and Applications,” In Logics for Databases and Information Systems, pp. 265-306, Kluwer, 1998.
-  J. W. Lloyd, “Foundations of Logic Programming,” Springer-Verlag, second, extended edition, 1987.