数据库复习

数据库复习内容

作者：哈利波特👑

加油！有些公式不想打了，就直接复制图片了… 复习时间不够…

第一章 引言

数据

定义：描述事务的基本符号，是数据库的基本对象。

数据库

定义：互相关联的数据集合 或 长期储存在计算机内、有组织的、可共享的大量数据集合。

数据模型：数据库结构的基础

  • 关系模型

    一个表就是一个关系。

    System-R 是关系模型。

    用的最广泛。

  • 实体-联系模型

  • 半结构化模型

  • 基于对象的模型。

数据库管理系统(DBMS)

是一个在操作系统下定义的系统软件。

定义：由一个互相关联的数据的集合（数据库）和一组用以访问这些数据的程序所组成。

目的：提供一种方便、高效地存取数据库信息的途径。

核心功能：数据定义、数据操作、数据安全、数据恢复和备份、并发控制、事务管理。

  • 数据定义：定义数据库的结构，包括表、视图、索引等。
  • 数据操作：支持数据的插入、更新、删除和查询。
  • 数据安全性：控制用户权限，确保数据的机密性和完整性。
  • 数据备份与恢复：提供数据备份和灾难恢复机制。
  • 并发控制：管理多个用户同时访问数据，避免冲突和数据不一致。

数据库系统

定义：由数据库、数据库管理系统、应用系统、数据库管理员（或用户）所组成。

目的：为用户提供抽象的数据视图，隐藏对数据的维护。

文件系统的弊端

数据的冗余和不一致性、数据访问困难、数据孤立、完整性问题、原子性问题等等。

  • 一个学生同时有两个专业，就会在两个文件存储信息。
  • 如果临时想要查询文件的子文件，都不行。
  • 很难增加新的约束。

数据抽象

一个可用的系统一定要高效的检索数据。

系统开发人员通过将数据抽象成 物理层、逻辑层、视图层 来对用户屏蔽复杂性。

  • 物理层

    最低层次的抽象，描述数据如何存储。

  • 逻辑层

    描述数据库存储什么数据以及数据之间的联系。

  • 视图层

    只描述数据库的某一部分。

**物理数据独立性：**应用程序不依赖物理模式，物理模式隐藏在逻辑模式下，可以在应用程序不受影响的情况下轻易更改。即使物理模式改变了，也无需重写应用程序。

**逻辑数据独立性：**指数据库的逻辑结构（表的属性）发生变化时，不会影响用户的外部视图或应用程序对数据的访问。

数据库系统模式（考点）

特定时刻存储的数据库中的信息集合称作数据库的一个实例。

数据库总体的设计称为数据库模式。按照刚刚所说的三个层次划分，数据库系统模式有物理模式、逻辑模式、子模式。

数据库系统模式就是变量类型，实例就是该变量在某个特定时间的值。

数据库语言

分为数据定义语言（DDL）和数据操纵语言（DML）。

  • 数据定义语言

    例如 create、alter等等。

    有域约束和引用完整性和授权。

    • 域约束就是create table的时候属性的类型，要符合该类型。
    • 引用完整性就是外键。
    • 授权就是grant。

  • 数据操纵语言

    分为过程化的 DML 和声明式的 DML。

    • 过程化

      要求指定用户需要什么数据以及如何获得这些数据。

    • 声明式（非过程化）

      要求指定用户需要什么数据即可。

      SQL是非过程化的！

存储管理器

存储管理器是数据库管理系统中的一个核心组件，负责管理和存储数据库中的数据。

负责将原始数据通过操作系统提供的文件系统存储在磁盘上。

实现了以下几种数据结构：

  • 数据文件

    存储数据库本身。

  • 数据字典

    数据字典是元数据的存储库，包含数据库中对象的定义、类型、约束等信息。

    它帮助DBMS管理和验证数据库的结构，并允许系统在执行查询时参考这些元数据。

  • 索引

    提供对数据项的快速访问。

数据字典（Data Dictionary）是一个存储数据库元数据的系统，用于描述和管理数据库中的所有数据元素、结构、约束和关系。

事务管理

事务是指一组数据库操作的集合，这些操作要么完全执行（提交），要么完全不执行（回滚）。

事务管理确保数据库操作在执行过程中满足ACID特性，即原子性、一致性、隔离性和持久性。

  • 原子性

    原子性保证事务中的所有操作要么完全执行，要么完全不执行。

    事务中的每个操作都是一个不可分割的单位。

  • 一致性

    一致性确保数据库从一个有效的状态转换到另一个有效的状态。

    即银行转账之后，a 和 b 的余额应该是不变的。

  • 隔离性

    隔离性确保多个事务并发执行时，一个事务的执行不会受到其他事务的干扰。

  • 持久性

    持久性确保一旦事务提交，事务的所有操作对数据库的更改是永久性的，即使系统发生崩溃也不会丢失。

原子性和持久性是靠恢复管理器实现。 隔离性是由并发控制管理器实现的。

为了保证原子性，经常需要故障修复，即将数据库恢复到该失败事务开始执行以前的状态。

事务管理器包括 恢复管理器 和 并发控制管理器 组成。

数据库系统

由三个子系统组成，分别是存储管理器子系统、编译管理器子系统（DDL和DML语句）、事务管理器子系统。

数据库系统的基本特征：数据共享性、独立性和冗余度小。

数据库系统包括数据库和数据库管理系统（DBMS）。

其他

SQL 语言是为做决策而产生的，是查询密集。 1980年代的数据库都是更新密集的。

1990年加入对象-关系模型。

**实体-联系数据模型(E-R)**是广泛用于设计数据库的。

过程化DML（如PL/SQL, T-SQL）

非过程化DML（如SQL）

在数据库中存储的是_________。
A、数据 B、数据模型
C、信息 D、数据以及数据之间的联系

正确答案：D

数据库的_________是指数据的正确性和相容性。
A、恢复 B、安全性 C、并发控制 D、完整性
正确答案：D

数据模型是由数据结构、数据操作、和完整性约束三部分组成的。

在数据库的三级模式结构中，用来描述数据库中全体数据的全局逻辑结构和特征的是__________。
正确答案： 逻辑模式

数据库系统的核心是____________________。
正确答案：数据库管理系统或DBMS

对DB的数据主要是两个操作：查询和更新。

SQL server中，每个表最多1024列。

第二章 关系模型介绍

关系数据库的结构

关系数据库由表构成（实际上就是表的集合）。

在关系模型中，关系 被用来指代 表，元组 被用来指代 行，属性 被用来指代 列。

  • 关系实际上是元组的集合。

对于每个属性的取值都有一个范围，这个范围就是域。并且该域中的元素都是**不可再分（原子）**的。

数据库模式：数据库的逻辑设计；数据库实例：某⼀时刻数据库中的数据的快照。关系模式、关系实例与之类似。

  • 关系模式由属性列表和各属性对应的域组成（可能包括主码约束）。

    1
    Students(student_id: INT, name: VARCHAR(100), age: INT)

  • 模式很少改变，但是实例会随着时间发生改变。

码（妈的）

**超码：**一个或多个属性的集合，这个集合可以唯⼀地区分出⼀个元组（行）。

**候选码：**最小超码，可能有多个。

主码：人为选中，作为⼀行的区分标准的候选码。

外码：：关系 r1 的属性中可能包含了关系 r2 的主码，这个属性在 上称作参照 r1 的外码，r1 称作外码依赖的参照关系， r2 称作外码依赖的被参照关系。（必须是 r2 的主码！！）

**参照完整性约束：**参照关系中的任意元组的特定属性的取值必须等于被参照关系中某个元组的特定属性的取值。这个对比外码放松了条件！不需要是主码！

关系代数

看那个 pdf，这里没时间写了。

在关系代数运算中，五种基本运算为并、差、选择、投影、笛卡尔积。

关系运算的结果也是关系（表）。

笛卡尔积运算跟连接不一样！结果一共有 n1 x n2 个元组。

集合运算 交 并 差的运算，记得是集合！所以并集中重复的部分只会保留一个！需要满足两个关系是属性数量一致并且属性的域相同。

这里简单的提下除法，除法的定义是如果关系 R 有 ABC 三个属性，关系 S 有 AB两个属性。那么R 除 S的集合结果是在 R 中找出属性 AB 取值跟 S 中的属性 AB 取值一样的元组。

总结

  1. 一个数据库可以有多个关系模式
  2. 每个关系模式可以包含多个表

假设有一个数据库 CompanyDB，该数据库包含多个关系模式，每个关系模式下有多个表：

  • HRSchema（人力资源模式）：包含 Employees（员工表）、Departments（部门表）、Salaries（薪资表）。
  • FinanceSchema（财务模式）：包含 Invoices（发票表）、Transactions（交易表）。
  • SalesSchema（销售模式）：包含 Customers（客户表）、Orders（订单表）、Products（产品表）。

其他

对关系的完整性约束通常包括_________三种。
A、实体完整性、属性完整性、关系完整性；
B、实体完整性、参照完整性、用户定义完整；
C、实体完整性、属性完整性、用户定义完整；
D、实体完整性、属性完整性、参照完整性；
正确答案：B

主键应该体现它的唯一和非空性。

在关系模式中，使用二维表表示数据。

第三章 SQL介绍

建表的时候的 primary key 和 foreign key 都是属于完整性约束，SQL 禁止任何破坏完整性约束的数据库更新。

一个数据库管理系统的实例可以创建多个数据库，一个数据库可以有多个关系模式，一个关系模式可以由多个表组成。

sql基本结构与关系代数对应

关系代数是集合运算！sql不是…

  1. SELECT 对应 π（投影）

    但是并不等价，因为select会返回重复的行，但$$\pi$$是集合运算不会返回重复的行。

  2. FROM 对应笛卡尔积（×）

  3. WHERE 对应 σ（选择）

  4. as对应P

执行顺序

  1. FROM
    执行首先发生在 FROM 子句，确定从哪个表（或视图）中获取数据。如果有多个表，数据库会先执行 JOIN 操作来将它们结合在一起。
  2. ON
    如果查询中涉及连接（JOIN），数据库会首先根据 ON 子句中指定的条件来匹配连接的行。
  3. JOIN
    对于多表查询，数据库在 FROM 中确定了表并处理了 ON 中的连接条件后，会执行连接操作（如 INNER JOIN、LEFT JOIN 等）。
  4. WHERE
    在从表中获取数据后，数据库会通过 WHERE 子句来过滤行，仅保留符合条件的行。
  5. GROUP BY
    接着，数据库会根据 GROUP BY 子句对结果进行分组。如果查询涉及聚合函数（如 COUNT、SUM、AVG 等），它们会在分组之后应用。
  6. HAVING
    HAVING 子句与 WHERE 类似，但它是在分组之后对聚合结果进行过滤的。WHERE 是用来过滤行的，而 HAVING 用来过滤分组。
  7. SELECT
    在数据被过滤并分组后，SELECT 子句决定了最终查询返回哪些列。如果查询中有聚合函数（如 SUM、AVG 等），此时会计算聚合值。
  8. DISTINCT
    在选择列后，如果查询使用了 DISTINCT 关键字，数据库会去除重复的行。
  9. ORDER BY
    ORDER BY 用于对查询结果进行排序。排序通常是在所有其他操作完成后执行的。

字符串运算

  • INtro%匹配以 INtro 打头的任意字符串。
  • %comp%匹配任意包含 comp 的字符串。
  • ___匹配只有三个字符的任意字符串
  • ___%匹配至少含有三个字符的任意字符串。

排序 order by

可以选择多个属性进行排序，例如对salary升序，但是对salary一样的元组进行 name 降序排列。

1
2
3
select *
from instructor
order by salary asc, name desc

集合运算

SQL 中的 union、intersect、except对应 并、交、差。

  1. UNION（并集）：

    UNION 用于合并两个查询的结果集，并去除重复的行。

    保留重复的行需要union all！！

    1
    2
    3
    4
    5
    SELECT column1, column2
    FROM table1
    UNION
    SELECT column1, column2
    FROM table2;

  2. INTERSECT（交集）：

    INTERSECT 用于返回两个查询结果中的公共部分（交集）。

    保留重复的行需要intersect all！！

    1
    2
    3
    4
    5
    SELECT column1, column2
    FROM table1
    INTERSECT
    SELECT column1, column2
    FROM table2;

  3. EXCEPT（差集）：

    EXCEPT 用于返回第一个查询结果中有而第二个查询结果中没有的行。

    保留重复的行需要except all！！

    去除重复项的操作是在集合差运算前，所以假设c1有四个重复的元组a，c2有两个重复的元组a，那么最后a不会有输出。

    若except all ，最终会有两个a输出。

    1
    2
    3
    4
    5
    SELECT column1, column2
    FROM table1
    EXCEPT
    SELECT column1, column2
    FROM table2;

空值

定义 true false 之外的第三种逻辑值 unknown。

  • and
    • false and unknown = false
    • unknown and unknown = unknown
  • or
    • true or unknown = true
    • false or unknown = unknown
    • unknown or unknown = unknown
  • not
    • not unknown = unknown
    • 如果 r.a 为空，那么 1 < r.a 和 not(1<r.a) 都为空。

聚集函数

在 SQL 中，聚集函数用于对一组数据进行操作，生成单个结果。常见的聚集函数有 AVG（计算平均值）、SUM（求和）、COUNT（计数）、MAX（最大值）、MIN（最小值）。

  • 平均值

    AVG 函数计算一列数据的平均值，即所有数据值的总和除以数据的数量。

    计算平均值的时候，保留重复项是很重要的。

    1
    2
    3
    SELECT AVG(column_name)
    FROM table_name
    WHERE condition;

    注意：AVG 函数忽略 NULL 值，也就是说，如果某一行的该列是 NULL，则该行不会计入总和和计数。

  • 计数

    COUNT(*) 计算结果集中所有行的数量，不会忽略 NULL 或空值，它包括所有的行。

    COUNT(column_name) 与 COUNT(*) 不同，COUNT(column_name) 会忽略该列中的 NULL 值。

    COUNT(DISTINCT column_name) 计算特定列中唯一非空值（NOT NULL）的数量，重复值会被去除。

  • 求和

    SUM 函数是 SQL 中常用的聚集函数之一，用于计算某一列中所有数值的总和。

    跟 count一样，SUM(column_name) 用于对指定列中的所有非空数值进行求和。该函数只适用于数值型数据列，且会忽略 NULL 值。

  • 最大最小值

    这个就不讲了。

除了count(*)以外的所有聚集函数都忽略NULL！！

分组聚集 group by

在 group by中，只有group by 的属性和聚集函数可以被 select。

搭配having使用。

子查询

集合比较

  • SOME 会检查子查询返回的多个值，只要至少有一个值满足条件，整个条件成立。

    如果我们想查找所有价格大于至少有一个订单中的产品的价格的产品，可以使用 SOME：

    1
    2
    3
    SELECT product_name, price
    FROM Products
    WHERE price > SOME (SELECT price FROM Orders WHERE Orders.product_id = Products.product_id);
    • 这里，SOME 检查 Products 中的每个产品的价格是否大于至少一个订单中的相应产品价格。

  • ALL 会检查子查询返回的所有值，只有所有值都满足条件时，整个条件才成立。

    继续使用上面的 Products 和 Orders 表。如果我们想查找价格大于所有订单中该产品价格的产品，可以使用 ALL：

    1
    2
    3
    SELECT product_name, price
    FROM Products
    WHERE price > ALL (SELECT price FROM Orders WHERE Orders.product_id = Products.product_id);
    • 这里，ALL 检查 Products 中的每个产品的价格是否大于所有订单中的相应产品价格。

  • EXISTS 用于判断子查询是否返回结果。如果子查询有结果（即返回至少一行数据），EXISTS 返回 TRUE；如果子查询没有结果，则返回 FALSE。

    假设我们希望查找那些有订单记录的产品，可以使用 EXISTS：

    1
    2
    3
    4
    5
    6
    7
    SELECT product_name
    FROM Products p
    WHERE EXISTS (
        SELECT 1 
        FROM Orders o 
        WHERE o.product_id = p.product_id
    );
    • 这里，EXISTS 检查是否存在至少一个订单与 Products 中的产品相关联。如果存在这样的订单，EXISTS 返回 TRUE，因此该产品会被选中。

  • with语句用于临时定义一个表。

  • 标量子查询，只要select语句的返回值是一个包含单个属性的元组（值），可以出现在select、where、having中。

**不相关子查询：**子查询的查询条件不依赖于父查询，由里向外逐层处理。既每一个子查询在上级查询处理之前求解，子查询的结果用于建立其子查询的查找条件。

**相关子查询：**子查询的查询条件依赖于父查询，首先取外层查询中的表的第一个元组，根据它与内层查询相关的属性值的属性值处理查询内层查询，若 where 子句返回的值为真，则取此元组放入查询结果表，然后再取外层表的下一个元组，重复这一过程，直至外层表全部检测完为止。

其他

  • as不能出现在where里面！

第四章 中级sql

  • 内连接

    内连接只返回两个表中有匹配的记录。如果两个表中某一行没有匹配的记录，那么这行数据不会出现在结果中。

  • 左外连接

    返回左表的所有记录，右表中没有匹配的行会显示为 NULL。

  • 右外连接

    返回右表的所有记录，左表中没有匹配的行会显示为 NULL。

  • 全外连接

    返回两个表的所有记录，左右表中没有匹配的行都会显示为 NULL。

以上四种连接输出顺序：公共属性，左边表属性，右边表属性。

以上的四种连接都只会输出一次进行连接的属性，但是如果使用 on 的话就会输出两个连接的属性。

视图

简单来说，就显示表的子集，是虚拟的。

视图是数据库中的虚拟表，它通过一个查询来表示数据，而不存储实际的数据。视图可以帮助简化复杂查询，增强数据的安全性，并提供更直观的接口。

定义：视图实际上是一个存储的查询。当你访问视图时，数据库会自动执行这个查询并返回结果。视图的内容取决于它所定义的查询，因此它不占用存储空间（除了存储查询本身的定义），只保存查询的结构。

  • 可以被当成一个表查询
  • 可以建立视图的视图

视图更新

条件如下：

  • 视图只涉及一个表
  • SELECT子句只包含关系的属性名
  • 没有使用 DISTINCT 或 GROUP BY或having
  • 没有出现在SELECT中的属性都可以取NULL。

with check option可以判断加入视图的元组是否满足创建视图的条件。

完整性约束

单个关系上的约束有：

  • not null

  • unique

    这意味着，两个元组（行）中对应 UNIQUE 列的 NULL 值可以同时出现，因为 SQL 不认为两个 NULL 值是相等的，它们被视为不同的值。

  • check(< 谓词 >)

    只要谓词不为假，check 就成立。为NULL也成立喔！！

引用完整性

外码

外键约束用于确保两个表之间的数据一致性。当我们在表中定义外键时，通常会为外键约束指定不同的级联操作。

  • DELETE CASCADE
    • 定义：当父表中的某个记录被删除时，所有引用该记录的子表中的记录也会被自动删除。
  • SET NULL
    • 定义：当父表中的某个记录被删除时，子表中所有引用该记录的外键列的值会被设置为 NULL。
  • RESTRICT
    • 定义：当父表中的某个记录被删除时，如果子表中有任何记录引用该父记录，删除操作将被拒绝。

授权

grant select on book to user1 with grant option

revoke select on book from user1

其他

视图是由基本表或者视图导出的。

SQL语言中，条件年龄 BETWEEN 18 AND 30表示年龄在18至30之间，且_________。
A、包括30岁但不包括18岁 B、包括18岁和30岁
C、包括18岁但不包括30岁 D、不包括18岁和30岁
正确答案：B

允许取空值但不允许出现重复值的约束是_________。
A、NULL B、PRIMARY KEY
C、UNIQUE D、FOREIGN KEY
正确答案：C

第五章 高级sql

触发器

触发器是一种数据库对象，它是在数据库操作（如 INSERT、UPDATE、DELETE）发生时自动执行的特定操作。触发器能够帮助自动化数据验证、修改、记录日志、执行业务规则等任务。

触发器通常是在表或视图上的某些事件发生时被触发。常见的触发器事件有：

  • INSERT：在向表中插入数据时触发。
  • UPDATE：在更新表中的数据时触发。
  • DELETE：在删除表中的数据时触发。

SQL Server 触发器语法

1
2
3
4
5
6
CREATE TRIGGER trigger_name ON table_name
[ FOR { INSERT | DELETE | UPDATE } ]
[ AS ]
BEGIN
    -- 触发器的逻辑
END;

触发器类型

  1. AFTER 触发器

    定义：在执行 INSERT、UPDATE 或 DELETE 操作后触发。SQL Server 中没有 BEFORE 触发器，因此所有触发器默认在操作之后执行。

  2. INSTEAD OF 触发器

    定义：用于代替 INSERT、UPDATE 或 DELETE 操作。在触发器触发时，原始的操作被替代为触发器定义的逻辑。

  3. BEFORE 触发器

    定义：在进行 INSERT、UPDATE 或 DELETE 操作之前触发。可以用于在操作前检查或修改即将进行的操作数据。

    1
    2
    3
    4
    5
    6
    create trigger<触发器名>
     {before | after}<触发事件>
     on <表名>
     referencing new | old row as <变量>
     for each{row | statement}
     [when <触发条件>] <触发动作体>;
    • FOR EACH ROW子句之后，对于新插入的每一行上面进行迭代。
    • REFERENCING NEW ROW AS NEW子句创建一个过度变量。

    Before 触发器不是 sql server所支持的，但是课本有，这里就提一下。以及这个触发器格式也不是 sql server的。

在 SQL Server 中，触发器提供了两个伪表来访问 INSERT、UPDATE 和 DELETE 操作中的数据：

  • INSERTED：在 INSERT 和 UPDATE 操作中，存储新插入或更新的行数据。
  • DELETED：在 DELETE 和 UPDATE 操作中，存储删除的行数据（或在 UPDATE 中存储更新前的行数据）。

触发器只能定义在基本表上，不能定义在视图上。

其他（必考）

第六章 使用E-R模型的数据库设计

实体 - 联系模型用于表示概念设计。逻辑（概念）模式定义了实体、实体的属性、实体间的联系、实体和联系上的约束等。

就是只考虑需要的功能，不需要考虑如何实现。

数据库设计中要避免的缺陷是冗余、不完整。

E-R模型的基本概念：

  • 实体：表示现实世界中的对象，具有独立存在的意义，例如学生、课程、员工等。实体通过一组属性来描述。

    实体要有主键！！

  • 实体集：是相同类型的实体的集合。

  • 联系：表示实体之间的联系或交互，例如学生和课程之间的“选修”关系。

  • 联系集：是相同类型联系的集合。实体集 E1、E2 … 参与联系集 R。

  • 弱实体（Weak Entity）：没有足够的属性来唯一标识的实体，它依赖于其他实体的主键来构成自己的主键。

    类似需要外键（即别人的主码）来描述自己。

联系集的度定义为实体集参与的数量。

构成 E-R 模型的三个元素：实体、属性、联系。

复杂属性

  • 简单和复合。

    简单属性就是不可再分的，复合属性就是可再分的。

  • 单值和多值

    像电话号码这类属性就是多值属性。{}

  • 派生属性

    可以从其他的属性中计算得到。派生属性的值不存储在数据库中。()

映射基数

映射基数主要有以下几种类型：

  1. 一对一（1:1）

    在一对一关系中，一个实体的每个实例最多只能与另一个实体的一个实例关联，反之亦然。

  2. 一对多（1:N）

    在一对多关系中，一个实体的每个实例可以与另一个实体的多个实例关联，但另一个实体的每个实例只能与一个实体的实例关联。

  3. 多对多（M:N）

    在多对多关系中，一个实体的每个实例可以与另一个实体的多个实例关联，反之亦然。

需要记得是可以为零的！！如果想要一个实体集在联系集中全部参与，记得要双线！！

主码

多对多的主码是 两个实体集的主码的并集。

一对多或者多对一的主码是 “多”那方的主码。

一对一的主码是 任一实体集的主码。

弱实体集

在实体-关系模型（E-R模型）中，弱实体集是指无法单独唯一标识其实例的实体集。弱实体集通常依赖于另一个实体集来进行标识（称为标识性实体集）因此无法独立存在。

没有完整的主键：弱实体集没有自己的主键，它需要依赖另一个实体集的主键来唯一标识每个实体。（外键）

主码由 标识性实体集（主码）和弱实体集的分辨符（即弱实体自己的主码）构成。

弱实体和联系都是双边框的。

标识性实体集 和 弱实体集 必须是一对多的。

转换为关系模型

1. 实体集到关系模型

每个实体集（Entity Set）转换为一个关系（Relation）。实体集中的每个属性都变成关系的一个字段。具体步骤如下：

  • 实体集：每个实体集（矩形框）会成为一个关系（表）。
  • 属性：实体集中的每个属性都变为关系表中的一列（列名）。
  • 主键：实体集中的主键属性在关系中作为主键。

2. 联系集到关系模型

  1. 一对一（1:1）关系：

    如果联系集是一对一（1:1）将其作为两个实体集之一的属性。

  2. 一对多（1:N）关系：

    对于一对多的关系，在“多方”实体集的表中加入“单方”实体集的主键作为外键。

  3. 多对多（M:N）关系：

    对于多对多的关系集，需要创建一个关联表。关联表的字段包括两个实体集的主键作为外键，以及可能的额外属性。

3. 弱实体集到关系模型

对于弱实体集，需要使用其依赖的强实体集的主键以及弱实体集的部分属性来唯一标识弱实体集的实例。

4. 多值属性到关系模型

在关系模型中，每个多值属性转换为一个独立的关系（表）。该表包括原实体集的主键。该关系的所有属性为主码。

其他

一般动作用联系集。

第七章 关系数据库设计

关系数据库设计的⽬的是得到⼀组合适的关系模式，使其不含冗余，结构良好，便于获取信息。

用于设计关系数据库的方法是使用一个叫规范化的过程。

简单来说判断关系好不好，不好就无损分解，使它变好。

分解

  • 有损分解

    对于分解后的两个模式进行自然连接后，无法完整地得到原有的信息。

  • 无损分解

    对于分解后的两个模式进行自然连接后，能够完整地得到原有的信息。

函数依赖

函数依赖是一个形如 $$\alpha \rightarrow \beta$$ 的逻辑推理公式，表示属性集 $$\alpha$$ 决定（determine）属性集 $$\beta$$，或称 $$\beta$$ 依赖 $$\alpha$$。同一模式中包含的多条函数依赖称为函数依赖集。

例如，R 上的两个属性 $$\alpha$$ 和 $$\beta$$，如果关系实例中的所有元组对 $$t_1$$, $$t_2$$ 都符合若 $$t_1[\alpha] = t_2[\alpha]$$，则$$t_1[\beta] = t_2[\beta]$$。也就是说，只要我们知道 $$\alpha$$ 的值，就能唯一确定 $$\beta$$ 的值，称 $$\alpha$$ 决定 $$\beta$$。特别地，如果 $$\beta \subseteq \alpha$$，称为平凡的函数依赖。

由此，我们得出超码的新定义：对于关系 R 和函数依赖集 K，若 $$K \rightarrow R$$ 在 r® 上成立，则 K 是 r® 的一个超码。

若$$R_1$$, $$R_2$$ 是 R 的无损分解，则 r® 上的函数依赖集闭包 $$F^+$$ 中至少存在以下依赖中的一个：

  • R_1 \cap R_2 \rightarrow R_1 ;$$$$R_1 \cap R_2 \rightarrow R_12 $$;

平凡依赖的例子

关系模式 R(A, B, C)

  • 依赖关系：
    • A → A
      这是一个平凡依赖，因为被依赖的属性 A 已经包含在决定属性 A 中。
    • AB → A
      这是一个平凡依赖，因为被依赖的属性 A 是决定属性 AB 的子集。

范式

第一范式

域是原子的，不可分的，即域只有单一的值。

第二范式

非码属性需要整个主码来推出，不能由主码的一部分推出。

BCNF范式

比第三范式严格。

一个关系模式 R 满足 BC 范式，当且仅当：

  • 对于 R 中的每一个非平凡函数依赖 X → Y，X 是 R 的一个超码。

第三范式

比第二范式严格，比 BCNF 放松。

在 2NF 的基础上，消除了非主属性对码的传递函数依赖。

简单来说，就是满足：

  • 对于 R 中的每一个非平凡函数依赖 X → Y，当Y是非主码属性的时候，X一定是超码。

BCNF与第三范式区别

若Y是主码，则一定满足第三范式！！但不一定满足BCNF范式。

BCNF分解 不满足 保持依赖 只满足无损分解！第三范式分解满足两个！！

  • 一个规范化过程是依赖保持的，如果在分解后的所有子关系模式中，所有原始关系模式的函数依赖都能够在这些子关系模式中找到相应的依赖，或者通过子关系模式中的依赖推导出来。

第四范式

比 BCNF 严格。

只能有一个多值依赖，BCNF 可以有多个。

Armstrong 公理系统

反复运用以下三条 Armstrong 公理，就能通过 FFF 求出 F+F^+F+，保证结果是正确有效的。

  • 自反律：若 $$\alpha$$ 为一属性集，$$\beta \subseteq \alpha$$，则$$\alpha \rightarrow \beta$$
  • 增补律：若 $$\alpha \rightarrow \beta$$，$$\gamma$$ 为一属性集，则$$\gamma\alpha \rightarrow \gamma\beta$$
  • 传递律：若 $$\alpha \rightarrow \beta$$ 且$$\beta \rightarrow \gamma$$，则$$\alpha \rightarrow \gamma$$
  • 合并律：若α→β\alpha \rightarrow \beta  且  $$\alpha \rightarrow \gamma$$ ,则$$\alpha \rightarrow \beta\gamma$$
  • 分解律：若$$\alpha \rightarrow \beta\gamma$$,则α→β\alpha \rightarrow \beta  且  $$\alpha \rightarrow \gamma$$
  • 伪传递律：若α→β\alpha \rightarrow \beta  且  $$\gamma\beta \rightarrow \delta$$,则$$\gamma\alpha \rightarrow \delta$$

属性闭包

给定一个关系模式 R 和一组属性 X，属性闭包 X⁺ 是 X 在一组函数依赖 F 下能够决定的所有属性的集合。换句话说，X⁺ 包含了所有可以通过函数依赖从 X 推导出的属性。

确定候选键：通过计算属性闭包，可以判断一组属性是否能唯一标识关系中的所有元组。

正则覆盖

就是精简化 F，同时$$F^+$$不变。

无关属性

在函数依赖 $$\alpha \rightarrow \beta$$ 中：

  • 要证明 $$\alpha$$ 中的属性 A 是无关的，计算 $$(\alpha - A)$$的闭包，如果闭包内属性包含$$\beta$$中所有属性，A 就是无关属性。
  • 要证明 $$\beta$$ 中的属性 A 是无关的，计算 $$\alpha $$的闭包，如果闭包内属性包含A，A 就是无关属性。

【数据库系统原理复习】正则覆盖/最小覆盖 canonical/minimal cover_sql_真的很拉风-腾讯云开发者社区

这个例子讲的很好

计算方法：

  1. 将右侧复合的函数依赖全部拆开。

  2. 去掉重复的。

  3. 看看左边能不能拆开。

  4. 合并。

分解

BCNF分解

满足无损分解，不满足保持依赖。

将每个依赖拆开成Ri，将Ri的主码加回去原本的依赖集内

3NF分解

满足无损分解和保持函数依赖。

将每个依赖拆分开成Ri，如果最后所有的Ri都没有候选码，就加上候选码成为最后一个Ri。

4NF分解（与BCNF类似）

多值依赖

一个 a 值对应了多个 b 值。

固定 a 值，更换 b 值，如果更换之后的元组还存在 R 中，则 a 多值依赖 b。

函数依赖是一个 a 值只能对应一个 b 值。

性质如下：

第一个很明显，多值依赖是一个a对应多个b，那么函数依赖一个a对应一个b当然满足。

其他

在下列关于规范化理论的叙述中，不正确的是_________。
A、任何一个关系模式一定有键。
B、任何一个包含两个属性的关系模式一定满足3NF。
C、任何一个包含两个属性的关系模式一定满足BCNF。
D、任何一个包含三个属性的关系模式一定满足2NF。
正确答案：D

在数据库设计中数据流图（DFD）和数据字典(DD)主要用来描述结构化方法中的_________阶段的工具。
A、概念结构设计 B、需求分析
C、可行性分析 D、逻辑结构设计
正确答案：B

15、关于BC范式下列说法正确的是_________。
A、如果R∈3NF ，则R一定是BCNF
B、若R∈3NF，且不存在主属性对非码的函数依赖，则其是BCNF
C、如果R∈BCNF，则R∈3NF
D、以上说法都不对
正确答案：C

答案是一范式。

上面的第五题原因是关系模式的属性一定是不可分的，刚好满足了第一范式的定义。

设计一个数据库需要六个流程：需求分析，概念设计，逻辑设计，物理设计，数据库实施，运行数据库和维护数据库。

第十二章 物理存储系统

物理存储介质

分为三层，头两层是主存储器，然后是辅助存储器，最后是三级存储器。

主存储器都是易失去的，其余的都是不易失去。

主存

  • 易失。
  • 读写速度很块。
  • 随机访问。

固态硬盘 SSD

  • 不易失。
  • 用闪存实现。
  • 随机访问。

磁盘

  • 不易失。
  • 随机访问。

磁带

  • 随机访问。
  • 顺序访问。

以上四种存储器从上到下容量增大，访问时间越长。

磁盘

分为多个磁盘面，每个磁盘面有多个磁道，每个磁道有多个扇区。

存取时间模型

  1. 寻道时间

    寻道时间是指磁头从当前磁道移动到目标磁道所需的时间。

  2. 旋转延迟

    旋转延迟是指盘片旋转到磁头所在扇区的时间，即磁头等待数据扇区旋转到其下方的时间。

  3. 数据传输时间

    数据传输时间是指从磁头读取数据到数据传输到系统的时间，或者将数据从系统传输到磁头的时间。

访问时间是发出请求到数据开始传输之间的时间，即寻道时间加旋转延迟。

第十三章 数据存储结构

文件组织（记录格式）

定长记录

定长记录是指每条记录的长度（即所占用的存储空间）相同的记录组织方式。在这种组织方式下，所有字段的字节数预先确定，且每条记录严格按照固定长度存储。

1
2
3
4
5
6
7
CREATE TABLE Fixed
(
col1 int              NOT NULL,
col2 char(5)          NOT NULL,
col3 char(3)          NULL,
col4 float            NOT NULL
)

不定长记录

不定长记录是指每条记录的长度可以变化的记录组织方式。在这种组织方式下，记录中的字段长度不固定，可以根据实际数据的需求动态调整。

文件中记录的组织

  • 堆文件组织

    堆文件组织是指记录在文件中无特定顺序地存储，每条记录可以存放在文件的任何位置。通常，一个关系对应一个单独的文件，记录插入时只需在文件末尾添加新记录。

  • 顺序文件组织

    记录根据搜索码的值顺序存储，搜索码是任意属性或属性的集合（不必是超码） 。

  • 散列文件组织

    散列文件组织是通过对记录的某些属性应用散列函数，来确定记录存储的位置（即存储块）。散列函数将搜索码映射到文件的某个存储块中，实现快速的随机访问。

  • 多表聚簇文件组织

    多表聚簇文件组织是指在同一个存储块中存储两个或多个关系中相关的记录。这种组织方式可以高效地处理连接操作，因为相关记录被存储在一起，减少了磁盘I/O操作。

    join 操作的时候会很方便，但是如果平时的简单查询则需要访问更多的块。

缓冲区管理（LRU MRU）

缓冲区是主存用于存储磁盘块拷贝的那部分。

当数据库中的程序需要磁盘中的块，首先先看缓冲区，如果没有的话就将要访问的块调入缓冲区内，使用（MRU或者LRU）算法决定调出的块。

  1. 最近最少使用（LRU）

    最近最少使用（LRU）策略选择在最近一段时间内最少被访问的数据块进行替换。即，最久未被使用的数据块优先被淘汰。

    • 符合时间局部性原理：大多数应用程序具有时间局部性，即最近访问的数据块可能在不久的将来再次被访问。LRU策略能够有效利用这一特性，保留频繁访问的数据块。
    • 适用于事务处理系统中频繁访问相同数据块。

  2. 最近最常使用（MRU）

    最近最常使用（MRU）策略选择在最近一段时间内最频繁被访问的数据块进行替换。即，最近被频繁访问的数据块优先被淘汰。

    • 适用于批量处理或一次性访问大量数据后不再访问。

第十四章 索引

用于在文件中查找记录的属性为搜索码。

不一定是主码！！！

索引分为顺序索引和散列索引。

顺序索引

顺序索引是一种索引方式，其中索引项按照搜索码的顺序排列。

每个索引记录包含搜索码值及其对应的数据记录的存储地址。

  • 聚集索引（主索引）

    搜索码在顺序索引的基础上，还定义了文件存储的次序。可以是稠密或者稀疏的。

  • 非聚集索引（辅助索引）

    搜索码指定的次序和文件存储的次序不同。一定要是稠密的！

常常使用的顺序索引有稠密索引和稀疏索引两类。

稠密索引

在稠密索引中，对于文件的每个搜索码值都有一个索引项。

  • 稠密聚集索引

    索引记录包括搜索码值以及指向具有该搜索码值的第一条数据记录的指针。

  • 稠密非聚集索引

    索引记录必须指向具有相同搜索码值的所有记录的指针列表。

稀疏索引

在稀疏索引中，只为某些搜索码值建立索引。

**一定要搭配聚集索引使用！！**否则根本找不到对应的数据记录。

稠密索引和稀疏索引比较

稠密索引访问速度更快，但是稀疏索引占据内存更小。

多级索引

发现我书本上关于这部分内容是完全没写笔记的，应该不重要。

小总结

聚集索引 可以是 稠密或者稀疏的。

非聚集索引一定是稠密的。

所以稀疏索引一定是 聚集的。

B+树索引

本质上是多级索引。

  • 根节点

    指针数量：根节点至少有两个指针（除非树中只有一个节点，即根节点本身也是叶节点）。

  • 内部节点

    关键字存储：仅存储用于引导搜索的关键字，不存储实际的数据记录。

    指针数量：每个内部节点至少有⌈n/2⌉个子节点指针（其中n为B+树的阶数），最多有n个子节点指针。

    稀疏索引：内部节点的关键字是稀疏的，仅涵盖了叶节点关键字的子集，减少了索引的大小。

  • 叶节点

    关键字和数据指针：每个叶节点存储键值及其对应的数据记录指针。

    链表连接：所有叶节点通过链表按关键字顺序相连，支持顺序遍历。

    指针数量：每个叶节点至少有⌈m/2⌉ - 1个关键字，最多有m - 1个关键字（其中m为B+树的阶数）。

关键字就是搜索码值!!

特点如下：

  1. 所有实际数据记录存储在叶节点
  2. 内部节点仅存储关键字，用于导航
  3. 叶节点通过链表相连，支持高效的范围查询
  4. 高度平衡，所有叶节点在同一层

B+树插入

  • 叶子节点拆分

    拆分完后将右边最小的那个搜索码值加入到父节点中。

  • 内部节点拆分

    将拆出来右边最小的搜索码值从该层去掉并加入到父节点中。

B+树删除

分成两种情况讨论：

问兄弟节点能不能借一个搜索码值：

  • 叶子节点

    将从兄弟那借到的搜索码值 A 写到父节点上。

  • 内部节点

    将从兄弟那借来的搜索码值 A 放到父节点，将原本的父节点值 B 加入到叶子节点中。

借不到搜索码值，需要合并

  • 叶子节点合并

    合并后删除原父节点，并重新分配父节点。

  • 内部节点合并

    这种情况通常是内部节点已经为空了。

    需要将父节点的搜索码值拉下来。

B+树高度

B+树的高度即它的最坏情况下查询复杂度，最坏情况下，每个内层的指针数为$$⌈\frac{n}{2}⌉$$。

h=log⁡⌈n2⌉(k)h = \log_{⌈\frac{n}{2}⌉}(k)

哈希索引

哈希索引通过将关键字通过哈希函数映射到特定的位置，从而实现快速的数据定位和访问。

与B+树索引不同，哈希索引主要优化等值查询（如=操作），而不支持范围查询（如BETWEEN或<, >等操作）

感觉不会考。

第十五章 查询处理

因为老师这部分讲的太烂了，我实在找不到重点。

查询处理：指从数据库中提取数据所做的一系列活动。这些活动包括：将 SQL 语句编译成在文件系统的物理层上使用的表达式、查询优化、查询执行。

要全面说明如何执行一个查询，不仅要提供关系代数表达式，还要对表达式加上注释来说明如何执行每个操作。注释可以声明某个具体操作所采用的算法，或将要使用的一个或多个特定的索引。

执行原语是数据库管理系统（DBMS）中最基本的操作单元，用于实现关系代数中的各类操作。

用于执行一个查询的原语操作序列称为查询执行计划。

常见的查询执行计划有下面所讲的四种连接运算。

查询执行引擎接受一个查询执行计划，执行该计划并把结果返回给查询。

构造最小查询代价的查询执行计划是系统的责任，这项工作叫查询优化。

优化器通常努力去尽可能降低查询计划总的资源消耗，而不是尽可能缩低响应时间。

选择运算

定义$$t_s$$为磁盘访问时间（寻道加旋转延迟），$$t_T$$为块传输时间。

线性搜索

  • A1

    假设文件的块是顺序存储。即我们只需要在磁盘中访问第一个文件块，然后一直顺着一直读下去即可。

  • A1

    因为等值成立就可以返回了，平均需要扫描一半的文件块。

B+树聚集索引

  • A2

    假设树高为$$h_i$$，那么需要从上到下访问$$h_i$$个块（读索引时间），然后获得最终的记录的地址，再去访问。

  • A3

    因为搜索码不是主码，所以最终的索引会有多条记录，但是因为是聚集索引，所以它们是连续存储的。

B+树辅助索引

  • A4

    搜索码为主码的等值比较跟 A2 一样。

  • A4

    因为搜索码不是码，所以最终的索引会有多条记录，并且因为是辅助索引，所以这些记录不是连续存储的。

排序

对不能全部放入内存中的关系进行的排序称为外排序。

其实只介绍了归并算法。

基本流程：假设内存最多可存 M 个块

  • 第一步初始化（创建归并段），每次读入 M 个块进行排序（下图第二列）
  • 第二步分一个内存块给每一个段（最多分 M - 1个），剩下一个作为比较输出。
  • 不断重复第二步，直到归并段数小于 M（此时可以一次性排序）

每执行一趟归并，归并段就会减少为原来的$$\frac{1}{M-1}$$。

嵌套循环连接

最坏情况下：(R 外 S 内)

  • 块传输：$$n_r*b_s + b_r$$

    因为一旦确定一个关系 r 的元组，就需要传输$$b_s$$次块进行一次循环，然后外循环本来也需要传输"自己"进内存$$b_r$$块。

  • 寻道次数：$$n_r+b_r$$

    因为一旦确定关系 r 的元组，就需要寻道一次（for 内循环 s），一共需要寻道 $$n_r$$次。外循环需要寻道$$b_r$$次。

最好情况下：即两个关系可以同时读入内存

  • 只需要一次读全部的关系进内存，需要两次寻道（分别找关系 r 和关系 s 的第一个块），要传输$$b_r+b_s$$次块。

块嵌套循环连接

分析跟上面一样，只不过外层循环以块做单位进行循环，而不是元组。

最坏情况下：(R 外 S 内)

  • 块传输次数：$$b_r*b_s + b_r$$

    因为一旦确定一个关系 r 的块，就需要传输$$b_s$$次块进行一次循环，然后外循环本来也需要传输"自己"进内存$$b_r$$块。

  • 寻道次数：$$b_r+b_r$$

    因为一旦确定关系 r 的块，就需要寻道一次（for 内循环 s），一共需要寻道 $$n_r$$次。外循环需要寻道$$b_r$$次。

最好情况分析跟上面类似。

归并连接

简单来说，就是和两个已经排好序的关系进行归并。

  • 块传输次数：$$b_r+b_s$$

    只需要将两个关系的块放进内存一次即可。

  • 寻道次数：$$\frac{b_r}{b_b} + \frac{b_s}{b_b}$$

    如果分配给每个关系的缓冲块是$$b_b$$，则每次只需要$$\frac{b_r}{b_b}$$次就可以将整个关系 r 读入内存。

散列连接

基本思想：假设一个 r 元组和一个 s 元组满足连接条件，那么它们对于连接属性就会取相同的值。若该值被散列成某个值 i ，则 r 元组必在 ri 中且 s元组必在 si 中。因此，只需要 ri 中的元组和 si 中的元组进行比较即可。

  • 块传输次数：$$3(b_r+b_s)$$

    先将两个关系读入内存，需要一个$$(b_r+b_s)$$；分区完之后写回磁盘，需要一个$$(b_r+b_s)$$；然后每一个拿出来比较，需要一个$$(b_r+b_s)$$。

  • 寻道次数为：$$2(\frac{b_r}{b_b}+\frac{b_s}{b_b})+2*n_h$$

    如果分配给每个关系的缓冲块是$$b_b$$，一共有$$n_h$$个分区。

    将两个关系完整的读入内存并写回需要$$2(\frac{b_r}{b_b}+\frac{b_s}{b_b})$$次寻道机会。每一个分区元组拿出来比较的时候，默认每个关系在每个分区都只需要一次寻道。

第十六章 查询优化

目标是尽早执行选择和投影运算。

关系表达式的转换

如果两个关系代数表达式在每个合法的数据库实例上都会产生相同的元组集，则这两个表达式是等价的。

一个合法的数据库实例是满足数据库模式中设定的完整性约束的数据库实例。

等价规则

这里我就强调几个感觉挺重点的（个人感觉）：

  • 连接运算满足交换律

    连接运算（Join Operation）满足交换律，即两个关系的连接顺序可以互换，结果不变。

    R⋈S=S⋈RR \bowtie S = S \bowtie R

  • 自然连接满足结合律

    自然连接（Natural Join）满足结合律，即多个自然连接的组合顺序不会影响最终结果。

    (R⋈S)⋈T=R⋈(S⋈T)(R \bowtie S) \bowtie T = R \bowtie (S \bowtie T)

  • 选择条件只涉及左侧关系的属性

    σθ(R⋈S)=σθ(R)⋈S\sigma_{\theta}(R \bowtie S) = \sigma_{\theta}(R) \bowtie S

    前提：选择条件 $$\theta$$ 只涉及关系 R 的属性。

  • 选择条件 $$\theta_1$$ 只涉及左侧关系的属性 和 选择条件 $$\theta_2$$ 只涉及右侧关系的属性

    σθ1∩θ2(R⋈S)=σθ1(R)⋈σθ2(S)\sigma_{\theta_1 \cap \theta_2}(R \bowtie S) = \sigma_{\theta_1}(R) \bowtie \sigma_{\theta_2}(S)

  • 令$$L1$$和$$L2$$分别代表$$E1$$和$$E2$$的属性，假设连接条件$$\theta$$只涉及$$L1 \cup L2$$的属性

    πL1∪L2(E1⋈θE2)=πL1(E1)⋈θπL2(E2)\pi_{L1 \cup L2}\left(E_1\bowtie_{\theta} E_2\right) = \pi_{L_1}(E_1) \bowtie_{\theta} \pi_{L2}(E_2)

感觉等价优化就是看能不能在连接前把选择和投影执行了。

规模估计

数据库目录存储了数据库的统计信息。

V(A,r)$$代表关系 r 中属性 A 的可取值数量。即域的大小。 假设 A 是性别，则$$V(A,r)$$是 2 ，因为只有男女。 #### 选择规模估计 - $$σ_{A=a}(r)$$： 估计为$$n_r*\frac{1}{V(A,r)}$$。 就是总元组数量 乘以 属性 A 等于 a 的概率。 - $$σ_{A<a}(r)$$： 估计为$$n_r * \frac{v-min(A,r)}{max(A,r)-min(A,r)}

合取估计

σθ1∧θ2⋯∧θn(r)\sigma_{\theta_{1} \wedge \theta_{2} \cdots \wedge \theta_{n}}(r)

假设一个条件满足的概率（中选率）数记为$$s_i/n_r$$，那么估计的元组数量为$$n_{r} \cdot \frac{s_{1} \cdot s_{2} \cdot \ldots \cdot s_{n}}{n_{r}^{n}}$$

析取估计

σθ1∨θ2∨⋯∨θn(r)\sigma_{\theta_{1} \vee \theta_{2} \vee \cdots \vee \theta_{n}}(r)

概率估计为$$1 - \left(1 - \frac{s_{1}}{n_{r}}\right) \cdot \left(1 - \frac{s_{2}}{n_{r}}\right) \cdot \cdots \cdot \left(1 - \frac{s_{n}}{n_{r}}\right)$$

连接估计

  1. R 和 S 没有交集

    当 R 和 S 没有交集时，表示没有共同的属性用于连接操作。在这种情况下，连接条件不涉及任何公共属性，因此连接操作将形成笛卡尔积（Cartesian Product），每个 R 中的元组都会与每个SS 中的元组连接。

    例如，假设 R 有 1000 个元组，S 有 500 个元组，则连接结果有 500,000 个元组。

  2. R 和 S 的交集是主码

    若交集是 R 的码，那么 S 中的每个元组最多只能跟一个 R 中的元组相连，所以连接后数量不会超过 S 中元组数量（因为可能 S 中的属性值在 R 中没有）；反之也一样。

    若交集是 S 中引用 R 的外码，则连接后数量与关系 S 元组数量一样。

  3. R 和 S 的交集不是主码

    假设交集的属性为 A ，考虑 R 中的元组 r，估计单个元组 r 能在连接中产生$$\frac{n_s}{V(A,s)}$$个元组。

    一共有 $$n_r$$个元组，所以一共能产生$$\frac{n_s*n_r}{V(A,s)}$$个元组。

    或者产生$$\frac{n_s*n_r}{V(A,r)}$$个元组。

    简单来想，就是数量相乘然后除以V(A,r)或者V(A,s)，取小的那个值。

外连接

  • 左、右外连接

    就是自然连接的估计再加上左或者右的关系规模。

  • 全外连接

    自然连接的估计加上左和右的关系规模。

第十七章 事务

事务的四个性质

ACID 属性是数据库事务管理的核心原则，确保事务执行的可靠性和数据库的完整性：

  • 原子性：事务的操作要么全部完成，要么全部不做。
  • 一致性：事务执行前后，数据库始终处于一致状态。
  • 隔离性：并发事务之间相互隔离，互不干扰。
  • 持久性：事务一旦提交，其结果永久保存在数据库中。

抽象事务模型

如果一个事务是已提交（commit）或者中止（rollback回滚之后），才能称这个事务是终止的。

当事务执行完最后⼀条语句，会进入部分提交状态。此时实际输出可能仍驻留在主存中，硬件故障可能会导致中止。

事务的并发调度

并发的好处：

  • 提高吞吐量和资源利用率
  • 减少等待时间

当多个事务并发执行时，隔离性可能被违背，这导致即使每个单独的事务都是正确的，但数据库的一致性还是会被破坏。

**调度：**描述的执行顺序，定义了指令在系统中的执行的时间顺序。必须包含所有事务的全部指令，并且这些指令必须保持它们原本事务的顺序。

串行调度和并发调度这里就不写了…

结论：并非所有的并发执行都能得到正确的状态（即保证了数据库的一致性）。

并发的一些问题

  1. 脏读： 一个事务读取了另一个事务尚未提交的数据。如果第二个事务回滚，第一事务读取到的数据就会无效。这会导致数据不一致。
  2. 不可重复读： 在同一事务中，两次读取同一数据得到的结果不同，原因是另一事务在期间修改了数据。
  3. 幻读：是指在一个事务内，多次查询同一范围的数据时，得到的结果集不一致。这种现象通常发生在并发事务中，当一个事务在读取数据时，另一个事务插入了新的数据行，导致第一个事务在后续读取时发现了新的行。

我们想要并发调度在某种意义上等价于一个串行调度，这个调度就是可串行化调度。

可串行化调度

主要考虑的是冲突可串行化调度。

冲突可串行化指的是一个并发事务调度可以通过交换不冲突的操作顺序，转化为某个串行调度，且两个调度的执行结果完全相同。

冲突的操作顺序：

  • 读-写冲突：事务 $$T_1$$读取 X，事务 $$T_2$$ 写入 X。
  • 写-读冲突：事务 $$T_1$$ 写入 X，事务 $$T_2$$ 读取 X。
  • 写-写冲突：事务 $$T_1$$ 写入 X，事务 $$T_2$$ 写入 X。

如果调度 S 经过一系列非冲突指令的交换转换成调度 S’，则称 S 和 S‘ 是冲突等价的。

如果调度 S 经过一系列非冲突指令的交换转换成串行调度，则称 S 和 S‘ 是冲突可串行化的。

优先图

结论：如果优先图中无环，则该调度是可冲突串行化的。

边：考虑上面的三种冲突的操作顺序，若满足这三个条件其中之一：

  • 读-写冲突：事务 $$T_1$$读取 X 之前，事务 $$T_2$$ 写入 X。
  • 写-读冲突：事务 $$T_1$$ 写入 X 之前，事务 $$T_2$$ 读取 X。
  • 写-写冲突：事务 $$T_1$$ 写入 X 之前，事务 $$T_2$$ 写入 X。

则插入由$$T_2$$为起点，$$T_1$$为终点的有向边进入优先图。代表$$T_2$$执行完后，$$T_1$$才能执行。

要记得起点是先执行的！！

事务的可恢复性

可恢复调度是指一种事务调度方式，其中如果一个事务 $$T_i$$ 依赖于另一个事务 $$T_j$$的修改（即 $$T_i$$读取了 $$T_j$$修改的数据），那么 $$T_j$$ 必须在 $$T_i$$提交之前先提交。

这确保了如果 $$T_j$$ 发生故障并回滚，依赖于它的事务 $$T_i$$ 也可以安全地回滚，避免数据不一致。

无级联调度是一种更加严格的可恢复调度。在无级联调度中，一个事务只读取已经提交事务的数据。这意味着，如果一个事务 $$T_i$$ 读取了事务 $$T_j$$ 的数据，那么 $$T_j$$必须在 $$T_i$$ 读取数据之前已经提交。这样，即使$$T_j$$失败，$$T_i$$ 也不会受到影响，因为 $$T_i$$ 只依赖于已提交的数据。

事务的隔离性级别

  • 可串行化
  • 可重复读
  • 已提交读
  • 未提交读

其他

一个事务执行过程中，其正在访问的数据被其他事务所修改，导致处理结果不正确，这是由于违背了事务的何种特性而引起的
A、隔离性 B、 一致性 C、原子性 D、 持久性
正确答案：A

在数据库恢复时，对尚未做完的事务执行（ ）。
A. REDO处理
B. UNDO处理
C. ABORT处理
D. ROLLBACK处理
正确答案： B

若事务中有表达式a/b，如果b=0时会产生的故障属于（ ）。
A. 事务故障
B. 系统故障
C. 介质故障
D. 死机
正确答案： A

若系统在运行过程中，由于某种硬件故障，使存储在外存上的数据部分损失或全部损失，这种情况称为（ ）。
A. 事务故障
B. 系统故障
C. 介质故障
D. 运行故障
正确答案： C

数据库恢复的基本原理是利用冗余数据。
A. 正确
B. 错误
正确答案： A

第十八章 并发控制

悲观的并发控制就是一检测到出事就立马回滚。

跟我的人生一样…

封锁协议（悲观）

锁有两种：

  • 共享锁（S）：是读取数据用的。
  • 排他锁（X）：是写数据用的。

只有共享锁和共享锁之间是相容的，其他情况都不相容。

数据项上可同时被多个事务持有共享锁（S），此时的排他锁必须一直等到这些事务都释放共享锁才能获得。

死锁

若假设事务$$T_i$$在等待事务$$T_j$$释放关于数据 X 的锁，与此同时，事务$$T_j$$在等待事务$$T_i$$释放关于数据 Y 的锁，两个事务之间互相等待，就发生了死锁。

一旦死锁发生时，就必须在这两个事务中选择一个牺牲者进行回滚。一旦其中一个事务被回滚，另一个事务就可以获得正在等待的锁了。

死锁检测

可以利用等待图来检测是否产生死锁（有环）。

若假设事务$$T_i$$在等待事务$$T_j$$释放关于数据 X 的锁，那么在等待图内就有起点在$$T_i$$终点在$$T_j$$的有向边。

注意：等待图和前面讲的优先图的方向其实是反的… 优先图是等待的事务在有向边终点，而等待图是等待的事务在起点。

死锁恢复

选择牺牲者，回滚牺牲者的事务…

因为选择牺牲者可能基于某个指标，所以可能存在某个事务一直被牺牲，可能会产生饥饿现象。

死锁不太像会考…

两阶段封锁协议

事务分成增长阶段（获得锁）和缩减阶段（释放锁）。

事务最后一次获得锁的位置称为封锁点。

即事务不可以lock -- unlock -- lock --unlock，只可以lock -- lock -- unlock --unlock。

两阶段封锁协议保证了冲突可串行化，因为假设冲突不可串行化，则优先图存在环，证明如下图：

但是两阶段封锁协议不保证死锁，例如在两个事务的增长阶段就可以发生死锁了…

并且也不保证无级联调度，因为两阶段协议没有对于提交有限制。

无级联调度其实就是已提交读。就是只能读取提交之后的数据（写到磁盘内），否则该数据若回滚则读取该数据的事务也需要回滚。

严格两阶段封锁协议

为了保证无级联调度，严格两阶段封锁协议要求事务只能在提交之后释放排他锁。以满足已提交读。

基于时间戳的协议（悲观）

这个协议保证了冲突可串行化和无死锁（因为不会发生等待）。

但是可能会发生不必要的回滚操作和饿死。

对于每个事务，根据系统时钟或者逻辑计数器分配一个时间戳。

基本思想：

  • 开始早的事务不能读开始晚的事务写的数据。
  • 开始早的事务不能写开始晚的事务已经读过或写过的数据。

读操作（Read Operation）

当事务 $$T_i$$ 试图读取数据项 X 时：

  • 检查 X 的最后写时间戳 W(X)。
  • 如果 $$W(X) > TS(T_i)$$，表示有一个较晚的事务已经修改了 X，此时 $$T_i$$读取到的数据可能是不一致的，因此 拒绝 $$T_i$$ 的读操作，并 回滚 $$T_i$$。
  • 否则，允许 $$T_i$$ 读取 X，并更新 X 的读时间戳 $$R(X) = \max(R(X), TS(T_i))$$。

写操作（Write Operation）

当事务 $$T_i$$ 试图写入数据项 X 时：

  • 检查 X 的最后读时间戳 R(X) 和最后写时间戳 W(X)。
  • 如果 $$R(X) > TS(T_i)$$ 或 $$W(X) > TS(T_i)$$，表示有一个较晚的事务已经读取或修改了 X，此时 拒绝 $$T_i$$ 的写操作，并 回滚 $$T_i$$。
  • 否则，允许 $$T_i$$ 写入 X，并更新 X 的写时间戳 $$W(X) = TS(T_i)$$。

Thomas 写规则

大部分都跟时间戳排序一样，不过在写操作中，如果$$W(X) > TS(T_i)$$，则不选择回滚，而是忽略。

基于有效性检查的协议（乐观）

tmd ppt就三页，而且我书上没有画任何笔记。

可串行化和避免级联回滚。

基于有效性检查的协议假设事务之间很少发生冲突，因此允许事务自由执行，直到提交阶段才进行冲突检测和验证。

为了判断有效性，需要增加三个时间戳：

  1. StartTS(Ti)：事务Ti开始的时间。
  2. ValidationTS(Ti)：事务Ti进行有效性检查的时间。
  3. FinishTS(Ti)：事务Ti完成其写阶段的时间。

通常分为三个阶段：

  1. 读阶段

    读取各项数据，并且将其保存在局部变量中。这时候执行的 write 操作都是对局部变量进行的。

  2. 有效性检查阶段

    判断读阶段的 write 操作是否满足有效性，满足的话进入写阶段；不满足则回滚。

    事务 Ti 的有效性检查时对于满足 TS(Tk) < TS(Ti) 的所有事务 Tk 需满足下列条件的其中一个：

    1. FinishTS(Tk) < StartTS(Ti)

      即事务 Tk 在事务 Ti 开始之前已经完成执行了。

    2. Tk 所写的数据项集合和 Ti 所读的数据项集合并不相交，并且在 Ti 开始有效性检查之前，Tk 已经完成写阶段了，即**(StartTS(Ti) < FinishTS(Tk) < Validation(Ti))**。

  3. 写阶段

    将局部变量的 write 操作结果拷入到数据库中。

多版本机制

每个 write (Q) 的操作就创建一个 Q 的新版本。

感觉不太重要。

其他

第十九章 恢复系统

恢复与原子性

使用最广泛的数据库修改的结构就是日志。

日志是日志记录的序列。

更新日志记录具有以下字段：<$$T_i$$, $$X_j$$,$$V_1$$,$$V_2$$>。

  • 事务标识$$T_i$$
  • 数据项标识$$X_j$$
  • 旧值$$V_1$$
  • 新值$$V_2$$

以下是其他的日志记录类型：

  • <$$T_i$$ start>
  • <$$T_i$$ commit>
  • <$$T_i$$ abort>

每次事务执行写操作时，必须在数据库修改前建立该次写操作的日志记录并把它加到日志中。再实际执行写数据库。

利用日志来恢复数据。

日志的恢复原理是利用了冗余数据。

使用日志重做和撤销事务

重做（redo($$T_i$$)）

这个过程将事务$$T_i$$更新过的数据项的值都设为新值。

  • 如果日志中只有<$$T_i$$​ start>语句并且有<$$T_i$$ commit>或<$$T_i$$ abort>语句，需要重做。

撤销（undo($$T_i$$)）

该过程将事务$$T_i$$更新过的数据项的值都设为旧值。

  • 撤销过程需要写日志记录！这个特殊的日志记录是 read-only 记录。

    类似<$$T_i$$, $$X_j$$, $$V_1$$>，这种日志也叫补偿日志记录。

  • 完成撤销操作之后需要增加<$$T_i$$, abort>语句，表示 undo 完成了。

  • 如果日志中只有<$$T_i$$ start>语句并且没有<$$T_i$$ commit>或<$$T_i$$ abort>语句，需要撤销。

每个事务在日志中，一定会以 <$$T_i$$, commit>或者<$$T_i$$, abort>终止。

检查点

在执行检查点的过程中将所有修改过的缓冲块（存在内存）全部写入磁盘（永久保存）。

然后在日志中加入< check point >语句。

提高了数据恢复的效率。

假设事务$$T_i$$在日志中的< check point >语句前已经有<$$T_i$$, commit>或者<$$T_i$$, abort>语句，则数据恢复的时候可以不用对事务$$T_i$$进行 redo 操作。

恢复算法（感觉本章重点）

事务回滚

正常情况下的事务$$T_i$$回滚流程：

  1. 从后往前检查日志，对于发现的<$$T_i$$, $$X_j$$,$$V_1$$,$$V_2$$>语句记录：
    • 将值$$V_1$$写入数据项$$X_j$$。
    • 往日志中写入<$$T_i$$, $$X_j$$, $$V_1$$>这种 read-only 记录（也叫补偿日志记录）。
  2. 一旦发现<$$T_i$$ start>语句，就停止算法，并且往日志中写入<$$T_i$$, abort>语句。

系统崩溃后的恢复

分为重做阶段（从上到下）和撤销阶段（从下到上）。

  1. 重做阶段

    系统通过从最后一个检查点开始从上到下扫描日志来重演所有事务的更新。

    • 初始化 undo-list ，将检查点时刻未终止的事务加入 undo-list。
    • 从检查点从上到下扫描日志，遇到形如 <$$T_i$$, $$X_j$$, $$V_1$$>或者<$$T_i$$, $$X_j$$,$$V_1$$,$$V_2$$>的语句就执行重做。
    • 一旦发现<$$T_i$$ start>语句就将$$T_i$$加入 undo-list。
    • 遇到<$$T_i$$, commit>或者<$$T_i$$, abort>语句就将该事务从undo-list中去除。

    此时 undo-list 中的事务是发生故障时还没终止的事务。

  2. 撤销阶段

    系统回滚 undo-list 中的事务。

    • 一旦发现 undo-list 中的事务的日志记录，就执行撤销操作。
    • 如果遇到<$$T_i$$ start>语句就将该事务从 undo-list 中去除。
    • 当 undo-list 为空时即完成恢复。

重做阶段就是从检查点开始重演了所有的日志记录，包括未完成事务的动作和回滚失败事务而执行的动作。

感谢名单：nn。

数据库原理及应用期末复习汇总(附某高校期末真题试卷)_数据库原理期末考试题-CSDN博客

数据库恢复技术-数据库习题_数据库恢复技术例题-CSDN博客

数据库期末考试复习题库(非常全面) - 百度文库

连接代价

数据模型是数据库的核心

数据模型是数据结构 数据操作 完整性约束

关系模型的完整性是实体完整性 用户自定义完整性 参照完整性

物理数据独立性

逻辑层的简单实现可能在物理层很复杂，但是逻辑层的用户并不清楚。

逻辑数据独立性

锁

可恢复调度 无级联调度

锁的调度

什么是调度

冲突可串行化解释

数据库复习
https://tobytam23.github.io/2025/01/25/数据库复习内容/
Author
tanzhuoheng
Posted on
January 25, 2025
Licensed under