数据库系统原理2022年总结

关系演算的安全性 #

• 注意，关系代数必然是安全的，因为他在有限的集合上执行有限的运算。
• 定义关系演算的安全性：如果结果不产生无限集合，或者运算过程中不发生无穷验证，那么这个关系演算是安全的。
• 产生无穷集合
  • 例如 ${t|t\in student \or 2>1}$，因为条件恒为真。结果所在范围与student无关，而是落在一个不可预知的全集中。
• 出现无穷验证
  • 对于全称或存在量词，因为它需要去遍历它要验证的范围，如果这个范围是无穷集合，就会导致无穷验证。

安全元组演算表达式（防止发生无穷验证） #

• 定义DOM（安全约束有限集合），其中包含了元组演算中出现的关系中的属性名。
• 如果要使用全称量词或存在量词，其验证范围不再是给定的范围，而是其和DOM的交集。对于该交集以外的元素，不再进行验证。对于全称量词，默认其为真（因为它遍历只是为了判断是否每个都真）；对于存在量词，默认其为假（因为它遍历只是为了判断是否每个都假）。

数据建模与数据库设计 #

三个世界 #

• 客观现实世界、信息世界、计算机世界。例如一头牛，在现实世界里是动物，在信息世界里是汉语“一头牛”，在计算机世界里可以例如编码成0100 0001.

数据模型与概念模型 #

• 概念模型是对客观世界的抽象，存在于产品设计中。例如E-R图。
• 数据模型是对概念模型的抽象，存在于计算机软件实现中。例如关系模型、非关系模型。

数据建模和数据库设计 #

• 数据建模是把客观世界抽象成概念模型的过程，而数据库设计是把概念模型实现成数据库的过程。

E-R图基本思想 #

• 即实体-关系模型。它认为客观世界都是由实体和他们之间的联系构成的。因此，可以用这种方法进行数据建模。

实体和实例 #

• 实体并不是“单个实际存在的个体”，而是“这样的存在的个体的集合”。这个集合中的元素称为实例。
• 精确到实体中的某一个，称为实例；如果称某一类实体，则成为实体。这是语义上的区别。
• 可以使用属性来刻画一种实体。而对于每个实例，则是这种属性构成的一个个元组。

属性的分类 #

• 单值、多值。
• 单一、复合。
• 可空、非空（SQL语句 not null）。
• 原始、导出。
  • 例如出生年月是原始属性，年龄是导出属性。
• 满足单值、单一属性，即1NF。

实体之间的联系 #

• 指的是一个实体的实例和另一个实体的实例发生了某种关系。
• 实体和联系都是需要命名的。可以采用一个被命名的表去为双方建立这种联系。这样才能发生“读者”“借阅”“图书”，其中借阅就是联系的命名。
  • 换个角度说，如果不命名，就不能区分这两个实体之间的不同联系。例如读者和图书之间除了借阅这种关系，还可以是拥有。

联系的元（度） #

• 这个联系与多少实体有关。（注意是与多少实体有关，而不是其实例）。
• 一元联系
  • 例如零件A由零件B和零件C装配而成。
  • 其中，零件A、B、C是“零件”实体的三个实例。
• 二元联系
  • 例如读者借阅图书
• 三元联系
  • 例如供货商、商品、零售商之间的联系
  • 因为这个联系涉及了三方。

角色 #

• 考虑零件A由零件B和零件C装配而成。其中，零件A、B、C是“零件”实体的三个实例。
• 如何区分这三个实例在这个联系中发挥的作用？引入角色的概念。即他们三个是不同的角色。
• 当同一实体的不同实例参与联系，为了区分他们的作用是不同的，需要显式地指明其角色是什么。

实体的映射基数 #

• 二元联系的分类
  • 一对一联系：例如店长和店面
  • 一对多联系：例如画家和它的画
  • 多对多联系：例如学生和课程
• 映射基数
  • 所谓基数，即一个实体的实例通过联系，能与另一实体中的多少个实例相关联。例如如果是多对一，那么这个实体的一个实例就能与对方实体中的多个实例建立联系。
  • 常用映射基数表示，即(1:1)、(1:m)、(n:m)。
• 映射基数是很关键的，涉及到如何进行数据库设计。
  • 例如一对一或一对多的情况，可以使用外码依赖实现。
  • 但是多对多无法使用外码依赖，否则不满足1NF。此时需要采用额外的联系表，例如我的Nesto中的 GroupPermission表。
• 实体的映射基数是根据参与联系的双方实体而定的。并不是关系所决定的。
  • 例如画家和它的画，画家参与该联系的映射基数是1对多的，而画参与该联系的映射基数是1对1的。

m对n映射的正确理解 #

• 虽然其定义是“m个A实体的实例可以与n个B实体的实例发生关系”，但是实际上对于单个实例，例如A实体的一个实例，它只能完成1对n的映射，而不可能是m对n的。所以m对n的定义是个谬论。其准确的理解应该是对于一方的一个实例，他可以进行1:m的映射；对于另一方的一个实例，其可以进行1:n的映射。

实体参与联系的方式：部分参与和完全参与 #

• 如果该实体中的实例都能参与到联系中，该实体完全参与该联系；如果该实体中存在没有参与到联系中的实例，那么该实体部分参与该联系。
• 在数据库设计时，如果是完全参与，那么其外码属性或额外联系表中它的主码那一项必须是非空属性。否则就可以是允许空属性。

E-R图表达：Chen方法 #

chen方法也就是属性需要写在圈圈里面，然后都连到关系上的那种表达方式。这比较繁琐，并不是工程中所使用的。

• 联系采用菱形框表示。所以很多圆形连接在矩形框上，表示这个矩形框表示的实体由这些圆形表示的属性来刻画；两个矩形连接在一个菱形框上，表示这两个实体参与了这个菱形框表达的联系。

• 多值属性采用双线的圆圈，导出属性采用虚线的圆圈。

• 复合属性采用层次表达，即一个圈可以继续连接其他圈，理论上可以构成一棵树；也可以采用编号的方式表达，不同属性之间编号相同的属于同一个复合属性。

• 实体参与数量和映射基数（箭头表述）

  • 联系向其连接的实体分别射出箭头或射线。有箭头的称为“1端”，没箭头的称为“多端”。

    • 如果都是箭头，那就是1对1；

    • 如果A是多端，B是1端，那么A到B的映射是1对1的，而B到A的映射是1对多的。

      • 注意，自己所连接的那根线和自己参与联系的情况没有任何关系。你要看对面那根线。

    • 如果都没有箭头，就是m对n的。（而且不能准确给出到底是多少对多少）

  • 如果是单线，就是部分参与；如果是双线，就是完全参与。

    • 假设联系到A的是双线，到B的是单线，那么A全部参与了该联系，B部分参与了该联系。

• 实体参与数量和映射基数（数字表述）

  • 理解方式和箭头法类似。只不过不通过箭头区分，而直接在上面标数字。仍然要注意，自己所连接的那根线和自己参与联系的情况没有任何关系。你要看对面那根线。
    • 例如连接实体A的线上写了a，连接实体B的线上写了b，那么A参与联系的映射基数是1对b的，B参与的则是1对a的。
  • 此外，可以采用范围表示法，例如A处的线上标称的数字是1..n，那么B参与该联系可以是1对1到n之间任何数字的联系，注意最小是1，所以B属于完全参与。如果标称 0..n，那就是说B是部分参与了（因为B中的1个实例可以不与A中的任意实例对应，也就是null）。
  • 参与数量情况和箭头描述一样。都是单线、双线法。因为引入了上述的范围表述，因此可以通过修改最小值，同样能达到参与情况的表述目的。

E-R图表达：Crow’s Foot方法 #

• 即采用矩形来表示关系，且把属性写在矩形里面。即Nesto采用的方法。

E-R图表达：IDEF1x方法 #

重要概念 #

• 实体被分成了强、弱实体。
• 联系被分成了可标定连接联系和非标定连接联系、分类联系、非确定联系。

强实体和弱实体 #

• 如果该实体能被其主码唯一确定，则这是强实体。
• 如果该实体不能通过其主码而唯一确定，而需要其他实体的码来进行标定。用于标定它的这个实体的码和它本身用于区分的字段共同构成了码。
  • 例如：合同、合同条目。合同条目中的用于区分的字段为“合同条目号”，合同中的主码字段为“合同号”，那么在合同条目表中，仅凭借合同条目号不能区分每个条目，因为这个合同条目号是相对于一个合同的，于是会出现很多个“第一条”，很多个“第二条”之类的。此时，如何区分他们？如果我们说“第一个合同的第一条”，“第三个合同的第五条”就能区分了。所以，应当再从合同实体中，把它的码继承过来，于是继承后的合同条目的各属性就变成了“合同号|合同条目号|….”，然后其中的“合同号|合同条目号”两个字段共同构成了合同条目的主码。
  • 因此，弱实体不能独立于强实体而存在，否则无法实现上述继承，导致不满足实体完整性约束。

分类联系 #

• 一般实体是对一类分类实体的抽象。它具有比较一般化的特征，而分类实体可以继承一般实体的基本特征，并且添加自己的其他特征。
• 但是注意，分类实体和其一般实体往往具有相同的主码字段。
• 一般实体中有一个“鉴别器属性”，通过它可以确定应该属于哪个分类。从而建立了“分类联系”。
• 属性继承
  • 低层实体（即比较具体化的实体）中包含了高层实体（即一般实体）的所有属性。而且共用主码。
• 例如零件表
  • 零件是一个一般实体，它具有例如编号（主码）、尺寸、名称等属性
  • 外购零件和自制零件是两个继承自它的分类实体，外购的可能有价格，自制的可能有工序。但是他们的主码应该都是编号，这一点和零件（一般实体）相同。
• 泛化和具体化
  • 具体化
    • 自顶向下。
    • 一个一般实体加上不同的属性可以获得不同的分类实体。例如学生+论文=研究生，学生+军训=本科生。
  • 泛化
    • 自底向上。
    • 多种分类实体可以抽象成一个一般实体，多个这样的一般实体相对其更高级的一般实体也能继续抽象。
• 在数据库中的表示
  • “ISA”。它表示具体化、泛化（或者说就是一个分类联系）。

概念模型向逻辑模型的转化 #

数据库设计的步骤 #

• 需求分析
• 概念数据库设计——设计出E-R图或IDEF1x图
• 逻辑数据库设计——把E-R图转换为关系模型
• 物理数据库设计——CREATE TABLE…

E-R图到关系的基本转换 #

• 实体转换为关系
• 属性转换为关系的属性
• 如何对特殊属性进行转换
  • 复合属性
    • 取代法：把复合属性用其包含的各个字段原地取代
    • 摆烂法：或把复合属性当成简单属性直接转换
  • 多值属性
    • 将主码和该多值属性单独拿出来作为一个关系。
    • 例如Nesto中的GroupPermission。
• 如何对特殊联系进行转换
  • 非全参与的一对一联系（0..1联系）
    • 将该联系定义为一个关系。属性采用各自的主码进行拼凑。
    • 例如配偶关系：一个职工实体上可以有一个配偶关系，由于是配偶所以是一对一联系，由于有人单身所以是非全参与。则单独把“配偶关系”拿出来作为一个关系，其属性是丈夫的ID、妻子的ID（可见由双方主码构成）。
  • 有一方全部参与的一对一联系（一边1..1，另一边0..1）
    • 将部分参与方关键字纳入到全参与方属性
      • 注意：怎么看是全参与方还是非全参与方？假设全参与方出现了不参与的情况。看是否符合常理。
    • 例如员工和部门的关系：员工不一定是经理的身份，但是部门必须要有经理在管理，且一山不容二虎。所以员工部分参与管理了部门且是一对一的，而部门全部参与且一对一地被管理。因此只需在全部参与一方（即部门表）中把员工的ID纳入到属性中，表示这个部门由谁在管理。
  • 一对多联系
    • 将单方的关键字纳入多方的属性
      • 注意：怎么看是单方还是多方？假设一方只有一个实例，看会有什么情况出现。那根据“一对多”的定义，其对方必然出现很多实例，很多实例那个就是多方。
    • 例如班主任和学生的关系，老师可以是多个学生的班主任，但是一个学生只能由一个老师担任班主任。此时在多方（学生方）纳入一个教师ID。
  • 多对多联系
    • 双方主码单独拿出来作为一个关系。
    • 例如Nesto中的GroupPermission。
  • 多元联系
    • 例如三个之间的联系：供货商、零件、工程项目。
      • 法1：必须非空
        • 转换为supply(工程项目，供货商，零件，联系集上的属性例如数量)
        • 因为三者共同构成主码，所以都必须全参与。不能空。
      • 法2：可以空
        • 转换为supply(条目号，工程项目，供货商，零件，联系集上的属性例如数量)
        • 好处：因为现在条目号做主码了，所以现在三者可以随意摆烂了。
      • 法3：转换为 $C^2_3$ =3个2元关系分别表示。
• 如何对特殊实体进行转换
  • 弱实体
    • 把弱实体的各属性连同其依赖的实体的主码一起构成一个关系
    • 也就是模仿了把依赖的实体的主码继承下来的过程
  • 泛化实体和具体化实体
    • 一般情况下，具体化实体只需要建立其新增的属性，然后纳入对应泛化实体的主码。（这是根据分类关系的定义。）
      • 例如学生具体化成了本科生，那么可以建立学生（sid，name），本科生（sid，军训），研究生（sid，论文）。可见，在具体化实体中，不再需要包含高层实体的除主码外的其他属性了。
    • 如果某泛化实体的各具体化实体包含了其全部，也就是例如上面的例子，一个学校的学生全都是本科生或研究生，不包括既不是本科生又不是研究生的无业游民，那么就可以不建立学生表（即那个泛化实体），而只去建立本科生（sid，name，军训），研究生（sid，name，论文）。也就是把高层实体的所有属性都纳入了。
      • 好处：查询具体实体不需要查询俩表了（先具体实体表，然后泛化实体表）。坏处：有冗余。

转换过程中出现的问题 #

• 不使用外码而导致的问题
  • 受控冗余
    • 例如把教师的详细信息直接存到每个学生身上，那么教师就算变更一点信息也需要遍历每个学生。
  • 插入异常
    • 例如新学生入学，还没有分班，故班级为null，则插不进去。
  • 删除异常
    • 例如一批学生毕业，如果某专业的学生全都毕业了，那这个系就消失了。

什么是数据库设计理论 #

• 数据库设计理论由数据依赖理论、关系范式理论、模式分解理论构成。
• 数据依赖理论包括函数依赖、多值依赖。
• 关系范式理论包括1NF、2NF、3NF、BCNF、4NF。
• 模式分解理论包括无损连接分解、保持依赖分解。

数据依赖理论 #

函数依赖 #

• 定义
  • 对于属性集合 $U={A_1,A_2,…,A_n}$，构成了一个关系模式 $R(U)$ 。
  • 且，对于关系模式U，有 $X\sub U,Y\sub U$。
  • 则对于 $R(U)$ 的任意一个可能的关系r，r中不可能存在两个元组，使得他们落在X中的属性的值相等，而落在Y中的属性的值不同。
  • 则称X函数决定Y。X->Y。
• 示例
  • U={sno，sname，sage，class，monitor，cno，score}，则{sno}函数决定了{sname，sage}。其中，X={sno}，Y={sname，sage}。
• 理解
  • 函数依赖是同一关系的属性值之间的取值约束关系。
• 特殊的函数依赖
  • 平凡的函数依赖
    • 若 $Y\sub X$，则是平凡的函数依赖。因为这是必然成立的（全集推子集）。
  • 恒成立的函数依赖
    • 如果在r中找不出落在X中的属性值相同的两个元组，则对于任意的Y，函数依赖X->Y恒成立。
  • 完全函数依赖和部分函数依赖
    • 如果任意 $X'\sub X$，X’都不能决定Y，则X->Y是完全函数依赖。也就是说X是可以函数确定Y的最小集合。这类似于候选码和超码的关系：完全函数依赖相当于候选码，部分函数依赖相当于超码。
    • 如果存在部分函数依赖，则说明存在冗余。
  • 传递函数依赖
    • 若X->Y,Y->Z成立，且他们都不平凡，且Y不能决定X，且Z不能包含于X，则这是一个传递函数依赖。（即X->Y不平凡，Y->Z不平凡，X->Z不平凡。）
    • 如果存在传递函数依赖，则说明存在冗余。

码 #

• 候选码和超码
  • 对于 $K\sub U$，如果K能够完全函数决定U，则称K是候选码。
  • 主码可以在任意一种这样的候选码中产生。
  • 非主属性是不包含在任何候选码中的属性。
  • 若此时还有 $S\sub K$，则S是超码。
• 外码
  • 如果有属性集合 $U_1,U_2$，有属性集合 $X\sub U_1$，但是X不是$R（U_1）$的候选码，却是 $R（U_2）$的候选码，则X是外码。

逻辑蕴含 #

• 是隐含的函数依赖。根据一些现有的函数依赖，能推出来新的这个函数依赖，则称现有的函数依赖集逻辑蕴含了这个新的函数依赖。
• 设关系模式R(U)有函数依赖集F，如果从F所包含的函数依赖中能推出函数依赖 X->Y，则称F逻辑蕴含X->Y。

函数依赖集闭包 #

• 现有函数依赖集F，该F逻辑蕴含的所有函数依赖构成了F的闭包，记作 $F^+$。
• 因此，即便是小小的F，也可以有大大的能量。只要它蕴含得够有深度，$F^+$也可以很大。如果一个 $F=F^+$，那么称这个F是完备的函数依赖集。

推导逻辑蕴含的利器：函数依赖的Armstrong公理 #

• 前提：已知关系模式 $R(U,F)$。其中U是关系模式的属性集，F是关系模式的函数依赖集。
• A1：自反律
  • $Y\sub X\sub U$，则X->Y $\in F^+$.
  • 属性集能函数决定它的子集。
• A2：增广律
  • 则X->Y $\in F^+$，则XZ->YZ $\in F^+$.
  • 两边同乘，仍然成立。
• A3：传递律
  • X->Y $\in F^+$，Y->Z $\in F^+$则X->Z $\in F^+$.
• 推论：被决定方的分解与合并
  • B1：合并律：合并两个被决定方
    • X->Y $\in F^+$，X->Z $\in F^+$，则X->YZ $\in F^+$.
  • B3：分解律：把两个被决定方分解开
    • $Z\sub Y$，X->Y $\in F^+$，则X->Z $\in F^+$.
• 推论：条件扩大
  • B2：伪传递律
    • X->Y $\in F^+$，WY->Z $\in F^+$，则WX->Z $\in F^+$.

Armstrong公理是完备的 #

• $F^+$逻辑蕴含的任何函数依赖都能通过A1、A2、A3在F上推出。

属性集闭包 #

• 现有函数依赖集F，属性集U，他们构成关系模式 $R(U,F)$，现在有一属性集 $X\sub U$，定义 $X^+_F$为X在函数依赖集F的逻辑蕴含下，能够函数决定的所有属性构成的集合。即 $X^+_F={A|X\rightarrow A\in F^+}$.
• 注意理解
  • 属性集闭包是属性的集合，而不是函数依赖的集合。因此上面给出的定义中，集合的描述元素是属性A。（Attribute.）
• 求属性集闭包的算法
  • 输入：属性集X，函数依赖集F；输出： $X^+_F$.
  • 初始化结果集合为给定的X集合。
  • loop：对于结果集合的每个属性子集，如果它能通过给定的F通过Armstrong推出能够函数决定的新的属性，就把这个新属性加入结果集合。
  • 如果结果集合不再发生改变，则算法停止，否则jmp loop。

属性集闭包引理 #

• $X\rightarrow Y\in F^+ \iff Y\in X^+_F$.（注意是充要条件。）
• 因此，可以通过求属性集闭包来判断函数依赖 X->Y是否 $\in F^+$。这样就不用求F+了，因为几乎没法求。

函数依赖集的覆盖关系 #

• 概念

  • 现有属性集U，函数依赖集F、G，如果对于 $R(U)$，有 $F^+=U^+$，则F和U互相覆盖。如果他们互相覆盖，那么他们等价。

  • 覆盖是基于闭包的。也就是说，如果G的闭包 $G^+$ 能够包含了F的闭包 $F^+$ ，那么F被G覆盖。

• 理解

  • 函数依赖集的闭包才是这个函数依赖集的本体啊！因为等价是根据闭包来判断的，而不是函数依赖集本身！也就是说，就算函数依赖集本身发生变化，如果其闭包不变，则仍然等价，相当于没有发生变化。

  • 数学中，等号是最重要的，它决定了万物法则。所以我们只能通过函数依赖集闭包来判断两个函数依赖集的关系，而不能通过其本身来判断。

函数依赖集的最小覆盖 #

• 函数依赖集的最小覆盖是一个函数依赖集。它是最小的能覆盖住现有函数依赖集的函数依赖集。

  要注意区分最小覆盖和覆盖：覆盖只是两个函数依赖集之间的一个关系，而最小覆盖是一个函数依赖集。即一个是关系，一个是集合。

• 前提：一个引理

  • 引理：每个函数依赖集F都能被一个里面都是形如 $X\rightarrow A$（即右边都只有一个属性）（注意，A是Attribute，只是一个属性，但是X可以是集合）的函数依赖集G所覆盖。也就是说，任意的函数依赖集都等价于一个上述这种最简形式的函数依赖集。

• 概念

  • 现有函数依赖集F，如果F同时满足下列三个条件，则F是一个最小覆盖（又称最小依赖集）
    • 后件是单属性 F中的函数依赖都是形如 $X\rightarrow A$的（即右边都只有一个属性）（注意，A是Attribute，只是一个属性，但是X可以是集合）。
    • 没有多余函数依赖 F中不存在多余的函数依赖，凡是只要去掉一个，$F^+$就变了（该函数依赖集和原来不再等价了）。
    • 没有多余属性 F中不存在多余的属性，凡是只要去掉一个（当然同时也要去掉其关联的函数依赖），$F^+$就变了（该函数依赖集和原来不再等价了）。
  • 也就是说，最小覆盖是最小的那个能保持 $F^+$的性质的那个函数依赖集。对于同一个 $F^+$，它可以有很多种等价的F表示，但是最小覆盖是“最小”的那个。上面三条同时满足能保证他“最小”。

• 定理

  • 每个函数依赖集都有其最小覆盖。

• 求解算法

  • 输入：函数依赖集F；输出：函数依赖集最小覆盖F'。
  • 首先根据引理，找出与F等价的那个包含函数依赖都是形如 $X\rightarrow A$的（即右边都只有一个属性）的函数依赖集作为结果集合。
  • 考虑结果集合的每一个依赖 $X\rightarrow Y$，如果删去仍然能保持和原来等价，则删去；
  • 考虑结果集合的每一个属性Z，如果把他删除（连通它所在的函数依赖中），如果删去仍然能保持和原来等价，则删去；
  • 于是，得到了和原来F等价的结果集合，输出。

关系范式理论 #

1NF #

• 不允许复合属性、多值属性这两种特殊属性的，即为满足1NF。
• 例如下面的情况：

|   person   |
|phone|passwd|
|12..3|asdaw |
...
|72..1|mdd2w |

• 可见，person下又分出来两个字段，则person这个表头相当于做了合并单元格操作。
• 或者说，1NF不允许关系进行嵌套。因此字段不可再分。

转换为1NF #

• 消除多值属性、复合属性。从而都转换为简单属性。
• 参考“概念模型转换为关系模型”。

2NF #

• 对于依赖于候选键的非主属性，如果该非主属性对候选码没有不完全依赖的，即为满足2NF。
• 可以消除数据冗余。
• 例如候选码是{sno,cno}，非主属性有cn、sd。有 sno->sd $\in F$, sno->cn $\in F$，那么{sno,cno}->sd、{sno,cno}->cn，不满足2NF。

判断是否为2NF #

• 找出候选码、非主属性，并找出候选码参与的部分依赖。
• 例如学生（学号，姓名，班级，课程号，课程名，成绩，教师，教师职务）
  • 找出候选码：{学号，课程号}
    • 因为这里面有学生信息，还有课程信息，所以候选码由两个ID构成！
  • 找出非主属性：姓名、课程名
  • 找出候选码参与的部分依赖：{学号、课程号}->姓名

分解为2NF #

• 拆成2个关系。其中一个旨在把候选码拆成更小的候选码，同时把非主属性包含进来，从而让拆分后的小候选码能够完全决定非主属性；另一个关系保留原来的候选码的情况，其它剩余的属性包含进去。
• 例如
  • 上例中可以把sno、sd和cn拆到一个关系中，这样sno在这个关系中是候选码，而且能完全决定sd和cn这两个非主属性了。
  • 剩下的关系中仍然保留sno和cno，因为他们还得做候选码呢。
• 实际上可以随便拆。只要保证不改变意思，且满足2nf即可。

3NF #

• 对于依赖于候选键的非主属性，如果该非主属性对候选码没有传递依赖的，即为满足3NF。
• 可以消除数据冗余。
• 例如候选码是{sid,pid}，非主属性是mgr，现在有{sid,pid}->did，{sid,did}->mgr，则mgr通过传递依赖来依赖于候选码。
• 和2NF的关系：如果满足了3NF，则必然满足2NF。

分解为3NF #

• 为F中的每个函数依赖都建立一个关系模式。这样就不可能出现传递了。
• 如果过多，在满足3NF的情况下可以合并一下。

BCNF #

• 所有非主属性都得依赖于候选码，即为满足BCNF。
• 例如候选码是{城市，街道}，现在有 {城市，街道}->邮政编码，邮政编码->城市，则存在“邮政编码->城市”导致不满足BCNF。但是它满足3NF，因为这并不是一个传递依赖（因为A->B,B->C，而A->C是平凡的，不算作C传递依赖A。）。

分解为BCNF #

• 给定函数依赖集F，把其中左边不是候选码的函数依赖都单独拿出来分别作为关系模式，剩余的自己组成一个关系模式。
• 如果有必要，可以合并。
• 例如U={A,B,C,D,E,F,G}，给定F={A->B,A->C,C->D,C->E,E->FG}，可以确定候选码A，则A->B,A->C是符合要求的，但是C->D,C->E,E->FG不符合要求，所以分解成如下几个关系：{R1(C,D),R2(C,E),R3(E,F,G),R4(A,B,C)}。这样一来，R1的候选码变成了C，从而满足了BCNF，其他类似。对于R4，其天生满足BCNF。此外，可以合并R1、R2.

模式分解理论 #

存储 #

磁盘读写时间的计算 #

• 先寻道：磁头移动到正确的磁道上方。
• 再旋转：磁头到了正确的磁道上，这个时候旋转才有用
• 最后传输。

提高访问速度的方式 #

• 降低IO次数
• 降低排队等待时间
• 降低寻道时间
  • 磁盘块连续存储
  • 多柱面并行存储（因为一次读取能把各盘面上的当前扇区都拿到）（对于老式磁盘，是这种情况）
  • RAID多体交叉思想

RAID #

• 多体交叉拆分算法
  • 不同的拆分算法可以实现不同的并行方式。
  • 比特级拆分：对字节进行拆分，把一个字节拆成8个bit，每个bit分别存在不同的并行磁盘上
  • 块级拆分：对文件进行拆分，把文件的不同块存在不同的并行磁盘上。
• RAID0
  • 没有冗余，只实现并行存取
• RAID1
  • 完全冗余，直接镜像一份
  • 例如原来需要4块磁盘，那我再加4块，把内容复制一遍
• RAID2
  • 基于比特级拆分。
  • 采用4-3码（海明码）校验。因此，磁盘的分配比例是4数据：3校验。
• RAID3
  • 采用Bit－interleaving（数据交错存储）技术，它需要通过编码再将数据比特分割后分别存在硬盘中（Wikipedia）
• RAID4
  • 基于块级拆分。其他同RAID3.
• RAID5
  • 基于块级拆分。
  • 在RAID4的基础上，使5个盘互位校验盘，解决了RAID4中，校验盘成为性能瓶颈的问题（且磨损严重）。

DBMS索引和Inode表的关系 #

• DBMS可以利用OS的FAT表先占用一些磁盘块。然后，就可以使用自己的索引去更加高效地管理这些磁盘快了。

• 索引能给出表项具体在哪个磁盘块上。

  区别：OS给出的是文件在哪个块上，DBMS给出的是表在哪个块上。

三级结构，两层交互 #

• 磁盘
  • 存储数据库的真正数据
• 内存（缓冲区）
  • 存储当前需要进行交互的数据。必须把磁盘中的块读入内存（我们认为磁盘快和内存页是一样大的），CPU才能处理。
  • 负责协调内存空间和磁盘之间关系的，是缓冲区。
  • 缓冲区掌握了内存页和磁盘块的映射索引，实现与磁盘的交互（读入写回）。
  • 缓冲区还掌握了记录和其所在页的映射索引，实现与DBMS的交互（数据缓冲）。
• DBMS
  • DBMS掌握了一套索引。内容是哪个记录在哪个磁盘块上（实现宏观上的与磁盘的交互。但是，实际上中间通过缓冲区实现具体IO细节，但是对DBMS来说，它可以实现直接根据自己的索引表去访问磁盘块上的记录）。
• DBMS和磁盘通过缓冲区交互的过程
  • DBMS需要访问一个块，缓冲区读入这个块到内存，建立记录和内存中指针（页）的索引（这是给DBMS看的），建立该页和磁盘快的索引（这是给磁盘看的），牵线搭桥，完成了任务。

数据存储与查询实现 #

• 自底向上，DBMS的存储查询实现是：
• 存储管理器
  • 处于系统最底层，负责控制磁盘读写，对上层提供块读写接口
• 缓冲区管理器
  • 负责管理内存缓冲区，控制内存分配
  • 实现DBMS和外部存储器之间的通信
• 索引文件记录管理器
  • 负责管理DB的三块信息：操作计划、数据模式、数据控制信息。
  • 这三块信息分别由DML引擎、DDL引擎、DCL引擎操作和控制。
• 三个引擎
  • DML引擎、DDL引擎、DCL引擎分别接受经DML编译器、DDL编译器、DCL编译器编译得到的执行序列，进行实际操作。
  • 各种操作的实际实现是经过了“三级结构，两层交互”。
• 三个编译器
  • DML编译器、DDL编译器、DCL编译器负责接受用户输入的DML、DDL、DCL命令并编译，供引擎来执行。
  • 特别地，DML编译器会把算法库中的各种算法进行选择性组合，给出调用顺序，生成查询计划。该查询计划可以传递给DML引擎。DML引擎执行计划的时候，还会再去调用算法库，实现查询操作。

记录的存储 #

• 定长和变长
  • 定长存储
    • 可以直接根据长度偏移量得出这是哪条记录
  • 变长存储
    • 按指针定位
    • 按定界符（开始结束标志）定位
• 跨块和非跨块
  • 跨块存储
    • 如果这个块剩下的空间不够存一条记录，那就能存多长存多长，然后从下一块开始处继续存。中间用指针链接。
    • 问题：块之间有关联，对这些块难以并行操作
  • 非跨块存储
    • 空着。
• 块分配方式
  • 连续分配
    • 存在扩展问题，但是速度快
  • 链接分配
    • 速度慢
  • 按Segment分配
    • Segment是若干连续磁盘块。不同Segments之间可以用指针链接
    • 这是前两种方法的折中，兼顾了二者优点
  • 索引分配
    • 类似FAT

文件组织 #

• 无序记录文件（堆文件）
  • 每次来了新记录都加在尾部
  • 删除记录只需要标记一下，然后来新记录可以优先从这里面找（但是可能因为前后记录大小不同造成内碎片）
  • 数据库重组：压缩内碎片，提升效率
• 有序记录文件（排序文件）
  • 查找效率高，可以折半搜索
  • 用于排序的字段称为排序字段、排序码
  • 插入慢
  • 可以引入“overflow表”来给插入提速，overflow表类似于一个堆文件。可以预见，当overflow表很大时，有序记录文件的查询效率向堆文件靠拢。
  • 数据库重组：把overflow表并入排序文件。
• 散列文件
  • 一般情况下一个桶对应一个块。通过表的某字段计算其散列，得到对应的桶。用于计算的这个字段和上面一种方法类似，称为散列字段、散列码。
  • 如果发生哈希碰撞，桶就对应不止一个块了。这个时候每个桶可以看做一个小的堆文件。
  • 桶是有大小的。如果碰撞过于离谱，可以使用overflow桶。即：在桶的尾部加一个指针，连接到新桶，从而扩容。通过这种方式，可以无限扩容一个桶。
• 聚簇文件
  • 把某一字段的值相同或相似的记录尽量放在连续的块。
  • 如果几个表相互关联，把他们按“相似”处理，可以对多表查询的情况进行提速。

Oracle数据库结构 #

• 逻辑存储层
  • 表空间：是整个数据库的顶级结构。数据库本身有一个系统表空间（SYSTEM），存储数据库各项信息。用户可以创建表空间，并自己命名。
    • 表空间即表的存放空间。一个表空间可以有多个表。
  • 操作系统文件：一个表空间可以由一个或多个操作系统文件构成。但是一个操作系统文件只能与一个数据库相连，显然这是一个单向的一对多的关系。
    • 因为多个文件构成一个表空间，所以操作往往是跨文件的。
    • 操作系统文件的作用只是用于占位，以保证OS和DBMS的一致性。这个可以类比Windows下的Pagefile。文件把这块空间划定了，这块空间就归DBMS管了。DBMS直接从OS处接管这块空间的存取控制。
    • 表和文件之间没有对应关系。一个表可以存放在多个文件中。（文件只是起到占位作用。实际怎么存还是看在哪些块上。）
• 物理存储层
  • 物理存储层是逻辑存储层的直接下层。为其提供存储服务。
  • 段：分配了一段特定数据结构的盘区。
    • 分为数据段、索引段、临时段
    • 段和表之间没有数量上的对应关系。可以是任意对任意的。
  • 盘区：特定数量的连续数据块。该“特定数量”可以需求视情况由DBMS管理员动态调整。
    • 按盘区访问数据库，盘区大小很关键。如果数据库很大，显然大盘区访问会更容易找到目标。
  • 数据块
    • 是最小的IO单位。

事务概述 #

事务的定义 #

• 数据库提供的控制数据操作的手段。通过该手段，程序可以把一系列一系列操作作为一个整体进行操作和控制，并能够保证一致性的状态转换。
• 从程序员的角度，一系列SQL语句的整体执行就可以看作一个事务。
  • 由程序员提出，并开始执行；在结束时，可以提交commit或撤销rollback。
• 事务以开始执行SQL语句为开始标志，以commit或rollback为结束标志，不一定非要有begin transaction或end transaction。
  • 有多少次commit或rollback，就产生多少个事务。
• 具有ACID特性的操作称为事务。

为什么需要事务的并发控制 #

• 多个事务可以并发执行。如果不加以管理，会导致数据的不一致性。
• 在事务并发时，通过对SQL语句操作的顺序进行合理安排，来保证事务宏观的独立性、完整性、正确性，就是事务的并发控制。
• 三种典型的不一致错误：损失修改、不能重复读、脏读

事务的特性：ACID #

• Atomicity原子性
  • 事务包含的操作要么都不做，要么一次性都做完。
• Consistency一致性
  • 保证在事务并发过程中，仍保证数据的一致性（即不能出现上述三种不一致性错误）
• Isolation隔离性
  • 事务在并发的过程中仍然要保持独立。互相不能影响结果。
  • 例如就算是T1、T2两个事务并发执行、其结果应当等效于先T1、后T2，或先T2、后T1.
• Durability持久性
  • 持久性包含两个方面：
  • 保证提交是持久的。已提交的数据应当写在了磁盘上，不应丢失。
  • 被撤销事务的影响是可恢复的。

重新定义事务 #

具有ACID特性的操作称为事务。

事务管理器 #

• 当应用程序进行SQL操作，事务管理器负责产生一个新的事务，并打时间戳。
• 事务的后续的操作由事务管理器产生、管理。

事务调度器 #

• 对当前存在的所有事务的操作产生一个合理的操作序列。
• 目标：保证一致性。

事务调度与可串行性 #

事务调度 #

• 事务的基本步即事务的基本操作，包括读、写、控制操作（例如加锁、解锁）
  • 事务的基本步可以类比OS中进程调度的机器指令。
• 事务调度即事务的各基本步的一个合理的执行顺序。

串行调度和并发调度 #

• 串行调度：例如当前有T1、T2都要执行，那我真的就是让T1先跑，跑完了才轮到T2.即：先依次执行T1的基本步，然后是T2的。
• 并发调度：例如T1的基本步和T2的基本步是交错执行的。就算只有一个基本步交错执行了，我们也称为是并发调度。
  • 当且仅当T1、T2两个事务并发调度，其结果应当等效于先T1、后T2，或先T2、后T1，才说明这个并发调度是正确的。

可串行性（可串行化） #

• 可串行性是用来衡量并发调度正确性的一个概念。即：不管当前数据库状态如何，这个调度对数据库的影响和某个串行调度相同，则说明这个调度是可串行化的，或具有可串行性。
• 当T1、T2两个事务并发调度，其结果确实等效于先T1、后T2，或先T2、后T1，那就是说这是个可串行化的并发调度了。

充分不必要 #

可串行化调度一定是正确的并行调度，但是正确的并行调度不一定可串行化。

可串行化调度是并行调度的子集。

等效串行序列 #

• 可串行化的并发调度的等效串行序列不唯一。
• 例如上面说的既可以等效为T1再T2，也可以是T2再T1.

表达模型 #

$r_T(A)$表示事务T读A元素。 $w_T(A)$表示事务T写A元素。这两个操作属于基本操作（基本步）。

冲突 #

• 冲突的定义
  • 调度中的一对连续的动作，如果他们俩调换顺序，那么所涉及的事务中至少一个的行为发生改变。
• 如果两个操作有冲突，那么他们不能交换次序。否则，可以交换。
• 常见冲突
  • 同一事务内相邻的两个基本步肯定冲突。否则就改变了编写这个事务的本意。
  • 不同事务对同一元素的紧挨着的写操作是冲突的。
  • 不同事务对同一元素的紧挨着的一读一写操作是冲突的。

冲突可串行性（冲突可串行化） #

• 如果一个调度，通过交换两个相邻的无冲突操作可以转换到（注意不是等效，而是真的转换得到）某串行调度，那么这个调度是冲突可串行化的。
  • 一般需要一系列交换才能达到目标。

冲突可串行性调度是可串行性调度的子集。

• 冲突可串行性的作用：因为不能直接判断并发调度的正确性，不能直接判断可串行性调度，但是我们可以判断是否具有冲突可串行性。如果具有冲突可串行性，由于包含关系，则我们就判断出了它具有可串行性，也就是说该并发调度是正确的。

因此，冲突可串行性调度是判断某并发调度是否正确的方法。

• 判断是否是冲突可串行化的一般方法：例如基本步序列 $r_2(A);r_1(B);w_2(A);r_2(B);r_3(A);w_1(B);w_3(A);w_2(B)$ ，这里有三个事务 $T_1,T_2,T_3$ ，可以画一个图，其中节点有1、2、3号分别代表这三个事务。观察基本步序列，可以看到$w_2(A);r_3(A)$、$r_2(B);w_1(B)$、$w_1(B);w_2(B)$ 是三对冲突基本步，他们不能交换顺序，也就是说必须保证他们的顺序，也就是说他们直接确定了这三个事务的相对顺序必须满足的条件。根据此，画前驱图：如果事务 $T_1$ 必须在 $T_2$ 之前完成，那么就有一条从1号点指向2号点的边。由此画图，如果最终的图没有环，这就是一个冲突可串行化的调度，且最终的串行化调度顺序就是这个图的拓扑序列。否则如果有环，这就不是一个冲突可串行化调度。可以看出这里在1、2点之间有环，所以~。

基于锁的并发控制 #

并发控制的基本方法（如何产生一个冲突可串行化调度？） #

• 基于封锁的并发控制（本节）
• 基于时间戳的并发控制
• 基于有效性确认的并发控制
• 基于封锁的控制是基于锁的方法；基于时间戳、有效性的属于基于撤回的方法。

锁 #

• 锁是控制并发的手段
• 每一个数据元素都有自己的锁
• 每一事务读写数据元素前，要获得该元素持有的锁；读写完毕后，要释放锁
  • 如果其他事务已经获得该锁，那么当前事务需要进入等待

元素的锁可以理解为该元素有一个初始值是1的信号量。事务相当于是进程。加锁是P，解锁是V。因为信号量初始值是1，所以如果该锁已经被其他事务拿走，新来的事务进入等待。

操作表达模型 #

$L_i(A)$表示事务i对元素A加锁； $U_i(A)$表示事务i对元素A解锁。这两个操作和前面提到的读、写一样都属于基本操作（基本步）。

锁表 #

• 锁表中存储了当前各锁的情况。
• 字段一般是元素-事务-类型。
  • 表示哪个事务对哪个元素加了锁；或是哪个事务对哪个元素加了什么类型的锁。