A method for automatic rule derivation to support semantic query optimization

ABSTRACT

The use of inference rules to support intelligent data processing is an increasingly important tool in many areas of computer science. In database systems, rules are used in semantic query optimization as a method for reducing query processing costs. The savings is dependent on the ability of experts to supply a set of useful rules and the ability of the optimizer to quickly find the appropriate transformations generated by these rules. Unfortunately, the most useful rules are not always those that would or could be specified by an expert. This paper describes the architecture of a system having two interrelated components: a combined conventional/semantic query optimizer, and an automatic rule deriver. Our automatic rule derivation method uses intermediate results from the optimization process to direct the search for learning new rules. Unlike a system employing only user-specified rules, a system with an automatic capability can derive rules that may be true only in the current state of the database and can modify the rule set to reflect changes in the database and its usage pattern. This system has been implemented as an extension of the EXODUS conventional query optimizer generator. We describe the implementation, and show how semantic query optimization is an extension of conventional optimization in this context.

REFERENCES

• 1: Rafiul Ahad, User-assisted design and evolution of physical databases, 1985
• 2: José A. Blakeley , Neil Coburn , Per-:1Vke Larson, Updating derived relations: detecting irrelevant and autonomously computable updates, ACM Transactions on Database Systems (TODS), v.14 n.3, p.369-400, Sept. 1989 [doi>10.1145/68012.68015]
• 3: BLAUSTEIN, B. Enfbrcmg database aggertlolfis~ Techmques and applications. Ph.D dissertation, Harvard U,fiv, 1981.
• 4: gLUM, R DJscovery, confirmation and incorporation of causal relationships from a large t~me-omented clinical data base: The RX project. Comput Bmmedtcal Res., 15, (1982), 164-187.
• 5: Alexander Borgida, Language features for flexible handling of exceptions in information systems, ACM Transactions on Database Systems (TODS), v.10 n.4, p.565-603, Dec. 1985 [doi>10.1145/4879.4995]
• 6: A. P. Buchmann , R. S. Carrera , M. A. Vazquez-Galindo, A generalized constraint and exception handler for an object-oriented CAD-DBMS, Proceedings on the 1986 international workshop on Object-oriented database systems, p.38-49, September 23-26, 1986, Pacific Grove, California, United States
• 7: Michael J. Carey , David J. DeWitt , Daniel Frank , M. Muralikrishna , Goetz Graefe , Joel E. Richardson , Eugene J. Shekita, The architecture of the EXODUS extensible DBMS, Proceedings on the 1986 international workshop on Object-oriented database systems, p.52-65, September 23-26, 1986, Pacific Grove, California, United States
• 8: U S Chakravarthy , D H Fishman , J Minker, Semantic query optimization in expert systems and database systems, Proceedings from the first international workshop on Expert database systems, p.659-674, January 1986, Kiawah Island, South Carolina, United States
• 9: Upendranath Sharma Chakravarthy, Semantic query optimization in deductive databases. (volumes i and ii) (integrity constraints, intelligent processing, logic), 1985
• 10: A. Y. Chan, INDEX SELECTION IN A SELF-ADAPTIVE RELATIONAL DATA BASE MANAGEMENT SYSTEM, Massachusetts Institute of Technology, Cambridge, MA, 1976
• 11: H.-T. Chou , David J. Dewitt , Randy H. Katz , Anthony C. Klug, Design and implementation of the Wisconsin storage system, Software—Practice & Experience, v.15 n.10, p.943-962, Oct. 1985 [doi>10.1002/spe.4380151003]
• 12: Randall Davis , Douglas B. Lenat, Knowledge-Based Systems in Artificial Intelligence: 2 Case Studies, McGraw-Hill, Inc., New York, NY, 1982
• 13: D^YAL, U., AND BERNSTEIN, P. On the updatability of relational views. In Proceedings of the 4th VLDB Conference (Berlin, Sept. 1978), pp. 368-377.
• 14: D^YAL, U., AND SMITH, J. Probe: A knowledge oriented database management system. In Proceedings of the Islamorada Workshop on Large Scale Knowledge Base and Reasoning Systems, (Islamorada Fla., Feb. 1985), pp. 103 138.
• 15: R. Elmasri , J. Weeldreyer , A. Hevner, The category concept: an extension to the entity-relationship model, Data & Knowledge Engineering, v.1 n.1, p.75-116, April 1985 [doi>10.1016/0169-023X(85)90027-8]
• 16: Sheldon Finkelstein, Common expression analysis in database applications, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582400]
• 17: S. Finkelstein , M. Schkolnick , P. Tiberio, Physical database design for relational databases, ACM Transactions on Database Systems (TODS), v.13 n.1, p.91-128, March 1988 [doi>10.1145/42201.42205]
• 18: Johann Christoph Freytag, A rule-based view of query optimization, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.173-180, May 27-29, 1987, San Francisco, California, United States
• 19: FURTADO, A., AND CASANOVA, M. Updating relational views. In Query Processing zn Database Systems. Springer-Verlag, 1985, pp. 127 144.
• 20: Goetz Graefe , David J. DeWitt, The EXODUS optimizer generator, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.160-172, May 27-29, 1987, San Francisco, California, United States
• 21: Goetz Graefe, Rule-based query optimization in extensible database systems, 1987
• 22: L. M. Haas , W. Chang , G. M. Lohman , J. McPherson , P. F. Wilms , G. Lapis , B. Lindsay , H. Pirahesh , M. J. Carey , E. Shekita, Starburst Mid-Flight: As the Dust Clears, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.143-160, March 1990 [doi>10.1109/69.50910]
• 23: HAMMER, M., AND ZDONDIK, S.B. Knowledge-based query processing. In Proceedings of the 6th VLDB Conference (Montreal, 1980), pp. 137-146.
• 24: Michael Hammer , Sunil K. Sarin, Efficient monitoring of database assertions, Proceedings of the 1978 ACM SIGMOD international conference on management of data, May 31-June 02, 1978, Austin, Texas [doi>10.1145/509252.509290]
• 25: U S Chakravarthy , D H Fishman , J Minker, Semantic query optimization in expert systems and database systems, Proceedings from the first international workshop on Expert database systems, p.659-674, January 1986, Kiawah Island, South Carolina, United States
• 26: JARKE, M. Common subexpressions isolation in multiple query optimization. In Query Processing in Database Systems. Springer-Verlag, 1985, 191-205.
• 27: Won Kim , D. S. Reiner , D. S. Batory, Query Processing in Database Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1985
• 28: Jonathan Jay King, Query optimization by semantic reasoning, 1981
• 29: KING, J.J. QUIST: A system for semantic query optimization in relational databases. In Proceedings of the 7th VLDB Conference (Cannes, Sept. 1981), pp. 510 517.
• 30: LARSON, P., AND YANG, H. Computing queries from derived relations. In Proceedings of the International Conference on Very Large Database Systems (Stockholm, Aug. 1985), pp. 259 269.
• 31: LENAT, D. Theory formulation by Heuristic search. The nature of Heuristics II: Background and examples. Arttf, Intell, 21, 1/2, (1983), 31-60.
• 32: LEN^T, D. EURISKO' A program that learns new Heuristics and domain concepts The nature of Heuristics III: Program design and results. Arttf. InteIl., 21, 1/2, (1983), 6198
• 33: LINDSAY, R., BUCHANAN, B., FEIOENBAUM, E, AND LEDERBERG, J. Applzcattons of Artzfzctal
• 34: MICHALSKI, R., CARBONELL, J., AND M~TC~ELL, T. Machine Learning, Tioga Publishing, 1983.
• 35: Shamkant Navathe , Stefano Ceri , Gio Wiederhold , Jinglie Dou, Vertical partitioning algorithms for database design, ACM Transactions on Database Systems (TODS), v.9 n.4, p.680-710, Dec. 1984 [doi>10.1145/1994.2209]
• 36: NIAMm, B. Attribute partitmning in a self-adaptive relational database system. Masters thes~s, MIT, TR-192, 1978.
• 37: M. Schkolnick , P. Tiberio, Estimating the cost of updates in a relational database, ACM Transactions on Database Systems (TODS), v.10 n.2, p.163-179, June 1985 [doi>10.1145/3857.3863]
• 38: Timos K. Sellis, Global query optimization, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.191-205, May 28-30, 1986, Washington, D.C., United States
• 39: Timos K. Sellis, Multiple-query optimization, ACM Transactions on Database Systems (TODS), v.13 n.1, p.23-52, March 1988 [doi>10.1145/42201.42203]
• 40: Sreekumar T. Shenoy , Z. Meral Ozsoyoglu, A system for semantic query optimization, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.181-195, May 27-29, 1987, San Francisco, California, United States
• 41: SIEGEL, M. Automatic rule derivation for semantic query optimization, In Second International Conference on Expert Database Systems (Tysons Corner, Va., Apr. 1988), pp. 371 385.
• 42: M. D. Siegel, Automatic rule derivation for semantic query optimization, Boston University, Boston, MA, 1989
• 43: Michael Stonebraker , Lawrence A. Rowe, The design of POSTGRES, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.340-355, May 28-30, 1986, Washington, D.C., United States
• 44: WATERMAN, n. Generalization learning techniques for automating the learning of heuristics. Artif. lntell., 1, (1970), 27-120.
• 45: XU, D. Search control in semantic query optimization. Univ. of Massachusetts, Dept. of Computer Science, Tech Rep, TR83-09, 1983.
• 46: C. T. Yu , W. Sun, Automatic Knowledge Acquisition and Maintenance for Semantic Query Optimization, IEEE Transactions on Knowledge and Data Engineering, v.1 n.3, p.362-375, September 1989 [doi>10.1109/69.87981]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Knowledge acquisition

General Terms:
Languages, Performance

Keywords:
integrity constraint, learning, transformation heuristic