Logic-based approach to semantic query optimization
ACM Transactions on Database SystemsPublished 1 June 1990Open access
Upen S. Chakravarthy, John Grant, Jack Minker
Citations347
SJR quartileQ1
SJR score0.91
SNIP1.85
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper consolidates the major results of these papers emphasizing the techniques and their applicability for optimizing relational queries and indicates how semantic query optimization techniques can be extended to databases that support recursion and integrity constraints that contain disjunction, negation, and recursion.
Abstract
The purpose of semantic query optimization is to use semantic knowledge (e.g., integrity constraints) for transforming a query into a form that may be answered more efficiently than the original version. In several previous papers we described and proved the correctness of a method for semantic query optimization in deductive databases couched in first-order logic. This paper consolidates the major results of these papers emphasizing the techniques and their applicability for optimizing relational queries. Additionally, we show how this method subsumes and generalizes earlier work on semantic query optimization. We also indicate how semantic query optimization techniques can be extended to databases that support recursion and integrity constraints that contain disjunction, negation, and recursion.
Keywords
Computer Science
Elsevier eBooksSymbolic Logic and Mechanical Theorem Proving
1,472 Citations1973
This book contains an introduction to symbolic logic and a thorough discussion of mechanical theorem proving its applications and how it can be applied to various areas such as question answering, problem solving, program analysis, and program synthesis.
Elsevier eBooksFoundations of Deductive Databases and Logic Programming
973 Citations1988
This book is referred to read because it is an inspiring book to give you more chance to get experiences and also thoughts and this foundations of deductive databases and logic programming.
ACM Computing SurveysLogic and Databases: A Deductive Approach
739 Citations1984Hervé Gallaire, Jack Minker +1 more
It is shown that logic provides a convenient formalism for studying classical database problems and the representation and manipulation of deduced facts and incomplete information is shown.
ACM SIGMOD RecordAn amateur's introduction to recursive query processing strategies
697 Citations1986François Bancilhon, Raghu Ramakrishnan
ACM Computing SurveysQuery Optimization in Database Systems
642 Citations1984Matthias Jarke, Jürgen Koch
These methods are presented in the framework of a general query evaluation procedure using the relational calculus representation of queries, and nonstandard query optimization issues such as higher level query evaluation, query optimization in distributed databases, and use of database machines are addressed.
An amateur's introduction to recursive query processing strategies
315 Citations1986François Bancilhon, Raghu Ramakrishnan
This paper surveys and compares various strategies for processing logic queries in relational databases and presents a set of sample rules and queries used for the performance comparisons and gives an analytical solution for each query/rule system.
ACM Transactions on Database SystemsEfficient optimization of a class of relational expressions
217 Citations1979A. V. Aho, Yehoshua Sagiv +1 more
The difficulty of optimizing queries based on the relational algebra operations select, project, and join is discussed, and a polynomial time algorithm exists to optimize tableaux that correspond to an important subclass of queries.
Very Large Data BasesKnowledge-based query processing
133 Citations1980Michael Hammer, Stanley B. Zdonik
The data indicate that further adjuvant radiation therapy to increase local control may not be indicated by tumor size alone in the absence of positive lymph nodes, indicating that patients with this risk factor require careful consideration with regard to further local therapy.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Query optimization by semantic reasoning
111 Citations1981Jonathan J. King
The thesis formally defines transformations that preserve semantic equivalence for queries in the relational calculus and identifies several classes of cost-reducing query transformations for relational database queries, and provides quantitative estimates of the improvements they can produce, based upon widely accepted models of query processing.
An optimizing prolog front-end to a relational query system
102 Citations1984Matthias Jarke, Jim Clifford +1 more
An optimizing translation mechanism for the dynamic interaction between a logic-based expert system written in PROLOG and a relational database accessible through SQL is presented and makes use of an intermediate language that decomposes the optimization problem and makes the proposed approach target-language independent.
Elsevier eBooksFoundations of Semantic Query Optimization for Deductive Databases
96 Citations1988Upen S. Chakravarthy, John Grant +1 more
This paper contains the formal definitions and proof of correctness of the semantic query optimization technique, a method based on subsumption which can be used both for standard relational databases and for deductive databases.
A system for semantic query optimization
94 Citations1987Sreekumar T. Shenoy, Z. Meral Özsoyoğlu
The scheme uses a graph theoretic approach to identify redundant join clauses and redundant restriction clauses specified in a user query and an algorithm is suggested to eliminate such redundant joins and avoid unnecessary restrictions.
Efficient optimization of a class of relational expressions
93 Citations1978Alfred V. Aho, Yehoshua Sagiv +1 more
The optimization problem is shown to be NP-complete, but a polynomial time algorithm can be given to optimize tableaux that correspond to an important subclass of expressions.
Multiple Query Processing in Deductive Databases using Query Graphs
76 Citations1986Upen S. Chakravarthy, Jack Minker
The Journal of Logic ProgrammingPerspectives in deductive databases
62 Citations1988Jack Minker
The relationships between techniques from formal logic, databases, logic programming, and artificial intelligence will continue to be explored and the field of deductive databases will become a more prominent area of computer science in coming years.
The use of a semantic network in a deductive question-answering system
50 Citations1977James R. McSkimin, Jack Minker
The use of a semantic network is considered to a id in the deduct ive search process of a Question-Answering (QA System) System.
Artech House, Inc. eBooksQUIST: a system for semantic query optimization in relational databases
49 Citations1981Jonathan J. King
QUIST analyzes a query at several levels of detail, along the lines of the plan-generate-test paradigm of artificial intelligence systems, and demonstrates significant cost reductions for a class of relational database queries.
Optimization in Deductive and Conventional Relational Database Systems
45 Citations1981John Grant, Jack Minker
The purpose of this paper is to describe a “global” optimizing algorithm which accounts for similarities between conjuncts in a deductive relational database system.
Semantic query optimization in recursive databases
18 Citations2003S. Lee, Jia Liang Han
The authors propose a compiled approach to utilizing semantic knowledge in recursive query processing, assuming recursive queries are processed using compiled iterative methods and a method of residue propagation for obtaining implied constraints that are often useful in optimization.
PLoS ONEThe use of semantic information in deductive question-answering systems.
17 Citations1976James R. McSkimin
CDV infection increased the 50-year extinction probability of tigers in SABZ by 6.3% to 55.8% compared to a control population, depending on risk scenario, and small populations were found to be disproportionately vulnerable to extinction through CDV infection.
National Conference on Artificial IntelligenceIntelligent control using integrity constraints
9 Citations1983Madhur Kohli, Jack Minker
This paper describes how integrity constraints, whether user supplied or automatically generated during the search, and analysis of failures can be used to improve the execution of function free logic programs.
Semantic query optimization in deductive databases. (volumes i and ii) (integrity constraints, intelligent processing, logic)
7 Citations1985Upendranath Sharma Chakravarthy
This thesis addresses the problem of efficient query evaluation over a deductive database and proposes several methods to optimize the evaluation of a query, and proposes a general framework in which domain specific knowledge--in the form of integrity constraints, is used to transform a query.