Query Processing and Optimization

Question 1

Describe the function of the scanner, parser and validator. What happens after all these carry out their function?

Answer 1

S- Identifies language tokens
P- Check query syntax
V-Checks all attributes and relation names are valid

After all these processes are carried out an internal representation (query tree or query graph) is created

Question 2

Define an execution strategy

Answer 2

A plan devised by the DBMS to retrieve the result of a query from database files

Question 3

Define query optimization

Answer 3

Process of choosing a suitable execution strategy for processing a query

Question 4

What are the main techniques of query optimization

Answer 4

1. Heuristic rules (Logical)- for reordering operations in the query
   2.Systematically estimating the cost of different execution strategies and choosing the lowest cost estimate.(input output requirements, memory, processing power and routing protocol

Question 5

Describe the typical steps in processing a high-level query

Answer 5

1. Query in high-level language
   Scanner, parser and validator
   2.Intermediate form of query eg query tree or query graph
   Query Optimizer
   3.Execution plan
   Query Code generator
   4.Object code for query
   Run-time DBMS processor
   5.Query Results

Question 6

What are the two internal representations of a query

Answer 6

query tree
query graph

Question 7

How is a query tree generated from sql

Answer 7

SQL is translated into an equivalent extended relational algebra expression which is represented as a query tree

Question 8

Describe query blocks. Illustrate how they are formed and translated

Answer 8

A query block is the basic unit that can be transformed into algebraic operators and optimized
In order to transform a given query into a query tree it is first decomposed into query blocks. The query optimizer generates an execution strategy for each query block.

A query block is made up of one SELECT-FROM-WHERE clause, and if present includes the GROUP BY and HAVING clause

*See 10 and 11 for illustrations