查询优化与并发控制.ppt

查询优化与并发控制 本章要点 1．在学会用SQL语言对数据库进行查询的基础上，了解数据库系统是如何对查询进行优化的。 2．深入理解查询优化策略；掌握用关系代数等价变换规则对关系代数查询表达式进行优化的方法；学会按查询优化的步骤对查询进行优化。 3．了解并发操作可能带来的数据不一致现象，深入理解保证数据一致性的三级封锁协议和保证并行调度可串行性的两段锁协议。 在系统开销尽量小的情况下对查询尽可能优化，采用以下策略： 1．选择运算尽早进行。 2．投影运算与选择运算同时进行 3．将笛卡尔积与随后的选择运算合并为连接运算。 4．投影运算与其他运算同时进行 5．找公共子表达式将结果存储。 6．对文件进行预处理。 关系代数的等价变换 关系代数表达式的优化是查询优化的重要基础。 所谓关系代数表达式的优化，就是要按照一定的等价变换规则将其转换为查询效率更高的表达式。 等价 用相同的关系代替两个关系代数表达式中相应的关系，如果所得到的结果关系完全一样，则称两个关系代数表达式E1和E2等价，记作： E1≡E2。 变换规则 常用的关系代数等价变换规则如下： 1．连接或笛卡尔积的交换律 设E1和E2是关系代数表达式，F是连接的条件，则有： E1╳E2 ≡ E2╳E1 E1 E2 ≡ E2 E1 E1 F E2 ≡ E2 F E1 2．连接或笛卡尔积的结合律 设E1、E2和E3是关系代数表达式，F1和F2是连接的条件，其中F1只涉及到E1和E2的属性，F2只涉及到E2和E3的属性，则有： (E1╳E2)╳E3 ≡ E1╳(E2╳E3) (E1 E2) E3 ≡ E1 (E2 E3) (E1 F1 E2) F2 E3 ≡ E1 F1 (E2 F2 E3) 3．投影的串接律 设E为关系代数表达式，A、B为属性集，且A是B的子集，则有： πA(πB(E)) ≡πA(E) 4．选择的交换/串接律 F1和F2为选择条件，则有： 4a.选择的交换律 σF1（σF2（E））≡σF2（σF1（E）） 4b.选择的串接律 σF1（σF2（E））≡σF1∧F2（E） 5．选择与投影的交换/串接律 5a.选择与投影的交换律 设选择条件F只涉及属性A1, A2, … , An，则有： πA1,A2,…,An（σF（E）） ≡σF（πA1,A2,…,An（E）） 5b.选择与投影的串接律 设选择条件F中有不属于A1,…,An的属性B1,…,Bm，则有： πA1, … , An（σF（E））≡πA1, … , An （σF（πA1,…,An, B1,…,Bm（E））） 6．选择对笛卡尔积的分配律 如果选择条件F只涉及E1中的属性： σF（E1╳E2）≡σF（E1）╳E2 如果选择条件F= F1∧F2，且F1只涉及E1的属性，F2只涉及E2的属性： σF（E1╳E2） ≡σF1（E1）╳ σF2（E2） 7．投影对笛卡尔积的分配律 设E1和E2是关系代数表达式， Ai（i=1,2,…,n）是E1的属性， Bj（j=1,2,…,m）是E2的属性,则有： πA1,…, An, B1,…,Bm(E1╳E2)≡ πA1,…,An(E1)╳π B1,…, Bm(E2) 8．选择对并的分配律 设E1和E2具有相同的属性集，则有： σF（E1∪E2） ≡ σ F（E1）∪ σ F（E2） 9．投影对并的分配律 设E1和E2有相同的属性集，则有： πA1, … ,An(E1∪E2) ≡πA1,…,An(E1)∪πA1,…,An(E2) 10．选择对差的分配律 设E1和E2有相同的属性集，则有： σF（E1﹣E2）≡σF（E1）﹣σF（E2） 设图书管理数据库关系模式如下： Book（Title,Author,Publisher, BN）； Student（Name, Class, LN）； Loan（LN, BN, Date）； X = πR（σF（B╳S╳L）） F 代表 S.LN=L.LN AND B.BN=L.BN， 形式上为选择条件，实际上是等值连接条件； R代表T、A、P、BN、N、C、LN和D，即三个关系的属性集。 于是，我们的查询要求可用如下表达式来描述： πT, N（σX）） 这一原始表达式可画成原始语法树，如下所示. 1.按照规则4b——选择的串接律，把相与的两个选择条件分解为两个独立的选择条件。 σS.LN=L.LN ANDB.BN=L.BN → a)σS.LN=L.LN b)σB.BN=L.