Multiple Transformations(Cont.) name,title name,title 6 dept_name=Music A year =2009 course year =2009 instructor dept_name-Music teaches course instructor teaches (a)Initial expression tree (b)Tree after multiple transformations Database System Concepts-6th Edition 1.17 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 6 1.17 ©Silberschatz, Korth and Sudarshan th Edition Multiple Transformations (Cont.)
Transformation Example:Pushing Projections Consider:IIname,title(dept name=Music"(instructor teaches) Icourse_id,title (course)))) When we compute (dept name=“"Music"(instructo☒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: IIname,title(IIname,course_id( Odept_name='Music"(instructor teaches)) 凶Πcourse_ja,te(course)》 Performing the projection as early as possible reduces the size of the relation to be joined. Database System Concepts-6th Edition 1.18 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 6 1.18 ©Silberschatz, Korth and Sudarshan th Edition Transformation Example: Pushing Projections Consider: name, title(dept_name= “Music” (instructor) teaches) course_id, title (course)))) When we compute (dept_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: name, title(name, course_id ( dept_name= “Music” (instructor) teaches)) course_id, title (course)))) Performing the projection as early as possible reduces the size of the relation to be joined
Join Ordering Example For all relations r.r2.and ra, (12)☒r3=r1凶(2☒r3) (Join Associativity) If r2ra is quite large and rr2 is small,we choose (1凶r2)r3 so that we compute and store a smaller temporary relation. Database System Concepts-6th Edition 1.19 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 1.19 ©Silberschatz, Korth and Sudarshan th Edition Join Ordering Example For all relations r1, r2, and r3 , (r1 r2 ) r3 = r1 (r2 r3 ) (Join Associativity) If r2 r3 is quite large and r1 r2 is small, we choose (r1 r2 ) r3 so that we compute and store a smaller temporary relation
Join Ordering Example(Cont.) Consider the expression IIname,title(deptname=Music"(instructor)teaches) 凶Πcourse_.id,tite(course)》 Could compute teaches Icourse id,title (course)first,and join result with dept_name=Music"(instructor) but the result of the first join is likely to be a large relation. Only a small fraction of the university's instructors are likely to be from the Music department it is better to compute Odept_name=Music"(instructor teaches first. Database System Concepts-6th Edition 1.20 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 1.20 ©Silberschatz, Korth and Sudarshan th Edition Join Ordering Example (Cont.) Consider the expression name, title(dept_name= “Music” (instructor) teaches) course_id, title (course)))) Could compute teaches course_id, title (course) first, and join result with dept_name= “Music” (instructor) but the result of the first join is likely to be a large relation. Only a small fraction of the university’s instructors are likely to be from the Music department it is better to compute dept_name= “Music” (instructor) teaches first
Enumeration of Equivalent Expressions Query optimizers use equivalence rules to systematically generate expressions equivalent to the given expression Can generate all equivalent expressions as follows: Repeat apply all applicable equivalence rules on every subexpression of every equivalent expression found so far 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 Optimized plan generation based on transformation rules Special case approach for queries with only selections,projections and joins Database System Concepts-6th Edition 1.21 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 6 1.21 ©Silberschatz, Korth and Sudarshan th Edition Enumeration of Equivalent Expressions Query optimizers use equivalence rules to systematically generate expressions equivalent to the given expression Can generate all equivalent expressions as follows: Repeat apply all applicable equivalence rules on every subexpression of every equivalent expression found so far 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 Optimized plan generation based on transformation rules Special case approach for queries with only selections, projections and joins