第7章 土地生态学

第7章关系数据库理论

7.1关系数据模式的标准化理论

7.1.1关系模式标准化的必要性7.1.2函数依赖及其关系的范式7.3关系系统及其查询优化技术7.3.1关系系统的定义和分类7.3.2关系系统的查询优化理论与技术.前面已经讲述了关系数据库、关系模型的根本概念以及关系数据库的标准语言。如何使用关系模型设计关系数据库，如何选择一个比较好的关系模式的集合，每个关系又应该由哪些属性组成。这属于数据库设计的问题，确切地讲是数据库逻辑设计的问题。.本章讲述关系数据库标准化理论和数据库操作理论。要求了解标准化理论的研究动机及其在数据库设计中的作用，掌握函数依赖的有关概念，第一范式、第二范式、第三范式及BC范式重点掌握并能够灵活运用关系模式标准化的方法掌握关系数据操作理论——关系数据查询和优化理论规那么.7.1关系数据模式的标准化理论标准化理论的主要内容：关系数据库的标准化理论最早是由关系数据库的创始人E.F.Codd提出的，后经许多专家学者对关系数据库理论作了深入的研究和开展，形成了一整套有关关系数据库设计的理论。范式〔NormalForm〕是指标准化的关系模式。由满足最根本标准化的关系模式叫第一范式，第一范式的关系模式再满足另外一些约束条件就产生了第二范式、第三范式、BC范式等等。一个低一级的关系范式通过模式分解可以转换成假设干高一级范式的关系模式的集合，这种过程叫关系模式的标准化。.范式的概念最早由E.F.Codd提出。从1971年起，Codd相继提出了关系的三级标准化形式，即第一范式〔1NF〕、第二范式〔2NF〕、第三范式〔3NF〕。1974年，Codd和Boyce以共同提出了一个新的范式的概念，即Boyce-Codd范式，简称BC范式。1976年Fagin提出了第四范式，后来又有人定义了第五范式。至此在关系数据库标准中建立了一个范式系列：1NF,2NF,3NF,BCNF,4NF,5NF,一级比一级有更严格的要求。各个范式之间的联系可以表示为：5NF4NFBCNF3NF2NF1NF如下图。.4NF5NFBCNF3NF2NF1NF规范与非规范关系.如何设计一个适合的关系数据库系统，关键是关系数据库模式的设计，一个好的关系数据库模式应该包括多少关系模式，而每一个关系模式又应该包括哪些属性，又如何将这些相互关联的关系模式组建一个适合的关系模型，这些工作决定了到整个系统运行的效率，也是系统成败的关键所在，所以必须在关系数据库的标准化理论的指导下逐步完成。.7.1.1关系模式标准化的必要性1.关系模式应满足的根本要求

1)元组的每个分量必须是不可分的数据项。

2)数据库中的数据冗余应尽可能少。

3)关系数据库不能因为数据更新操作而引起数据不一致问题。

4)当执行数据插入操作时，数据库中的数据不能产生插入异常现象。

5)数据库中的数据不能在执行删除操作时产生删除异常问题。

6)数据库设计应考虑查询要求，数据组织应合理。

.2.关系标准化可能出现的问题数据冗余大.插入异常。删除异常。更新异常。学号姓名年龄性别系名系主任课程名成绩98001李华20男计算机系王民程序设计8898001李华20男计算机系王民数据结构7498001李华20男计算机系王民数据库8298001李华20男计算机系王民电路6598002张平21女计算机系王民程序设计9298002张平21女计算机系王民数据结构8298002张平21女计算机系王民数据库7898002张平21女计算机系王民电路8398003陈兵20男数学系赵敏高等数学7298003陈兵20男数学系赵敏数据结构9498003陈兵20男数学系赵敏数据库8398003陈兵20男数学系赵敏离散数学87.3.模式分解是关系标准化的主要方法

上述的关系模式:教学(学号，姓名，年龄，性别，系名，系主任，课程名，成绩).p216异常情况分析。可以按“一事一地〞的原那么分解成“学生〞、“教学系〞和“选课〞三个关系，其关系模式为：

学生(学号，姓名，年龄，性别，系名称)；

教学系(系名，系主任)；

选课(学号，课程名，成绩)..经过上述分析，我们说分解后的关系模式是一个好的关系数据库模式。从而得出结论，一个好的关系模式应该具备以下四个条件：1.尽可能少的数据冗余。2.没有插入异常。3.没有删除异常。4.没有更新异常。

.将结构复杂的关系分解成结构简单的关系，从而把不好的关系数据库模式转变为好的关系数据库模式，这就是关系的标准化。标准化又可以根据不同的要求而分成假设干级别。我们要设计的关系模式中的各属性是相互依赖、相互制约的，这样才构成了一个结构严谨的整体。因此在设计关模式时，必须从语义上分析这些依赖关系。数据库模式的好坏和关系中各属性间的依赖关系有关，因此，我们先讨论属性间的依赖关系，然后再讨论关系标准化理论。.7.1.2函数依赖及其关系的范式关系模式中的各属性之间相互依赖、相互制约的联系称为数据依赖。数据依赖一般分为函数依赖、多值依赖和连接依赖。其中,函数依赖是最重要的数据依赖。函数依赖〔FunctionalDependency〕是关系模式中属性之间的一种一一对应的逻辑依赖关系。.例如在关系模式Student中，SNO与SN、AGE、DEPT之间都有一种依赖关系。由于一个SNO只对应一个学生，而一个学生只能属于一个系，所以当SNO的值确定之后，SN，AGE，DEPT的值也随之被唯一确实定了。我们说SNO决定函数〔SN，AGE，DEPT〕，或者说〔SN，AGE，DEPT〕函数依赖于SNO。.1.关系模式的简化表示法

关系模式的完整表示是一个五元组：

R〈U，D，Dom，F〉.

其中：R为关系名；U为关系的属性集合；D为属性集U中属性的数据域；Dom为属性到域的映射；F为属性集U的数据依赖集。

关系模式可以用三元组来为：

R〈U，F〉.

.2.函数依赖的概念1)设R〈U〉是属性集U上的关系模式，X、Y是U的子集。假设对于R〈U〉的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而Y上的属性值不等，那么称X函数确定Y函数，或Y函数依赖于X函数，记作X→Y。

例如，对于教学关系模式：教学〈U，F〉；

U={学号，姓名，年龄，性别，系名，系主任，课程名，成绩}；

F={学号→姓名，学号→年龄，学号→性别，学号→系名，系名→系主任，(学号，课程名)→成绩}.

.相关概念及表示 ①X→Y，但YX，那么称X→Y是非平凡的函数依赖。假设不特别声明，总是讨论非平凡的函数依赖。

②X→Y，但YX，那么称X→Y是平凡的函数依赖。

③假设X→Y，那么X叫做决定因素〔Determinant〕，Y叫做依赖因素〔Dependent〕。

④假设X→Y，Y→X，那么记作X↔Y。

⑤假设Y不函数依赖于X，那么记作XY。. 2)在R〈U〉中，如果X→Y，并且对于X的任何一个真子集X‘，都有X‘Y，那么称Y对X完全函数依赖，记作：X→Y；假设X→Y，但Y不完全函数依赖于X，那么称Y对X局部函数依赖，记作：X→Y。

例如，在教学关系模式：(学号，课程名)→成绩，(学号，课程名)→姓名

3)在R〈U〉中，如果X→Y，(YX)，YX，Y→Z，那么称Z对X传递函数依赖。传递函数依赖记作X→Z。

例如，在教学模式中，因为：学号→系名，系名→系主任；所以：学号→系主任。PFFP传递传递.

3.1NF的定义如果关系模式R，其所有的属性均为简单属性，即每个属性都是不可再分的，那么称R属于第一范式，记作R1NF。

4.2NF的定义假设R1NF，且每一个非主属性完全依赖于码，那么R2NF。

〔即消除非主属性码对码的局部依赖〕.在教学模式中：属性集={学号，姓名，年龄，性别，系名，系主任，课程名，成绩}.

函数依赖集={学号→姓名，学号→年龄，学号→性别，学号→系名，系名→系主任，(学号，课程名)→成绩}.

主码=(学号，课程名).非主属性=(姓名，年龄，系名，系主任，成绩)。

非主属性对码的函数依赖：{(学号，课程名)→姓名，(学号，课程名)→年龄，(学号，课程名)→性别，(学号，课程名)→系名，(学号，课程名)→系主任；(学号，课程名)→成绩}.教学模式不服从2NF，将教学模式分解为：学生－系〔学号，姓名，年龄，性别，系名，系主任〕选课〔学号，课程名，成绩〕pppppF.5.3NF的定义关系模式R〈U，F〉中假设不存在这样的码X、属性组Y及非主属性Z(ZY)使得X→Y、YX、Y→Z成立，那么称R〈U，F〉3NF。

可以证明，假设R3NF，那么每一个非主属性既不局部函数依赖于码，也不传递函数依赖于码。〔即消除非主属性对码的局部和传递函数依赖〕

.考查学生_系关系，由于存在：学号→系名，系名→系主任。那么：学号→系主任。所以学生_系3NF。

如果分解为：

学生(学号，姓名，年龄，性别，系名)；

教学系(系名，系主任).

显然分解后的各子模式均属于3NF。传递.6.BCNF的定义关系模式R〈U，F〉1NF。假设X→Y且YX时X必含有码，那么R〈U，F〉BCNF。〔即消除主属性对码的局部和传递函数依赖〕

也就是说，关系模式R〈U，F〉中，假设每一个决定因素都包含码，那么R〈U，F〉BCNF。由BCNF的定义可以得到结论，一个满足BCNF的关系模式有：

1)所有非主属性对每一个码都是完全函数依赖。

2)所有的主属性对每一个不包含它的码，也是完全依赖。

3)没有任何属性完全函数依赖于非码的任何一组属性。.7.BCNF和3NF的比较1)BCNF不仅强调其他属性对码的完全的直接的依赖，而且强调主属性对码的完全的直接的依赖，它包括3NF，即RBCNF，那么R一定属于3NF。

2)3NF只强调非主属性对码的完全直接依赖，这样就可能出现主属性对码的局部依赖和传递依赖。

.例如，关系模式STJ(S，T，J)中，S表示学生，T表示教师，J表示课程。语义为：每一教师只能讲授一门课程，每门课程由假设干教师讲授；每个学生选修某门课程就对应一个固定的教师。由语义可以得到STJ模式的函数依赖为：

F={(S，J)→T，T→J}

显然：(S，J)和(T，S)都是关系的码；关系的主属性集为{S，T，J}，非主属性为〔空集〕。

由于STJ模式中无非主属性，所以它属于3NF；但因为存在T→J，由于T不是码，故STJBCNF。分解为〔S，T〕和

〔T，J〕两个模式。.7.1.5关系模式的标准化到目前为止，标准化理论已经提出了六类范式〔有关4NF和5NF的内容不再详细介绍〕。各范式级别是在分析函数依赖条件下对关系模式别离程度的一种测度，范式级别可以逐级升高。一个低一级范式的关系模式，通过模式分解转化为假设干个高一级范式的关系模式的集合，这种分解过程叫作关系模式的标准化〔Normalization〕。.关系模式标准化的目的和原那么一个关系只要其分量都是不可分的数据项，就可称作标准化的关系，但这只是最根本的标准化。这样的关系模式是合法的。但人们发现有些关系模式存在插入、删除、修改异常、数据冗余等弊病。标准化的目的就是使结构合理，消除存储异常，使数据冗余尽量小，便于插入、删除和更新。标准化的根本原那么就是遵从概念单一化“一事一地〞的原那么，即一个关系只描述一个实体或者实体间的联系。假设多于一个实体，就把它“别离〞出来。因此，所谓标准化，实质上是概念的单一化，即一个关系表示一个实体。

.关系模式标准化的步骤标准化就是对原关系进行投影，消除决定属性不是候选码的任何函数依赖。具体可以分为以下几步：1．对1NF关系进行投影，消除原关系中非主属性对码的局部函数依赖，将1NF关系转换成假设干个2NF关系。2．对2NF关系进行投影，消除原关系中非主属性对码的传递函数依赖，将2NF关系转换成假设干个3NF关系。3．对3NF关系进行投影，消除原关系中主属性对码的局部函数依赖和传递函数依赖，也就是说使决定因素都包含一个候选码。得到一组BCNF关系。.关系标准化的根本步骤如下图。1NF2NF3NFBCNF消除决定属性不是候选码的非平凡的函数依赖消除非主属性对码的部分函数依赖消除非主属性对码的传递函数依赖消除主属性对码的部分和传递函数依赖标准化过程.一般情况下，我们说没有异常弊病的数据库设计是好的数据库设计，一个不好的关系模式也总是可以通过分解转换成好的关系模式的集合。但是在分解时要全面衡量，综合考虑，视实际情况而定。对于那些只要求查询而不要求插入、删除等操作的系统，几种异常现象的存在并不影响数据库的操作。这时便不宜过度分解，否那么当要对整体查询时，需要更多的多表连接操作，这有可能得不偿失。在实际应用中，最有价值的是3NF和BCNF，在进行关系模式的设计时，通常分解到3NF就足够了。.7.3关系系统及其查询优化技术7.3.1关系系统的定义和分类能够在一定程度上支持关系模型的数据库管理系统是关系系统。由于关系模型中并非每一局部都是同等重要的并不苛求一个实际的关系系统必须完全支持关系模型。.1.关系系统的定义一个数据库管理系统可定义为关系系统，当且仅当它至少满足：1.支持关系数据库〔即关系数据结构〕从用户角度看，系统中只有表这种结构2.支持选择、投影和〔自然〕连接运算对这些运算不要求用户定义任何物理存取路径对关系系统的最低要求.不支持关系数据结构的系统显然不能称为关系系统仅支持关系数据结构，但没有选择、投影和连接运算功能的系统仍不能算作关系系统。原因：不能提高用户的生产率支持选择、投影和连接运算，但要求定义物理存取路径，这种系统也不能算作真正的关系系统原因：就降低或丧失了数据的物理独立性选择、投影、连接运算是最有用的运算.2.关系系统的分类分类依据：支持关系模型的程度分类⒈表式系统：支持关系数据结构(即表),不支持集合级的操作。⒉(最小)关系系统支持：关系数据结构 选择、投影、连接关系操作⒊关系完备的系统支持：关系数据结构 所有的关系代数操作 支持关系的实体完整性和参照完整性⒋全关系系统支持：关系模型的所有特征 特别是:数据结构中域的概念，支持实体完整性、参照完整性和所有用户定义的完整性

.

数据结构数据操作完整性表式系统表

(最小)关系系统表选择、投影、连接

关系完备的系统表

全关系系统

.1.一个实例例：求选修了课程Ｃ2的学生姓名

SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.Sno ANDSC.Cno='2';.假设1：外存： Student:1000条,SC:10000条,选修2号课程:50条假设2：一个内存块装元组:10个Student,或100个SC, 内存中一次可以存放:5块Student元组,1块SC元组和假设干块连接结果元组假设3：读写速度：20块/秒假设4：连接方法：基于数据块的嵌套循环法

.执行策略1Ｑ1＝ПＳname(бStudent.Sno=SC.Sno

∧SC.Cno='2'

(Student×SC))

①Student×SC

读取总块数=读Student表块数+读SC表遍数*每遍块数

=1000/10+(1000/(10×5))×(10000/100)=100+20×100=2100

读数据时间=2100/20=105秒.不同的执行策略,考虑I/O时间

中间结果大小=1000*10000=107(1千万条元组)

写中间结果时间

=10000000/10/20=50000秒

②б

读数据时间

=50000秒

③П总时间=105＋50000＋50000秒=100105秒

=27.8小时.2.Ｑ2＝ПＳname(бSC.Cno='2'(StudentSC))

① 读取总块数=2100块 读数据时间=2100/20=105秒 中间结果大小=10000〔减少1000倍〕 写中间结果时间=10000/10/20=50秒

②б 读数据时间=50秒

③П

总时间＝105＋50＋50秒＝205秒=3.4分

执行策略2.3.Ｑ2＝ПSname(StudentбSC.Cno='2'(SC))

①б

读SC表总块数=10000/100=100块

读数据时间=100/20=5秒

中间结果大小=50条不必写入外存

② 读Student表总块数=1000/10=100块

读数据时间=100/20=5秒

③П

总时间＝5＋5秒＝10秒执行策略3.执行策略44.Ｑ2＝ПＳname(StudentбSC.Cno='2'(SC))假设SC表在Cno上有索引，Student表在Sno上有索引

①б

读SC表索引=

读SC表总块数=50/100<1块 读数据时间

中间结果大小=50条不必写入外存② 读Student表索引=

读Student表总块数=50/10=5块 读数据时间③П总时间<10秒.查询优化的必要性查询优化极大地影响RDBMS的性能。

查询优化的可能性关系数据语言的级别很高，使DBMS可以从关系表达式中分析查询语义。用户不必考虑如何最好地表达查询以获得较好的效率系统可以比用户程序的优化做得更好(1)优化器可以从数据字典中获取许多统计信息，而用户程序那么难以获得这些信息(2)如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行方案。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。(3)优化器可以考虑数百种不同的执行方案，而程序员一般只能考虑有限的几种可能性。(4)优化器中包括了很多复杂的优化技术查询优化的总目标选择有效策略，求得给定关系表达式的值

.2.查询优化的一般准那么选择运算应尽可能先做

目的：减小中间关系在执行连接操作前对关系适当进行预处理按连接属性排序在连接属性上建立索引

投影运算和选择运算同时做目的：防止重复扫描关系将投影运算与其前面或后面的双目运算结合目的：减少扫描关系的遍数某些选择运算＋在其前面执行的笛卡尔积===>连接运算例：бStudent.Sno=SC.Sno(Student×SC)

StudentSC提取公共子表达式.3.关系代数等价变换规那么关系代数表达式等价指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的优化策略大局部都涉及到代数表达式的变换.

常用的等价变换规那么

设E1、E2等是关系代数表达式，F是条件表达式

l.连接、笛卡尔积交换律

E1×E2≡E2×E1 E1E2≡E2E1 E1FE2≡E2FE1

.

2.连接、笛卡尔积的结合律

(E1×E2)×E3≡E1×(E2×E3)(E1E2)E3≡E1(E2E3)(E1E2)E3≡E1(E2E3)

F

F

F

F.3.投影的串接定律πA1,A2,,An(πB1,B2,,Bm(E))≡πA1,A2,,An(E)假设：1) E是关系代数表达式2) Ai(i=1，2，…，n),Bj(j=l，2，…，m)是属性名3){A1,A2,…,An}构成{Bl，B2，…，Bm}的子集4.选择的串接定律бF1〔бF2〔E〕〕≡бF1∧F2(E)选择的串接律说明选择条件可以合并这样一次就可检查全部条件。.5.选择与投影的交换律(1)假设:选择条件F只涉及属性A1，…，AnбF(πA1,A2,

,An(E))≡πA1,A2,

,An(бF(E))

(2)假设:F中有不属于A1,…,An的属性B1,…,Bmπ

A1,A2,

,An

(

бF

(E))≡

πA1,A2,

,An(бF

(πA1,A2,

,An,B1,B2,

,Bm(E))).6.选择与笛卡尔积的交换律(1)假设：F中涉及的属性都是E1中的属性 бF(E1×E2)≡бF(E1)×E2

(2)假设：F=F1∧F2，并且F1只涉及E1中的属性，F2只涉及E2中的属性 那么由上面的等价变换规那么1，4，6可推出： бF(E1×E2)≡бF1(E1)×бF2(E2)

(3)假设：F=F1∧F2，F1只涉及E1中的属性，F2涉及E1和E2两者的属性 бF(E1×E2)≡бF2(бF1(E1)×E2)

它使局部选择在笛卡尔积前先做.7.选择与并的交换 假设：E=E1∪E2，E1，E2有相同的属性名

бF(E1∪E2)≡бF(E1)∪бF(E2)

8.选择与差运算的交换 假设：E1与E2有相同的属性名

бF(E1-E2)≡бF(E1)-бF(E2).9.投影与笛卡尔积的交换 假设：E1和E2是两个关系表达式，A1，…，An是E1的属性，B1，…，Bm是E2的属性πA1,A2,…,An,B1,B2,…,Bm〔E1×E2)≡ πA1,A2,…,An〔E1)×πB1,B2,…,Bm(E2)l0.投影与并的交换 假设：E1和E2有相同的属性名 πA1,A2,…,An(E1∪E2)≡ πA1,A2,…,An(E1)∪πA1,A2,…,An(E2).4.关系代数表达式的优化算法

算法：关系表达式的优化输入：一个关系表达式的语法树。输出：计算该表达式的程序。方法：〔1〕分解选择运算利用规那么4把形如бF1∧F2∧…∧Fn(E)变换为бF1(бF2(…(бFn(E))…)).〔2〕通过交换选择运算，将其尽可能移到叶端对每一个选择，利用规那么4～8尽可能把它移到树的叶端。

〔3〕通过交换投影运算，将其尽可能移到叶端 对每一个投影利用规那么3，9，l0，5中的一般形式