《03 关系数据理论》由会员分享，可在线阅读，更多相关《03 关系数据理论（110页珍藏版）》请在金锄头文库上搜索。
1、1 1第3章 关系数据理论3.1 基本概念3.2 函数依赖的推理规则3.3 规范化3.4 模式分解2 23.1 基本概念函数依赖术语和符号为什么要讨论函数依赖？模式分解3 3函数依赖Y=f(X) 函数Y=sin(X)Y=X+1Y=X2+2X+1省=f(城市)姓名=f(学号)4 4函数依赖的直观定义：如果有一个关系模式R(A1,A2,An)，X和Y为A1,A2,An的子集，那么对于关系R中的任意一个X值，都只有一个Y值与之对应，则称X函数决定Y，或Y函数依赖于X，并用XY表示。5 5例：对仓库关系仓库(仓库号,城市,面积)有函数依赖：仓库号城市（城市函数依赖于仓库号）仓库号面积（面积函数依赖于仓
2、库号）6 6函数依赖的严格形式化定义定义3.1：设有关系模式R(A1,A2,An)，X和Y均为A1,A2,An的子集，r是R的任一具体关系，t1、t2是r中的任意两个元组；如果由t1X=t2X可以推导出t1Y=t2Y，则称X函数决定Y，或Y函数依赖于X，记为XY。定义3.1中特别要注意：只要 t1X=t2X t1Y=t2Y就可以推导出: XY也就是说：只有当 t1X=t2X 为真，而t1Y=t2Y为假时，函数依赖不成 立；而当t1X=t2X为假时，不管t1Y=t2Y为真或为假都有XY成立。当t1X=t2X 为真， t1Y=t2Y为真；当t1X=t2X 为真， t1Y=t2Y为假；当t1X=t2
3、X 为假， t1Y=t2Y为真；当t1X=t2X 为假， t1Y=t2Y为假；8 8注意：注意： 1 1、函数依赖不是指关系模式、函数依赖不是指关系模式R R的某个或某些关系实的某个或某些关系实 例满足的约束条件，而是指例满足的约束条件，而是指R R的所有关系实例均的所有关系实例均 要满足的约束条件。要满足的约束条件。2 2、函数依赖和别的数据之间的依赖关系一样，是语、函数依赖和别的数据之间的依赖关系一样，是语 义范畴的概念，我们只能根据数据的语义来确定义范畴的概念，我们只能根据数据的语义来确定 函数依赖。函数依赖。 例如：例如：“ “姓名姓名年龄年龄” ”这个函数依赖只有在没有同名人这个函数
4、依赖只有在没有同名人 的条件下成立，如果有相同名字的人，则的条件下成立，如果有相同名字的人，则“ “年龄年龄” ” 就不再函数依赖于就不再函数依赖于“ “姓名姓名” ”了。了。9 9定义定义3.1 3.1 也可以这样来理解：也可以这样来理解：即对于即对于R(U)R(U)的任意一个可能的关系实例的任意一个可能的关系实例r, r, r r中不可能存在两个元组在中不可能存在两个元组在X X上的属性值相等，上的属性值相等， 而在而在Y Y上的属性值不等，则称上的属性值不等，则称XYXY。1010术语和符号(1)如果XY，但Y不包含于X，则称XY是非平凡的函数依赖。如不特别说明，我们 总是讨论非平凡函数
5、依赖。如：(学号,课程号)成绩如：(学号,所在系)所在系非平凡依赖平凡依赖1111术语和符号(2)如果Y不函数依赖于X，则记作X Y。如学号不函数依赖于性别，则记作性别 学号。1212术语和符号(3)如果XY，则X称作决定因素。如学号所在系，则学号称作决定因素1313用U表示关系模式R的属性全集 ，即U=A1,A2,An，用F表示关系 模式R上的函数依赖集，则关系模式 R可表示为R(U,F)。术语和符号(4)如U=仓库号,城市,面积F=仓库号城市,仓库号面积 则R(U,F)表示仓库关系1414术语和符号(5)如果K是关系模式R(U,F)的任一候选关键字，X是任一属性或属性集，如果XK，则X称为
6、主属性；否则称为非主属性。如(仓库号,器件号)是库存关系的关键字，那么仓库号和器件号均是主属性，而 数量为非主属性。1515术语和符号(6)如果XY，并且YX，则可记作XY。1616术语和符号(7)如果XY，并且对于X的一个任意真子集X/ 都有X/ Y，则称Y完全函数依赖于X，并记 作 ；如果X/ Y成立，则称Y部分函数 依赖于X，并记作 。如：(学号,课程号)成绩是完全函数依赖而：(学号,所在系)系主任是部分函数依赖1717术语和符号(8)如果XY（非平凡函数依赖，并 且Y X）、YZ，则称Z传递函数 依赖于X。如学号专业，专业所在系，则所在系传递函数依赖于学号。18181919设有库存关系
7、：数据冗余问题数据更新问题数据插入问题数据删除问题2020为什么会出现以上种种操作异常现象呢？因为这个关系模式没有设计好，在它的某因为这个关系模式没有设计好，在它的某些属性之间存在着些属性之间存在着“ “不良不良” ”的函数依赖。如何改造的函数依赖。如何改造这个关系模式？克服以上种种问题，就是我们这个关系模式？克服以上种种问题，就是我们这一章要解决的根本问题，也是我们要讨论函这一章要解决的根本问题，也是我们要讨论函数依赖的根本原因。数依赖的根本原因。2121模式分解解决各种操作异常现象的方法就是进行解决各种操作异常现象的方法就是进行模式分解，即把一个关系模式分解成两个模式分解，即把一个关系模式
8、分解成两个或多个关系模式，在分解的过程中消除那或多个关系模式，在分解的过程中消除那些些“ “不良不良” ”的函数依赖，从而获得好的关系模的函数依赖，从而获得好的关系模式。式。2222分解举例仓库（仓库号，地点） 仓库（仓库号，地点）设备（设备号，设备名） 设备（设备号，设备名）库存（仓库号，设备号，库存数量） 库存（仓库号，设备号，库存数量）刚才提到的刚才提到的库存库存关系模式，我们可以把其分解为：关系模式，我们可以把其分解为：2323注意：模式分解不能破坏原来的语义；模式分解不能破坏原来的语义；模式分解必须遵守：模式分解必须遵守：l l无损连接分解；无损连接分解；l l保持函数依赖分解。保持
9、函数依赖分解。无损连接是指无损连接是指 分解后的关系经过自分解后的关系经过自 然连接可以恢复成原然连接可以恢复成原 来的关系。来的关系。保持函数依赖是指保持函数依赖是指 分解后的关系不能破坏分解后的关系不能破坏 原来的函数依赖（不能原来的函数依赖（不能 破坏原来的语义）。破坏原来的语义）。2424函数依赖的推理规则Amstrong公理的内容及正确性Amstrong公理的推论及正确性逻辑蕴涵和闭包公理的完备性闭包的计算函数依赖集的等价和最小化2525Amstrong公理：设有关系模式设有关系模式R(U,F)R(U,F)，X X、Y Y、Z Z均为均为U U的的子集，推理规则如下：子集，推理规则如
10、下：自反律自反律：如果如果Y Y X X，则则XYXY；增广律增广律：如果如果XYXY，则则XZYZXZYZ；传递律传递律：如果如果XYXY、YZYZ，则则XZ XZ 。2626定理：AmstrongAmstrong公理是公理是正确正确的的。2727证明自反律：设YX U对关系模式R的任一关系 r 中的任意两个元组t和s，如果tX=sX，由于Y X，所以tY=sY，由定义3.1有XY成立，自反律得证。2828证明增广律： 设XY，且ZU，r、t、s的含义同上如果tXZ=sXZ，则一定有tX=sX和tZ=sZ又根据XY可有tY=sY由tY=sY和tZ=sZ可得tYZ=sYZ即由tXZ=sXZ推导
11、出了tYZ=sYZ由定义3.1有XZYZ成立，增广律得证。2929证明传递律：设XY、YZ，r、t、s的含义同上如果tX=sX，由于XY，根据定义3.1可得tY=sY同理由于YZ，可得tZ=sZ即由tX=sX推导出了tZ=sZ根据定义3.1 XZ成立，传递律得证。3030Amstrong公理的推论：推论推论- -合并规则合并规则：如果：如果XYXY、XZXZ，则则XYZXYZ；推论推论- -分解规则分解规则：如果：如果XYZXYZ，则则XYXY、XZXZ；推论推论- -伪传递规则伪传递规则：如果：如果XYXY、YWZYWZ，则则XWZXWZ。3131定理：AmstrongAmstrong公理的
12、三公理的三个推论是正确的。个推论是正确的。3232证明合并规则：设XY、XZ根据增广律分别有XXY、XYYZ又根据传递律有XYZ，合并规则得证。3333证明分解规则：设XYZ根据自反律有YZY和YZZ又根据传递律分别有XY和XZ，分解规则得证。3434证明伪传递规则：设XY、YWZ根据增广律有XWYW又根据传递律有XWZ，伪传递规则得证。3535引理3.1引理3.1：XAXA1 1A A2 2AAn n的的充分必要条件充分必要条件是是XAXAk k成立成立( (k=1,2,n)k=1,2,n)。根据合并规则和分解规则可以得出根据合并规则和分解规则可以得出 如下重要结论：如下重要结论：3636逻
13、辑蕴涵和闭包有时需要根据给定的一组函数依赖来判断另外一些函数依赖是否成立，这就是函数依赖逻辑蕴涵所要研究的内容。 比如有关系模式R(U,F)，U=A,B,C，F=AB,B C，问A C是否也成立？3737逻辑蕴涵定义3.2：设有关系模式设有关系模式R(U,F)R(U,F)，X X U U、Y Y U U，如果从如果从F F中的函数依赖能够推导出中的函数依赖能够推导出X XY Y，则称则称F F逻辑蕴涵逻辑蕴涵X XY Y，或称或称X XY Y是是F F的的逻辑蕴涵。逻辑蕴涵。3838闭包定义定义3 3.3.3 在关系模式在关系模式R R( (U U, ,F F) )中，被中，被F F 所逻所逻
14、辑蕴涵的函数依赖的全体称作辑蕴涵的函数依赖的全体称作F F 的闭包，的闭包，记为记为F F + 。 闭包闭包F F+ +的计算是一个的计算是一个NPNP完全问题，即理论上可计算而实完全问题，即理论上可计算而实 际上不可计算的问题。比如从际上不可计算的问题。比如从F= XAF= XA1 1A A2 2A An n 出发，就至出发，就至少能够推导出少能够推导出2 2n n个不同的函数依赖，所以计算个不同的函数依赖，所以计算 F F+ +是非常麻烦是非常麻烦 的事情，即使的事情，即使F F不太大，不太大，F F+ +也可能很大。也可能很大。3939闭包计算举例假设有关系模式假设有关系模式R(U,F)
15、R(U,F)，U=X,Y,ZU=X,Y,Z ，F=XF=XY,YY,YZZ，则则F F+ +为：为：4040属性集闭包4141计算属性集闭包举例如果X=A，则： A,B,C如果X=B，则 B,C如果X=C，则 C设有关系模式R(U,F)，U=A,B,C，F=AB,BC4242公理的完备性建立一套公理系统必须明确两个问题：建立一套公理系统必须明确两个问题： 一是能否保证按公理推导出的函数依赖都是正确的一是能否保证按公理推导出的函数依赖都是正确的，即，即 这些函数依赖是否都属于这些函数依赖是否都属于F F+ +；也就是说对于关系模式也就是说对于关系模式 R(U,F)R(U,F)，只要只要F F中的函数依赖为真，则用公理根据中的函数依赖为真，则
