[数据库系统]第7讲 关系模式的优化知识点整理 |
您所在的位置：网站首页 › 关系模型规范化的目的是什么 › [数据库系统]第7讲 关系模式的优化知识点整理 |
[数据库系统]第7讲 关系模式的优化知识点整理
|
第1节 关系模型的好坏
ER模型转换的关系是否就是最优的关系？不一定。 关系模型潜在的问题： 添加异常修改异常 删除异常数据冗余 冗余 当数据的某些部分能由其他部分推导出来，就意味着存在冗余冗余的存在是因为存在完整性约束 如何解决冗余问题 由于存在约束，特别是函数依赖，导致冗余的产生。如果存在冗余，就需要对关系模式进行优化。 主要优化技术: 模式分解 (比如， ABCD 用 AB和BCD, 或者 ACD 和 ABD替代)。 如何正确地使用模式分解: 是否有必要分解一个模式?分解以后会不会出现什么问题? 如何评价一个关系是好的还是坏的？坏关系到好关系 对关系模式进行优化主要优化技术：模式分解(比如ABCD用AB和BCD，或者ACD和ABD代替) 第2节 函数依赖的概念 函数依赖概念 函数依赖可形式化表示为X->Y, 其中X and Y是属性集例如：rating->hrly_wage, AB->C如果对于关系实例r中的任意一对元组t1和t2，有t1.X = t2.X逻辑蕴含t1.Y = t2.Y，那么函数依赖X->Y在关系r中成立即关系r中给定两个元组，如果X属性值相等则Y的值也必须相等（X和Y是属性集）如果对关系R中的每个实例r，都满足函数依赖，则该函数依赖在关系R上成立。 函数依赖必须由应用的语义所决定。对于给定关系R的某实例r，我们能判断它是否违反了某个函数依赖。但是不能仅仅根据一个满足函数依赖的实例来断定该函数依赖在关系模式R上成立。 函数依赖起到检测冗余是否存在的作用 完全函数依赖在一张表中，若 X → Y X \rightarrow Y X→Y，且对于 X 的任何一个真子集（假如属性组 X 包含超过一个属性的话）， X ′ → Y X' \rightarrow Y X′→Y 不成立，那么我们称 Y 对于 X 完全函数依赖，记作 X → F Y X\mathop{\rightarrow}\limits ^F Y X→FY 例如： 学号 → F \mathop{\rightarrow}\limits ^F →F姓名（学号，课名） → F \mathop{\rightarrow}\limits ^F →F分数 （注：因为同一个的学号对应的分数不确定，同一个课名对应的分数也不确定） 部分函数依赖假如 Y 函数依赖于 X，但同时 Y 并不完全函数依赖于 X，那么我们就称 Y 部分函数依赖于 X，记作 X → P Y X \mathop{\rightarrow}\limits ^P Y X→PY 例如： （学号，课名） → P \mathop{\rightarrow}\limits ^P →P姓名 主属性包含在任意一个码中的属性称为主属性。 非主属性不包含在任何一个码中的属性称为非主属性。 第3节 范式和Armstrong公理 范式如果一个关系满足一种范式（BCNF，3NF等），就能判断该关系模式是否避免了某类问题。这样就能知道该关系是否需要分解。 任何符合BCNF的关系也符合 2NF 第一范式（1NF） 每个属性都是原子属性本质上所有关系都满足第一范式 第二范式（2NF） 任何满足第二范式的关系满足第一范式所有非主属性必须依赖于整个主码而不能依赖于主码的部分属性例如：关系模式 Inventory(part, warehouse, quantity,warehouse_address). 假设 {part, warehouse}是主码. warehsouse_address 单独依赖于 warehouse -则违反了第二范式。 解决方法: 分解关系模式 第三范式(3NF) 任何符合BCNF的关系也符合 3NF符合3NF要求的数据库设计，基本上解决了数据冗余过大，插入异常，修改异常，删除异常的问题。有一些情况 BCNF 不能保持函数依赖,在更新上有效的检查函数依赖是否违背是非常重要的。 解决方法: 定义一个弱的关系, 叫做第三范式 (3NF)允许存在一些冗余 函数依赖是否保持可以在单独的关系上检查，而不需要进行连接计算. 3NF一般是保持无损连接分解和保持函数依赖 R符合BCNF, 那么R符合3NF如果 R 符合 3NF, 可能会存在一定的冗余，它是分解和性能的一种折中将R分解为满足3NF的关系集合，是保持了无损连接分解和保持函数依赖的 3NF分解 显然, 分解为BCNF的无损连接分解的算法能够用来获取无损连接分解的3NF.为了保持函数依赖, 一个思想是: 如果 X → Y 不保持, 增加关系XY.问题是XY可能会违背 3NF! 细化: 不考虑 FDs F, 而是使用F的最小的函数依赖集.对于 R 有函数依赖集 FDs F ，如果R符合BCNF 当且仅当每一个非平凡的 FD X → A in F , X 是R的超键 (i.e., X → R in F+). 对于 FD X → A 是平凡的，当且仅当 A ⊆ X. 也就是说, R 符合BCNF 当且仅当非平凡的FDs 箭头左侧是键. BCNF: R中没有数据能够使用FDs预测. Why: X是超键, 不会有两个元组的X值相同如果R只有两个属性, 那么它符合BCNF 如果F只包括R中的属性: R 符合BCNF 当且仅当每一个F中的函数依赖 X → Y (not F+!), X 是 R的超键, i.e., X → R is in F+ (not F!). BCNF的检测 列出所有的非平凡函数依赖确认每一个函数依赖箭头左边的属性集是R的超键。注意：我们需要首先找出R的超键!例：Courses(course_num, dept_name, course_name, classroom, enrollment, student_name, address) 符合BCNF? FDs 包括: course_num, dept_name → course_name course_num, dept_name → classroom course_num, dept_name → enrollment 那么(course_num, dept_name)+? {course_num, dept_name, course_name, classroom, enrollm ent} Therefore, the key is {course_num, dept_name, student_name}不符合BCNF BCNF范式分解 当一个关系不符合BCNF: 那么分解它.假定关系R 包含属性A1 … An. R的分解会分解为两个或者多个关系: 每个新的关系的属性为R属性的子集 (不会有属性不属于 R), 并且R 中的每一个属性至少会在一个新的关系中. 考虑关系R 和函数依赖集 FDs F. 如果F中的函数依赖 X → A 违背 BCNF, 那么: 分解R 为R – A 和XA.重复这个思想，我们会得到一个符合BCNF的关系集合.保持无损连接分解。 将关系模式R分解为一个BCNF的基本步骤首先对于给定的R(U)和函数依赖集F,可以将它的属性划分为4类: L类,仅出现在F的函数依赖左部的属性。R类,仅出现在F的函数依赖右部的属性。N类,在F的函数依赖左部和右部均未出现的属性。LR类,在F的函数依赖左部和右部两部均出现的属性。根据以下定理和推论来求解候选码。 定理1:对于给定的关系模式R及其函数依赖集F,若X(X∈R)是L类属性,则X必为R的任一候选码的成员。推论1:对于给定的关系模式R及其函数依赖集F,若X(X∈R)是L类属性,且X+包含了R的全部属性,则X必为R的唯一候选码。定理2:对于给定的关系模式R及其函数依赖集F,若X(X∈R)是R类属性,则X不在任何候选码中。定理3:设有关系模式R及其函数依赖集F,如果X是R的N类属性,则X必包含在R的任一候选码中。推论2:对于给定的关系模式R及其函数依赖集F,如果X是R的N类和L类组成的属性集,且X+包含了R的有属性,则X是R的唯一候选码。例： 如设有关系模式R(U),其函数依赖集为F,其中:U={A,B,C,D,E}, F={A→C,C→A,B→AC,D→AC} 求R的候选码。 解: 根据函数依赖可得: 属性B、D为L类,E为N类,因此属性B、D、E必为候选码的成员, 且此三个属性的闭包:B+=ABC,(BD)+=ABCD,(BDE)+=ABCDE,根据推论2可得BDE是R的唯一候选码。 所以R的候选码为BDE。如果把例题中关系模式R(U)中的属性E去掉,那么再求R的候选码的话可以根据推论1得出BD为R的唯一候选码。 快速求解方法适用于判断有属性是属于L类、N类或其中一种的情况下求解。如果有L类和N类的属性,则求解候选码速度非常快。 简而言之： L、R、N、LR类。根据定理，L、N类必为侯选码之一，如果L+包含全部R，则L为唯一侯选。R类不在任何侯选码中。 L+N类且（L+N）+包含所有R，则L+N为唯一侯选。（适于有L、N类至少一种的情况。） 例题： 设有关系模式R(A,B,C,D,E)，其函数依赖集F={A→BC，CD→E，B→D，E→A}，求R的所有候选码。 解： (1)Fm={A→B， A→C，CD→E，B→D，E→A} (2)A，B，C，D，E五个属性在F中各个函数依赖的右边和左边都出现了，所以候选码中可能包含A，B，C，D，E。 (3)A+=ABCDE，即A→U，所以A是一个候选码 B+，C+，D+→U，所以B，C，D不是候选码 E+=ABCDE，即E→U，所以也E是一个候选码 (4)除去A，E两个候选码，在B，C，D中查找两个属性的候选码 (BC)+=ABCDE，即BC→U，所以BC是一个候选码 (BD)+=BD，即BC→U，所以BD不是一个候选码 (CD)+=ABCDE，即CD→U，所以CD是一个候选码 候选码有：A，E，BC，CD BCNF 和 依赖保持 分解得到的关系，符合BCNF，但可能不满足保持函数依赖.例子: 关系CSZ (city, street_name, zip_code) 函数依赖 FDs: CS → Z, Z → C (city, street_name) → zip_code zip_code → city要保持CS → Z，则不能分解, 但是CSZ 不符合BCNF. 函数依赖理论：Armstrong公理从一个给定的函数依赖集推导出它所逻辑蕴含的所有函数依赖 给定R(A,B,C) A->ABC意味着A是一个键（码）通常, X → R 意味着 X 是一个超键.键的约束 ssn → didF = {A → B, B → C, C D → E } Step 1: F中的每一个函数依赖, 使用自反律得到:CD → C; CD → D 加到F上: F = {A → B, B → C, C D → E; CD → C; CD → D } Step 2: F中的每一个函数依赖, 使用增补率 A → B 得到: A → AB; AB → B; AC → BC; AD→ BD; ABC →BC; ABD → BD; ACD →BCDB → C 得到: AB → AC; BC → C; BD → CD; ABC → AC; ABD → ACD, etc. Step 3: 使用传递率重复1~3步骤…可以看出计算F+代价太高. 4.3 求最小依赖集关系模式R(U,F)中，R=ABCDEG F={BE→G,BD→G,CD→A,CE→G,CDE→AB,BC→A,B→D} 首先把右边的属性都变成单个属性 函数依赖集F={BE→G,BD→G,CD→A,CE→G,CDE→A,CDE→B,BC→A,B→D} 对于函数依赖F中的每个函数X->A,设G=F-{X->A},如果A属于关于函数依赖集G的闭包，将X->A从F中删除，否则保留，然后得出新的F。 BE+=BEDG，包含G，删除。 BD+=BD,不包含G，保留。 CD+=CD，不包含A，保留。 CE+=CE，不包含G，保留。 CDE+=CDEAGBA，包含A，删除。 CDE+=CDEAG，不包含B，保留。 BC+=BCDGA,包含A，删除。 B+=B，不包含D，保留。 得到新的F={BD→G,CD→A,CE→G,CDE→B,B→D} 对于F中每一个左端包含多个属性的X->A（即去掉各依赖左部多余的属性。一个一个地检查函数依赖左部非单个属性的依赖），选择X的每个子集Z,如果A属于Z的闭包,则用Z->A代替X->A。 BD→G：B+=BDG，包含G，去掉；D+=D，不包含G，保留。 CD→A：C+=C，不包含A，保留；D+=D，不包含A，保留。 CE→G：C+=C，不包含G，保留；E+=E，不包含G，保留。 CDE→B：C+=C，不包含B，保留；D+=DG，不包含B，保留；E+=E，不包含B，保留。 最后得出关系模式R(U,F)的最小依赖集Fm={D→G,CD→A,CE→G,CDE→B,B→D} 4.3 属性集闭包 (函数依赖集闭包的大小是（属性的）指数级的)很多时候, 我们仅仅是想判断一个 FD X →Y 是否在F的闭包中. 一个有效的方式是: 计算属性X的闭包 (记为X+) : X的闭包 就是由X在F上蕴含的所有属性的集合。计算属性的闭包仅仅需要一个线性的时间算法就够了. F = {A → B, B → C, C D → E } A → E成立吗? 属性集闭包的作用 测试超键 – 判断X是否是一个超键？只需要计算 X+, 检查 X+ 是否包括R的所有属性. 检测函数依赖 判断X → Y 是否成立 (或者说, 是否在F+中), 只需要判断Y ⊆ X+.因此, 我们计算X+, 然后检测这个属性集闭包是否包括 Y.简单有用的方法 计算F的函数依赖集闭包模式分解可能存在三种问题: 一些查询可能会代价变高. e.g., Attishoo 挣了多少钱? (earn = W*H)分解后，根据分解的实例, 我们可能不能重新构建分解前的实例!检查某些依赖需要考虑分解后的多个关系.折中: 考虑这些问题 vs. 冗余. 分解 将分解符合3NF或更高的范式是一种很好的保证方法.所有分解应该是无损的! (Avoids Problem (2)) 无损连接分解 将R 分解为 R1 和R2 ，如果是无损连接分解，那么应该满足：如果不能得到这些 函数依赖的保持使用3NF产生冗余 Example |
【本文地址】
今日新闻 |
推荐新闻 |