JACIII Vol.10 No.3 pp. 270-280
doi: 10.20965/jaciii.2006.p0270


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

February 22, 2005
December 21, 2005
May 20, 2006
semantic query optimization, deductive database, integrity constraint, equivalent transformation, semantic preservation

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.

Cite this article as:
Pongtawat Chippimolchai, Kiyoshi Akama, and Vilas Wuwongse, “Semantic Query Optimization: Correctness and Control,” J. Adv. Comput. Intell. Intell. Inform., Vol.10, No.3, pp. 270-280, 2006.
Data files:
  1. [1] 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.
  2. [2] 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.
  3. [3] 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.
  4. [4] 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.
  5. [5] U. S. Chakravarthy, J. Grant, and J. Minker, “Foundations of Semantic Query Optimization for Deductive Databases,” Foundations of Deductive Databases and Logic Programming, 1987.
  6. [6] 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.
  7. [7] 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.
  8. [8] J. W. Lloyd, “Foundations of Logic Programming,” Springer-Verlag, second, extended edition, 1987.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Mar. 05, 2021