从冗余到精简：MySQL范式化之道

上期填坑

leetcode, 1791. 找出星型图的中心节点
有一个无向的星型图，由 n 个编号从 1 到 n 的节点组成。
星型图有一个中心节点，并且恰有 n - 1 条边将中心节点与其他每个节点连接起来。
给你一个二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示在节点 ui 和 vi 之间存在一条边。
请你找出并返回 edges 所表示星型图的中心节点

public int findCenter(int[][] edges) {
    int n = edges.length + 1;
        int[] degrees = new int[n + 1];
            for (int[] edge : edges) {
                degrees[edge[0]]++;
                degrees[edge[1]]++;
            }
            for (int i = 1; ; i++) { //星型图中中心节点的度为n-1，其余节点为1
                if (degrees[i] == n - 1) {
                    return i;
                }
    }
}

范式的概念

在设计数据库时，要遵循不同的规范要求，这些规范要求就被称为范式(Normal Form，NF)。范式的作用是使设计的表结构更合理，减少数据的冗余，消除数据增删改的异常; 目前常见的范式分为六种，各种范式呈层级递增，越高的范式数据库冗余越小。具体的关系如下如所示：

六种范式及其关系.png

数据库的码

码又称为键（key），是能唯一标识实体的属性。根据码的范围与性质的不同，有可以分为以下几种：
针对下面的学生信息表，对不同的码进行说明：

     CREATE TABLE student (
    id int(11) NOT NULL PRIMARY KEY         COMMENT '主键ID',
    sno int(11) DEFAULT NULL                COMMENT '学号',
    scardid varchar(255) DEFAULT NULL       COMMENT '身份证号'，
    classid int(11) DEFAULT NULL            COMMENT '课程号'，
    teacher varchar(255) DEFAULT NULL       COMMENT '教师'，
    sinfo varchar(255) DEFAULT NULL  COMMENT '学生信息(包含姓名，性别，年龄)')，
    foreign key classid references class(id)
    )

超码

一个或者多个属性的集合，能唯一标识元组。
如果A是一个超码，那么任何包含A的属性集合都是超码。
在student表中，id，sno，scardid，都可以唯一标识一条数据，它们都是码，亦是超码。那么包含其中任意一个的属性集合也是超码。

候选码

从超码中选出的最小超码，即是候选码。所谓最小超码，就是该超码任意真子集都不能成为超码。
在student表中，候选码有（id)、（sno）、（scardid），那么包含其中任意一个的属性集合，都不在可能是候选码。

主码

即主键，从候选码中选择的，通常选择那些极少改变的候选码。
在student表中，（id)、（sno）、（scardid）都可以作为主码，但是选择了（id）作为主码。
因为主码不可以包含空值，但（sno）、（scardid）默认为空。故不选择。
主码也可以是由多个属性组成。

外码

即外键，另一张表中的主码，表示该表与另一张表中的关联。在student表中，(classid)即为外码。

属性

• 主属性：包含在任一候选码中的属性，即主属性是候选码所有属性的并集。
• 非主属性：除了主属性之外的属性。

函数依赖

定义：设R(U)是一个属性集U上的关系模式，X和Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称“X函数确定Y"或“Y函数依赖于X”，记作X->Y。
说人话就是，在属性集中，确定了属性X，就唯一确定了属性Y，即是Y函数依赖于X。类似与数学中的Y=f(X)函数关系一样。
在student表中，确定了sno(学号)，就唯一确定了sinfo（学生信息），即是sinfo函数依赖于sno，记作sno -> sinfo.

完全和部分函数依赖

在R(U)中，如果X决定Y，并且X存在多个，确定Y时必须依赖全部的X，则称Y对X是完全函数依赖， 确定Y时不必需要依赖全部的X，X中的部分属性就可以唯一确定Y，则称Y对X是部分函数依赖。
假设在student表中，X为（sno，cardid），Y为（sinfo），X -> Y，现在只要知道sno，就可以唯一确定sinfo，那么就说Y部分依赖于X；

传递函数依赖

在R(U)中，Z函数依赖于Y，且Y函数依赖于X，并且Y不函数依赖于X，X不函数依赖于Y，那么我们就称Z传递函数依赖于X。
类似我们数学中学到的大小关系的传递。X -> Y，Y -> Z；X->Z。
在student表中，假设通过sno -> classid，而classid -> teacher ,那么就可以说teacher传递依赖于sno.

六种范式

学习完前置的概念，接下来学习六种范式。

第一范式（1NF）

数据表中每个字段的值必须具有原子性，每一列都是不可分割的基本数据项。

下面的student表就不符合第一范式：

 CREATE TABLE student (
sno int(11) DEFAULT NULL                COMMENT '学号',
scardid varchar(255) DEFAULT NULL       COMMENT '身份证号'，
classid int(11) DEFAULT NULL            COMMENT '课程号'，
teacher varchar(255) DEFAULT NULL       COMMENT '教师'，
sinfo varchar(255) DEFAULT NULL  COMMENT '学生信息(包含姓名，性别，年龄)')，
)

sinfo(学生信息)，它还可以拆分成颗粒度更细的字段，不符合数据库设计对第一范式要求的“每个字段的值必须具有原子性”。将student_info拆分后如下:

CREATE TABLE student (
sno int(11) DEFAULT NULL                COMMENT '学号',
sname varchar DEFAULT NULL              COMMENT '姓名',
ssex varchar DEFAULT NULL               COMMENT '性别',
sage int DEFAULT NULL                   COMMENT '年龄'，
scardid varchar(255) DEFAULT NULL       COMMENT '身份证号'，
classid int(11) DEFAULT NULL            COMMENT '课程号'，
teacher varchar(255) DEFAULT NULL       COMMENT '教师'，

第二范式（2NF）

在满足第一范式的基础上，还要满足数据表里的每一条数据记录都是可唯一标识的，即要有主码。非主属性必须完全依赖于候选码(在1NF基础上消除非主属性对主码的部分函依赖)。
例如，假设在如下student表中，

CREATE TABLE student (
sno int(11) DEFAULT NULL                COMMENT '学号',
sname varchar DEFAULT NULL              COMMENT '姓名',
ssex varchar DEFAULT NULL               COMMENT '性别',
sage int DEFAULT NULL                   COMMENT '年龄'，
classid int(11) DEFAULT NULL            COMMENT '课程号'，
teacher varchar(255) DEFAULT NULL       COMMENT '教师'，

主码都为（sno(学号)， classid(课程号)）,那就可以得出如下的关系：
(sno,classid) -> (sname, ssex, sage, teacher)
但是上面的关系中，还存在着如下对应关系：
(classid) -> (teacher)，这种就违背了第二范式的“非主属性对主码的完全函依赖，对于非主属性来说，并非完全依赖候选码。
为了避免上面的问题出现，我们就需要进行拆分表结构来满足第二范式，拆分方式如下：
student= (U={sno, sname, ssex，sage})
class = (U={classid, teacher})

第三范式（3NF）

在第二范式的基础上，确保数据表中的每一个非主属性字段都要和主码直接相关，也就是说，要求数据表中的所有非主属性字段不能依赖于其它非主属性字段(就是在2NF基础上消除传递依赖)。
在2NF中我们拆分成了满足要求的class表中加两个字段，如下：
student= (U={sno，sname， ssex，sage})
class = (U={classid， teacher，sdept，mname })
要满足第三范式则需要“非主属性字段不能依赖于其它非主属性字段”，
但可以看出class表中的非主属性（teacher，sdept，mname）里面的（sdept, mname）构成了传递依赖，
其中非主属性sdept(专业)依赖于classid(课程号), 而非主属性mname(系主任名称)则可以依赖于非主属性sdept(专业)，
因为通过专业可以找到具体的专业里的系主任，所以需要如下修改，拆分学生表达到第三范式：
student= (U={sno，sname， ssex，sage})
class = (U={classid， teacher，sdept})
dept = (U={sdept, mname})

巴斯科德范式（BCNF）

BCNF只是对第三范式中设计规范要求更强，使得数据库冗余度更小。所以，称为是修正的第三范式，或扩充的第三范式。
BCNF主要就是消除主属性对码（单码或复合码）的部分函数依赖和传递函数依赖
假设有一张表STJ表属性为U={S(学生),T(教师),J(课程)}
如上表关系：每一教师只教一门课。每门课有若干教师，某一学生选定某门课，就对应一个固定的教师
那么其中分析主属性（S,J,P）,候选码为(S,J), (S,T)
由语义可得到函数依赖: (S,J)->T, (S,T)->J, T->J
(S,J)->T：通过学生和课程字段可以得出教师
(S,T)->J：通过学生和教师字段可以得出课程
T->J：因为每一教师只教一门课，所以通过教师可以得出课程
关系模式中没有非主属性对码传递依赖或部分依赖，所以满足第三范式
因为主属性T部分依赖于候选码，所以当前表不满足BCNF。
判断是否为BCNF，只需要判断主属性内部是否存在部分函数依赖和传递函数依赖，如果不存在则是BCNF；

第四范式（4NF）

限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖。
在之前范式中，研究的都是属性的函数依赖关系（X与Y之前的关系），而第四范式研究的更为特殊的多值依赖问题（X、Y和Z之间的关系）。
举例：教师、课程和参考书的关系：
在某个学校中，一门课程可能由多个教师讲授，每个教师可能讲授多门课程。
同时，每本参考书可能被多门课程使用。
这种关系可以通过一个非规范化的关系来表示，其中教师(T)、课程(C)和参考书(B)之间的关系可以表示为Teaching(C,T,B)。
在这个例子中，如果一个课程增加了一名讲课教师或去掉了一本参考书，那么必须插入或删除多个元组，这表明了多值依赖的存在

第五范式（5NF）

也被称为完美范式。它要求关系模式R的依赖关系完全由R的候选码所隐含，即属性均为候选码。
第五范式旨在通过分隔语义连接的关系来存储多值事实，以减少关系数据库中的冗余。

反范式

范式的优点：数据的标准化有助于消除数据库中的数据冗余，消除增删改的异常。
范式的缺点：可能降低查询的效率。
因为范式等级越高，设计出来的数据表就越多、越精细，数据的冗余度就越低，进行数据查询的时候就可能需要关联多张表，这不但代价昂贵，也可能使一些索引策略无效。

范式只是提出了设计的标准，实际上设计数据表时，未必一定要符合这些标准。
开发中，我们会出现为了性能和读取效率违反范式化的原则
通过增加少量的冗余或重复的数据来提高数据库的读性能
，减少关联查询，JOIN表的次数，实现空间换取时间的目的。
因此在实际的设计过程中要理论结合实际，灵活运用。
范式本身没有优劣之分，只有适用场景不同。没有完美的设计，只有合适的设计，我们在数据表的设计中，还需要根据需求将范式和反范式混合使用。
在实际开发设计中，遵循业务优先的原则，首先满足业务需求，再尽量减少冗余。

每日一算

leetcode,108. 将有序数组转换为二叉搜索树给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树。