Top > JACIII > Semantic Query Optimization: Correctness and Control

single-jc.php

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

Paper:

Views over last 60 days: 770

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

Received:
February 22, 2005
Accepted:
December 21, 2005
Published:
May 20, 2006
Creative Commons License
Keywords:
semantic query optimization, deductive database, integrity constraint, equivalent transformation, semantic preservation
Abstract
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:
P. Chippimolchai, K. Akama, and V. Wuwongse, “Semantic Query Optimization: Correctness and Control,” J. Adv. Comput. Intell. Intell. Inform., Vol.10 No.3, pp. 270-280, 2006.
Data files:
References
  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.

Creative Commons License  This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

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

Last updated on Jul. 04, 2025