Equivalence Rules (Cont.) Note that several equivalences that hold for joins do not hold for outerjoins Oyear=2017(instructor teaches)oyear=2017(instructor teaches) Outerjoins are not associative (r凶S)凶t丰r(St) ·e.g.with r(A,B)={(1,1),s(B,C)={(1,1)},t(A,C)={} Database System Concepts-7th Edition 16.17 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 16.17 ©Silberschatz, Korth and Sudarshan th Edition Equivalence Rules (Cont.) Note that several equivalences that hold for joins do not hold for outerjoins ▪ year=2017(instructor ⟕ teaches) ≢ year=2017(instructor ⨝ teaches) ▪ Outerjoins are not associative (r ⟕ s) ⟕ t ≢ r ⟕ (s ⟕ t) • e.g. with r(A,B) = {(1,1), s(B,C) = { (1,1)}, t(A,C) = { }
Transformation Example:Pushing Selections Query:Find the names of all instructors in the Music department,along with the titles of the courses that they teach .IIname.titledept name=Music' (instructor☒(teaches☒Πcourse_iate(course)》) Transformation using rule 7a. ·Πname,te(depLname=Music(instructor)）☒ (teaches☒Πcourse_atie(course)》 Performing the selection as early as possible reduces the size of the relation to be joined. Database System Concepts-7th Edition 16.18 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 16.18 ©Silberschatz, Korth and Sudarshan th Edition Transformation Example: Pushing Selections ▪ Query: Find the names of all instructors in the Music department, along with the titles of the courses that they teach • name, title(dept_name= ‘Music’ (instructor ⨝ (teaches ⨝ course_id, title (course)))) ▪ Transformation using rule 7a. • name, title((dept_name= ‘Music’ (instructor)) ⨝ (teaches ⨝ course_id, title (course))) ▪ Performing the selection as early as possible reduces the size of the relation to be joined
Multiple Transformations (Cont.) Iname,title Iname,title dept_name-Music ∧Jear=2017 Icourse id,title Odept_name =Music 0 year 2017 instructor teaches Icourse id,tile instructor teaches course course (a)Initial expression tree (b)Tree after multiple transformations Database System Concepts-7th Edition 16.20 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 16.20 ©Silberschatz, Korth and Sudarshan th Edition Multiple Transformations (Cont.)
Join Ordering Example For all relations r r2 and ra, (r1☒r2)☒r3=r1☒(2☒r3) (Join Associativity) ■lfr2☒r3 is quite large and r☒r2 is small,we choose (r1☒r2)☒r3 so that we compute and store a smaller temporary relation. Database System Concepts-7th Edition 16.22 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 16.22 ©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 Πname,te(dept name=Music"(instructor)）☒teaches) ☒Πcourse_ate(course)》 ■ Could compute teaches Ioursde(course)first,and join result with deptname=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. Database System Concepts-7th Edition 16.23 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 16.23 ©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