《数据库系统概念 Database System Concepts》原书教学资源（第七版，PPT课件讲稿，英文版）Chapter 16 Query Optimization

Equivalence Rules (Cont.) 7.The selection operation distributes over the theta join operation under the following two conditions: (a)When all the attributes in 0o involve only the attributes of one of the expressions(E)being joined. o0(E1凶gE2)三(c9(E》凶gE2 (b)When 0,involves only the attributes of E and 02 involves only the attributes of E2. 91A2(E1凶gE2)三 (o(E1)凶(o2(E2) Database System Concepts-7th Edition 16.12 @Silberschatz,Korth and Sudarshan

Database System Concepts - 7 16.12 ©Silberschatz, Korth and Sudarshan th Edition Equivalence Rules (Cont.) 7. The selection operation distributes over the theta join operation under the following two conditions: (a) When all the attributes in 0 involve only the attributes of one of the expressions (E1 ) being joined. 0 (E1 ⨝ E2 ) ≡ (0 (E1 )) ⨝ E2 (b) When 1 involves only the attributes of E1 and 2 involves only the attributes of E2 . 1  2 (E1 ⨝ E2 ) ≡ (1 (E1 )) ⨝ (2 (E2 ))

Equivalence Rules (Cont.) 8.The projection operation distributes over the theta join operation as follows: (a)if 0 involves only attributes from L1L2: ΠL1UL2(E1凶gE2)=ΠL(E)凶ΠL2(E2) (b)In general,consider a join E1 E2. Let L1 and L2 be sets of attributes from E and E2,respectively. Let L3 be attributes of E that are involved in join condition 0,but are not in L1L2,and let L4 be attributes of E2 that are involved in join condition 0,but are not in L1 L2. ΠL1UL2(E1☒。E2)三ΠIL1UL2(ΠL1UL(E)凶gΠL2UL4(Ez)》 Similar equivalences hold for outerjoin operations:and Database System Concepts-7th Edition 16.13 @Silberschatz,Korth and Sudarshan

Database System Concepts - 7 16.13 ©Silberschatz, Korth and Sudarshan th Edition 8. The projection operation distributes over the theta join operation as follows: (a) if  involves only attributes from L1  L2 :  L1  L2 (E1 ⨝ E2 ) ≡  L1 (E1 ) ⨝  L2 (E2 ) (b) In general, consider a join E1 ⨝ E2 . • Let L1 and L2 be sets of attributes from E1 and E2 , respectively. • Let L3 be attributes of E1 that are involved in join condition , but are not in L1  L2 , and • let L4 be attributes of E2 that are involved in join condition , but are not in L1  L2 .  L1  L2 (E1 ⨝ E2 ) ≡  L1  L2 ( L1  L3 (E1 ) ⨝  L2  L4 (E2 )) Similar equivalences hold for outerjoin operations: ⟕, ⟖, and ⟗ Equivalence Rules (Cont.)

Equivalence Rules (Cont.) 9.The set operations union and intersection are commutative EE2 E20E E1∩E2≡E2∩E1 (set difference is not commutative). 10.Set union and intersection are associative. (E10E2)UE3 E10(E20E3) (E1∩E2)∩E3≡E1∩(E2∩E3) 11.The selection operation distributes over and-. a.Co (EE2) 三O(E)Uo(E2) b.(E1nE2)≡O(E)n(E2 c.o6(E1-E2)= o(E)-o(E2) d.o(E1∩E2) 三 o(E)∩E2 e.o%(E1-E2)≡o(E)-E2 preceding equivalence does not hold for 12.The projection operation distributes over union Π(E1UE2)= (Π(E)U(Π(E2) Database System Concepts-7th Edition 16.14 @Silberschatz,Korth and Sudarshan

Database System Concepts - 7 16.14 ©Silberschatz, Korth and Sudarshan th Edition Equivalence Rules (Cont.) 9. The set operations union and intersection are commutative E1  E2 ≡ E2  E1 E1  E2 ≡ E2  E1 (set difference is not commutative). 10. Set union and intersection are associative. (E1  E2 )  E3 ≡ E1  (E2  E3 ) (E1  E2 )  E3 ≡ E1  (E2  E3 ) 11. The selection operation distributes over ,  and –. a.  (E1  E2 ) ≡  (E1 )   (E2 ) b.  (E1  E2 ) ≡  (E1 )   (E2 ) c.  (E1 – E2 ) ≡  (E1 ) –  (E2 ) d.  (E1  E2 ) ≡  (E1 )  E2 e.  (E1 – E2 ) ≡  (E1 ) – E2 preceding equivalence does not hold for  12. The projection operation distributes over union L (E1  E2 ) ≡ (L (E1 ))  (L (E2 ))

Exercise Create equivalence rules involving The group by/aggregation operation Left outer join operation Database System Concepts-7th Edition 16.15 ©Silberscha乜，Korth and Sudarshan

Database System Concepts - 7 16.15 ©Silberschatz, Korth and Sudarshan th Edition Exercise ▪ Create equivalence rules involving • The group by/aggregation operation • Left outer join operation

Equivalence Rules (Cont.) 13.Selection distributes over aggregation as below o(GYA(E)三GYA(o(E) provided 0 only involves attributes in G 14.a.Full outerjoin is commutative: E1xE2≡E2E1 b.Left and right outerjoin are not commutative,but: E1☒E2≡E2E1 15.Selection distributes over left and right outerjoins as below,provided 0 only involves attributes of E a.1(E1凶gE2)三(c1(E》凶E2 b.91(E1∝E2)三E2凶g(o1(E)》 16.Outerjoins can be replaced by inner joins under some conditions a.o1(E1凶gE2)三o1(E1凶gE2) b.1(E1∝gE)三O1(E1☒gE2) provided 0 is null rejecting on E2 Database System Concepts-7th Edition 16.16 @Silberschatz,Korth and Sudarshan

Database System Concepts - 7 16.16 ©Silberschatz, Korth and Sudarshan th Edition Equivalence Rules (Cont.) 13. Selection distributes over aggregation as below  (G𝛾A (E)) ≡ G𝛾A ( (E)) provided  only involves attributes in G 14. a. Full outerjoin is commutative: E1 ⟗ E2 ≡ E2 ⟗ E1 b. Left and right outerjoin are not commutative, but: E1 ⟕ E2 ≡ E2 ⟖ E1 15. Selection distributes over left and right outerjoins as below, provided 1 only involves attributes of E1 a. 1 (E1 ⟕ E2 ) ≡ (1 (E1 )) ⟕ E2 b. 1 (E1 ⟖ E2 ) ≡ E2 ⟕ (1 (E1 )) 16. Outerjoins can be replaced by inner joins under some conditions a. 1 (E1 ⟕ E2 ) ≡ 1 (E1 ⨝ E2 ) b. 1 (E1 ⟖ E1 ) ≡ 1 (E1 ⨝ E2 ) provided 1 is null rejecting on E2