BC范式判定定理及关系的规范化研究

背景关系模型是目前应用得最为广泛的数据库模型，关系模型的规范化理论是关系型数据库逻辑设计的基础，信息系统开发人员对关系规范化的运用能力将直接影响所设计数据库系统的质量， 并进而影响整个系统的性能。范式的概念最早是由IBM公司的研究员E.F.Codd提出的，他于1971至1972年间发表的一系列论文中系统地提出了1NF,2NF和3NF的标准，并深入探讨了关系进一步规范化的问题，由此奠定了关系规范化理论的基础。1974年，E.F.Codd和Boyce又共同提出了BCNF1976年，Fagin又提出了4NF,以后又有人提出了5NE虽然关系规范化的理论研究发展至今已经相当完备，但仍有进一步完善和充实的必要。在函数依赖的范畴内， BC范式已达到完美的程度（已完全消除了有害的函数依赖关系），本文试图在函数依赖的范畴内对关系规范化的理论和运用作进一步的探讨。—一基本概念基本概念：定义1（BCNF）给定R和F,对F中的每个函数依赖X>A,X不包含A,若X为R的超键（码），则称R关于F是BCNF的。定义1说明，如果一个关系模式R是BCNF,则在R上关于函数依赖集F的闭包中，每一个函数依赖a>B要么是平凡的，要么其决定因素a是R的一个超码。3NF（第三范式）已经排除了非主属性对候选码的传递函数依赖，但仍然可能存在主属性之间的部分或传递函数依赖，进而造成数据冗余度大、插入异常、删除异常、更新异常等问题。BCNF要求对于R中的每个函数依赖XtY,如果Y不是X的真子集，则X中必含有候选码，也就是说，每一个非平凡的函数依赖，其决定因素必须包含候选码，这样正是对 3NF的不足之处加以补充，所以BCNF是增强的3NF。定义2设R是1NF,若R中的每个属性都不传递函数依赖于R的任一候选码，则称R是BC范式。定义1与定义2的意义是等价的。一方面，假设关系模式R中存在传递依赖于候选码X的一组函数依赖XtyYta因为传递函数依赖的前提是YtX不成立，所以Y中不应包含候选码，这使得R不能满足定义1中的要求，R不能成为BCNF另一方面，假设关系模式R中存在一个非平凡的函数依赖XtY,其决定因素X中不包含候选码，那么对于R的任一候选码K，有Ktx,而XtY,也就是说Y传递依赖于候选码K,这使得R不能满足定义2的要求，R

不能成为BCNF定义3（最小覆盖）设F和G是两个函数依赖集，若GkF,则称G为F的一个覆盖.特别地，当GFa。且不存在G的真子集口作为F的覆盖，则称G为F的一个最小覆盖，记为Fmin。由定义显然有Fmin FU,且F且Fmin=F+a=F+，事实上，Fa=UFm^。二基本性质每个BCNF关系模式都应具有如下三个性质：（1） 所有非主属性都完全函数依赖于每个候选码；（2） 所有主属性都完全函数依赖于每个不包含它的候选码；（3） 没有任何属性完全函数依赖于非主的任何一组属性。由于R€BCNF按定义排除了任何属性对码的传递依赖与部分依赖所以R€3NF.但是若R€3NF,则R未必属于BCNF三定理:定理1设Fax为Fa中仅由X中的属性组成的函数依赖的全体，Fx为F在X上的投影，即Fx=IIx（F）,则Fax与Fx等价。证Fax二Fx显然成立.下面证明Fax二Fx,-Y》Z，Fx,不失一般性，设Z为单个属性.根据Fa的定义，有原子函数依赖Y' >Z Fa（Y' Y）.因为YZ X,所以Y' Z X,从而Y'>乙Fax。根据Armstrong公司的增广律，有YY>Z・Fax+（注意YX）,即Y》Z・Fax+（因为Y' Y），从而Fax+=Fx。证毕。定理2（守恒定理）设X、Y和Z为R上的属性集.对-X,Y.F+,若X不包含Y,贝SZ>AFm.，ZX;反之，对Z>AFmin,在F中（不是百中）必有X》Y,X不包含Y且ZX。定理3将Fmin分成包含A和不包含A的两部分，即Fmin—{*,Xi>A,AYj>Bj},其中*表示不合A的函数依赖，Xi>A表示右边为A的函数依赖，AYi>B,表示左边含有A的函数依赖，Xi和Yj为属性集（Yj可以为空），Bj为单个属性.则FR-a={*,XiYj>Bj,}等价于F在R-A上的投影IIr-a（F）。四判定定理判定规则1任何一个二目关系R一定是BCNF证明假设关系模式R（A,B）是二目关系，A、B为关系模式R的两个属性，R的候选码存在两种可能：全码，即属性组（AE）构成一个候选码；单属性码，即单属性A或B构成R的候选码。解释如下：（1）全码属性组（AB构成一个候选码，则R中不存在两个元组，在A和B属性值上均相等，此时关于R的每一个函数依赖都包含候选码，因此R是BCNF单属性码A和B之间存在着函数依赖关系，A-B(或：B-A),R中不存在两个元组，在A的属性值上相等而在B的属性值上不等(或：在B的属性值上相等而在A的属性值上不等)。因为R是一个二目关系，所以R中不存在传递函数依赖于候选码的属性，因此R是BCNF例1:关系模式DS(Department,Speciality)记录学院专业设置情况，Department表示系别，Speciality表示专业名称，在专业设置上不同系别设置的专业名称应该不完全相同，所以Speciality可以作为关系模式DS的一个候选码，DS满足BCNF的要求。判定规则2只有一个候选码的3NF关系模式一定是BCNF证明假设关系模式R(U,F)是一个3NF的关系模式，U为R的属性集，F为关于R的函数依赖的集合，K是R唯一的候选码。⑴因为R是3NF,所以R中的非主属性都不传递依赖于R的候选码K;⑵假设A是R中的主属性(组),存在一个不包含候选码K的属性集Y(K二Y),使得Y—A成立。令K'=(K-A)UY,贝卩K'—(KA),K'-Y,因为Y-A成立，所以K'-A成立，可得：K'-(K-A)UA,即：K'—K,故关系模式R除候选码K外还存在另一个候选码K'，与前提矛盾。综上所述，只有一个候选码的3NF关系模式一定是BCNR例2:关系模式Student(Sno,NameBirthday,Gen-der,Address)记录学生档案，Sno表示学号，Name表示姓名，Birthday表示出生日期，Gender表示性别，Address表示住址，Sno是该关系模式唯一的候选码，Student满足BCNF的要求。判定规则3至多只有一个复合候选码（多属性候选码）的3NF关系模式一定是BCNF证明假设关系模式R（U,F）是一个3NF的关系模式，U为R的属性集，F为关于R的函数依赖的集合，K是R唯一的复合候选码。（1） 因为R是3NF，所以R中的非主属性都不传递依赖于R的候选码K；（2） 因为R是3NF，K是R唯一的复合候选码，所以所有主属性都完全函数依赖于每个不包含它的候选码。综上所述，只有一个复合候选码的3NF关系模式一定是BCNR例3:关系模式WPE（WnoPno,Eno,Quantity）记录仓库的配件管理情况，其中Wno表示仓库号，Pno表示配件号，Eno表示职工号，Quantity表示数量。因为一个仓库有多个职工、一个职工仅在一个仓库工作、每个仓库里一种型号的配件由专人负责、 一个人可以管理几种配件、同一种型号的配件可以分放在几个仓库中， 所以属性组（Wno卩门0）和（Pno,Eno）都可以构成WPE的候选码，两个候选码相交，又主属性Wno和Eno之间存在着函数依赖Eno宀Wno所以WPE不满足BCNF的要求。综合BCNF的性质和判定规则后，可以发现常出现BCNF的情况是：有超过两个的复合候选码且候选码中属性有相交，即多个候选码中存在公共属性。五BC范式的分解算法BCNF的分解算法仅具备无损连接性，不具有函数依赖保持性。算法:BCNF分解算法输入:关系模式R,R的属性集合U和函数依赖集F输出：具有无损连接性的分解 p,p中的所有关系模式都是BCNF方法：p:={R};WHILEp中存在非BCNF的关系模式DO选择一个非BCNF的模式S€p；选择S的一个违反BCNF要求的函数依赖3Y;用两个关系模式(S-丫)和(XUY)取代p中的S;ENDWHILE结束语目前的关系数据库逻辑设计主要以规范化设计理论为基础， 分析关系模式中的数据依赖，通过投影分解等方法消除不合理的数据依赖， 解决因不合理的数据依赖对关系模式带来的异常问题等。 规范化设计理论中关于BCNF的理论和算法在实践中不容易操作和使用，尤其对于初学者来说难以掌握。本文根据国内外多名教授学者的研究成果， 对BCNF的定义、性质、判定规则与算法进行了简洁、准确、灵活的阐述与分析，对理解和掌握BCNF有一定的实用价值。参考文献AbrahamSilberschatz, HenryF.Korth,S.Sudarshan,DatabaseSystemConcepts（Fourth Edition）[M].Beijing, High