Answer for Assignment 2
& Query Optimization
COMP3278 2023
TA: Zhixuan Liang
liangzx@connect.hku.hk
Q1.(a) Please transform the above
SQL query to relational algebra
expression. Please write the
relational algebra expression and
draw the corresponding
expression tree.
Query Optimization (查询优化)
• Cost difference between evaluation plans for a query can be enormous
Q1.(b) Please apply 3 • E.g. seconds vs. days in some cases
different equivalence rules • Steps in cost-based query optimization
to optimize your relational 1. Generate logically equivalent expressions using equivalence rules
algebra expression in (a) 2. Annotate resultant expressions to get alternative query plans
above. You only need to 3. Choose the cheapest plan based on estimated cost
write the final relational • Estimation of plan cost based on:
algebra expression after • Statistical information about relations. Examples:
optimization and draw the • number of tuples, number of distinct values for an attribute
final optimized expression • Statistics estimation for intermediate results
tree. • to compute cost of complex expressions
• Cost formulae for algorithms, computed using statistics
Transformation Example: Pushing Selections
Query Optimization (查询优化)
Query: Find the names of all instructors in the Music
department, along with the titles of the courses that they teach
Pname, title(sdept_name= “Music”
(instructor (teaches Pcourse_id, title (course))))
Transformation using rule 7a.
Pname, title((sdept_name= “Music”(instructor))
(teaches Pcourse_id, title (course)))
Performing the selection as early as possible reduces the size
of the relation to be joined.
Database System Concepts - 6th Edition 1.14 ©Silberschatz, Korth and Sudarshan
Transformation Example: Pushing Projections
Query Optimization (查询优化)
Consider: Pname, title(sdept_name= “Music” (instructor) teaches)
Pcourse_id, title (course))))
When we compute
(sdept_name = “Music” (instructor teaches)
we obtain a relation whose schema is:
(ID, name, dept_name, salary, course_id, sec_id, semester,
year)
Push projections using equivalence rules 8a and 8b; eliminate
unneeded attributes from intermediate results to get:
Pname, title(Pname, course_id (
sdept_name= “Music” (instructor) teaches))
Pcourse_id, title (course))))
Performing the projection as early as possible reduces the size
of the relation to be joined.
Database System Concepts - 6th Edition 1.16 ©Silberschatz, Korth and Sudarshan
Enumeration of Equivalent Expressions
Query Optimization (查询优化)
Query optimizers use equivalence rules to systematically generate
expressions equivalent to the given expression
Can generate all equivalent expressions as follows:
Repeat
4 apply all applicable equivalence rules on every subexpression of
every equivalent expression found so far
4 add newly generated expressions to the set of equivalent
expressions
Until no new equivalent expressions are generated above
The above approach is very expensive in space and time
Two approaches
4 Optimized plan generation based on transformation rules
4 Special case approach for queries with only selections, projections
and joins
Database System Concepts - 6th Edition 1.20 ©Silberschatz, Korth and Sudarshan
Q1.(b) Please apply 3 different
equivalence rules to optimize
your relational algebra expression
in (a) above. You only need to
write the final relational algebra
expression after optimization and
draw the final optimized
expression tree.
Q1.(b) Please apply 3 different
equivalence rules to optimize
your relational algebra expression
in (a) above. You only need to
write the final relational algebra
expression after optimization and
draw the final optimized
expression tree.
Q1.(b) Please apply 3 different equivalence rules to optimize your relational algebra
expression in (a) above. You only need to write the final relational algebra expression
after optimization and draw the final optimized expression tree.
Q1.(b) Please apply 3 different equivalence rules to optimize your relational algebra
expression in (a) above. You only need to write the final relational algebra expression
after optimization and draw the final optimized expression tree.
5
3*5=15 15+15=30
Q1.(b) Please apply 3 different equivalence rules to optimize your relational algebra
expression in (a) above. You only need to write the final relational algebra expression
after optimization and draw the final optimized expression tree.
Q2. R = (A, B, C,D, E), F = {AD → E, C → A, DE → B, BE → D, E → AB}
(a) Pick C → A, {𝐶 }+ = {𝐴 , 𝐶 } ≠ 𝑅 , so R is not in BCNF.
(b) Part I
C A
E B
D
(b) Part II
C A
E B
D
C A
E B
D
In summary
DataBase Usage
• SQL Query
DataBase Design
• How to model a problem —— E-R Model
• How to define reasonable table from E-R model —— FD and Normal Form
• How to express query —— Relational Algebra
• How to optimize query —— Query Optimization and Cost Estimation
• How to accelerate query —— Indexing (B+ Tree)
Other untaught but also important topic in database design
(Maybe you will learn in other courses or your future life J)
• How to storage database data —— RAID
• How to guarantee query consistency —— Atomicity, Consistency, Isolation and Duration
Wish you a high score in the final exam
and all the best in your future life !
TA: Zhixuan Liang
liangzx@connect.hku.hk
