数据库知识点整理

第一章概述

文件系统：数据以文件形式保存在外存，存取以记录为单位，程序数据有一定独立性，文件与数据一一对应，数据共享性差冗余度大（存储消耗大，容易造成数据不一致性）

数据库系统：数据集成及共享（核心技术：数据模型、数据独立性）
数据库系统管理特点：全组织的复杂数据结构，数据冗余度小易扩充，数据和程序的独立性、映像功能、统一的数据控制、最小存取单位是数据项
数据库中模型分为两类：概念模型（信息模型）、数据模型（层次、网状、关系模型）。概念模型用于现实世界到信息世界，数据模型以计算机系统的形式对数据建模。
数据模型：抽象和表示现实世界中的是数据和信息。（严格定义的概念集合）

概念模型：基于信息世界主要概念，表达应用中各种语义。
概念模型基本概念：
- 实体（Entity）：客观存在并可区分的事物；
- 属性（Attribute）：实体所具有的某一特性；
- 码（Key）：唯一标识实体的属性集；
- 域（Domain）：某个/些属性的取值范围（一组具有相同数据类型值的集合）；
- 实体型（Entity Type）：表示一类实体，用实体名和实体属性来表示；
- 联系（Relation）：实体之间的相互关联，分为一对一、一对多、多对多。
E-R图：描述现实世界的信息及信息之间的联系。用矩形表示实体型，椭圆表示实体属性，菱形表示实体间联系。

联系的语义扩充：存在依赖：实体型B如果依赖实体型A的存在才能存在，称实体型B为弱实体。（如人与子女）

标识依赖：实体型必须通过与其联系的另一实体型共同标识才能确定其唯一性。（如学校与学生）

实体的子类：子类继承父类属性，并附加新属性。
数据模型三要素：数据结构、数据操作、完整性约束。

数据结构：包含对象的类型、内容、性质，以及对象之间的联系。（数据静态特性）

数据操作：对各种对象的实例数值允许执行的操作集合，包括操作及操作规则，主要有检索和更新两大类。（数据动态特性）

数据约束条件：完整性规则（数据模型中数据极其联系所有的制约和依存规则）的集合。
数据模型分类：层次模型（树结构）、网状模型（图结构）、关系模型（二维表）。
数据独立性：应用程序与数据结构之间相互独立的关系。

数据的物理独立性：数据存储结构变化时，数据逻辑结构不变，从而应用不变。

数据的逻辑独立性：数据逻辑结构改变时应用不变。
数据库系统体系结构上具有三级模式两级映像的结构特征。

三级模式：模式、外模式、内模式

两级映像：外模式-模式，模式-内模式

结构：应用-外模式-模式-内模式-数据库
模式：用模式DDL（Data Description Language）写出的一个数据库逻辑定义的全部语句，也称逻辑模式、概念模式，数据库中全体数据的逻辑结构和特性的描述。三级模式的核心，只定义数据的逻辑结构（数据记录结构、数据之间的联系）、数据安全性完整性要求，不涉及数据的具体处理（具体语言和程序）。
外模式：用外模式DDL定义，也称子模式、用户模式，是个别用户的数据视图。通常是模式的子集，对应于应用（一个应用只能启用一个外模式）。
内模式：用内模式DDL定义，也称存储模式，是数据在数据库系统内部的表示。
外模式-模式映像：通过改变映像适应模式变化，使得外模式不变。（数据的逻辑独立性）

模式-内模式映像：通过改变映像适应内模式变化，使得模式不变。（数据的物理独立性）
三级模式两级映像可以保障数据独立性、简化用户接口、有利于数据共享、有利于数据安全保密。
DBMS：数据库管理系统，在操作系统支持下控制。

功能：数据定义、数据存取、数据库运行管理、数据组织管理存储、数据库建立维护

DDL：数据定义语言； DML：数据操纵语言； DCL：数据管理语言。
DBA：建库用库改进，随时监测库性能。

第二章关系数据库

关系：笛卡尔积的子集称为在域上的关系，用表示，是关系的名字，是关系的目或度。
关系可以表示为二维表，每一行是一个元组，每一列是一个域。
属性：每个列附加一个名称，且属性的名字是唯一的。
关系的性质：
- 列是同质的，每一列中分量来自同一域，是同一类型数据；
- 不同列可以来自同一域，不同列必须有不同属性名；
- 列顺序行顺序无关紧要；
- 每一分量必须是不可再分的数据。（满足这一条件称作满足第一范式1NF的）
关系模型的数据结构是关系（二维表）。
候选码：关系中某一组属性，其值唯一标识了一个元组，并具有最小性，则称该属性组为候选码。

主码：若关系中有多个候选码，则选定一个候选码为主码。

全码：若关系中仅有一个候选码，且这个候选码包含关系的所有属性，则称为全码。

所有候选码中的属性称为主属性，不包含在任何候选码中的属性称为非主属性。
关系模式：关系的描述称为关系模式，可表示为，表示属性名集合，表示属性来自域的集合，表示属性向域的映射集合，表示属性间数据依赖关系集合。也可简记为。

关系模式是相对确定的，关系是变化的。关系是关系模式在某一时刻的状态或内容。
关系数据库的型：关系模式的集合构成关系数据库模式。

关系数据库的值：关系的集合构成具体的关系数据库。
关系模型的完整性约束：实体完整性，参照完整性，用户定义完整性。

实体完整性：必须有属性或属性组合作为主码，主码值不可为空或部分为空（不在域内的值）。

参照完整性：F是关系R的一个非主码属性，如果其与关系S的主码K相对应（两个码定义于一个域上），则称F是R的外码，且R与S可能是同一关系。R中每一元组的F值等于S中某一元组的K值，或为空。（实际上是关系相同对象的对应）

用户定义完整性：用户针对具体的应用环境定义的完整性约束条件。
关系模型的数据操作：操作方式特点是集合操作，操作对象与结果都是集合。操作基础是关系运算（代数方式，逻辑方式）。
关系演算（逻辑方式）：元组关系演算：，为元组

域关系演算：，为域变量
关系代数（代数方式）：常规：并，交，差，笛卡尔积

特有：选择，投影，连接，自然连接，求商
选择：在关系中选择满足给定条件的元组。（）
投影：从关系中取出若干属性，删去重复元组组成新关系，即取出若干元组不重复的列。（）
连接：关系R和S在属性X和Y上的连接，从两关系笛卡尔积上选择X和Y间满足比较条件的元组。（）
- 为时，是等值连接
- 为时，是大于连接
- 为时，是小于连接
自然连接：关系R和S从笛卡尔积上选择相同属性列上取值相等的元组，并删去相同属性列。（）
求商：关系和关系，其中、具有相同属性数。商是在上投影的子集，该集合满足和的笛卡尔积包含在中。（）
元组关系运算：表示为。其中为元组，若元组变量前有全称量词或存在量词，则称为约束元组变量，反之称为自由元组变量（为该元组的第个分量）。为元组关系演算公式，由原子公式和运算符组成，简称公式。

运算符次序：算术比较运算符>>>>>
域关系运算：表示为。其中为域，若域变量前有全称量词或存在量词，则称为约束域变量，反之称为自由域变量。
安全运算：关系运算中不产生无限关系和无穷验证的运算（其表达式称为安全表达式，其限制称为安全约束）。
关系代数是安全运算，关系演算则不一定是。
关系运算中通常采用的安全约束方法是：对运算式定义一个有限符号集，使表中所有元素都属于该有限集。

第三章关系数据库标准语言

分类：DDL（定义），DML（操纵，有联机交互方式和宿主语言方式），DCL（控制）。
特点：一体化（将所有功能融到一种查询语言），非过程化（只提干什么），面向集合的操作方式，可独立可与主语言嵌套使用。
优越性原因：数据结构简单，建立在关系运算数学基础上。
优点：
- 严格的数学概念，有严格设计理论；
- 概念单一，操作语言一致性；
- 数据结构简单直观，语言简洁；
- 存取对用户透明，数据独立性高，安全保密性高。
缺点：
- 查询效率低，不如层次、网状；
- 查询需要优化，开发难度增加。
基本表：实际存在，每个表可用一个存储文件表示。
导出表：从基本表导出，有视图和快照。（视图是虚表，不实际存储在数据库中；快照指某一时间点数据库中表的数据）
查询：SELECT-FROM-WHERE （SELECT后加DISTINCT去除重复行；WHERE后是选取条件）
比较运算符：=,>,>=,<,<=,!=, BETWEEN AND（在范围内）
排序检索：ORDER BY 列名 ASC(升序)/DESC(倒序)，作为最后一个子句出现。

多属性排序：ORDER BY A ASC, B DESC
连表检索：FROM后有多个表，WHERE后有连接条件和选取条件。

表自连接：FROM后将表定义为不同名称，其余同上。

检索所有比小明年龄大的学生姓名、年龄。

SELECT X.SN，X.SA

FROM S X，S Y

WHERE X.SA>Y.SA AND Y.SN=’小明’;
外连接：在连接谓词某一边加上*/+，强制在连接时另一表对应本表不存在的元组增加空行。
子查询/嵌套查询：子句可包含另一查询块，包含子查询的语句称为外部查询。

普通子查询：子查询时与外部查询无关，可单独执行。（子查询不需要外查询值）

相关子查询：外查询时列值作为检索条件条件值。（子查询需要外查询值）

实际上相关子查询效率要低于普通子查询
如果子查询返回唯一值，则可以直接使用比较运算符；如果返回一组值，则需要使用ANY，ALL。

可使用IN代替=ANY（以及NOT IN）
存在检索：EXISTS（子查询），当且仅当子查询结果为非空时为真。（以及NOT EXISTS，可用来表示全称）
并差交：UNION，MINUS，INTERSECT（并差交，操作对象必须是同类关系）
库函数检索：COUNT()对列值计数，COUNT(*)对全部行计数；SUM()对数值列求和；AVG()对数值列求平均值；MAX()对数值列求最大值；MIN()对数值列求最小值。

库函数只能出现在SELECT语句或HAVING语句。
分组检索：GROUP BY 列名 [HAVING condition]，每组在分组属性列上具有相同值，对每一组执行SELECT操作，出现在WHERE语句后。（HAVING是对分组后每组的值进行限制）
SELECT中允许存在属性列、常数、库函数、算术运算符等组成的算术表达式，检索结果数据项名可用表达式表示或别名表示。
部分匹配查询：列名 LIKE/NOT LIKE string，列名必须为字符型或变长字符型，string可包含两种特殊符号%：任意0个或多个字符，_:任意一个字符。
派生表：当子查询出现在FROM语句中，子查询生成的表称为临时派生表。使用AS definition对该表定义。
定义：操作：CREATE，DROP，ALTER

表类型：Table（表），Index（索引），View（视图）
索引：主键+指针，指向表中数据，增加查询效率
视图：虚表，内存中不存在。使用时从数据字典中取出视图定义，与用户查询结合，对基本表查询（视图消解）。

作用：简化用户操作，使用户从多种角度看待，逻辑独立性，对数据提供安全保护。
插入：INSERT INTO 表 VALUES

修改：UPDATE 表 SET 值 WHERE 条件

删除：DELETE FROM 表 WHERE 条件
数据控制：授权：GRANT 权限 ON 授权范围 TO 用户/角色

收权：REVOKE 权限 ON 授权范围 FROM 用户
空值：可初始化或赋予某个属性为空值，空值与任何值运算结果为空值，与任何值比较结果为UNKNOWN

空值的判断：IS NULL
嵌入式SQL：多采用预编译的方法处理，SQL语句翻译为主语言源码，按主语言通常方式进行编译连接为可执行代码。
动态SQL允许程序运行过程中临时组装SQL语言。
ODBC(OPEN DATA BASE CONNECT)、JDBC(JAVA DATA BASE CONNECT)：提供api接口，允许各种SQL语言使用。

第四章数据库保护

数据库安全性控制，数据库完整性控制
安全性：保护数据库防止非法使用造成数据泄露、更改和破坏。（有权用户获得正确数据，无权用户无法获得数据）
用户标识和认证是系统提供的最外层安全保护措施。（常用用户名和口令）
存取控制：确保合法用户在指定权限内使用和访问数据。（包括用户权限定义和合法权限检查，组成DBMS的安全子系统）
存取控制方法：自主存取控制：不同用户对于同一对象有不同权限，用户可以将权限赋予其他用户。

强制存取控制：对于任意用户，只有具有相关权限的用户可以存取。
自主存取控制：根据预先定义的用户权限（用户对数据对象允许执行的数据类型，由数据对象和操作类型组成）进行存取控制。

对于用户存取权限的定义称为授权，授权时应指明用户名、数据对象名、允许的操作类型。
基于角色的存取控制：角色是一组相关权限的集合，将角色授予用户实现权限分配，用户访问时根据所拥有的角色权限进行存取控制。使用角色存取控制，可以简化权限管理复杂度。
SQL可授予两种权限：用户极权限（整个数据库），关系极权限（关系和视图）。
强制存取方法(MAC)：实体被分为主体和客体，主体为用户和用户进程，客体为文件基本表索引视图等。DBMS为每一个实体赋予一个敏感度标记(Label)，如绝密(TS)，机密(C)，秘密(S)，公开(P)。主体敏感度标记称为许可证级别，客体敏感度标记称为密级。

通过对比主客体的敏感度标记，判断是否允许存取。主体敏感度大于等于客体敏感度时可以访问数据，主体敏感度等于客体敏感度时可以存储数据。
数据安全性控制的其它方法：
- 视图机制：不同的用户定义不同的视图，可以将用户对数据的访问限制在一定的范围内。
- 审计：将所有操作自动记录并放入审计日志，后续可根据日志查询访问记录。
- 数据加密：根据一定的算法将原始数据（明文）变换为不可识别的格式（密文）。
完整性：数据的正确性（数据合法）和相容性（各表中相同对象数据自洽）。

完整性关系到数据库是否可以正确反应物理世界。
数据完整性控制防止数据库中出现不合法数据，输出错误数据。

数据安全性控制防止非法更改和访问数据。
完整性约束条件：施加在数据库数据上的语义约束条件，作用对象可以是元组、列、关系。
完整性约束可以分为静态约束（确定状态时应满足的约束）和动态约束（状态变化过程中应满足的约束）。
列级约束：动态是指修改列定义或列值时应满足的约束条件，静态是对列的取值域的说明。

元组约束：动态是指修改元组值时元组中各个字段间需要满足的约束，静态是对一个元组的各个列之间关系的约束。

关系约束：动态是指加在关系变化前后状态上的限制条件，静态是一个关系若干元组或若干关系间的联系约束。
数据库完整性控制应包括定义功能、检查功能、违约响应。
完整性约束条件按照完整性检查的时机分为立即执行约束（一条语句执行之后立即检查）和延迟执行约束（所有语句执行之后检查，若不合法则拒绝全部语句）。
一条完整性规则可以用一个五元组(Data, Operation, Assertion, Condition, Procedure)，分别指数据对象，数据操作，断言或语义约束，作用的谓词，违反完整性规则时触发的过程。
断言：CREATE ASSERTION name CHECK condition，使condition不为真的操作将被拒绝。
触发器(Trigger)：定义在关系上的一类由事件驱动的特殊过程，对表更新时，系统激活相应触发器，执行完整性控制，判断更新是否可以执行。

第五章关系数据理论

数据依赖：一个关系内部属性值之间相互依赖又相互制约的关系。

可分为函数依赖、多值依赖。
函数依赖：对于同一关系中两组属性,，对于任一元组,，时都有（对于任意，有且仅有一个与其对应），则称函数决定，函数依赖于，记作，叫做决定因素。
对于函数依赖，如果，则称作平凡的函数依赖（即中属性全部包含于中）；反之则成为非平凡的函数依赖。
函数依赖与属性间联系：1对1，互为函数依赖；1对多，1函数依赖于多；多对多，不存在函数依赖。
完全函数依赖：若，对于任意一个真子集，都不存在，记作。

部分函数依赖：若，对于存在一个真子集，使得，记作。

传递函数依赖：若，，且不存在，记作。
函数依赖的逻辑蕴含：关系模式$R $中，$ U $表示属性名集合，$ F $表示属性间数据依赖关系集合，$ X $、$ Y $是$ R $的属性集合，如果从$ F $中的函数依赖可以推出$ X\rightarrow Y $，则称$ F $逻辑蕴含$ X\rightarrow Y$。
函数依赖集的闭包：逻辑蕴含的所有函数依赖称为的闭包（和可以推出的全部），记作。
阿姆斯特朗公理系统：对于关系模式$R$有如下规则：
- 自反律：若，则为蕴含。
- 增广律：若为蕴含，且，则为蕴含。
- 传递律：若，为蕴含，则为蕴含。
- 合并规则：若，，则。
- 为传递规则：若，，则。
- 分解规则：若，，则。
属性集关于函数依赖集的闭包： $能由根据公理导出$ 。
阿姆斯特朗公理系统是有效的、完备的。

有效性：由出发根据Armstrong公理推导出来的每个函数依赖一定在所蕴含的函数依赖的全体之中；

完备性：所蕴含的函数依赖的全体中的每一个函数依赖，必定可以由根据Armstrong公理导出。
完备性证明（第五章P35）
函数依赖集等价：，和等价，覆盖，覆盖。
最小依赖集（极小函数依赖集/最小覆盖）：
- ，必有是单属性。（右部单属性）
- 不存在使得与等价。（无多余FD: Functional Dependency）
- 不存在，，使得与等价。（FD左部无多余属性）
函数依赖集极小化处理：每个均等价于一个最小依赖集。
范式：一个关系满足某个指定的约束集。
满足最低要求约束的关系称为第一范式，记为1NF。（关系只包含原子值，无表中表）

满足每个非主属性完全依赖于码的第一范式称为第二范式，记为2NF。

满足每个非主属性都不传递依赖于任何码的第二范式称为第三范式，记为3NF。
投影分解： 2NF：消除非主属性对码的部分依赖关系，即将对码是部份依赖的非主属性分割出来。

3NF：消除非主属性对码的传递依赖关系，即将对码是传递依赖的非主属性分割出来。
BCNF：每个非平凡函数依赖，必含有码的第一范式。
BCNF性质：非主属性均完全函数依赖于每个候选码；主属性均完全函数依赖于每个不包含他的候选码；没有任何属性完全函数依赖于非码的任何一组属性。
其他类型依赖：多值依赖，连接依赖，分层依赖，相互依赖。
多值依赖：设是属性集上的一个关系模式，、、是的子集，并且，关系模式中多值依赖成立，当且仅当的任一关系，给定的一对 $，$ 值有一组Y的值，这组值仅仅决定于值而与值无关。
不存在非平凡的非函数依赖的多值依赖的BCNF称为第四范式，记为4NF。
规范化的基本思想是逐步消除数据依赖中不合适的部分，使数据库模式中各关系模式分离，一个关系只描述一个实体或实体间联系。（实质是概念的单一化）
规范化过程： 1NF→2NF：消除非主属性对码的部分函数依赖；

2NF→3NF：消除非主属性对码的传递函数依赖；

3NF→BCNF：消除主属性对码的部分和传递函数依赖；

1NF→BCNF：消除决定因素非码（中的不是码）的非平凡函数依赖；

BCNF→4NF：消除非平凡且非函数依赖的多值依赖。
范式间关系：。
模式分解：，称为在上的投影。
无损分解：对一模式分解，若任一关系等于其分解后所有投影的自然连接，则称为无损分解（即分解后不损失任何属性）。
无损分解的判定（第五章P70）
保持函数依赖性：分解后所有关系模式的依赖集的并集的闭包等于原依赖集的闭包，即不损失任何一个函数依赖。
模式分解原则：通过投影分解完成。
候选码的求解方法（第五章P86）

第六章数据库设计

数据库设计：对于给定的应用环境，设计并建立数据库逻辑结构和物理结构，以适应要求。（主要是设计出三级模式两级映像）
设计特点：数据设计和处理设计结合。
规范设计法：把设计过程划分为多个阶段，每个阶段只解决设计中部分问题。（迭代和逐步求精的过程）

分为需求分析、概念结构设计、逻辑结构设计、物理结构设计、数据库实施、数据库运行和维护。
需求分析：对应用环境进行详细调查，收集支持系统目标的基础数据及其处理。包括用户所需功能、数据之间关系。
概念结构设计：通过对用户需求进行综合、归纳与抽象，形成独立于数据库逻辑结构与具体DBMS的概念模型，可以用E-R图等表示。
逻辑结构设计：将概念结构转换为某个DBMS所支持的数据模型，将逻辑结构转换成特定DBMS能处理的模式、子模式。
物理结构设计：设计数据库在物理设备上的存储结构和存取方法。一般分为两步：一是确定数据库的内模式；二是对物理结构进行时间与空间效率的评价。
数据库实施：建立数据库，用DBMS的DDL描述三级模式，调试产生目标模式；开发应用程序，组织数据入库并试运行。
数据库运行维护：在数据库正式运行时，由DBA执行对数据库经常性的维护工作，包括数据库转储与恢复、数据库控制、数据库性能监控、数据库的重组与重构。
六阶段形成的模式：
数据流图：以图形方式表示系统功能，数据在系统中的逻辑流向和逻辑变换过程。（数据和处理的关系）

数据字典：数据集中说明，包括数据元素的名字含义等。（系统中各类数据）
E-R法：概念模型，用E-R图描述现实世界，将E-R图转化为相应数据模型。

组成：实体、联系、属性。

自顶向下分析需求，自底向上设计概念模型。首先设计出局部E-R图，整合并消除冲突，生成初步E-R图，消除冗余生成基本E-R图。
E-R图向关系模型的转换规则：一个实体型或一个关系（具有相同码的关系可以合并）转化为一个关系模式。弱实体类型转化为一个关系模式，并将被依赖关系添加到新关系中。
关系模式的优化：按照范式等级优化即可，进行合并和分解（水平分解元组，垂直分解属性）。
常用存取方法：索引、聚集、哈希。
索引：记录索引项，包含索引域、指针两个域。

常用B+树索引，所有关键字都按递增次序从左到右安排在叶节点上，并且链接起来。B+树能同时进行随机查找和顺序查找。
聚集：把关系中某个属性/组(聚集键)值相同的记录集中存放在连续的物理块，称为聚集。一个关系只能参与一个聚集。

经常进行连接操作的关系，单个关系的某组属性经常进行相等比较可以构建聚集。
hash存储：将记录的关键字通过hash函数或hash表转换为地址。

关系大小可预知且不变可以直接建立，关系大小动态改变需要DBMS提供动态hash存取方法。

第七章存储管理与索引

存储管理目标：最小化磁盘存取次数

实现手段：在主存中保持尽量多的块，使得上层要访问块时他在主存中概率最大。
数据库存储结构主要是文件的组织结构。
数据库中表映射到文件（记录的序列），存储到若干磁盘块上。

一个块上可以存储多条记录，而一条记录只能存储到单个块中。每条记录有唯一的标识ID，由块号和记录在块中的位置组成。
数据库存储采用页块结构，使用页表存储块。
堆文件组织：记录可以存放在文件空间中的任何位置。可以采取链表方式（维护header页，存储空白页链表头指针和数据页链表头指针，每页记录当前包含的空槽数）和页目录方式（维护特殊页保存文件中数据页位置，记录每个页中空槽数）。
顺序文件组织：文件中记录按搜索码（用于在文件中查找记录的任意属性集合）排序排列。通过指针将记录链接起来，每个记录的指针指向按搜索码排列的下一条记录（可高效按搜索码处理记录）。
索引文件组织：索引是指记录的关键字与相应记录的存储地址的对照表，索引文件由主文件（可按主关键字有序组织或无序组织）和索引表（必须按关键字有序）构成。
散列文件组织：存储单位为桶，桶号可以是相对块号，最终可以转换为外存空间上的物理地址。使用哈希函数，将记录散列到桶上。如果记录个数超过一个桶的容量，即哈希函数出现冲突，形成一个主桶和多个溢出桶的列表。

二次检索：先利用哈希函数确定项所在的主桶，再根据列表逐一找到每个溢出桶。
聚集文件组织：具有相同或相似属性值得记录存储于连续的磁盘块中，并获得聚集码（哪些记录被存储在一起）。

多表聚集：将多个关系存储于一个文件中，在每个块中存储两个或更多关系得相关记录。
缓冲区：主存中存储磁盘块副本的区域。

缓冲区管理器：负责缓存空间分配，内外存交换。
块/页是存储分配和数据交换的单位。
索引分类：排序索引、哈希索引（顺序与哈希函数确定的乱序）
聚集索引：索引域排列顺序与记录在排列顺序一致，也称主索引。

非聚集索引：顺序不同，也称辅助索引。
稠密索引：对于文件中每一个搜索码值都有一个索引项。

稀疏索引：只有部分搜索码值有索引项。（占空间小且维护代价低，定位记录慢）
多级索引：索引规模大，无法全部放入内存，建立外层索引（基本索引的稀疏索引）和内层索引（基本索引文件）。
B树：限制了每个节点放置关键字与指针的最小和最大个数。所有叶节点都分布在同一层上，关键字散布在各层上。
B+树：所有关键字都按递增顺序从左到右安排在叶节点上，并链接。能同时进行随机查找和顺序查找。

查询：从树的根节点开始，通过比较查询码值和节点的值，向下遍历树直至到达包含指定值的叶节点。

插入：查询到要插入的叶节点，若有空间插入该条记录，否则拆分（将原叶节点后一半差分出一个叶节点，并将新叶节点插入原叶节点的父节点中；向上递归处理，直至不再需要拆分）。

删除：查询到要删除的叶节点，删除该条记录，如果删除后叶节点中码个数低于下限，可能需要合并或重新分配（将原叶节点与其兄弟节点合并，并在父节点中删除原叶节点；如果合并时超出上限，则需要重新分配合并的码值）。
hash索引：使用哈希表实现从码到存储地址的映射。

哈希表包括哈希函数（映射函数，速度快碰撞率低）和哈希方案（解决一个哈希值对应多条记录，常用溢出链接法：链表）两部分。

静态哈希：哈希表不可变化，文件增大时访问效率降低，文件缩小时造成空间浪费。

动态哈希：哈希表可变化，创建新的哈希表，把原表中的码值重新缔造哈希函数并存入新哈希表。

第八章查询处理与优化

四个阶段：分析、检查、优化、执行。

词法分析、语法分析 => 语义分析、安全性检查、完整性检查、符号名转换 => 代数优化、物理优化 => 代码生成、代码执行
选择操作：全表扫描、索引扫描。
排序操作：内存中完全容纳，可采用快速排序等算法；内存中无法容纳，采用外排序-归并算法。
连接操作：嵌套循环（较小表为外循环，较大表为内循环）、索引连接（一个表按照连接属性建立索引，另一个表取连接属性与其比对）、排序合并（按照连接属性排序，两个表按连接属性比对）、hash-join（连接属性作为hash码，两个表散列到同一个hash文件）。
去重操作：使重复数据相邻，保留一个数据并去除其他。
投影操作：每个元组投影，再进行去重操作。
并差交：类似于排序-合并连接。
表达式的执行：物化方法（按次序每次只执行一个运算，运算结果存为临时表，一般需要写到磁盘上）和流水线方法（同时执行多个运算，将结果传递给下一个运算）。
查询优化目标：访问磁盘块数最少。
代数优化：改变代数表达式中操作的次序和组合。

物理优化：存取路径和底层操作算法的选择。
查询计划：定义每个操作的算法以及操作执行的顺序。
关系代数表达式等价变换规则：
- 连接、笛卡尔积的交换律：；
- 连接、笛卡尔积的结合律：；
- 投影的串接定律：，其中；
- 选择的串接定律：；
- 选择与投影的交换律：；
- 选择与笛卡尔积交换律：若代表选择的属性集合中含有中属性集合和中属性集合，则存在；
- 选择与并差交、自然连接的分配律：；
- 投影与笛卡尔积的分配律：；
- 投影与并的分配律：。
优化的一般准则：
- 选择运算尽早执行。（减小中间关系-减少元组数据）
- 投影运算尽早执行。（减小中间关系-减少属性数目）
- 把投影运算和选择运算同时进行；把投影同其前或其后的双目运算结合起来。（减少扫描关系的次数）
- 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算。（把笛卡尔积与选择转换为连接）
- 找出公共子表达式，把公共子表达式的结果写入中间文件，重复使用。（中间结果复用）
查询树优化：查询树是关系代数表达式的树型表示。类似于四元式的DAG图，构造出查询树够使用关系代数表达式等价变换规则。

分组：双目运算和它的直系祖先 (选取、投影)为一组；双目运算后代直到叶子全是单目运算时并入该组。笛卡尔积的后面若不是与之可以合并的自然连接的等值选择时，其后代单独分为一组。

生成查询代码时，每组节点的计算是程序中的一步。各步的顺序是任意的，只要保证任何一组的计算不会在其后代组之前计算。
物理优化：选择高效合理的操作算法或存取路径，得到优化的查询计划。

常用方法：基于规则的启发式优化、基于代价估算的优化。
选择操作的启发式规则：小关系使用全表顺序扫描；大关系采用索引扫描、全表顺序扫描。

连接操作的启发式规则：两个表都已经按照连接属性排序，使用排序-合并法；一个表在连接属性上有索引，使用索引连接法；连接属性上未建立索引未排序，且其中一个表较小，使用hash-join法；其余可使用嵌套循环法，选择较小的表为外循环表。
基于代价估算：利用数据库统计信息，计算各种操作算法的执行代价，选出具有最小代价的执行计划。

统计信息包括：基本表的规模，基本表列信息（不同值个数、最大最小值、是否有索引、索引类型）、索引的具体信息
查询优化一般步骤：查询转换成语法树；查询树利用代数优化转换为优化后标准形式；启发式优化选择底层的操作算法与存取路径，生成查询计划；基于代价优化选取代价最小的。

第九章事务处理技术

事务的概念：用户定义的数据库操作序列，不可分割的工作单位。
事务特性：原子性、一致性、隔离性、持久性。
利用数据库的并发控制与恢复机制保证事务的特性不被破坏。
数据库的恢复基本原理是冗余，即利用存储在其他地方的数据重建数据库。
恢复是通过数据库管理系统的恢复子系统完成的，数据转储与登录日志文件。
故障种类：事务内部故障、系统故障、介质故障、计算机病毒。
日志是用来记录事务对数据库更新操作的文件。
故障恢复策略：事务故障：UNDO；系统故障：UNDO+REDO；介质故障：恢复到最近一次转储，装入日志，重做已完成事务。
检查点技术：增加检查点记录（正执行事务清单，最近记录地址）。
恢复子系统操作：缓存日志记录写入日志文件；写入检查点记录；缓存的数据记录写入数据库；检查点记录地址写入重新开始文件。
并发控制提高吞吐量，减少平均响应时间。
并发控制问题：可能破坏数据一致性。（丢失更新、读出脏数据、无法重复读）
基本思想：合理调度，避免事务间干扰破坏一致性。
基本手段：封锁。（基本封锁两种：排他锁X锁、共享锁S锁）
三种封锁协议分别对应三种问题：一级对应丢失更新、二级对应读出脏数据、三级对应无法重复读。
一级封锁协议：事务对数据修改前必须加排他锁。

二级封锁协议：增加读取数据前必须加共享锁。（读取完成释放）

三级封锁协议：增加读取数据前必须加共享锁。（事务完成释放）
封锁对象大小称为封锁粒度。
粒度大，并发度低，结构简单，开销小。
多粒度封锁：一个系统中同时支持多种封锁粒度。考虑封锁开销和并发度以选择封锁粒度。
多粒度封锁协议：允许多粒度树中每个节点被独立加锁，其后续子节点也会被全部加锁。
意向锁：该节点的下层节点正在被加锁。（因此加锁时只检查对象和其上级节点）
三种意向锁：意向排他锁，意向共享锁，意向共享排他锁。
对对象加锁时应先向其上级节点加意向锁。
活锁指其他对象已获得锁，当前对象处于等待；死锁指互相等待对方的完成。
死锁预防：一次封锁法（一次将所有要使用的对象加锁，并发度降低）、顺序封锁法（规定一个顺序，难度大）。
死锁检测：超时法、等待图法。
死锁恢复：撤销一个处理死锁代价小的事务并重做这个事务。
可串行性：并发执行正确当且仅当其结果与按某一次序执行结果相同。
两段锁协议：对数据读写前事务要取得该数据的封锁；释放封锁后事务不再获得任何其他封锁。即事务分为获得锁和释放锁两个阶段。

第十章分布式数据库系统

分布式数据库：一组分布在计算机网络不同节点的数据，每个节点具有独立处理能力，可执行局部应用，也可通过网络通信执行全局应用。
特点：数据独立性（逻辑和物理独立性）、集中与自治相结合的结构、适当增加数据冗余（不同节点可能存储相同数据）、全局一致性可串行性和可恢复性。
分布式数据库系统的模式结构：
分片方式：基本：水平分片、垂直分片；

复杂：混合分片、导出分片。
水平分片：按行分为若干不相交子集。

垂直分片：按列分为若干不相干子集，通过连接恢复原关系（各片段都包含码）。

导出分片：导出水平分片，分片条件不是关系本身属性而是其他关系属性，如学生课程关系按学生关系中的系属性分片。

混合分片：混合三种方式，按一种分片方式分完后再按另一种方式分片。
分片方式应满足：完全性、不相交性、可重构性。
分布透明性包括：分片透明性（只对全局关系进行操作，不考虑切片）、位置透明性（不必了解片段存储场地及数据一致性）、局部数据模型透明性（不必了解局部场地上使用的数据模型）。
分布式查询分类：局部查询（仅本地）、远程查询（仅远程）、全局查询（均存在）。
分布式查询优化：减少查询开销（IO+CPU+通信，首要目标是减少通信开销），可分为分布优化（更重要）和局部优化。
连接查询的优化：半连接，。
分布事务处理：一个全局事务被划分为在多个节点上的子事务。
分布事务的原子性：组成该事务的全部子事务要么一起提交，要么一起回滚。
两段提交协议保证分布事务原子性。

所有局部事务管理分为两类：一个协调者，多个参与者。

分为两个阶段：第一阶段协调者向参与者发信息并接收返回，做出决定；第二阶段：参与者执行决定。

发生故障时，各场地利用各自有关日志进行事务恢复。

第一章 概述

第二章 关系数据库

第三章 关系数据库标准语言

第四章 数据库保护

第五章 关系数据理论

第六章 数据库设计

第七章 存储管理与索引

第八章 查询处理与优化

第九章 事务处理技术

第十章 分布式数据库系统

第一章概述

第二章关系数据库

第三章关系数据库标准语言

第四章数据库保护

第五章关系数据理论

第六章数据库设计

第七章存储管理与索引

第八章查询处理与优化

第九章事务处理技术

第十章分布式数据库系统