Assignment - 7 Query Processing & Optimization

Assignment – 7         Query Processing & optimization    Submission Date 30-05-11  

Q-1. Explain the Following Questions in detail.

1).What do you mean by the term query processing? What are its objectives? 

Draw a neat sketch of high-level query processing?

2).Discuss the reason for converting SQL query into relation algebra queries before query optimization.

3).What is syntax analyzer? Explain with an example.

4).Explain the query decomposer with different phases in detail?

5).What is query optimization? Why it is needed.

6).Describe the query optimization with detail block diagram.

7).Explain how heuristic query optimization is performed with an example.

8).Describe the Transformation rules for query optimizer.

9).What is relational algebra query tree? Explain with example.

10).What is heuristic optimization algorithm? Discuss various steps in heuristic optimization algorithm.

11).Discuss the main components for a cost function that is used to estimate query execution cost.

12).What are the cost components are used most often as the basis for cost function.

13).List the cost function for the SELECT operation.

14).List the cost function for the JOIN operation.

15).What are basic query optimization strategies? List out the different technique.

---------------------------------------------------------------------------------------------------------------

Q-2. Do as Directed

1). Let us consider the fallowing relations (tables) that form part of a database of a relational DBMS

HOTEL     (HOTEL-NO, HOTEL-NAME, CITY)

ROOM      (ROOM-NO, HOTEL-NO, TYPE, PRICE)

BOOKING (HOTEL-NO, GUEST-NO, DATE-FROM, DATE-TO, ROOM-NO)

GUEST      (GUEST-NO, GUEST-NAME, GUEST-ADDRESS)

draw a relational algebra tree for each of the following queries. Use the heuristic rules to transform the queries into a more efficient form.

(A). SELECT R.ROOM-NO, R.TYPE, R.PRICE

       FROM ROOM R, HOTEL H, BOOKING B

       WHERE R.ROOM-NO=B.ROOM-NO AND

       B.HOTEL-NO=H.HOTEL-NO AND

       H.HOTEL-NAME=’EMPERIAL’ AND

       R.PRICE>100

(B). SELECT G.GUEST-NO, G.GUEST-NAME

       FROM GUEST AS G, BOOKING AS B. HOTEL AS H, ROOM AS R

       WHERE H.HOTEL-NO = B.HOTEL-NO AND

       G.GUEST-NO = B.GUEST-NO AND

       H.HOTEL-NO = R.HOTEL-NO AND

       H.HOTEL-NAME = ‘Shiv International’ AND

       B.DATE-FROM >= '1-Jan-05' AND

       B.DATE-TO<='31 Dec-05

2). Write and justify an efficient relational algebra expression that is equivalent to the following given query

SELECT B1.BANK-NAME

FROM BANK1 AS B1, BANK2 AS B2

WHERE B1.ASSESTS>B2.ASSESTS AND

B2.BANK-LOCATION=’Rajkot’

3). Using the above HOTEL schema, determine whether the following queries are semantically correct and justify your answer.

(A). SELECT R.TYPE, R.PRICE

      FROM ROOM AS R, HOTEL AS H

      WHERE R.HOTEL-NUM = H.HOTEL-NUM AND

      H.HOTEL-NAME = 'Taj Residency' AND

      R..TYPE > l00

(B).   SELECT G.GUEST-NO, G.GUEST-NAME

        FROM GUEST AS G, BOOKING AS B, HOTEL AS H

        WHERE R.HOTEL-NO=B.HOTEL-NO AND

        H.HOTEL-NAME=’TAJ’

(C).  SELECT R.ROOM-NO, H.HOTEL-NO

       FROM   ROOM AS R, HOTEL AS H, BOOKING AS B

       WHERE H.HOTEL-NO=B.HOTEL-NO AND

       H.HOTEL-NO=’H40’ AND

       B.ROOM-NO=R.ROOM-NO AND

       R.TYPE>’S’ AND B.HOTEL-NO=’H50’    

Assignment - 6 Relational Algebra

Assignment – 6 Relational Algebra    Submission Date 12-05-11  

Q.1	Consider the following relations: Suppliers (Sid, S_name, Address) Parts (Pid, P_name, Colour) Catalogue (Sid, Pid, Cost) The key fields are underlined. Write the following queries in relational algebra.
	1) Find the names of suppliers who supply some red parts. 2) Find the Pid of parts supplied by every supplier at less than INR 500. 3) Find the Pid of parts that are supplied by at least two different suppliers. 4) Find the Sid of suppliers who supply every part or green part. 5) Find the Sid of suppliers who supply every part. 6) Find the Sid of suppliers who supply some red or green part. 7) Find the Sid of suppliers who supply some red and some green parts.
Q.2	Consider the relation schemas as follows and Convert Following query into SQL and Relational Algebra. WORKS           (PERSON_NAME, COMPANY_NAME, SALARY) LIVES              (PERSON_NAME, STREET, CITY) LOCATED_IN   (COMPANY_NAME, CITY) MANAGERS     (PERSON_NAME, MANAGER_NAME)           Where manager_name referes to Person_name
	1)    Find the name of the persons who work for company ‘FBC’ 2)    List the names of the persons who work for company ’FBC’ along with the cities they live in. 3)    Find the persons who work for company ’FBC’ with a salary of more than 10000. List the names of these persons along with the streets and cities where they live. 4)    Find the names of the persons who live and  work in the same city. 5)    Find the names of the persons who live in the same city and on the same street as their managers. 6)    Find the names of the persons who do not work for Company ’FBC’. 7)    Find the persons whose salaries are more than the salary of everybody who work for company ’SBC’. 8)    Find the names of the companies that is located in every city where company ’SBC’ is located in.
Q.3	Write down Relational Algebra for the given schema. SOFTWARE(sid,software_name,develop_in,selling_cost,development_cost) PROGRAMMER (pid, pname, date_join, dept_name, sid,Salary, gender)
	Find out the selling cost average for packages developed in Oracle. List details of programmer whose salary is greater than Rs.10,000. Display details of Software develop by “Mr. Ram”. How many software has highest development cost. List details of programmer who join in the current month. Retrieve name of programmer who do not involve in any software development. Retrieve all male programmers working in ‘MCA’ department.

Basic of Join

INNER JOIN

This join returns rows when there is at least one match in both the tables.

OUTER JOIN

There are three different Outer Join methods.

LEFT OUTER JOIN
This join returns all the rows from the left table in conjunction with the matching rows from the right table. If there are no columns matching in the right table, it returns NULL values.


RIGHT OUTER JOIN
This join returns all the rows from the right table in conjunction with the matching rows from the left table. If there are no columns matching in the left table, it returns NULL values.


FULL OUTER JOIN
This join combines left outer join and right after join. It returns row from either table when the conditions are met and returns null value when there is no match.

CROSS JOIN

This join is a Cartesian join that does not necessitate any condition to join. The resultset contains records that are multiplication of record number from both the tables.

Additional Notes related to JOIN:

The following are three classic examples to display where Outer Join is useful. You will notice several instances where developers write query as given below.

SELECT t1.*FROM Table1 t1WHERE t1.ID NOT IN (SELECT t2.ID FROM Table2 t2)GO

The query demonstrated above can be easily replaced by Outer Join. Indeed, replacing it by Outer Join is the best practice. The query that gives same result as above is displayed here using Outer Join and WHERE clause in join.

/* LEFT JOIN - WHERE NULL */SELECT t1.*,t2.*FROM Table1 t1LEFT JOIN Table2 t2 ON t1.ID = t2.IDWHERE t2.ID IS NULL

The above example can also be created using Right Outer Join.


NOT INNER JOIN
Remember, the term Not Inner Join does not exist in database terminology. However, when full Outer Join is used along with WHERE condition, as explained in the above two examples, it will give you exclusive result to Inner Join. This join will give all the results that were not present in Inner Join.

Relational Algebra

What is Relational Algebra?

1.    The relation algebra is a procedure query language.

2.    It consists of set of operation that takes one or two relation as input and produced a new relation as result.

3.    The select, project, and rename operation are called unary operation because they operate on one relation.

4.    Other operations operate on more than one relation and therefore it’s called binary operation.

Six basic operators:

·       Unary Operators

1)   Select    -  σ  (Sigma)

2)   Project   -  ∏ (PI)

3)    Rename -  ρ  (rho)

·       Binary Operators

1)    Union    -  U

2)    Set Difference - –

3)    Cartesian Product - X

Four Additional operators:

1)    Set intersection - ∩

2)    Natural join      -  

                    I.        Left Outer Join    -  

                  II.        Right Outer Join -  

                 III.        Full Outer Join   -

3)    Division - ÷

4)    Assignment - ←

Three Database Modification operators:

1)    Insert Operator  r ← r U E

2)    Delete Operator  r ← r – E

3)    Update Operator r ← ∏ F1,F2….Fn  (r)

Projection

Example:   (Table) EMPLOYEE

nr	name	salary
1	John	100
5	Sarah	300
7	Tom	100

SQL	Result	Relational algebra
select salary from Employee	salary 100 300	∏salary(Employee)
select nr, salary from Employee	nr salary 1 100 5 300 7 100	∏nr, salary(E)

Note that there are no duplicate rows in the result.

Selection

SQL	Result	Relational algebra
select * from Employee where salary < 200	nr name salary 1 John 100 7 Tom 100	σsalary < 200(Employee)
select * from Employee where salary < 200 and nr >= 7	nr name salary 7 Tom 100	σsalary < 200 and nr >= 7(Employee)

Cartesian product

The cartesian product of two tables combines each row in one table with each row in the other table.
Example: The table  (for EMPLOYEE)

enr	ename	dept
1	Parag	A
2	Kapil	C
3	Deven	A

(DEPARTMENT)

dnr	dname
A	Marketing
B	Sales
C	Legal

SQL	Result	Relational algebra
select * from E, D	enr ename dept dnr dname 1 Parag A A Marketing 1 Parag A B Sales 1 Parag A C Legal 2 Kapil C A Marketing 2 Kapil C B Sales 2 Kapil C C Legal 3 Deven A A Marketing 3 Deven A B Sales 3 Deven A C Legal	Employee X Department

• Seldom useful in practice.
• Usually an error.
• Can give a huge result.

The Natural join Operation:

•   The Natural join is a binary operation that allows us to combine certain selections and Cartesian product into one operation.
•   It is denoted by the join symbol ( ).
•   The natural join operation forms a Cartesian product of its two arguments, performs a selection forcing equality on those attribute that appear in both relation, and removes the duplicate attributes.

Example

                                       EMP

Emp No	Emp Name	City	Salary	Deptno
1	Parag	Snagar	17000	10
2	Kapil	Sidhpur	18000	20
3	Deven	Junagadh	20000	10
4	Rahul	Rajkot	22000	30
5	Saurav	Jamnagar	35000	Null

    DEPT

Deptno	Deptname	Location
10	Computer	Ahmedabad
20	Account	Surat
30	Finance	Banglore
40	Research	Bombay
50	Marketing	Rajkot

∏ Emp.Empno,Empname,Salary,Deptname

 

(σEmp.deptno=dept.deptno ^{(EMP                                DEPT)})

Output:

Empno	Empname	Salary	Deptname
1	Parag	17000	Computer
2	Kapil	18000	Account
3	Deven	20000	Computer
4	Rahul	22000	Finance

•   The result of this expression is shown in above table. Notice that we have lost the record about Saurav because he is not working in any department.
•   Similarly, we have lost the record of deptno 40 and 50 from Dept because there is no employee working in deptno 40 and 50.
•   In short, it returns record on base of deptno.