Mumbai University > Computer Engineering > Sem 4 > Database Management System

Marks: 5M

Year: Dec 2014

The steps involved in processing a query appear in Figure below:

1. Parsing and translation:

The first action the system must take in query processing is to translate a given query into its internal form. This translation process is similar to the work performed by the parser of a compiler.

In generating the internal form of the query, the parser checks the syntax of the user’s query, verifies that the relation names appearing in the query are names of the relations in the database. The system constructs a parse-tree representation of the query, which it then translates into a relational-algebra expression.

2. Optimization:

In this step an optimal evaluation plan with the lowest cost for the query plan is generated.

Select balance from account where balance <5000

Given relational algebra expression may have many equivalent such as σbal<5000 (Πbal (account)) is equivalent to Πbal (σbal<5000 (account))

Relational –algebra expression can be evaluated in many ways were the expression specifying detailed evaluation strategy is called an evaluation-plan.

An index can be used on bal to find accounts with bal< 5000 or can perform complete relation scan and discard accounts with bal>5000.

3. Evaluation:

The query-execution engine takes a query-evaluation plan, executes that plan, and returns the answers to the query.

The different evaluation plans for a given query can have different costs. Users do not write the irqueries in a way that meet the efficient evaluation plan.

Instead itistheresponsibilityofthesystemtoconstructaquery-

evaluationplanthatminimizesthecostofqueryevaluation.

Once the query plan is chosen, the query is evaluated with that plan, and the result of the query is output.