ACM SIGMOD Anthology TODS dblp.uni-trier.de

A Method for Automatic Rule Derivation to Support Semantic Query Optimization.

Michael Siegel, Edward Sciore, Sharon C. Salveter: A Method for Automatic Rule Derivation to Support Semantic Query Optimization. ACM Trans. Database Syst. 17(4): 563-600(1992)
@article{DBLP:journals/tods/SiegelSS92,
  author    = {Michael Siegel and
               Edward Sciore and
               Sharon C. Salveter},
  title     = {A Method for Automatic Rule Derivation to Support Semantic Query
               Optimization},
  journal   = {ACM Trans. Database Syst.},
  volume    = {17},
  number    = {4},
  year      = {1992},
  pages     = {563-600},
  ee        = {http://doi.acm.org/10.1145/146931.146932, db/journals/tods/SiegelSS92.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

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.

Copyright © 1992 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 2, TODS 1991-1995, TKDE 1989-1992" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 2664 KB]

References

[1]
...
[2]
José A. Blakeley, Neil Coburn, Per-Åke Larson: Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates. ACM Trans. Database Syst. 14(3): 369-400(1989) BibTeX
[3]
...
[4]
...
[5]
Alexander Borgida: Language Features for Flexible Handling of Exceptions in Information Systems. ACM Trans. Database Syst. 10(4): 565-603(1985) BibTeX
[6]
Alejandro P. Buchmann, R. S. Carrera, M. A. Vazquez-Galindo: A Generalized Constraint and Exception handler for an Object-Oriented CAD-DBMS. OODBS 1986: 38-49 BibTeX
[7]
Michael J. Carey, David J. DeWitt, Daniel Frank, Goetz Graefe, M. Muralikrishna, Joel E. Richardson, Eugene J. Shekita: The Architecture of the EXODUS Extensible DBMS. OODBS 1986: 52-65 BibTeX
[8]
Upen S. Chakravarthy, Daniel H. Fishman, Jack Minker: Semantic Query Optimization in Expert Systems and Database Systems. Expert Database Workshop 1984: 659-674 BibTeX
[9]
...
[10]
...
[11]
Hong-Tai Chou, David J. DeWitt, Randy H. Katz, Anthony C. Klug: Design and Implementation of the Wisconsin Storage System. Softw., Pract. Exper. 15(10): 943-962(1985) BibTeX
[12]
...
[13]
Umeshwar Dayal, Philip A. Bernstein: On the Updatability of Relational Views. VLDB 1978: 368-377 BibTeX
[14]
...
[15]
Ramez Elmasri, James A. Weeldreyer, Alan R. Hevner: The Category Concept: An Extension to the Entity-Relationship Model. Data Knowl. Eng. 1(1): 75-116(1985) BibTeX
[16]
Sheldon J. Finkelstein: Common Subexpression Analysis in Database Applications. SIGMOD Conference 1982: 235-245 BibTeX
[17]
Sheldon J. Finkelstein, Mario Schkolnick, Paolo Tiberio: Physical Database Design for Relational Databases. ACM Trans. Database Syst. 13(1): 91-128(1988) BibTeX
[18]
Johann Christoph Freytag: A Rule-Based View of Query Optimization. SIGMOD Conference 1987: 173-180 BibTeX
[19]
...
[20]
Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172 BibTeX
[21]
Goetz Graefe: Rule-Based Query Optimization in Extensible Database Systems. Ph.D. thesis, Univ. of Wisconsin-Madison 1987
BibTeX
[22]
Laura M. Haas, Walter Chang, Guy M. Lohman, John McPherson, Paul F. Wilms, George Lapis, Bruce G. Lindsay, Hamid Pirahesh, Michael J. Carey, Eugene J. Shekita: Starburst Mid-Flight: As the Dust Clears. IEEE Trans. Knowl. Data Eng. 2(1): 143-160(1990) BibTeX
[23]
Michael Hammer, Stanley B. Zdonik: Knowledge-Based Query Processing. VLDB 1980: 137-147 BibTeX
[24]
Michael Hammer, Sunil K. Sarin: Efficient Monitoring of Database Assertions (Abstract). SIGMOD Conference 1978: 159 BibTeX
[25]
...
[26]
Matthias Jarke: Common Subexpression Isolation in Multiple Query Optimization. Query Processing in Database Systems 1985: 191-205 BibTeX
[27]
Won Kim, David S. Reiner, Don S. Batory (Eds.): Query Processing in Database Systems. Springer 1985, ISBN 3-540-13831-5
Contents BibTeX
[28]
...
[29]
Jonathan J. King: QUIST: A System for Semantic Query Optimization in Relational Databases. VLDB 1981: 510-517 BibTeX
[30]
Per-Åke Larson, H. Z. Yang: Computing Queries from Derived Relations. VLDB 1985: 259-269 BibTeX
[31]
Douglas B. Lenat: Theory Formation by Heuristic Search. Artif. Intell. 21(1-2): 31-59(1983) BibTeX
[32]
Douglas B. Lenat: EURISKO: A Program That Learns New Heuristics and Domain Concepts. Artif. Intell. 21(1-2): 61-98(1983) BibTeX
[33]
...
[34]
...
[35]
Shamkant B. Navathe, Stefano Ceri, Gio Wiederhold, Jinglie Dou: Vertical Partitioning Algorithms for Database Design. ACM Trans. Database Syst. 9(4): 680-710(1984) BibTeX
[36]
...
[37]
Mario Schkolnick, Paolo Tiberio: Estimating the Cost of Updates in a Relational Database. ACM Trans. Database Syst. 10(2): 163-179(1985) BibTeX
[38]
Timos K. Sellis: Global Query Optimization. SIGMOD Conference 1986: 191-205 BibTeX
[39]
Timos K. Sellis: Multiple-Query Optimization. ACM Trans. Database Syst. 13(1): 23-52(1988) BibTeX
[40]
Sreekumar T. Shenoy, Z. Meral Özsoyoglu: A System for Semantic Query Optimization. SIGMOD Conference 1987: 181-195 BibTeX
[41]
Michael Siegel: Automatic Rule Derivation For Semantic Query Optimization. Expert Database Conf. 1988: 669-698 BibTeX
[42]
...
[43]
Michael Stonebraker, Lawrence A. Rowe: The Design of Postgres. SIGMOD Conference 1986: 340-355 BibTeX
[44]
Donald A. Waterman: Generalization Learning Techniques for Automating the Learning of Heuristics. Artif. Intell. 1(1/2): 121-170(1970) BibTeX
[45]
...
[46]
Clement T. Yu, Wei Sun: Automatic Knowledge Acquisition and Maintenance for Semantic Query Optimization. IEEE Trans. Knowl. Data Eng. 1(3): 362-375(1989) BibTeX

Referenced by

  1. I-Min A. Chen: Query Answering Using Discovered Rules. ICDE 1996: 402-411
  2. Show-Jane Yen, Arbee L. P. Chen: An Efficient Algorithm for Deriving Compact Rules from Databases. DASFAA 1995: 364-371
  3. Edward Sciore, Michael Siegel, Arnon Rosenthal: Using Semantic Values to Falilitate Interoperability Among Heterogeneous Information Systems. ACM Trans. Database Syst. 19(2): 254-290(1994)
  4. Michael Siegel, Stuart E. Madnick: A Metadata Approach to Resolving Semantic Conflicts. VLDB 1991: 133-145
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:13 2008