一种典型的模式分解算法分析与应用

2010-09-01冷强奎秦玉平

赤峰学院学报·自然科学版 2010年7期

关键词：典型规范化数据库

冷强奎，秦玉平

（渤海大学信息科学与工程学院，辽宁锦州 121000）

一种典型的模式分解算法分析与应用

冷强奎，秦玉平

（渤海大学信息科学与工程学院，辽宁锦州 121000）

从非优化关系存在的问题出发，结合模式分解准则和规范化理论，分析了一种典型的模式分解算法，并给出其在抽象关系中的应用.最后，通过该算法将存在问题的关系分解，分解后的关系符合较高级的范式，达到了应用系统逻辑结构设计的要求.

模式分解；规范化；关系；逻辑结构；范式

关系模式逻辑结构设计是数据库应用系统开发的核心环节，这个阶段不但能够调整数据模型结构，还能够提升系统性能[1].一个非优化的关系中存在大量的数据冗余和异常，不能满足系统性能要求，制约系统后续开发进程的实施.本文从分析非优化关系存在的问题出发，结合模式分解准则和规范化理论[2]，分析了一种典型的模式分解算法，并对非优化关系执行分解，实际应用取得了较好的效果.

1 非优化关系存在的问题

对于一个典型的非优化关系S={Sno,Sdept,Mname, Cno,Grade}，其中Sno为学号、为系别、Sdept为系主任姓名、为课程号、为成绩，为的一个函数依赖集，中部分数据如表1.

表1 学生信息表

根据关系S的基本数据信息，可得到关系的码为(Sno, Cno)，在F中存在Mname对码的传递函数依赖，以及Sdept对码的部分函数依赖，所以S不能达到3Nf.达不到3Nf的关系S存在如下问题：

(1)数据冗余，当关系S中再出现信息系的学生时，Mname属性的值还为“程前”；

(2)插入异常，学生入学还未选课，则信息无法存入S中；

(3)删除异常，若S中体育系学生全部毕业了，在删除学生信息时，系信息也随之删除；

(4)更新异常，某系更换系主任后，所在系学生元组的Mname属性都要更新.

对关系S的优化是数据库逻辑结构设计阶段必须要解决的问题，为了消除数据冗余和三种异常情况，需要对S执行模式分解操作.

2 一种典型的模式分解算法分析

2.1 模式分解的原则

模式分解要遵循两个基本原则[3]，即分解具有“无损连接性”和“保持函数依赖”，保证分解后的关系与原关系模式等价.设ρ={R1,…,RK}为R的一个分解，r是R的任意一个子关系,定义mρ(r)=πR1 πR2(r) …πRk(r)，即mρ(r)是r在ρ中各关系模式上投影的连接，这里πRi={t,Ui|t∈r}，两个分解原则如下：

无损连接原则：ρ={R1,…,RK}是R的一个分解，若对R的任何一个子关系r均有r=mρ(r)成立，则称分解ρ具有无损连接性.

2.2 属性闭包和最小依赖集理论

公理系统[4]是模式分解算法的理论基础，设U为属性全体，F是U上的一组函数依赖，对于关系模式R，存在

A1自反律：若Y哿X哿U，则X→Y为F所蕴含；

A2增广律：若X→Y为F所蕴含，且Z哿U，则XZ→YZ为F所蕴含；

A3传递律：若X→Y及Y→Z为F所蕴含，则X→Z为F所蕴含.

定义1 根据Armstrong公理系统和推理规则，设F为属性集U上的一组函数依赖，X哿U，X+F={A|X→A能由F根据Armstrong公理得出}，X+F称为属性集X关于函数依赖集F的闭包.

X+F求得结果即为属性X所能决定的因素，当X+F=U时，且X的真子集不能决定U时，则说明X是可以充当关系R的码值，这是属性闭包的一个典型应用.由Armstrong公理系统推导得出的F中所逻辑蕴含的函数依赖的全体称为F的闭包，记作F+.F+是一个完备的集合，但使用F+参与运算会使计算非常复杂，于是要找到一个与F+等价的最小函数依赖集Fm.Fm的求解由算法(1)描述：

算法1 求关系R的一个最小函数依赖集Fm.

(1)根据分解规则，将F中各函数依赖右侧元素单一化.逐一检查F中各函数依赖FDi：X→Y，若Y=A1A2…Ak,k>2，则用{X→Aj|j=1,2,…,k}来取代X→Y.

(2)将冗余的函数依赖去掉.逐一检查F中各函数依赖FDi：X→A，令G=F-{X-A}，若A∈X+G，则从F中去掉此函数依赖.

(3)将决定因素中多余的属性去掉.逐一取出F中各函数依赖FDi：X→A，设X=B1B2…Bm，逐一考查Bi(i=1,2,…,m)，若A∈(X-Bi)+F，则以X-Bi取代X.

2.3 转换为3NF的模式分解算法[5]

算法2 求达到3NF的既保持函数依赖又无损连接的分解

(1)求R中的函数依赖集F的最小函数依赖集Fm，并用Fm代替F.

(2)找出不在F中出现的属性，把这样的属性构成一个关系模式.把这些属性从U中去掉，剩余的属性仍记为U.

(3)若有X→A∈F，且XA=U，则ρ={R}，转(5).

(4)否则，对F按具有相同左部分组，每一组函数依赖F'i所涉及全部属性形成一个属性集Ui.若Ui∈Uj则去掉Ui，得到的分解ρ={R1,…,RK}.

(5)利用属性闭包求关系码值，假设求得X+F，则X为码.令τ=ρU{R*}.

(6)若有某个Ui,U哿Ui，，将R*从τ中去掉. (7)τ为所求.

3 模式分解算法的应用

利用算法(2)对一个抽象的关系R执行分解，U= {A,B,C,D,E,G}，F={A→G,AE->B,CD->A.CE->D,CG->D}.将R转换为达到3NF既无损连接又能保持函数依赖的分解，步骤如下：

(1)根据算法 (1)，由F可得Fm=A→G,AE->B,CD->A, CE->D,CG->D}.

(2)关系R函数依赖集合F中不存在X→A∈F且XA=U的情况，算法继续执行.

(3)对F按具有相同左部分组，共分五组R1，其中U1={A,G},F1={A→G}；R2，其中U2={A,B,E}，F2={AE→B}；R3，其中U3={A,C,D}，F3={CD→A}；R4，其中U4={C,D,E}，F4={CE→D}；R5，其中U5={C,D,G}，F5= {CG→D}.ρ={R1,…,R5}

(4)利用属性闭包求关系R的码X，可得X=CE，R*<{C, E},覬>0.

(5)由于码值(CE)∈U4，则最后的分解为ρ.ρ为无损连接且保持函数依赖的分解.同时ρ中各关系均能够达到3NF.