written 7.1 years ago by | • modified 2.2 years ago |

**Subject:** Distributed Database

**Topic:** Distributed query processing and optimization

**Difficulty:** High

**1 Answer**

0

11kviews

What is query optimisation? List distributed Query optimisation algorithms and explain any one from that.

written 7.1 years ago by | • modified 2.2 years ago |

**Subject:** Distributed Database

**Topic:** Distributed query processing and optimization

**Difficulty:** High

ADD COMMENT
EDIT

2

412views

written 7.1 years ago by |

**Query Optimization**

Query optimization is the process of selecting the most efficient quey-evaluation plan from among the many strategies usually possible for a given query. It does not expect users to write their queries so that they can be processed efficiently. Rather, it expects the system to construct a query evaluation plan that minimizes the cost of query evaluation.

**Distributed query optimization algorithm:**

- Semi-join Algorithm
- INGRES Algorithm
- System R Algorithm
- System R* Algorithm
- Hill Climbing Algorithm
- SDD-1 Algorithm

**Hill Climbing Algorithm**

- It refinements of an initial feasible solution are recursively computed until no more cost improvements can be made.
- In hill climbing algorithm, Semijoins, data replication, and fragmentation are not used.
- It devised for wide area point-to-point networks.
- It is the first distributed query processing algorithm.
The hill-climbing algorithm proceeds as follows:

i. Select initial feasible execution strategy ES0

• i.e., a global execution schedule that includes all intersite communication

• Determine the candidate result sites, where a relation referenced in the query exist

• Compute the cost of transferring all the other referenced relations to each candidate site

• ES0 = candidate site with minimum cost

ii. Split ES0 into two strategies: ES1 followed by ES2

• ES1: send one of the relations involved in the join to the other relation’s site –

• ES2: send the join result to the final result site

iii. Replace ES0 with the split schedule which gives

iv. Recursively apply steps 2 and 3 on ES1 and ES2 until no more benefit can be gained

v. Check for redundant transmissions in the final plan and eliminate them

ADD COMMENT
EDIT

Please log in to add an answer.