vlambda博客
学习文章列表

真正的数据库优化-关系数据理论简明介绍

为什么要谈关系数据理论?

    好的程序最起码要具有可拆分的特性,模块化要做好。这样的程序不容易出错,并且可维护性强。

    最为项目工程的一部分,数据库在设计的时候,也应当遵循类似的原则。设计多个表,(类似于程序中的多个函数)这样的数据库查询速度快,可维护性强。

    这就是所谓的“数据库优化”。

    举个具体的例子:

    学校的数据库有下面的属性:

    学生的学号(Sno),所在系(Sdept),系主任名字(Mname),课程名(Cname),课程编号(Cno),成绩(Grade)

    有以下关系:

  1. 一个系有若干学生,一个学生只属于一个系。
  2. 一个系有一名主任
  3. 一个学生可以选修多门课,每门课有若干学生选修。
  4. 每个学生所学的每门课都有一个成绩。
  5. ... ...(太多关系了,就不列举了,之所以举学校的例子,就是大家都熟悉,很多的关系我们用常识判断就可以。 下面的例子都是基于这个描述学校的数据库。)

    新手的话,会这样设计这个数据库:

    只设计一张表:

Sno(学号) Sdept(系) Mnane(系主任名字) ......
1 计科 王某某 ......
2 计科 王某某 ......
3 物理 张某某 ......
...... ...... ...... ......

    只看前三列,当系主任变动时,我们要把所有的列都重写一遍,这造成的浪费可想而知。

    但是,如果我们通过模式分解把表拆出来,系和系主任单独存成一张表,再用新表的码和主表关联起来,那么我们改动数据的时候,只需要改动那张最小的表就可以了。

    具体应该怎么拆分表来设计数据库,就是关系数据理论解决的问题。

    注意:数据库和程序还是有区别的。数据库的特点是数据量大,存储空间有限,我们设计数据库的时候往往更追求空间复杂度最小;而程序设计的时候,一般程序用到的存储空间都是够用的,我们程序设计追求的更多是时间复杂度最小。

一些关键的基本概念:

    函数依赖:

        简答来说,就是若X确定,那Y就一定确定。

        比如知道一个人的身份证号,就能确定他的姓名。

        (X,Y都可以是多个属性,上面的例子里,X,Y分别各是一个属性)

        以上面那个学校的数据库为例:

        关系SC(Sno,Cno,Grade)中,(Sno,Cno)-->Grade。也是一个依赖。

        完全函数依赖

        (Sno,Cno) --> Grade

        知道学号和课程号,就决定了一个成绩。

        部分函数依赖

        (Sno,Cno,Sname)--p--> Grade

        知道学号,课程号,姓名,就决定一个成绩。这个依赖也成立,但是姓名是冗余的。

        显然,部分依赖产生的这样的冗余并没啥用,反而会浪费存储空间。

        传递函数依赖

        Sno --> Sdept, Sdept --> Mname;

        Sno --T--> Mnane

        学号决定系,系决定系主任名字。那么系主任的名字(Mnane)传递依赖于学生的学号(Sno)

        显然,同一张表里出现传递依赖的话,也会产生大量的冗余,浪费空间。

        码

        主码,外码,候选码。就不赘述了,这个相信大家都知道。

        注意主属性和候补码的关系:

        主属性是候补码用到的所有属性。

        我们下面讲的”码“,都是指”候选码“。

    多值依赖:


X Y Z
t x y1
z1
s x y2 z2
w x y1
z2
v x y2 z1

        x相同,y和z是 的全排列。

        记x为X,( )( )为Y。则称Y多值依赖于X,记作X -->--> Y。

        平凡多值依赖

        下面的非平凡多值依赖的例子,只剩WS(W,S)的话,即为平凡的多值依赖。

        S多值依赖于W(只有一项,就没有全排列可言)。或者可以看成全排列的特例。

        非平凡多值依赖

        举例:

        S多值依赖于W,C多值依赖于W。

        关系模式:WSC(W,S,C)W表示仓库,S表示保管员,C表示商品。每个仓库有若干保管员,若干商品,每个保管员所在仓库的所有商品,每种商品被所有它所在的仓库的保管员所保管。(假设仓库 有两个保管员 ,存放三个商品 ;仓库 有两个保管员 存放两个商品

W S C
w1
s1
c1
w1
s1
c2
w1
s1 c3
w1
s2
c1
w1 s2 c2
w1
s2 c3
w2 s1
c1
w2 s1 c2
w2 s2
c1
w2
s2 c2

每个仓库里,管理员和商品的全排列构成所有的内容。

   范式

    关系数据理论为我们定义了一套规范,满足这些规范的数据库设计,就是基于关系数据理论设计出来的比较好的数据库啦。这一套规范被称为“范式”。

        第一范式(1NF)

        一个关系模式中的所有属性都是不可分的基本数据项,那么这个关系模式满足第一范式

        就是每一张表的每个属性,必须是不可再分的。

        第二范式(2NF)

        关系模式满足第一范式,并且每一个非主属性和码都是完全函数依赖的关系。那么这个关系模式满足第二范式。

        举例:

        关系模式:SLC(Sno,Sdept,Sloc,Cno,Grade)

        学号,学生院系,学生宿舍楼,课程号,成绩。

        候选码为:(Sno,Cno)

        非主属性为:Sdept,Sloc,Grade

        因为Sno --> Sdept(学号可以决定学生所在的系),

        所以(Sno,Cno)--P--> Sdept(Sdept部分依赖于码(Sno,Cno))。

        所以这个关系模式不满足第二范式。

        分析:这个例子,会发生插入异常,删除异常,数据冗余的问题。

        插入异常:当学生没选课的时候,这条数据只有Sno,没有Cno,那么这个学生的数据不能插入表里。

        删除异常:如果某个学生只选了一门课,那么他的其他信息(所在院系)就只存在这一条数据里;如果这个学生要退选这门课,那么他的这一整条记录都要删除,将来他的学号,所在院系就都查不到了。(这显然不合理,人家退一门课就相当于被开除了?)

        解决方法:把SLC表,拆成SC,SL两个表

        其中SC(Sno,Cno,Grade),SL(Sno,Sdept,Sloc),这样两个表,不存在部分依赖的关系,那么这样的设计就满足第二范式了。

        第三范式(3NF)

        关系模式满足第一范式,第二范式,且每一个非主属性与码之间不存在传递函数依赖的关。那么这个关系模式满足第三范式。

        在第二范式的例子里,最后提出的解决方案里的SL(Sno,Sdept,Sloc)就不满足第三范式。

        学生所在院系可以决定宿舍楼号(Sdept --> Sloc)学号可以决定所在院系(Sno --> Sdept)所以存在传递函数依赖Sno --T--> Sloc。

        可能产生的问题也是插入异常,删除异常,数据冗余。这里和第二范式的例子类比就行了。

        扩充第三范式(BCNF)

        关系模式满足第一范式,第二范式,第三范式,且每一个主属性和码之间都不存在部分函数依赖和传递函数依赖。

        举例:

        关系模式:C(Cno,Cname,Credit)其中Cname允许重复。

        码:Cno

        FD:Cno --> Cname, Cno -->Credit

        非主属性:Cname, Credit

        每个非主属性都由主属性决定,且主属性只有一个,这是BC范式。

        特殊例子:

        关系模式:S(Sno,Sname,Sdept,Sage),且不允许重名。

        码:Sno,Sname

        FD:Sno --> Sname, Sname -->Sno, Sno --> Sdept, Sno --> Sage

        非主属性:Sdept, Sage

        这个关系模式也满足BC范式,因为虽然有Sname -->Sno, Sno --> Sdept。

        但是:Sno --> Sname, Sname -->Sno,两个码之间可以相互决定,实际实际建表的时候,可以指定任意一个码为主码,建成表后,把另一个码看作非主属性的时候,并不存在传递函数依赖和部分函数依赖的关系。所以这样的关系模式是满足BC范式的。所以判断BC范式,我们可以从建表的角度进行判断。

        例子:

        关系模式:STJ(S,T,J),其中S表示学生,T表示老师,J表示课程。

        一个老师只教一门课,每门课由若干老师交。

        由描述,推断出下面的FD:

        (S, J) --> T; (S, T) --> J; T -->J

        码:(S,J),(S,T)

        非主属性:无

        不满足BC范式,因为FD中,函数依赖T --> J,其中的决定因素T不包含在这个关系模式的码中。

        第四范式(4NF)

        没有非平凡多值依赖且非函数依赖的关系。

        满足第一范式,第二范式,第三范式,BC范式。

        举例1:

        S多值依赖于W,C多值依赖于W。

        关系模式:WSC(W,S,C)W表示仓库,S表示保管员,C表示商品。每个仓库有若干保管员,若干商品,每个保管员所在仓库的所有商品,每种商品被所有它所在的仓库的保管员所保管。(假设仓库 有两个保管员 ,存放三个商品 ;仓库 有两个保管员 存放两个商品

W S C
w1
s1
c1
w1
s1
c2
w1
s1 c3
w1
s2
c1
w1 s2 c2
w1
s2 c3
w2 s1
c1
w2 s1 c2
w2 s2
c1
w2
s2 c2

        这张表中,w,s,c之间是非平凡多值依赖的关系,而且不是函数依赖的关系。所以这张表,表示的关系模式不满足第四范式。

        码:W,S,C

        举例:

        关系模式:WSC(W,S,C)W表示仓库,S表示保管员,C表示商品。每个仓库有若干保管员,若干商品,每个保管员所在仓库的所有商品,每种商品被所有它所在的仓库的保管员所保管。(假设仓库 有两个保管员 ,存放三个商品 ;仓库 有两个保管员 存放两个商品

        T是随便加入的一列,可以理解成保管员S对货物C完成某项操作花费的时间。(意义在于它不是W或S或C的属性)

W S C T(时间)
w1
s1
c1

10
w1
s1
c2
20
w1
s1 c3 30
w1
s2
c1
...
w1 s2 c2
...
w1
s2 c3
...
w2 s1
c1
...
w2 s1 c2
...
w2 s2
c1
...
w2
s2 c2
...

        这张表中,w,s,c,t不再有多值依赖的关系。(要从整张表来看)

        码:(W,S,C)

        满足第二范式,第三范式,BC范式,且没有多值依赖。

        这个关系模式满足第四范式。

总结:

    第一范式最简单,它只要求属性的原子性。

    第二范式要求排除非主属性和码之间的部分函数依赖关系。

    第三范式要求排除非主属性和码之间的传递函数依赖关系。

    BC范式要求排除主属性和码之间的部分函数依赖关系和传递函数依赖关系。

    第四范式要求排除非平凡多值依赖且非函数依赖的关系。

        其中第四范式最难理解,其实从实用的角度出发,我们就能理解了:

    当表中有全排列的数据时,没有必要全部存储,因为我们完全可以计算出所有的全排列。有100x100的数据的时候,我们存成两张表就是一共200条数据,但是要以全排列的规则,存到一张表里,就是1000 0000条数据。(当然,这样做的坏处就是速度慢了,所以实际工作中,我们因地制宜。土豪公司完全可以疯狂买服务器,用钱砸掉第四范式的约束。)