数据库原理与应用教程NO16.ppt

《数据库原理与应用教程NO16.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、4.3关系模式的分解*4.3.1模式分解问题定义4.11设有关系模式R(U)，属性集为U，R1、…、Rk都是U的子集，并且有R1∪R2∪…∪Rk＝U。关系模式R1、…、Rk的集合用ρ表示，ρ=｛R1，…，Rk｝。用ρ代替R的过程称为关系模式的分解。这里ρ称为R的一个分解，也称为数据库模式。泛关系模式Rr泛关系数据库模式ρ={R1，…，Rk}σ=＜r1，…，rk＞数据库实例(数据库)这里就有两个问题：①σ和r是否等价?用“无损分解”表示。②{F1,…,Fk}与F是否等价?用“保持依赖”表示。计算机中的数据并不是存储在泛关系r中，而是存储在数据库ρ中。R上有函数依赖集F，每一个

2、Ri上有一个函数依赖集Fi，{F1，…，Fk}4.3.2无损连接分解定义4.12：设R是一个关系模式，F是R上的一个FD集。R分解成数据库模式ρ=｛R1，…，Rk｝。如果对R中满足F的每一个关系r，都有r=πR1（r）⋈πR2（r）⋈…⋈πRk（r）那么称分解ρ相对于F是“无损连接分解”（losslessjoindecomposition），简称为“无损分解”，否则称为“损失分解”（lossydecomposition）。例4.10（1）未丢失信息的分解：r1⋈r2=r（2）丢失信息的分解：r1⋈r2≠r211211111111CAr2BAr1CBAr32142131131

3、213214114111411CBAr1⋈r2CAr2BAr1CBAr多出来的元组称为寄生元组（额外元组）丢失的元组称为悬挂元组。在泛关系模式R分解成数据库模式ρ={R1，…，Rk}时，泛关系r在ρ的每一模式Ri（1≤i≤n）上投影后再连接起来，比原来r中多出来的元组，称为“寄生元组”（SpuriousTuple）。实际上，寄生元组表示着错误的信息。寄生元组也就是4.1.3节模式设计准则4中提到的额外元组(在上节NO15中）。无损的‘损’指的是信息丢失而不是元组丢失.如果一个分解不具有‘无损’的性质，那么泛关系在投影连接后就可能产生寄生元组。寄生元组表示着错误的信息r的投影

4、连接表达式πR1（r）⋈…⋈πRk（r）用符号mρ（r）表示，即mρ（r）=⋈πRi（r）。设ρ=｛R1，…，Rk｝是关系模式R的一个分解，r是R的任一关系，ri=πRi（r）（1≤i≤k），那么有下列性质：①rmρ(r)；②若s=mρ(r)，则πRi(s)=ri；③mρ(mρ(r))=mρ(r)，这个性质称为幂等性（idempotent）。r=mρ(r)时就是无损连接分解4.3.3无损分解的测试算法（算法4.3）①构造一张k行n列的表格，每列对应一个属性Aj，每行对应一个模式Ri。如果Aj在Ri中，那么在表格的第i行第j列处填上符号aj，否则填上bij。②把表格看成模式

5、R的一个关系，反复检查F中每个FD在表格中是否成立，若不成立，则修改表格中的值。修改方法如下：对函数依赖X→Y,找X相等的行，改Y的分量值：如果Y值中有一个是aj，那么另一个也改成aj；如果没有aj，那么用其中一个bij替换另一个值（尽量把下标ij改成较小的数）。一直到表格不能修改为止。（这个过程称为‘追踪chase’过程）③若修改的最后一张表格中有一行是全a，即a1a2…an，那么称ρ相对于F是无损分解，否则称损失分解。例4.11设关系模式R(ABCD)，R分解成ρ={AB,BC,CD}。如果R上成立的函数依赖集F1={B→A，C→D}，那么ρ相对于F1是否无损分解？(无

6、损分解)a4a3b32b31CDa4a3b32b31CDa4a3a2a1BCb24a3a2b21BCb14b13a2a1ABb14b13a2a1ABDCBADCBA续例4.11设关系模式R(ABCD)，R分解成ρ={AB,BC,CD}。如果R上成立的函数依赖集F1={A→B，C→D}，那么ρ相对于F1是否无损分解？(损失分解)a4a3b32b31CDa4a3b32b31CDa4a3a2b21BCb24a3a2b21BCb14b13a2a1ABb14b13a2a1ABDCBADCBA再看例4-12（P153)ABCDE例：设R=(ABCDE)分解成ρ{AD,AB,BE,CDE

7、,AE}函数依赖F={A→C，B→C，C→D，DE→C，CE→A}判断是否无损连接分解。解：按条件给出初始表a1b12b13a4b15ADa1a2b23b24b25b31a2b33b34a5b41b42a3a4a5a1b52b53b54a5ABBECDEAEABCDEa1b12b13a4b15ADa1a2b13a4b25a1a2a3a4a5a1b42a3a4a5a1b52a3a4a5ABBECDEAE通过追踪过程（CHASE）最终得表：由于第3行全为a,所以该分解是无损连接分解。定理4.6设ρ=｛R1，R2｝是关系