1993 LearningTransfRulesForSemQueryOpt
- (Shekhabar et al., 1993) ⇒ Shashi Shekhar, Babak Hamidzadeh, Ashim Kohli, and Mark Coyle. (1993). “Learning Transformation Rules for Semantic Query Optimization: A Data-Driven Approach.” In: IEEE Transactions on Knowledge and Data Engineering, 5(6). doi:10.1109/69.250077
Subject Headings: Query Transformation Rule, Transitive Closure Algorithm.
Notes
Cited By
Quotes
Author Keywords
Transformation Rule; Semantic Query Optimization. Transformation rules; semantic query optimization; data-driven approach; query-transformation rules; closure algorithm; data distribution; correctness; completeness; complexity; SQO; data-driven discovery; computational complexity; deductive databases; learning (artificial intelligence); query processing.
Abstract
An approach to learning query-transformation rules based on analyzing the existing data in the database is proposed. A framework and a closure algorithm for learning rules from a given data distribution are described. The correctness, completeness, and complexity of the proposed algorithm are characterized and a detailed example is provided to illustrate the framework.
…
2. Related Approaches and Our Contributions
The learning of query transformation rules can be query-driven or data-driven. In query-driven frameworks [7, 11] the search for new query transformation rules is guided by the set of queries arriving at the database using query comparisons [7] and hypothesis generation and testing [11, 12]. In query comparison, the set of queries arriving after the last update are analyzed by comparing the set of tuples retrieved to answer various queries. If the set of tuples retrieved by two queries are identical then query transformation rules relating the restrictions in the two queries can be added[7]. In hypothesis generation and testing approaches [13], the queries are used to generate a candidate query transformation rule. A candidate rule consists of an antecedent restriction and the set of variables in the consequent. The antecedent restriction is generated from the restriction clauses of the queries arriving at the system. The set of free variables for the consequent is generated by heuristics such as index introduction[1]. The antecedent restriction is evaluated against the database state to retrieve and summarize all possible values of the free variables to form the consequent.
In the data-driven framework the search is directed by the data, leading to the learning of rules characterizing patterns in the data representing query transformation rules. This learning can take place off-line in order to limit the effect of larger processing times on on-line processing. An advantage of this framework for learning query transformation rules is that the rules are learned a priori and they cover many queries that may not have been requested before. Data-driven approaches can be based on the learning algorithms developed in Artificial Intelligence (AI). Many of these learning algorithms discover rules represented in languages similar to first order predicate logic (FOPL), which can be used to represent general integrity constraints [14, 15] and query transformation rules. For example, the representation languages used in AQ15[16] and in the conceptual clustering algorithm Cluster 2[17] are fairly close to FOPL.
References
,
| Author | volume | Date Value | title | type | journal | titleUrl | doi | note | year | |
|---|---|---|---|---|---|---|---|---|---|---|
| 1993 LearningTransfRulesForSemQueryOpt | Shashi Shekhar Babak Hamidzadeh Ashim Kohli Mark Coyle | Learning Transformation Rules for Semantic Query Optimization: A Data-Driven Approach | IEEE Transactions on Knowledge and Data Engineering | http://ieeexplore.ieee.org/xpl/freeabs all.jsp?arnumber=250077 | 10.1109/69.250077 | 1993 |