User Aware Query Transformation

Abstract

SQL is a block-structured query language for data retrieval and manipulation from database. There are many ways of writing same query using di erent keywords to retrieve same result. This research is for identify di erent ways of writing queries to produce same result-set and prove equivalence of these queries. Query equivalence is a fundamental problem within database theory. A theory of query equivalence methodology in existing query processing and optimization is used to prove the correctness of transformed query. Relational algebra and relational calculus are the two well known query languages to prove the correctness of transformed query used in existing query optimizer. DBMS optimizer internally optimizes these queries in another e cient way without knowledge of user. This optimization gets extra execution time for query processing. This work emphasizes on di erent types of queries which reduces this extra execution cost. This thesis for identify many equal queries for a given query with their execution cost. It has proved above objective for nested correlated non-aggregate queries since nested query is one of the most powerful features in SQL. Relational algebra is used to prove query equivalence as a mathematical theory because equivalence of output result-set is not enough to show that. Generate relational algebra expression for each query and then applies Algebraic laws to get canonical form of generated all queries. Transformation of query to group of another semantically equivalent query is done by using modi ed Kim's algorithm. This research gives knowledge to the user how to write e cient query and way to prove query equivalence. Demonstrate the possible performance gains of di erent type of semantic equal queries using experimental result.