database-theory-summary

数据库 期末复习

第一章 绪论

基本概念

• 数据：描述现实世界中各种事物的可以识别的符号。
• 信息：一种已经被加工为特定形式的数据。数据只有被加工为信息才有价值。
  • 信息是各种数据所包括的意义。
  • 数据是信息的载体，是信息的具体表现形式。
• 数据处理：从大量原始数据抽取和推导有价值信息的加工过程。包括：数据收集、组织、存储、加工、分类、检索、输出、传输等操作。
• 数据管理：数据处理一般性的基本操作，研究专门的技术——数据库管理技术。
• 数据库技术：按照某种数据结构对数据进行组织，将数据存储在计算机的二级存储中，并可以提供数据共享操作的数据管理技术。

什么是数据库系统

建立在数据库管理系统之上，以满足实际应用需求的数据管理（组织、存储、使用）为主要功能的计算机软件系统。

数据管理技术的发展

人工管理阶段

• 时间：20世纪50年代中期以前
• 背景：外存只有磁带、卡片、纸带等，没有磁盘等直接存取设备，没有OS。
• 特点：
  • 数据不在计算机上保存。
  • 没有软件系统对数据进行管理。程序规定数据的逻辑结构与物理结构，程序与数据不具备独立性。
  • 没有文件的概念，数据组织方式必须由程序员设计。
  • 一组数据对应一个程序，数据是面向应用的，程序间不能共享数据。

文件系统阶段

• 时间：20世纪50年代后期到60年代中期。
• 背景：有磁盘、有文件系统。
• 特点：
  • 以文件形式保存在外存上。
  • 文件多样化。
  • 数据的存取基本上以记录为单位。
  • 程序和数据有一定的独立性。
  • 缺点：
    • 数据冗余度大，浪费空间并且易造成数据的不一致性。
    • 数据和程序缺乏独立性。
    • 不能反映现实世界事物之间的关系。

数据库系统阶段

• 时间：20世纪60年代后期开始
• 背景：有了大容量磁盘、光盘，计算机管理数据量大，关系复杂，共享性要求强。
• 特点：
  • 面向全组织的复杂的数据结构，不仅描述数据本身，还描述联系，使得整个组织结构化。数据结构化是数据库与文件系统的根本区别。
  • 数据冗余度小，易扩充。
  • 具有较高的数据和程序独立性。
    • 数据物理独立性：存储结构改变时，逻辑结构可以不变。
    • 数据逻辑独立性：逻辑结构改变时，应用程序可以不变。
  • 提供了两方面映像功能（映像功能实现数据的独立性）：
    • 存储结构与逻辑结构映像——实现物理独立性。
    • 全局逻辑结构与某类应用所涉及的局部逻辑结构之间的映像——实现逻辑独立性。
  • 统一的数据控制功能。
    • 数据安全性控制。
    • 数据完整性控制。
    • 并发控制。
    • 数据库恢复。
  • 数据的最小存取单位是数据项。

数据库系统的组成

• 数据库：数据库中存储的数据是集成的、共享的。
• 用户：存储、维护和检索数据的各类请求。分为三类：
  • 终端用户
  • 应用程序员
  • 数据库管理员
• 软件：包括DBMS和各种应用系统。
• 硬件：存储数据库和运行DBMS的硬件资源，如内存、外存。

数据模型

数据模型用来抽象和表示现实世界中的数据和信息。

在数据库中，模型分为两类：概念模型和数据模型。

数据模型的层次

现实世界 —— 信息世界（概念模型） —— 机器世界（数据模型）

• 数据模型：按计算机系统的观点对数据建模。
• 概念模型：现实世界到信息世界的抽象，是用户和数据库设计人员进行交流的语言。

概念模型

基于信息世界的主要概念，表达应用中的各种语义。具有较强的语义表达能力，能够方便、直接表达应用中的各种语义。应该简单、清晰、易于理解。

概念

• 实体：客观存在并可以相互区分的事物。
• 属性：实体所具有的某一特性。
• 码：唯一标识实体的属性集。
• 域：某个（某些）属性的取值范围。
• 实体型：表示一类实体，用实体名称与属性名集合来抽象刻画。
• 联系：实体之间的联系，有名称、类型（3种），并且可以具有属性。

ER图

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

• 实体：长方形。
• 属性：椭圆形，用无向边连接属性。
• 联系：菱形，用无向边连接有关的实体，并在边上标注联系类型。
• 一些说明：
  • 同一个实体集内部各实体可以有一对一、一对多和多对多联系。
  • 三个或以上的实体可能具有联系。
  • 两个实体之间可能有多种联系。

数据模型

三要素

• 数据结构：由描述数据对象以及对象之间的联系的一组概念组成。是静态特性的描述，是刻画数据模型最重要的方面。
  • 描述对象的类型、内容和性质的概念，如域、属性。
  • 描述对象之间联系的概念，如关系。
• 数据操作：是对数据库中各种数据对象的实例允许执行的操作集合，包括操作以及操作规则。是数据模型的动态特性的描述。数据库主要有检索和更新两大类操作。
• 完整性约束：完整性规则的集合，是给定数据模型中数据及其联系所有的制约和依存规则，用以保证数据正确、相容。

分类

• 层次模型：树结构，用有向树表示一对多联系。
  • 特点：有且仅有一个结点没有双亲，其他节点仅有一个双亲。
  • 优点：结构简单易于实现。
  • 缺点：支持联系种类太少，数据操纵不方便。
  • 代表：IBM的IMS数据库。
• 网状模型：图结构，用有向图表示一对多联系。
  • 特点：可以有一个以上结点没有双亲，至少有一个结点有多于一个双亲。表达的联系种类丰富，结构复杂。
• 关系模型：二维表
  • 特点：用关系描述实体与实体间的联系，可直接表示多对多联系，关系必须是规范化关系（不允许表套表），必须建立在数学概念基础上。

数据库系统的结构

三级模式、两级映像。

模式

数据库中全体数据的逻辑结构和特性的描述。

是三级模式的核心，不涉及物理存储细节，与具体应用程序和编程语言无关。

用模式DDL写出的一个数据库逻辑定义的全部语句称为某个数据库的模式。

外模式

个别用户的数据视图，即与某一应用有关的数据的逻辑表示。通常是模式的子集，一个应用只能启用一个外模式。数据库提供外模式描述语言定义外模式。

内模式

称为存储模式，是数据在数据库系统内部的表示，即对数据的物理结构和存储方式的描述。

两级映象

• 外模式/模式映象定义某个外模式与模式之间的对应关系，当模式改变时，映像做出改变就可以保证外模式不变。——数据的逻辑独立性
• 模式/内模式映象定义数据逻辑结构与存储结构之间的对应关系，内模式改变时，修改该映象可以使得模式保持不变。——数据的物理独立性

三级模式结构的优点

• 保证数据的独立性
• 简化用户接口，方便用户使用
• 有利于数据共享
• 有利于数据的安全保密

DBMS

主要功能

• 数据库定义功能：提供DDL语言描述外模式、模式和内模式，模式翻译程序把原模式翻译成目标模式，存入数据字典。
• 数据存取功能：提供DML语言进行增删查改。
• 数据库运行管理：并发控制、存取控制、完整性约束条件检查和执行……
• 数据组织、存储和管理
• 数据库的建立和维护

组成

• 语言编译处理程序
• 系统运行控制程序
• 系统建立和维护程序
• 数据字典

第二章 关系数据库

关系的数学定义

• 域
• 元组和分量
• 关系：笛卡尔积$D_1 * D_2 * …$的子集叫做在域$D_1 * D_2 * …$上的关系，用$R(D_1, D_2, …)$表示。$n$是关系的度或目（$degree$）。

关系数据模型

数据结构

• 关系模型的数据结构——关系。
• 码
  • 候选码：关系中的某一个属性组，若它唯一标识元组并具有最小性则为候选码。
  • 主码：选定一个候选码为主码。
• 主属性：码中的属性。
• 非主属性：不在码中的属性。
• 关系模式：$R(U, D, dom, F, I)$，简记作$R(A_1, A_2,\dots,A_n)$。关系式关系模式在某一时刻的状态或内容。关系模式是相对稳定的，关系是动态的。
• 语义约束：
  • 实体完整性：要有属性或属性组合作为主码，主码不能为空或部分为空。
  • 参照完整性：
    • 外码：某个R的属性（组）与另外一个基本关系S的主码对应，即为外码。R为参照关系，S为被参照关系（目标关系）。
    • 参照完整性：外码或者等于S的主码，或者为空。
  • 用户定义完整性

数据操作

• 特点：集合操作，操作对象都是集合。

• 基础：关系运算，分为代数方式和逻辑方式。

  • 关系代数

  • 关系演算

    • 元组关系演算
    • 域关系演算

关系代数

共有9种：

• 常规集合运算：并、差、交、广义笛卡尔积。
• 特有关系运算：选择、投影、连接、自然连接、求商。

传统集合运算

是二目运算，除了笛卡尔积外，要求参加运算的两个关系必须是同类关系。

• 并：将R和S的元组统一到一个集合。
• 差：从R中剔除S中存在的元组。
• 交：R和S的共同元组。
• 广义笛卡尔积：将R和S的元组并列。

专门的关系运算

• 选择：在R中选择出满足条件的元组，记作$\sigma_F® = {t|t∈R,F(t)=true}$。
• 投影：从R中选出若干属性删除重复的行，记作$\pi_A®={t[A]|t∈R,A\sube U}$。
• 连接：R和S在属性X和Y上的连接（X，Y是连接属性，即X和Y包含同等数量的属性，且相应属性有共同的域），是从两个关系的广义笛卡尔积里选出满足比较条件θ的元组，记作 $R⋈S_{X \theta Y}={t|t=<r,s>\and s∈S\and r∈R\and r[X]\theta r[Y]}$。
• 自然连接：在相同属性列取值相等为条件的连接，要去掉重复属性列。
• 除法：关系S的属性是关系R属性的子集，记为$R\div S={t|t∈\pi_X®\and s∈S\and <t,s>∈R}$。（结果包含S中没有的属性）

关系演算

元组关系演算

基本结构是元组演算表达式。

域关系演算

类似于元组演算，公式中的变量对应元组各个分量的域变量。

关系运算的安全约束

不产生无限关系和无穷验证的运算成为安全运算，其表达式称为安全表达式，对其采取的限制称为安全约束。

数据库数据语言

• DDL：数据定义（描述）语言
• DML：数据操纵语言，检索、插入、修改、删除。
  • 联机交互方式
  • 宿主语言方式
• DCL：数据控制语言，完成安全性控制、完整性控制、并发控制等。
• 关系数据语言特点：
  • 一体化
  • 非过程化
  • 面向集合的存取方式
  • 既可以独立使用又可以与主语言嵌套使用

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

SQL的特点

• 综合统一
• 高度非过程化
• 面向集合
• 以同一种语法结构提供两种使用方式
• 语言简捷、易学易用

基本概念

• 基本表：实际存在的
• 导出表：有视图（虚表）和快照。

检索

• SELECT A FROM B：对应不去重的投影操作。
• SELECT DISTINCT A FROM B：对应投影。
• SELECT A FROM B WHERE C = D：选取检索，可以用AND、OR或NOT连接条件=，<>，>，>=，<，<=。可以使用BETWEEN a AND b表示某个区间。
• SELECT A FROM B WHERE C = D ORDER BY A ASC：对A升序排列，如果降序可以写DESC。
• WHERE后可以指明连接条件，选择需要的若干列。
• 外连接：SELECT * FROM S, SC WHERE S.S#=SC.S#(*)
• 子查询：
  • 如果返回单值，可以直接用比较运算。
  • 如果返回了多值，必须在比较运算符和子查询之间加入ANY或ALL。
  • IN与=ANY是等价的，NOT IN与!=ALL是等价的。
  • EXISTS：在子查询结果非空时为真。
  • NOT EXISTS：子查询结果为空时为真。
• 并：UNION
• 交：INTERSECT
• 差：MINUS
• COUNT：按列值记个数，COUNT(*)对行记数。
• SUM：对数值列求和。
• AVG：求数值列平均值。
• MAX：求列的最大值。
• MIN：求列的最小值。
• GROUP BY A [HAVING B = C]。

表操作

定义基本表

CREATE TABLE table_name (S# char(5) not null unique, SN char(20) not null, SA int, primary key(S#), check(SA >= 18))

修改基本表

ALTER TABLE table_name [ADD <新列名><数据类型>][DROP<完整性约束名>][MODIFY<列名><数据类型>]

删除基本表

DROP TABLE table_name

定义视图

CREATE VIEW view_name AS (SELECT ...)

• 视图消解：将视图定义的子查询和用户查询结合，转换成对基本表的查询。
• 视图作用：
  • 检化用户操作
  • 使用户能够以多种角度看待同一数据
  • 提供一定程度的逻辑独立性
  • 能够对数据提供安全保护

数据更新

插入

INSERT INTO table_name ([<属性列>{,<属性列>}]) VALUES(<值>{,<值>})

修改

UPDATE table_name SET <列名>=<表达式>

删除

DELETE FROM table_name [WHERE <条件>]

嵌入式SQL

把SQL的最佳特性与程序设计语言的最佳特性结合，使SQL功能更强，灵活性更强。

预编译法：把嵌入在程序中的SQL语句翻译为高级语言源码，然后按主语言的通常方式进行编译、链接生成可执行代码。

动态SQL

允许程序运行过程中临时组装SQL语句，有语句可变、条件可变、数据库对象，查询条件均可变三种形式。

ODBC/JDBC

四个组件：应用程序、驱动程序管理器、驱动程序和数据源。

第四章 数据库设计

数据库设计概述

• 数据库设计：对于一个给定的应用环境，设计优化的数据库逻辑和物理结构，建立数据库，使之能够有效地存储数据，为开发满足用户需求的应用系统奠定基础。
• 数据库设计的特点：要把数据设计和处理设计密切结合。
• 设计方法：
  • 手工试凑法：根据应用的数据要求与处理要求直接设计数据库的结构。
  • 规范设计法：运用软工思想，整个设计过程划分为若干阶段，每个阶段只解决整个设计中的部分问题，是迭代和逐步求精的过程。

数据库设计的基本步骤

• 需求分析：现实世界
• 概念结构设计：概念模式，生成概念模型，ER图
• 逻辑结构设计：逻辑模式，生成DBMS支持的数据模型
• 物理结构设计：内模式，设计存储结构和存取方法
• 数据库实施
• 数据库运行维护

需求分析

• 目标：收集支持系统应用目标的基础数据及其处理。重点是“数据”和“处理”，包括处理要求，信息要求，安全性与完整性要求。
• 两个阶段：调查用户实际要求；分析表达需求，用数据流图和数据字典。
• 数据流图
  • 自顶向下逐步分解处理功能以及他们所用的数据。
• 数据字典：需求分析阶段，可以看成数据元素表。
  • 包含每一个数据元素的名字、含义等各方面的描述。
  • 从数据流图提取出所有原子数据项。
  • 把有联系的数据项组合起来形成数据组。
  • 以数据组为单位写出语义定义、类型定义、完整性约束定义等。

概念结构设计

ER图：参考上面第一章内容。

设计概念结构四类方法

• 自顶向下
• 自底向上：最常用
• 逐步扩张
• 混合策略

数据抽象

• 分类：定义某一概念作为现实世界中一组对象的类型。
• 聚集：定义某一类型的组成成分。
• 概括：定义类型之间的一种子集联系。

实体模型的调整原则

• 属性不能再分，必须是不可分的数据项。
• 属性不能与其他实体有联系。
• 实体与属性之间保持1:1或n:1联系，不满足的情况可以将属性上升为实体。

集成局部ER图

• 合并：解决各分ER图之间的冲突，将各分ER图合并成初步ER图。冲突主要包括属性冲突、命名冲突和结构冲突。
• 修改和重构：消除冗余生成基本ER图。

设计基本ER图

• 消除冗余，可能存在冗余数据或冗余联系。

逻辑结构设计

把概念结构转换为选用的DBMS所支持的数据模型。

步骤

• 概念结构根据转换规则生成一般数据模型。
• 根据关系数据理论，进行规范化。
• 生成特定DBMS支持下的数据模型。
• 优化数据模型。

物理结构设计

• 确定存储结构：索引、聚集、hash。
• 选择关系的存取方法

第五章 关系数据理论

函数依赖

• 数据依赖：属性值之间相互依赖又相互制约的关系。最重要的有两种：函数依赖和多值依赖。

函数依赖的定义

• 定义：对于X的每个具体值，Y有唯一的值与之对应，则称X函数确定Y或Y函数依赖于X。（$X\rightarrow Y$）

相关术语

• 平凡函数依赖：$Y\sube X$。
• 非平凡函数依赖：不是平凡函数依赖。
• 决定因素：$X$是$X\rightarrow Y$的决定因素。
• 完全函数依赖：如果有$X\rightarrow Y$且对于任意$X$的真子集$X’$都有$X’\nrightarrow Y$，则是完全函数依赖。
• 部分函数依赖：不是完全函数依赖的函数依赖。
• 传递函数依赖：$X\rightarrow Y$且$Y\rightarrow Z$，并且$Y \nrightarrow X$，则称$Z$对$X$传递函数依赖。

补充说明

函数依赖是语义范畴的概念，不随时间变化。

与联系的关系

• 1对1：有$X\rightarrow Y$和$Y\rightarrow X$。
• 1对m：有$Y\rightarrow X$。
• n对m：无函数依赖关系。

关系键的形式定义

• 候选码与主码：
  • 候选码：U完全函数依赖于K。
  • 主码：如果多个候选码，就选一个作为主码。性质有唯一性和最小性。
• 主属性与非主属性：
  • 主属性：包含在任何一个候选码中的属性。
  • 非主属性：不是主属性。
• 外部码：R中的属性或属性组X不是R的码但是是另一个关系模式的码，则X是R的外部码。

函数依赖的逻辑蕴涵

• 从$R<U, F>$中可以推出$X \rightarrow Y$则称为$F$逻辑蕴涵$X \rightarrow Y$。
• $F$的闭包：$F$所蕴涵的函数依赖的全体，记作$F^+$。

Armstrong公理系统

对于$R<U, F>$有如下规则：

• A1自反律：若$Y\sube X\sube U$则$X \rightarrow Y$为$F$所蕴涵。
• A2增广律：若$X \rightarrow Y$为$F$所蕴涵，且$Z\sube U$则$XZ\rightarrow YZ$为$F$所蕴涵。
• A3传递律：若$X \rightarrow Y$且$Y \rightarrow Z$为$F$所蕴涵，则$X \rightarrow Z$为$F$所蕴涵。

推论

• 合并规则：由$X \rightarrow Y$，$X \rightarrow Z$，有$X \rightarrow YZ$。
• 伪传递规则：由$X \rightarrow Y$，$WY \rightarrow Z$，有$XW \rightarrow Z$。
• 分解规则：由$X \rightarrow Y$和$Z \sube Y$，有$X \rightarrow Z$。
• 定理1：$X \rightarrow A_1 A_2 A_3\dots A_k$成立等价于$X\rightarrow A_i$（i = 1, 2, 3…k）成立。

属性集闭包

• 定理：$X \rightarrow Y$可以由$F$根据公理系统导出等价于$Y \sube X_F^+$。

公理系统的有效性与完备性

• 有效性：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F所蕴涵的函数依赖的全体之中。
• 完备性：F所蕴涵的函数依赖的全体中的每一个函数依赖，必定可以由F根据Armstrong公理系统导出。

求属性闭包的算法

• 初始，$X_F^+=X$，然后把$F$中所有$X_F$下属性能推出的属性都加进去，直到不变或者变为属性全集$U$。

函数依赖集等价

• 若函数依赖集$F^+=G+$，则称F和G等价。
• 最小函数依赖集条件：
  • $F$中任一函数依赖$X \rightarrow A$，$A$必须是单属性。
  • $F$中不存在$X \rightarrow A$使得$F$与$F-{X\rightarrow A}$等价，即不存在多余的依赖。
  • $F$中不存在$X \rightarrow A$，在$X$中有真子集$Z$，使得$F$与$F-{X \rightarrow A}∪{Z \rightarrow A}$等价，即左侧不能有多余的属性。
• 极小化的算法：
  • 首先将所有$X\rightarrow Y$的$Y$展开。
  • 逐个检查$F$中的函数依赖的左侧，如果左侧是多属性，且删去一个属性后依然可以推出右侧，则能够删掉。形式化为：对于$X \rightarrow A$，设$X=B_1\dots B_m$，如果$A∈(X-B_i)^+_F$，则以$(X-B_i)$取代$X$直到$F$不再改变。
  • 逐个检查$F$中的每个函数依赖，如果删掉函数依赖后的$G=F-{X\rightarrow A}$，仍然可以有$A∈(X)_G^+$，就删除该函数依赖。

范式

如果一个关系满足某个指定的约束集，则称它属于某种特定的范式（Normal Form）。

1NF

当一个关系只包含原子值这一约束时，称为1NF。也就是表里每个格只有一个值。满足原子值这一约束条件的关系称为规范化关系简称范式。

一个低一级范式的关系模式，可以通过模式分解转换为若干高级范式的关系模式的集合，这个过程称为规范化。

2NF

• 定义：1NF的关系的每个非主属性完全依赖于码，就是2NF。
• 弊病：
  • 插入异常有所改善但是仍然存在。
  • 删除异常。
  • 数据冗余得到了一定的改善。

3NF

定义：如果不存在码$X$，属性组$Y$和非主属性$Z(Z不是Y的子集)$，使得下式成立，$X\rightarrow Y$，$Y\rightarrow Z$，$Y \nrightarrow X$，则$R∈3NF$。（2NF的关系模式，每个非主属性都不传递依赖于任何码）

BCNF

• 所有非主属性都完全函数依赖于每个候选码。
• 所有主属性都完全函数依赖于每个不包含它的候选码。
• 没任何属性完全函数依赖于非码的任意一组属性。

多值依赖与4NF

• 多值依赖定义：$Z = U - X - Y$，关系模式$R(U)$中多值依赖$X\rightarrow \rightarrow Y$成立，当且仅当对$R(U)$的任一关系r，给定的一对$(x,z)$值有一组$Y$的值，这组值仅仅取决于x值而与z值无关。
• 多值依赖有对称性，若$X\rightarrow \rightarrow Y$则$X\rightarrow \rightarrow (U-X-Y)$。
• $X\rightarrow Y$可以推出$X\rightarrow \rightarrow Y$。
• 4NF：对于每个非平凡的多值依赖$X\rightarrow \rightarrow Y$且必须是函数依赖，$X$都含有码。

规范化目的与基本思想

在关系数据库中，对关系的最基本要求是满足1NF。

规范化要逐步消除数据依赖中不合适的部分，使数据库模式中各关系模式达到某种程度的“分离”，使一个关系只描述一个实体或者实体间的一种联系，即**“一事一地”的设计原则。规范化的实质是概念的单一化**。

模式分解理论

无损连接性分解判定算法

$F={FD_1,\dots, FD_p}$

• 如果将n个属性的关系模式分解为k个，先建立n列k行的表TB：
  • 每一列对应一个属性$A_i$。
  • 每一行对应分解中的一个关系模式$R_i$。
  • 分量的取值：$C_{ij}=A_j∈U_i?a_j:b_{ij}$。
• 对$FD_i$中每一个函数依赖$X\rightarrow Y$，若TB中存在元素t1和t2使，t1[X]=t2[X]，则对每一个$A_i∈Y$：
  • 若$t1[A_i], t2[A_i]$有一个等于ai，则另一个也改为ai。
  • 若上面不成立，就取$t1[A_i]=t2[A_i]$。（t1行号小于t2）
• 反复执行上一步直到：
  • TB出现一行为全a，即为无损分解。
  • TB不变且没有一行为全a，为有损分解。

无损分解判定准则

定理：分解$ρ={R_1<U_1,F_1>,R_2<U_2,F_2>}$具有无损连接性的充分必要条件是，$U_1∩U_2\rightarrow U_1-U_2∈F^+$或$U_1∩U_2\rightarrow U_2-U_1∈F^+$。即$R_1, R_2$的共同属性至少构成$R_1,R_2$两者之一的候选码。

保持函数依赖判定准则

$R$中的每个函数依赖都能够从$R_1,\dots,R_n$函数依赖的并集中逻辑导出。

模式分解原则

• 投影分解应遵循的原则：
  • 具有无损连接性
  • 保持函数依赖
• 模式分解能够达到的最高范式等级：
  • 要求保持函数依赖，总可以达到3NF，不一定到BCNF。
  • 要求无损连接，一定可以达到4NF或更高。
  • 要求两者都保持，可以达到3NF，但不一定到BCNF。

达到3NF的等价模式分解

保持函数依赖的分解算法

• 对F进行极小化。
• 找出不在F的属性，将它们构成一个关系模式，并且从U中去掉。
• 若有$X\rightarrow A∈F$，且$XA=U$，则$ρ={R}$，算法终止。
• 对F按具有相同左部的原则分成k组，每一组函数以阿里所涉及的属性全体记为$U_i$，若有$U_i\sube U_j$则去掉$U_i$。令$F_i$为$F$在$U_i$上的投影，则可以获得一个保持函数依赖的分解$ρ={R_1<U_1,F_1>,\dots,R_k<U_k,F_k>}$。

同时保持函数依赖和无损连接的分解算法

设$ρ$是一个保持函数依赖的分解，$X$为$R<U,F>$的码。

• 如果有某个$U_i$满足$X\sube U_i$，则ρ即为所求。
• 否则令$τ=ρ∪{R^*<X,F_X>}$，τ即为所求。

达到BCNF的无损连接分解算法

• 令$ρ=R<U,F>$。
• 检查$ρ$中各关系模式是否属于BCNF，若是，则算法终止。
• 设ρ中的$R_i<U_i,F_i>$不属于BCNF，则存在函数依赖$X\rightarrow A∈F_i^+$，且$X$不是$R_i$的码，则$XA$是$U_i$的真子集，将$R_i$分解为$\sigma={S_1,S_2}$，其中$U_{S_1}=XA,U_{S_2}=U_i-{A}$，以$\sigma$代替$R_i$返回上一步。

候选码的求解

属性分类

• L类：只出现在F函数依赖左侧的属性。
• R类：只出现在F函数依赖右侧的属性。
• N类：没有出现在函数依赖中的属性。
• LR类：在左右均出现的属性。

定理

• 如果X是L类属性，则必是任一候选码的成员。
• 如果X是R类属性，则X不在R的任何一个候选码中。
• 如果X是N类属性，则X必包含在任一候选码中。

图论判定法

将函数依赖关系绘制成有向图。

• 入度为0的为原始点，L类。
• 出度为0的为终结点，R类。
• 入度出度均不为0的为途中点，LR类。
• 入度出度均为0的为孤立点，N类。
• 关键点：原始点和孤立点。
• 独立回路：不能由其他点到达的回路。

定理

• 关键点必在R的任何候选码中。
• 终结点必不在R的任何候选码中。
• R具有唯一候选码的充要条件是G中不存在独立回路。
• 若Y是途中点且Y在独立回路，则Y必在某候选码中。

多属性依赖集候选码求解

• 将所有属性分成L、R、LR和N四类，并令X代表L和N类，Y代表LR类。
• 求出$X_F^+$，如果是U，则X为唯一候选码，否则继续下一步。
• 对于Y中任一一个属性A，求$(XA)_F^+$，若为U，则XA为一个候选码，否则在Y中依次取2个、3个，求属性闭包，直到闭包包含R的全部属性。

与数据库设计的联系

• 求最小依赖集消除冗余联系。
• 一般情况下3NF足以满足要求。

第六章 关系查询处理与查询优化

关系查询处理步骤——四个阶段

• 查询分析：词法分析，语法检查和语法分析。
• 查询检查：语义检查，存取权限检查，SQL语句转换为关系代数表达式。
• 查询优化：选择一个高效的查询处理策略，按照优化的层次分为代数优化和物理优化。
• 查询执行：生成查询计划，生成执行查询计划的代码。

查询优化

• 目标：选择一个高效的执行查询处理策略，使得查询代价最小。
• 执行开销：总代价=IO代价+CPU代价+内存代价
• 按照优化层次分为代数优化和物理优化：
  • 代数优化：改变代数表达式的操作次序和组合。
  • 物理优化：存取路径和底层操作算法选择。
• 一般步骤：
  • 把查询转换成语法树，如关系代数语法树。
  • 代数优化语法树。
  • 物理优化，选择存取路径。
  • 生成查询计划。

代数优化

通过对关系代数表达式的等价变化来提高查询效率。

等价：用相同的关系代替两个表达式中相应的关系所得到的结果是相同的。

• 连接和笛卡尔积交换律。
• 连接和笛卡尔积结合律。
• 投影串接定律。
• 选择串接定律。
• 选择与投影的交换律。
• 选择与笛卡尔积的交换律。
• 选择与并的分配律。
• 选择与差的分配律。
• 选择对自然连接的分配律。
• 投影与笛卡尔积的分配律。
• 投影与并的分配律。

查询树的启发式优化：

• 减小中间关系——选择运算早做。
• 减少扫描关系的次数
• 把笛卡尔积与选择转换为连接
• 中间结果复用

物理优化

常用方法：

• 基于规则的启发式优化方法
• 基于代价估算的优化方法
• 两者结合的优化方法

基于启发式规则的存取路径选择优化：

• 选择操作的启发式规则：
  • 小关系使用全表顺序扫描。
  • 大关系可以使用索引扫描。
• 连接操作的启发式规则：
  • 嵌套循环
  • 排序合并
  • 索引连接
  • hash join

第七章 事务处理技术

事务的概念

事务的定义

事务是用户定义的数据库操作序列，这些操作要么都做，要么都不做。

• 事务与应用程序是两个概念。
• 事务的开始与结束可以由用户显式控制。

事务的特性

• 原子性：事务中包括的所有操作要么都做，要么都不做。
• 一致性：事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态。
• 隔离性：一个事务的执行不能被其他事务干扰，一个事务内部的操作及使用的数据对其他并发事务是隔离的，并发执行的事务之间不能互相干扰。
• 持久性：一个事务一旦提交，它对数据库的影响必须是永久的，其他操作或故障不应该对其执行的结果有任何影响。

ACID特性对于数据库数据的正确有效有重要意义。

• 利用数据库并发控制机制以及数据库恢复机制保证事务的特性不被破坏。从而保证数据库数据的正确有效。
• 事务是数据库恢复和并发控制的基本单位。

SQL事务的定义

• 开始：BEGIN TRANSACTION。
• 结束：COMMIT或ROLLBACK。

数据库恢复技术

概念

把数据库从某一错误状态恢复到某一已知的正确状态。

通过数据库管理系统的恢复子系统完成。

意义

• 保证事务原子性。
• 当系统故障后，使数据库恢复正常状态。

故障种类

• 事务内部故障：
  • 可预期的：事务根据内部条件来回滚。
  • 不可预期的：不能由应用程序处理，比如死锁、运算溢出、违反完整性规则等。
• 系统故障：
  • 造成系统停止运行的任何事情。
  • 使事务都异常终止但不会破坏数据库。
• 介质故障：
  • 外存故障。
  • 破坏全部或部分数据库，并影响正在存取这部分数据的所有事务。
• 计算机病毒：
  • 数据库主要威胁，人为破坏或故障。
  • 对数据进行非法修改。

两种影响：

• 数据库本身被破坏。
• 数据库没有被破坏但数据可能不正确。

恢复的实现技术

基本原理：冗余。

数据转储

• 概念：DBA定期将整个数据库复制到磁带或另一个磁盘上保存起来的过程，备用数据称为后备副本或后援副本。
• 两种转储状态：
  • 静态转储：无事务运行时的转储操作。
  • 动态转储：转储期间允许对数据库进行存取或修改。需要用后援副本加上日志文件恢复。
• 两种转储方式：
  • 海量转储：每次转储全部数据库。
  • 增量转储：每次只转储上一次转储后更新过的数据。
• 日志：记录事务对数据库更新操作的文件，分为以记录为单位和以数据块为单位的两种格式。
  • 作用：事务故障和系统故障恢复必须使用日志文件。
  • 写入规则：先写入日志文件，后写数据库。

故障的恢复策略

• 事务故障的恢复：UNDO，撤销事务，在不影响其他事务的情况下强行回滚。反向扫描日志，执行所有更新操作的逆操作。
• 系统故障：UNDO+REDO，撤销故障发生时未完成的事务，重做已完成但没有写入数据库的事务。
• 介质故障：装入最新数据库后备副本，使数据库恢复到最近一次转储时的一致状态。装入转储以后的日志文件副本，重做已经完成的事务。

检查点技术

日志文件天啊及检查点记录，要记下所有正在执行的事务清单和这些事务最近一个日志记录的地址。

增加一个重新开始文件，用来记录各个检查点记录在日志文件中的地址。

数据库镜像

把整个DB或关键数据复制到另一个磁盘上，由DBMS自动保证镜像数据库与主数据库的一致性。

并发控制技术

并发控制

事务并发的优点

• 一个事务多个步骤并发执行，提高系统吞吐量。
• 如果各个事务涉及的是数据库的不同部分，采用并发会减少平均响应时间。

带来的问题

• 多个事务同时存取同一数据时，不加以控制会读取或存取不正确的数据，破坏一致性。
• 丢失更新：两个事务同时读入数据并修改，后面的事务会破坏前面事务的结果，导致前面事务的结果丢失。
• 脏数据的读出：先前事务的结果被撤销，后面事务已经读出了错误的数据。
• 不能重复读：一个事务读取后，另一个事务更新了数据，导致第一个事务不能再现结果。

并发控制的基本思想

合理调度并发事务，避免并发事务之间的互相干扰造成数据的不一致性。

主要方法是封锁机制。

封锁

事务T在对某个数据如表、记录等操作之前，先向系统发出请求，对其加锁，从而对该数据对象有了一定的控制权。

封锁的类型

• 排它锁（X锁）：上锁后，则只允许当前事务对数据对象进行读取和修改，直到释放锁。
• 共享锁（S锁）：上锁后可以读取但不能修改数据对象，其他事务只能加S锁，也不能加X锁，直到释放S锁。

封锁协议

运用两种基本封锁可以建立不同的约定，形成不同级别的封锁协议。

• 一级封锁协议：防止丢失修改。在修改数据R之前加X锁，结束才可以释放。
• 二级封锁协议：防止读脏数据。一级封锁协议加上在读取R之前必须加S锁，读完释放S锁。
• 三级封锁协议：保证数据可以重复读。一级封锁协议加上读取R前必须加S锁，直到事务结束才可以释放。

封锁粒度

封锁对象的大小称为封锁的粒度。

粒度大，则并发度低，封锁机构简单，开销小。

粒度小，则并发度高，封锁机构复杂，开销高。

多粒度封锁：在一个系统中同时支持多种封锁粒度，选择封锁粒度时应同时考虑封锁开销和并发度两个因素。

多粒度封锁协议：允许多粒度树中每个结点被单独加锁，对一个结点加锁意味着所有后裔结点也被加以同样类型的锁。

意向锁：该结点的下层结点正在被加锁，对任意结点加锁时，必须先对上级结点加意向锁。好处是，对象加锁时，不需要再检查下级结点的封锁。

三种常用意向锁

• 意向共享锁（IS锁）：如果要对一个对象加IS锁，表示他的后裔结点拟加S锁。
• 意向排它锁（IX锁）：如果要对一个数据对象加IX锁，表示他的后裔结点拟加X锁。
• 意向共享排它锁（SIX锁）：如果要对一个数据对象加SIX锁，表示对它加S锁，再加IX锁。

活锁与死锁

• 活锁：一个事务一直占用锁，后面可能一直等待，采用先来先服务法。
• 死锁：预防死锁，死锁检测与解除。
• 死锁预防：
  • 一次封锁法：要求每个事务必须一次将其所有要使用的数据全部加锁，否则就不能执行，降低了系统的并发度。
  • 顺序封锁法：预先对数据对象规定一个封锁顺序，所有事务都按照这个顺序封锁，实现难度大。
• 死锁检测：
  • 超时法：如果等待时间超过时限就认为发生死锁。
  • 等待图法：图中有回路说明出现了死锁。
• 死锁恢复：选择一个处理死锁代价最小的事务，将其撤销。

事务的调度

N个事务的一个调度S是N个事务所有操作的一个序列S，表示这些操作的执行顺序，并且这个序列满足，对每个事务T，如果操作i在事务T中先于操作k，则在S中i也先于操作k。

并发调度正确性

• 一个事务正常或者预想的结果是没有其他并行事务干扰时得到的结果，因此一组事务的串行调度策略一定是正确的调度策略。
• 各种结果都将保持数据库数据的一致性，所以都是正确的。

并发调度的可串行性

• 可串行化：多个事务并发执行正确，当且仅当按某一次序串行执行它们时的结果相同，我们称这种调度策略为可串行化调度。
• 可串行性是并行事务正确性的准则，一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调度。
• 一个调度Sc在保证冲突操作次序不变的情况下，可以通过交换两个事务不冲突操作的次序，得到另一个串行调度Sc’，则调度Sc为冲突可串行化调度。
• 两段锁协议可以保证并行事务的可串行性。
  • 内容：
    • 对任何数据进行读写操作之前，事务首先要获得对该数据的封锁。
    • 在释放一个封锁之后，事务不再获得任何其他封锁。
  • 含义：事务分为两个阶段，第一个阶段获得封锁称为扩展阶段，第二阶段释放封锁，称为收缩阶段。
  • 定理：若所有事务均遵从两段锁协议，则这些事务的所有并发调度都是可串行化的。
  • 注意：遵守两段锁协议只是充分条件。遵守两段锁的事务仍然可能发生死锁。

第八章 数据库保护

安全性控制

• 安全性：保护数据库以防止不合法的使用所造成的数据泄漏、更改和破坏。
  • 向授权用户提供可靠的信息服务。
  • 拒绝对数据库的非授权存取访问请求，保证数据的可用性、完整性和一致性，进而保护数据库所有者和使用者的合法权益。
• 安全性控制：包含数据库系统的计算机系统安全模型。
  • 用户标识与鉴别：用户标识和认证是系统提供的最外层安全保护措施。
    • 标识：系统采用一定的方式标识其用户或应用程序的名字或身份。
    • 认证：系统在用户或应用程序登录时判断其是否为合法的授权用户。
• 存取控制：确保合法用户按照指定的权限使用DBMS和访问数据。
  • 用户权限定义
  • 合法权限检查
  • 上述两者一起组成了DBMS的安全子系统。
• 存取控制方法分类
  • 自主存取控制（DAC）：用户对于不同数据对象有不同的存取权限，不同用户对同一对象也有不同的权限。用户还可以将其拥有的权限转授给其他用户。
  • 强制存取控制（MAC）：对于任意一个对象，只有具有合法许可证的用户才可以存取。
  • 对于用户存取权限的定义称为授权。在授权中应指明用户名、数据对象名、允许的操作对象类型。
• SQL可以授予用户的两类权限：
  • 用户级权限：DBA为每个用户授予特定权限，是对用户使用整个数据库权限的限定。
  • 关系级权限：DBA和数据库对象的拥有者为用户授予的与关系或视图有关的权限，这种权限是对用户使用关系的视图权限的限定。
  • 授权：GRANT option TO user，回收权限：REVOKE option ON user。
• 角色与用户组
  • 角色是一组权限的集合。
  • 用户组是一组具有相同特性用户的集合，可以在授权或收回权限时以用户组为单位进行。
• 强制存取方法：MAC中全部实体被分为主体和客体。
  • 主体是系统中的活动实体，包括实际用户和代表用户的各进程。
  • 客体是系统的被动实体，由主体操纵。
  • 对于主客体，DBMS为每个实例指定一个敏感度标记（Label）。主体的敏感度标记称为许可证级别，客体的敏感度标记称为密级。
  • MAC机制通过对比主体的label和客体的label最终确定主体是否能够存取客体。
  • 当某一主体以某一许可证级别注册入系统时，系统要求他对任何客体的存取必须遵循如下规则：
    • 只有当主体的许可证级别大于等于客体的密级时，主体才能读取相应客体。
    • 仅当主体许可证级别等于客体的密级时，才可以写相应客体。
• 其他方法：
  • 视图机制
  • 审计
  • 数据加密

完整性控制

• 完整性：数据的正确性和相容性。
  • 正确性：数据应该具有合法类型，在有效取值范围内。
  • 相容性：表示同一个事实的两个数据应该相同。
  • 数据库是否保持完整性关系到数据库系统是否能真实反映现实世界。
• 完整性约束条件：施加在数据库数据之上的语义约束条件称为数据库完整性约束条件。作用对象可以是列、元组和关系三种。
• 完整性约束条件分类：
  • 静态约束：反应数据库状态合理性的约束。
  • 动态约束：反应数据库状态变迁的约束。
• 完整性控制包括三个方面的功能：
  • 定义功能
  • 检查功能
  • 违约相应
• 完整性检查时机：
  • 立即执行约束：在执行用户事务过程中，在一条语句执行完后立即进行完整性约束的检查。
  • 延迟执行约束：整个用户事务执行完毕后，在进行完整性约束的检查。
• 完整性规则表示：五元组
  • D：数据对象。（工资）
  • O：触发完整性检查的数据库操作。（插入或修改）
  • A：数据库对象必须满足的断言或语义约束。（工资>=500000000）
  • C：选择A作用的数据对象值的谓词。（职称=‘老八’）
  • P：违反完整性规则时触发的过程。（拒绝执行该操作）
• SQL完整性：断言ASSERTION，触发器TRIGGER。

第九章 分布式数据库

分布式数据库系统

• 分布性：数据分布存储在网络的各个节点。
• 逻辑上的整体性：数据被一种机制联系在一起，构成一个有机整体。
• 分布式数据库定义：由一组分布在计算机网络的不同结点上的数据组成，每个结点具有独立处理的能力，可以执行局部应用，同时每个结点也可以通过网络通信支持全局应用。
• 场地自治性：每个场地有自己的数据库，一组终端（局部应用）。
• 自治场地之间的协作性：逻辑上如同一个集中式数据库，可以在任何场地执行全局应用。

分布式数据库系统的特点

• 数据独立性：
  • 逻辑独立性
  • 物理独立性
  • 分布独立性：逻辑分片、数据物理位置的分布细节等与用户无关。
• 集中与自治相结合的控制结构：
  • 数据共享分为局部共享和全局共享。
  • 分布式数据库有自治功能，系统又设有集中控制结构。
• 适当增加数据冗余：
  • 在不同结点存储同一个数据的多个副本。
  • 提高系统可靠性、可用性。
  • 提高系统性能。
• 全局的一致性、可串行性和可恢复性

体系结构

• 全局外模式
• 全局概念模式
• 分片模式：
  • 分片方式：水平分片、垂直分片、导出分片、混合分片。
  • 满足完全性、不相交性和可重构性。
• 分布模式
  • 分布透明性：分片透明性、位置透明性、局部数据模型透明性。
• 局部概念模式
• 局部内模式

DDBMS

组成

• LDBMS：局部场地上的数据库管理系统。
• GDBMS：全局DBMS。
• GDD：全局数据字典。
• CM：通信管理。

主要技术

查询类型

• 局部查询：单结点
• 远程查询：单结点
• 全局查询：多个结点

处理过程

• 查询分解
• 选择操作执行的次序
• 选择执行操作的方法
• 使用半连接缩减关系。