第8章数据库设计理论V22

DATABASE@UESTC学以致用用以促学电子科技大学计算机学院胡旺[e-mail]2019年12月19日星期四《数据库原理及应用》第8章数据库设计理论DATABASE@UESTC学以致用用以促学ClicktoaddTitle1关系模式设计问题1ClicktoaddTitle2函数依赖2ClicktoaddTitle2模式分解3ClicktoaddTitle1规范化4ClicktoaddTitle1*多值依赖5ClicktoaddTitle2*连接依赖6DATABASE@UESTC学以致用用以促学如何构造一个合适的数据库模式？应该构造几个关系模式？每个关系应该由哪些属性组成？思考：教务管理数据库模式？数据库逻辑设计的工具关系数据库的规范化理论DATABASE@UESTC学以致用用以促学关系模式的五元组表示：R(U,D,DOM,F)R：关系名U：组成该关系的属性名集合D：属性组U中属性所来自的域DOM：属性向域的映象集合F：属性间数据的依赖关系集合关系模式的简化三元组表示：R（U,F）数据依赖举例医生姓名、医生职称、医生年龄与医生编号之间的关系？DATABASE@UESTC学以致用用以促学关系模式实例设有一个医生与患者之间的就诊关系模式R（Dname，Dlevel，Dsal，Pname，Fsum），其属性分别表示医生姓名、医生职称级别、医生工资、患者姓名、诊治费用。R上的语义：假设医生和患者的姓名分别都是唯一的。医生与患者之间是多对多的关系，即医生可以为不同的患者看病，同时患者可以选择不同的医生。假设同一名患者不看相同的医生，即可以选择Dname和Pname作为就诊关系模式R的主键。一位患者每次就诊都有一个花销总金额。每位医生具有相应的职称级别。职称级别决定了医生的工资金额。DnameDlevelDsalaryPnameFsum罗晓主任医师3200张珍¥30.00杨勋副主任医师2800张珍¥50.00杨勋副主任医师2800刘景¥55.00杨勋副主任医师2800张柳¥58.00邓英超主治医师2400李秀¥75.00罗晓主任医师3200傅伟相¥35.00DATABASE@UESTC学以致用用以促学可以确定以下函数依赖：F={{Dname,Pname}→Fsum，Dname→Dlevel，Dlevel→Dsal}DnamePnameDlevelDsalFsumDATABASE@UESTC学以致用用以促学就诊模式R存在的问题（虽然只有5个属性）：数据冗余：浪费存储空间，引起异常。操作异常：更新异常（UpdateAnomalies）。删除异常（DeleteAnomalies）。插入异常（InsertAnomalies）。因此，就诊关系模式R不是一个好的关系模式。DnameDlevelDsalaryPnameFsum罗晓主任医师3200张珍¥30.00杨勋副主任医师2800张珍¥50.00杨勋副主任医师2800刘景¥55.00杨勋副主任医师2800张柳¥58.00邓英超主治医师2400李秀¥75.00罗晓主任医师3200傅伟相¥35.00DATABASE@UESTC学以致用用以促学消除冗余和异常现象（模式分解）R1（Dname，Dlevel）R2（Dlevel，Dsal）R3（Dname，Pname，Fsum）DnameDlevelDsalaryPnameFsum罗晓主任医师3200张珍¥30.00杨勋副主任医师2800张珍¥50.00杨勋副主任医师2800刘景¥55.00杨勋副主任医师2800张柳¥58.00邓英超主治医师2400李秀¥75.00罗晓主任医师3200傅伟相¥35.00DATABASE@UESTC学以致用用以促学ClicktoaddTitle1关系模式设计问题1ClicktoaddTitle2函数依赖2ClicktoaddTitle2模式分解3ClicktoaddTitle1规范化4ClicktoaddTitle1*多值依赖5ClicktoaddTitle2*连接依赖6DATABASE@UESTC学以致用用以促学什么是数据依赖？是现实世界属性间相互联系的抽象是数据内在的性质是语义的体现数据依赖的类型函数依赖（FunctionalDependency，简记为FD）多值依赖（MultivaluedDependency，简记为MVD）DATABASE@UESTC学以致用用以促学函数依赖是指一个关系表中属性（列）之间的联系。函数依赖是关系中属性之间在语义上的关联特性。函数依赖关注一个属性或属性集与另外一个属性或属性集之间的依赖，亦即两个属性或属性集之间的约束。数据库设计者根据对关系R中的属性的语义理解确定函数依赖，确定约束R的所有元组r的函数依赖集，并获知属性间的语义关联。DATABASE@UESTC学以致用用以促学符号说明：R表示一个关系的模式；U＝{A1，A2，…，An}是R的所有属性的集合；F是R中函数依赖的集合；r是R所取的值；t[X]表示元组t在属性X上的取值。例如t[Dname]=‘杨勋’函数依赖定义函数依赖图左部称为决定因子右部称为依赖因子。XYY函数依赖于X函数依赖图DATABASE@UESTC学以致用用以促学定义平凡函数依赖必然成立，它不反映新的语义。例如：{Dname,Pname}→{Pname}。平常所指的函数依赖一般都指非平凡函数依赖。DATABASE@UESTC学以致用用以促学定义完全函数依赖用来表明函数依赖的决定因子中的最小属性集。属性集Y完全函数依赖于属性集X，如果满足下列条件：Y函数依赖于X。Y不函数依赖于X的任何真子集。DATABASE@UESTC学以致用用以促学举例DnamePnameDlevelDsalFsumDATABASE@UESTC学以致用用以促学定义直接依赖DATABASE@UESTC学以致用用以促学举例：在就诊关系R中，存在函数依赖Dname→Dlevel，Dlevel→Dsal，所以Dname→Dsal。DnamePnameDlevelDsalFsumDATABASE@UESTC学以致用用以促学函数依赖中需要解决的问题：从一些已知的函数依赖去判断另外一些函数依赖是否成立。例如，如果A→B和B→C在某个关系中成立，记F={A→B，B→C}，那么A→C在该关系中是否成立的问题称为逻辑蕴涵问题，若A→C成立，则说F逻辑蕴涵A→C，记作F╞A→C。定义DATABASE@UESTC学以致用用以促学一个关系模式可能有多个函数依赖形成函数依赖集，现在有一个新的函数依赖不在函数依赖集里，但能从集合里根据一定的规则推导出来，就说那个集合逻辑蕴涵这个新的函数依赖。举例如果一个函数依赖能够由集合中的其他函数推出，则该函数依赖是多余的。DATABASE@UESTC学以致用用以促学闭包(*)函数依赖集的闭包（也成为完备集）定义了由给定函数依赖集所能推导出的所有函数依赖。通过F得到F＋的算法可以由Armstrong公理推导出来。DATABASE@UESTC学以致用用以促学无冗余的函数依赖集和函数依赖的完备集（闭包）是好的关系设计。根据已知函数依赖集，推导其它函数依赖时所依据的规则称为推理规则。函数依赖的推理规则最早出现在Armstrong的论文里。这些规则常被称为“Armstrong公理”。DATABASE@UESTC学以致用用以促学设U是关系模式R的属性集，F是R上成立的只涉及U中属性的函数依赖集。FD推理规则（1）自反性（Reflexivity）（2）增广性（Augmentation）（3）传递性（Transitivity）DATABASE@UESTC学以致用用以促学(*)DATABASE@UESTC学以致用用以促学Armstrong公理是正确的（Sound），即如果X→Y是从F用推理规则导出，那么X→Y在F＋中。Armstrong公理（FD推理规则{A1，A2，A3}）是完备的（Complete）。推理规则的正确性是指“从FD集F使用推理规则推出的FD必定在F+中”，而推理规则的完备性是指“F+中的FD都能从F集使用推理规则推出”。即正确性保证了推出的所有FD都是正确的，完备性保证了可以推出所有被蕴涵的FD。这些就保证了推导的有效性和可靠性。DATABASE@UESTC学以致用用以促学候选码与主码：用函数依赖定义包含在任何候选码中的属性称为主属性（PrimeAttribute）。不包含在任何候选码中的属性称为非主属性（Non-KeyAttribute）。最简单的情况，单个属性是码。最极端的情况，整个属性组是码，称为全码（All-key）。DATABASE@UESTC学以致用用以促学候选码与主码的举例在关系模式R1（Dno，Dlevel，Dsal）中Dno是码在关系模式R2（Dno，Pno，Fsum）中的属性组合（Dno，Pno）是码。关系模式R3（Dno，Pno，Mno）表示医生给患者开具的药品，假设一个医生可以给多个患者看病，一位患者可以选择不同的医生就诊，不同的医生可以给患者开具不同的药品，因此（Dno，Pno，Mno）为R3的码，即全码。DATABASE@UESTC学以致用用以促学外码：用函数依赖定义举例：在关系模式R2（Dno，Pno，Fsum）中，Dno不是码，但Dno是关系模式R1（Dno，Dlevel，Dsal）的码，则Dno是关系模式R2的外码。主码与外码提供了一个表示关系之间联系的手段。如上述关系模式R1和R2的联系就是通过Dno来体现的。DATABASE@UESTC学以致用用以促学DATABASE@UESTC学以致用用以促学判断能否从已知的FD集推导出FDX→Y，那么可先求出F的闭包F+，然后再看X→Y是否在中F+。但是从F求F+是一个NP完全问题（指数级的时间复杂度）。下面引入属性集闭包概念，将使该问题化为多项式级的时间复杂度问题。属性集闭包的定义定理DATABASE@UESTC学以致用用以促学从属性集X求X＋并不太难，花费的时间与F中的FD数目成正比，是一个多项式级时间复杂度的问题。求属性集闭包的算法举例DATABASE@UESTC学以致用用以促学函数依赖集等价：F=G设F是属性集U上的函数依赖集，如果Fmin是F的一个最小依赖集，那么Fmin应满足下列4个条件：DATABASE@UESTC学以致用用以促学求最小函数依赖集的算法举例每个FD至少存在一个Fmin，但不一定唯一。DATABASE@UESTC学以致用用以促学ClicktoaddTitle1关系模式设计问题1ClicktoaddTitle2函数依赖2ClicktoaddTitle2模式分解3ClicktoaddTitle1规范化4ClicktoaddTitle1*多值依赖5ClicktoaddTitle2*连接依赖6DATABASE@UESTC学以致用用以促学由函数依赖可以引起的更新异常问题，同样，多值依赖和连接依赖也会引起类似的问题。解决这些问题的途径就是按照“一事一地”的原则，对关系模式进行分解，使之表达的语义概念单纯化。关系模式R的分解就是用两个或两个以上关系来替换R，分解后的关系模式的属性集都是R中属性的子集，其并集与R的属性集相同。模式分解帮助消除不良设计中的一些问题，如冗余、不一致或异常。DATABASE@UESTC学以致用用以促学模式分解的定义模式分解的问题DATABASE@UESTC学以致用用以促学一个关系表被分解成两个或两个以上的小表，通过连接被分解后的小表可以获得原始表的内容，则称为无损连接分解。例如：将R（X，Y，Z）分解成R1（X，Y）和R2（X，Z），如果X是R1和R2的共同属性或属性集，且存在函数依赖集F={X→Y，X→Z}，则该分解是无损的。DATABASE@UESTC学以致用用以促学无损中的损是指信息丢失。如果一个