课程：【CMU 15-445】数据库系统
课本：Database System Concepts, 7th Edition, by Silberschatz, Korth, and Sudarshan

Chapter 1

A database-management system (DBMS) consists of a collection of interrelated data and a collection of programs to access those data. The data describe one particular enterprise

ACID 是数据库管理系统（DBMS）中事务处理的四个关键属性的首字母缩写，分别代表原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）和持久性（Durability）。这些属性确保了数据库事务的可靠性和数据的完整性。
原子性（Atomicity）：
原子性确保事务中的所有操作要么全部完成，要么全部不完成。换句话说，事务是不可分割的最小工作单元。如果事务中的任何一个操作失败，整个事务将回滚到事务开始前的状态。
例如，在银行转账操作中，资金从一个账户扣除并添加到另一个账户，这两个操作要么都成功，要么都不执行。
一致性（Consistency）：
一致性确保事务在完成时，数据库从一个一致状态转换到另一个一致状态。事务的执行不能违反数据库的完整性约束。
例如，如果数据库有一个约束规定账户余额不能为负数，那么在事务完成后，这个约束仍然必须成立。
隔离性（Isolation）：
隔离性确保并发执行的事务彼此之间不互相干扰。每个事务的中间状态对其他事务是不可见的，事务之间的操作是隔离的。
例如，在一个事务完成之前，其他事务不能看到它的未提交数据。
持久性（Durability）：
持久性确保一旦事务提交，其结果将永久保存在数据库中，即使系统发生故障（如电源故障或崩溃），事务的结果也不会丢失。
例如，一旦银行转账操作成功提交，即使系统崩溃，转账结果也会被保留。

view of Data
Data Modles
A collection of tools for describing data, data relationships, data semantics, and consistency constraints.

Relational Model 关系模型
本文的大部分内容都集中在关系模型上，因为它是大多数数据库应用程序的基础。

关系模型使用一组表来表示数据和这些数据之间的关系。每个表有多个列，每个列有一个惟一的名称。表也被称为关系。关系模型是基于记录的模型的一个例子。基于记录的模型之所以如此命名，是因为数据库是由几种类型的固定格式记录构成的。每个表包含特定类型的记录。每个记录类型定义了固定数量的字段或属性。表的列对应于记录类型的属性。关系数据模型是使用最广泛的数据模型，目前绝大多数数据库系统都是基于关系模型的。

第2章和第7章详细介绍了关系模型

Entity-Relationship Model 实体关系（E-R）模型

实体-关系(E-R)数据模型使用一组称为实体的基本对象，以及这些对象之间的关系。实体是现实世界中有别于其他对象的“事物”或“对象”。实体-关系模型在数据库设计中应用广泛。第六章对此进行了详细的探讨。

Semi-structured Data Model 半结构化数据模型

半结构化数据模型允许对数据进行规范，其中相同类型的单个数据项可能具有不同的属性集。这与前面提到的数据模型相反，在数据模型中，特定类型的每个数据项必须具有相同的一组属性。JSON和可扩展标记语言(XML)是广泛使用的半结构化数据表示。第8章将详细探讨半结构化数据模型。

Object-Based Data Model 基于对象的数据模型

面向对象编程(特别是在Java、c++或c#中)已经成为占主导地位的软件开发方法。这最初导致了一种独特的面向对象数据模型的开发，但是今天对象的概念已经很好地集成到关系数据库中。存在将对象存储在关系表中的标准。数据库系统允许将过程存储在数据库系统中，并由数据库系统执行。这可以看作是用封装、方法和对象标识的概念扩展关系模型。第8章总结了基于对象的数据模型。

Relational Model

在关系模型中，数据以表的形式表示。每个表有多个列，每个列有一个惟一的名称。表格的每一行代表一条信息。图1.1给出了一个示例关系数据库，其中包含两个表:一个表显示大学教师的详细信息，另一个表显示大学各个院系的详细信息。

例如，第一个表是教员表，它显示了一个ID为22222、名叫Einstein的教员，他是物理系的一员，年薪为95,000美元。例如，第二张表格“部门”显示生物系位于沃森大楼，预算为9万美元。当然，现实世界中的大学会有更多的院系和教师。我们在课文中用小表格来说明概念。可以在网上找到相同模式的更大示例。
alt text

Data Abstraction

图1.2显示了三个抽象层次之间的关系。
alt text
数据库系统允许应用程序开发人员使用数据模型的抽象来存储和检索数据，并将抽象操作转换为低级实现上的操作。

对编程语言中数据类型概念的类比可以澄清抽象级别之间的区别。许多高级编程语言都支持结构化类型的概念。例如C中的结构体，C++中的类，Java中的类。结构化类型允许程序员定义新的数据类型，这些数据类型由多个字段组成。

在物理层，教员、院系或学生的记录可以被描述为一个连续的字节块。编译器对程序员隐藏了这一层次的细节。类似地，数据库系统对数据库程序员隐藏了许多最底层的存储细节。另一方面，数据库管理员可能知道数据的物理组织的某些细节。例如，有许多可能的方法将表存储在文件中。一种方法是将表存储为文件中的记录序列，使用特殊字符(例如逗号)来分隔记录的不同属性，并且可以使用另一个特殊字符(例如换行字符)来分隔记录。如果所有属性都有固定的长度，那么属性的长度可以单独存储，并且可以从文件中省略分隔符。可变长度属性可以通过存储长度，然后存储数据来处理。数据库使用一种称为索引的数据结构来支持对记录的有效检索;这些也构成了物理层的一部分。

在逻辑级别上，每个这样的记录由类型定义描述，如前面的代码段所示。这些记录类型的相互关系也在逻辑级别上定义;教员记录的部门名称值必须出现在部门表中的要求就是这种相互关系的一个例子。使用编程语言的程序员在这个抽象层次上工作。类似地，数据库管理员通常在这个抽象级别上工作。

最后，在视图层，计算机用户看到一组隐藏数据类型细节的应用程序。在视图级别，定义了数据库的几个视图，数据库用户可以看到其中的一些或全部视图。除了隐藏数据库逻辑级别的详细信息外，视图还提供了一种安全机制，以防止用户访问数据库的某些部分。例如，大学注册办公室的职员只能看到数据库中有学生信息的那部分;他们无法获得有关教师工资的信息。

Instances and Schemas 实例和模式

数据库随着信息的插入和删除而变化。在特定时刻存储在数据库中的信息集合称为数据库的实例。数据库的总体设计称为数据库模式。数据库模式和实例的概念可以类比为用编程语言编写的程序来理解。数据库模式对应于程序中的变量声明(以及相关的类型定义)。每个变量在给定的时刻都有一个特定的值。程序中变量的值在某个时间点对应于数据库模式的实例。

数据库系统有几个模式，根据抽象级别进行分区。物理模式在物理层描述数据库设计，而逻辑模式在逻辑层描述数据库设计。数据库在视图级别也可能有多个模式(有时称为子模式)，它们描述数据库的不同视图。

Database Languages

数据库系统提供数据定义语言DDL (data-definition language)来指定数据库模式，提供数据操作语言DML (data-manipulation language)来表达数据库查询和更新。实际上，数据定义语言和数据操作语言并不是两种独立的语言;相反，它们只是构成单一数据库语言的一部分，比如SQL语言。几乎所有的关系数据库系统都使用SQL语言，我们将在第3章、第4章和第5章详细介绍。

DDL

我们通过一组由称为数据定义语言(DDL)的特殊语言表示的定义来指定数据库模式。DDL还用于指定数据的其他属性。

我们通过一组语句指定数据库系统使用的存储结构和访问方法，这些语句使用一种称为数据存储和定义语言的特殊DDL类型。这些语句定义了数据库模式的实现细节，这些细节通常对用户是隐藏的。

存储在数据库中的数据值必须满足一定的一致性约束。

例如，假设大学要求某个部门的账户余额永远不能为负。DDL提供了指定此类约束的工具。数据库系统在每次更新数据库时检查这些约束。通常，约束可以是属于数据库的任意谓词。但是，任意谓词的测试成本可能很高。因此，数据库系统只实现那些可以用最小开销测试的完整性约束:

Domain constraints: 指定每个属性的允许值的范围。
每个属性（例如，整数类型、字符类型、日期/时间类型）都必须与一个可能值的域相关联。将属性声明为特定域可作为对其可采用的值的约束。域约束是完整性约束的最基本形式。每当有新数据项输入数据库时，系统都可以轻松地测试它们。
Referential integrity: 指定两个关系之间的参照完整性。
在某些情况下，我们希望确保出现在给定属性集的一个关系中的值也出现在另一个关系中的某组属性中（参照完整性）。例如，每门课程列出的部门必须是大学中实际存在的部门。更准确地说，课程记录中的部门名称值必须出现在部门关系中某些记录的部门名称属性中。数据库修改可能导致违反参照完整性。当违反参照完整性约束时，正常程序是拒绝导致违规的操作。
Authorization: 指定哪些用户有权访问数据。
我们可能希望根据用户对数据库中各种数据值的访问权限类型来区分用户。这些区别以授权的形式表达，最常见的是：读取授权，允许读取数据，但不允许修改数据；插入授权，允许插入新数据，但不允许修改现有数据；更新授权，允许修改数据，但不允许删除数据；删除授权，允许删除数据。我们可以为用户分配所有、不分配或这些类型的授权的组合。

DDL 语句的处理，就像任何其他编程语言的语句一样，会产生一些输出。DDL 的输出放在数据字典中，其中包含元数据，即有关数据的数据。数据字典被视为一种特殊类型的表，只能由数据库系统本身（而不是普通用户）访问和更新。数据库系统在读取或修改实际数据之前会查阅数据字典。

The SQL Data-Definition Language

最常见的sql文件中的语句。略。

Data-Manipulation Language

数据操作语言(DML)是一种使用户能够访问或操作由适当数据模型组织的数据的语言。访问的类型有:

检索存储在数据库中的信息。
将新信息插入数据库。
删除数据库中的信息。
修改存储在数据库中的信息。
基本上有两种类型的数据操作语言:
Declarative DMLs （过程性 DML）要求用户指定需要什么数据以及如何获得这些数据。
Declarative DMLs （声明性 DML，也称为非过程性dml）要求用户指定需要哪些数据，而不指定如何获取这些数据。
Database Access from Application Programs
数据库系统提供了一种接口，使应用程序可以访问数据库。这种接口允许应用程序员指定数据库操作，而不必关心数据存储和检索的细节。

非过程查询语言（例如 SQL）不如通用图灵机强大；也就是说，有些计算可以使用通用编程语言进行，但使用 SQL 则无法完成。SQL 也不支持用户输入、显示输出或网络通信等操作。此类计算和操作必须用宿主语言（例如 C/C++、Java 或 Python）编写，并嵌入 SQL 查询以访问数据库中的数据。

应用程序是用于以这种方式与数据库交互的程序。大学系统中的示例是允许学生注册课程、生成班级名册、计算学生 GPA、生成工资支票和执行其他任务的程序。

要访问数据库，需要将DML语句从主机发送到数据库，在那里它们将被执行。这通常是通过使用应用程序编程接口来实现的，该接口可用于向数据库发送DML和DDL语句并检索结果。开放数据库连接(Open Database Connectivity, ODBC)标准定义了与C和其他几种语言一起使用的应用程序编程接口。Java数据库连接(JDBC)标准为Java语言定义了相应的接口。

Database Design

高级数据模型为数据库设计人员提供了一个概念框架，用于指定数据库用户的数据需求以及如何构建数据库以满足这些需求。数据库设计的初始阶段是充分描述潜在数据库用户的数据需求。数据库设计人员需要与领域专家和用户进行广泛的互动才能完成这项任务。此阶段的结果是用户需求的规范。接下来，设计人员选择一个数据模型，并通过应用所选数据模型的概念，将这些需求转化为数据库的概念模式。在此概念设计阶段开发的模式提供了企业的详细概述。设计人员审查该模式以确认所有数据需求确实得到满足并且彼此不冲突。设计人员还可以检查设计以删除任何冗余功能。此时的重点是描述数据及其关系，而不是指定物理存储细节。

就关系模型而言，概念设计过程涉及到我们希望在数据库中捕获哪些属性以及如何将这些属性分组以形成各种表的决策。“What”部分基本上是一个业务决策，我们将在本文中进一步讨论它。“How”部分主要是一个计算机科学问题。解决这个问题主要有两种方法。第一种是使用实体-关系模型(第6章);另一种是采用一组算法(统称为规范化)，将所有属性集合作为输入并生成一组表(第7章)。

一个完全开发的概念模式表明了企业的功能需求。在功能需求规范中，用户描述将对数据执行的操作（或事务）类型。示例操作包括修改或更新数据、搜索和检索特定数据以及删除数据。在概念设计的这个阶段，设计人员可以检查模式以确保它满足功能要求。从抽象数据模型转移到数据库实现的过程分为两个最终设计阶段。在逻辑设计阶段，设计人员将高级概念模式映射到将要使用的数据库系统的实现数据模型上。设计人员在随后的物理设计阶段使用生成的系统特定数据库模式，在此阶段指定数据库的物理特性。这些特性包括文件组织形式和内部存储结构；它们将在第 13 章中讨论。

Database Engine

数据库系统被划分为处理整个系统各项职责的模块。数据库系统的功能组件大致可分为存储管理器、查询处理器组件和事务管理组件。

The storage manager 存储管理器非常重要，因为数据库通常需要大量的存储空间。企业数据库的大小通常从数百 GB 到数 TB 不等。1 GB 大约等于 10 亿字节，即 1000 兆字节（更准确地说是 1024 兆字节），而 TB 大约等于 1 万亿字节或 100 万兆字节（更准确地说是 1024 GB）。最大的企业拥有的数据库达到数 PB 级（1 PB 等于 1024 TB）。由于计算机的主内存无法存储这么多信息，并且主内存的内容在系统崩溃时会丢失，因此信息存储在磁盘上。数据会根据需要在磁盘存储和主内存之间移动。由于数据进出磁盘的移动速度相对于中央处理器的速度较慢，因此数据库系统必须对数据进行结构化，以尽量减少在磁盘和主内存之间移动数据的需要。固态磁盘 (SSD) 越来越多地用于数据库存储。SSD 比传统磁盘更快，但成本也更高。

The query processor 查询处理器很重要，因为它帮助数据库系统简化和方便对数据的访问。查询处理器允许数据库用户获得良好的性能，同时能够在视图级别上工作，而不必负担理解系统实现的物理层细节。数据库系统的工作是在逻辑层将用非过程性语言编写的更新和查询转换为物理层的高效操作序列。

The transaction manager 事务管理器很重要，因为它允许应用程序开发人员将一系列数据库访问视为一个单元，要么全部发生，要么根本不发生。这允许应用程序开发人员在更高层次上思考应用程序，而无需关心管理并发访问数据和系统故障的影响的较低层次的细节。

虽然数据库引擎传统上是集中式计算机系统，但如今并行处理是高效处理大量数据的关键。现代数据库引擎非常重视并行数据存储和并行查询处理。

Storage Manager

存储管理器子系统提供数据库中存储的低级数据与提交给系统的应用程序和查询之间的接口。

Authorization and integrity manager 授权和完整性管理器，用于测试是否满足完整性约束并检查用户访问数据的权限。
Transaction manager 事务管理器，它确保数据库在系统故障时保持一致(正确)状态，并发事务执行无冲突地进行。
File manager 文件管理器，它管理磁盘存储空间的分配和用于表示存储在磁盘上的信息的数据结构。
Buffer manager 缓冲区管理器，负责从磁盘存储中提取数据到主存，并决定在主存中缓存哪些数据。缓冲区管理器是数据库系统的关键部分，因为它使数据库能够处理比主内存大得多的数据大小。

存储管理器在物理系统实现过程中实现了几种数据结构：

Data files 数据文件，用于存储数据库本身。
Data dictionary 数据字典，用于存储有关数据库结构（特别是数据库模式）的元数据。
Indices 索引，用于快速访问数据项。与本教科书中的索引一样，数据库索引提供指向包含特定值的数据项的指针。
例如，我们可以使用索引查找具有特定 ID 的讲师记录，或具有特定名称的所有讲师记录。
我们在第 12 章和第 13 章中讨论了存储介质、文件结构和缓冲区管理。第 14 章讨论了有效访问数据的方法
Query Processor
查询处理器子系统编译并执行 DDL 和 DML 语句。
查询处理器组件包括：
DDL interpreter DDL 解释器，解释 DDL 语句并将定义记录在
数据字典中。
DML compiler DML 编译器，将查询语言中的 DML 语句转换为由查询评估引擎
理解的低级指令组成的评估计划。查询通常可以转换为许多备选评估计划中的任何一个，这些计划都给出相同的结果。DML 编译器还执行查询优化；也就是说，它从备选方案中选择成本最低的评估计划。
Query evaluation engine 查询评估引擎，执行由 DML 编译器生成的低级指令

Query evaluation 将在第15章中介绍，而查询优化器从可能的求值策略中选择的方法将在第16章中讨论

Transaction Manager

事务管理确保数据库在系统发生故障时仍保持一致（正确）状态。事务管理器确保并发事务执行不会发生冲突。

事务是数据库应用程序中执行单个逻辑功能的操作的集合。每个事务都是原子性和一致性的单位。因此，我们要求事务不违反任何数据库一致性约束。也就是说，如果事务开始时数据库是一致的，则事务成功终止时数据库也必须是一致的。但是，在执行事务期间，可能需要暂时允许不一致，因为 A 的借记或 B 的贷记必须先于另一个完成。这种暂时的不一致虽然是必要的，但如果发生故障，可能会导致困难。

确保原子性和持久性属性是数据库系统本身的责任 - 具体来说，是恢复管理器的责任。在没有故障的情况下，所有事务都会成功完成，并且很容易实现原子性。但是，由于各种类型的故障，事务可能并不总是成功完成其执行。如果我们要确保原子性属性，则失败的事务必须对数据库的状态没有影响。因此，必须将数据库恢复到相关事务开始执行之前的状态。因此，数据库系统必须执行故障恢复，即它必须检测系统故障并将数据库恢复到故障发生之前的状态。

最后，当多个事务同时更新数据库时，即使每个单独的事务都是正确的，数据的一致性也可能不再得到保持。并发控制管理器负责控制并发事务之间的交互，以确保数据库的一致性。

事务管理器由并发控制管理器和恢复管理器组成(concurrency-control manager and the recovery manager)。

第 17 章介绍了事务处理的基本概念。第 18 章介绍了并发事务的管理。第 19 章详细介绍了故障恢复。

事务的概念已广泛应用于数据库系统和应用程序中。虽然事务最初是在金融应用程序中使用，但现在该概念已用于电信的实时应用程序，以及产品设计或管理工作流等长期活动的管理。

Database and Application Architecture

alt text
图 1.3 所示的集中式架构适用于共享内存服务器架构，这种架构具有多个 CPU 并利用并行处理，但所有 CPU 都访问一个公共共享内存。为了扩展到更大的数据量和更高的处理速度，并行数据库被设计为在由多台机器组成的集群上运行。此外，分布式数据库允许跨多个地理上分离的机器进行数据存储和查询处理。

在第20章中，我们将介绍现代计算机系统的一般结构，重点是并行系统体系结构。第21章和第22章描述了如何实现查询处理来利用并行和分布式处理。第23章介绍了在并行或分布式数据库中处理事务时出现的一些问题，并描述了如何处理每个问题。这些问题包括如何存储数据、如何确保在多个站点执行的事务的原子性、如何执行并发控制以及如何在出现故障时提供高可用性。

我们现在考虑使用数据库作为后端的应用程序的体系结构。数据库应用程序可以划分为两个或三个部分，如图1.4所示。早期的数据库应用程序使用两层体系结构，其中应用程序驻留在客户机机器上，并通过查询语言语句调用服务器机器上的数据库系统功能。

相比之下，现代数据库应用程序使用三层体系结构，其中客户机仅充当前端，不包含任何直接的数据库调用;Web浏览器和移动应用程序是当今最常用的应用程序客户机。前端与应用服务器通信。反过来，应用服务器与数据库系统通信以访问数据。应用程序的业务逻辑(说明在什么条件下执行什么操作)嵌入到应用程序服务器中，而不是分布在多个客户机上。三层应用程序比两层应用程序提供更好的安全性和性能。
alt text

Database Users and Administrators

数据库系统的主要目标是从数据库中检索信息并将新信息存储在数据库中。使用数据库的人可以分为数据库用户或数据库管理员。

Database Users and User Interfaces

有四种不同类型的数据库系统用户，根据他们期望与系统交互的方式进行区分。针对不同类型的用户，设计了不同类型的用户界面。

Native 用户是通过使用预定义的用户界面(如web或移动应用程序)与系统交互的简单用户。Native 用户的典型用户界面是 web 表单界面，用户可以在其中填写表单的适当字段。Native 用户还可以查看从数据库生成的已读报告。
应用程序程序员是编写应用程序的计算机专业人员。应用程序程序员可以从许多工具中选择开发用户界面。
资深用户无需编写程序即可与系统交互。相反，他们使用数据库查询语言或使用数据分析软件等工具来形成请求。提交查询以探索数据库中的数据的分析师属于这一类
Database Administrator
使用 DBMS 的主要原因之一是可以集中控制数据和访问这些数据的程序。对系统具有这种集中控制权的人称为数据库管理员 (DBA)。DBA 的功能包括：
Schema definition. 模式定义。DBA 通过执行 DDL 中的一组数据定义语句来创建原始数据库模式。
存储结构和访问方法定义。DBA 可以指定一些与数据的物理组织和要创建的索引有关的参数。
Schema and physical-organization modification. 模式和物理组织修改。DBA 对模式和物理组织进行更改以反映组织不断变化的需求，或更改物理组织以提高性能。
Granting of authorization for data access. 授予数据访问授权。通过授予不同类型的授权，数据库管理员可以规定不同用户可以访问数据库的哪些部分。授权信息保存在一个特殊的系统结构中，每当用户尝试访问系统中的数据时，数据库系统都会查阅该结构。
Routine maintenance. 日常维护。数据库管理员的日常维护活动示例包括：
- 定期将数据库备份到远程服务器，以防止在发生洪水等灾难时丢失数据。
- 确保有足够的可用磁盘空间用于正常操作，并根据需要升级磁盘空间。
- 监控数据库上运行的作业，并确保性能不会因某些用户提交的非常昂贵的任务而降低。
  History of Database Systems
  20 世纪 70 年代末和 80 年代：尽管关系模型在学术上很有趣，但由于其性能缺陷，最初并未在实践中使用；关系数据库无法与现有的网络和层次化数据库的性能相匹配。随着 System R 的出现，这种情况发生了改变，这是 IBM 研究部门的一个开创性项目，开发了构建高效关系数据库系统的技术。功能齐全的 System R 原型促成了 IBM 的第一款关系数据库产品 SQL/DS 的诞生。与此同时，加州大学伯克利分校正在开发 Ingres 系统。它促成了同名的商业产品。同样在这个时候，Oracle 的第一个版本也发布了。最初的商业关系数据库系统（如 IBM DB2、Oracle、Ingres 和 DEC Rdb）在推进高效处理声明式查询的技术方面发挥了重要作用。到 20 世纪 80 年代初，关系数据库甚至在性能方面也与网络和分层数据库系统相媲美。关系数据库非常易于使用，最终取代了网络和分层数据库。

2000 年代：在此期间，存储在数据库系统中的数据类型发展迅速。半结构化数据变得越来越重要。XML 成为数据交换标准。JSON 是一种更紧凑的数据交换格式，非常适合存储来自 JavaScript 或其他编程语言的对象，随后变得越来越重要。随着主要商业系统增加了对 XML 和 JSON 格式的支持，越来越多的此类数据存储在关系数据库系统中。空间数据（即包含地理信息的数据）在导航系统和高级应用程序中得到广泛使用。数据库系统增加了对此类数据的支持。开源数据库系统（尤其是 PostgreSQL 和 MySQL）的使用率不断提高。数据库系统添加了“自动管理”功能，以便自动重新配置以适应不断变化的工作负载。这有助于减少管理数据库的人工工作量。

社交网络平台发展迅速，需要管理有关人们与其发布数据之间联系的数据，而这些数据并不适合表格行列格式。这导致了图形数据库的发展。
在本世纪后期，数据分析和数据挖掘在企业中的使用变得无处不在。数据库系统是专门为服务于这个市场而开发的。这些系统具有适合分析处理的物理数据组织，例如“列存储”，其中表格按列存储，而不是主要商业数据库系统的传统行式存储。
庞大的数据量，以及用于分析的大部分数据是文本或半结构化数据的事实，导致了 map-reduce 等编程框架的开发，以方便应用程序程序员使用并行性来分析数据。随着时间的推移，对这些功能的支持迁移到了传统数据库系统中。即使在 2010 年代后期，数据库研究界仍在争论一个数据库系统同时服务于传统事务处理应用程序和较新的数据分析应用程序与为这些角色维护单独的系统之间的相对优缺点。

各种新的数据密集型应用程序和快速开发的需求，尤其是初创公司的需求，导致了提供轻量级数据管理形式的“NoSQL”系统的出现。这个名字源于这些系统缺乏对无处不在的数据库查询语言 SQL 的支持，尽管这个名字现在通常被视为“不仅仅是 SQL”。由于缺乏基于关系模型的高级查询语言，程序员可以更灵活地处理新类型的数据。由于传统数据库系统不支持严格的数据一致性，因此应用程序使用分布式数据存储时可以更加灵活。NoSQL 的“最终一致性”模型允许数据的分布式副本不一致，只要它们最终会在没有进一步更新的情况下收敛即可。

Chapter 2: Introduction to the Relational Model

Structure of Relational Databases

关系数据库由一组表组成，每个表都有一个唯一的名称。
因此，在关系模型中，术语 relation 关系 用于指代表，而术语 tuple 元组用于指代行。类似地，属性指的是表中的一列。
一般来说，关系模式（relation schema）由属性序列以及各属性对应域组成
我们使用术语“relation instance ”来指代关系的特定实例，也就是说，它包含一组特定的行。图2.1所示的教员实例有12个元组，对应12个教员。

我们要求，对于所有关系r, r的所有属性的域都是原子的。如果域的元素被认为是不可分割的单元，那么域就是原子的。

例如，假设表教练有一个属性电话号码，该属性可以存储与教练对应的一组电话号码。那么电话号码的域就不是原子的，因为域的元素是电话号码的集合，并且它有子部分，即集合中的单个电话号码。

重要的问题不是域本身是什么，而是我们如何在数据库中使用域元素。现在假设电话号码属性存储单个电话号码。即使这样，如果我们将电话号码属性的值拆分为国家代码、地区代码和本地号码，我们也会将其视为非原子值。如果我们将每个电话号码视为单个不可分割的单元，那么属性电话号码将具有一个原子域。

null值是一个特殊值，表示该值未知或不存在。例如，假设和前面一样，我们在教员关系中包含了属性电话号码。可能是教师根本没有电话号码，或者电话号码没有列出。然后，我们必须使用空值来表示该值未知或不存在。稍后我们将看到，当我们访问或更新数据库时，空值会导致许多困难，因此应该尽可能消除空值。我们首先假定空值不存在，在第3.6节中，我们将描述空值对不同操作的影响。

我们将看到，相对严格的关系结构在数据存储和处理方面带来了几个重要的实际优势。这种严格的结构适合定义良好且相对静态的应用程序，但不太适合不仅数据而且这些数据的类型和结构都随时间变化的应用程序。现代企业需要在结构化数据的效率和预定结构受限的情况之间找到良好的平衡。

Database Schema

当我们谈论数据库时，我们必须区分数据库模式和数据库实例，前者是数据库的逻辑设计，后者是数据库中数据在给定时刻的快照。

关系（relation）的概念对应于变量的编程语言概念，而关系模式（relation schema）的概念对应于类型定义的编程语言概念。给定变量的值可能随时间变化;类似地，关系实例的内容可能随着关系的更新而改变。相反，关系的模式通常不会改变。

Keys

我们必须有一种方法来指定如何区分给定关系中的元组。

这是用它们的属性来表示的。也就是说，元组的属性值的值必须能够唯一地标识该元组。换句话说，关系中的两个元组不允许对所有属性具有完全相同的值。超键是一个或多个属性的集合，这些属性使我们能够在关系中唯一地标识一个元组。 例如，关系 instructor 的 ID 属性足以区分一个 instructor 元组和另一个 instructor 元组。因此，ID 是一个超级键。另一方面，instructor 的 name 属性不是超级键，因为多个讲师可能具有相同的名称。

形式上，设 R 表示关系 R 模式中的属性集。如果我们说 R 的子集 K 是 R 的超键，我们将考虑限制在关系 R 的实例上，其中没有两个不同的元组在 K 的所有属性上具有相同的值。

也就是说，如果t1和t2在r中并且t1≠t2，那么t1。K≠t2。

A superkey may contain extraneous attributes. For example, the combination of ID and name is a superkey for the relation instructor. If K is a superkey, then so is any superset of K. We are often interested in superkeys for which no proper subset is a superkey. Such minimal superkeys are called candidate keys. 如果K是一个超键，那么K的任何超集也是一个超键。我们经常感兴趣的是那些没有合适子集是超键的超键。这样的最小超键称为候选键。

可能有几个不同的属性集可以作为候选键。

假设名称和部门名称的组合足以区分教员关系的成员。然后，{ID}和{name, dept name}都是候选键。虽然属性ID和name一起可以区分讲师元组，但它们的组合{ID, name}并不能形成候选键，因为属性ID本身就是一个候选键。

We shall use the term primary key to denote a candidate key that is chosen by the database designer as the principal means of dentifying tuples within a relation. A key (whether primary, candidate, or super) is a property of the entire relation, rather than of the individual tuples. Any two individual tuples in the relation are prohibited from having the same value on the key attributes at the same time. The designation of a key represents a constraint in the real-world enterprise being modeled. Thus, primary keys are also referred to as primary key constraints.

接下来，我们考虑对关系内容的另一种类型的约束，称为外键约束（foreign-key constraint）。考虑讲师关系的属性dept name。如果讲师中的元组的dept name值与部门关系中的部门不对应，则没有意义。因此，在任何数据库实例中，给定教员关系中的任意元组(例如ta)，在部门关系中必须存在某个元组(例如tb)，使得ta的dept name属性的值与tb的主键dept name的值相同。

A foreign-key constraint from attribute(s) A of relation r1 to the primary-key B of relation r2 states that on any database instance, the value of A for each tuple in r1 must also be the value of B for some tuple in r2. Attribute set A is called a foreign key from r1, referencing r2. The relation r1 is also called the referencing relation of the foreign-key constraint, and r2 is called the referenced relation.

注意，在外键约束中，被引用的属性必须是被引用关系的主键。更一般的情况是，引用完整性约束（referential integrity constraint）放宽了引用属性构成引用关系主键的要求。

引用完整性约束（Referential Integrity Constraint） 的基本概念：引用完整性约束确保数据库中的关系（表）之间的数据一致性。具体来说，它要求在一个关系（表）中的某些属性（列）中的值必须在另一个关系（表）中的某些属性（列）中存在。

引用关系（Referencing Relation）：
- 这是包含外键（Foreign Key）的关系（表）。外键是一个或多个属性（列），它们引用另一个关系（表）的主键（Primary Key）。
被引用关系（Referenced Relation）：
- 这是被外键引用的关系（表）。被引用的属性通常是主键或具有唯一约束的属性。

引用完整性约束的要求

外键约束：在引用关系中的外键属性的值必须在被引用关系的主键属性中存在。
数据一致性：这确保了引用关系中的每个外键值都能在被引用关系中找到对应的主键值。

事实上，外键约束是引用完整性约束的一种特殊情况，其中引用的属性构成引用关系的主键。目前的数据库系统通常支持外键约束，但是它们不支持引用的属性不是主键的引用完整性约束。

Schema Diagrams

数据库模式以及主键和外键约束可以通过模式图来描述。图2.9显示了我们大学组织的架构图。每个关系显示为一个框，关系名称以蓝色显示在顶部，框内列出了属性。

主键属性用下划线显示。外键约束以箭头的形式显示，从引用关系的外键属性指向被引用关系的主键。我们使用双头箭头(而不是单头箭头)来指示不是外键约束的引用完整性约束。

alt text

我们将在第6章详细讨论模式的另一种图解表示，称为实体-关系图;虽然在外观上有一些相似之处，但这两种符号有很大的不同，不应相互混淆。

Relational Query Languages

查询语言是用户从数据库请求信息时使用的语言。

这些语言通常在比标准编程语言更高的级别上。查询语言可以分为命令式、函数式和声明式。

在命令式查询语言中，用户指示系统对数据库执行特定的操作序列以计算期望的结果;这种语言通常有状态变量的概念，在计算过程中更新状态变量。

在函数查询语言中，计算被表示为对可能对数据库中的数据或对其他函数的结果进行操作的函数的求值;函数没有副作用，也不会更新程序状态在声明性查询语言中，用户描述所需的信息，而不给出获取该信息的特定步骤序列或函数调用;所需的信息通常使用某种形式的数学逻辑来描述。如何获取所需的信息是数据库系统的工作。

有许多“纯”查询语言。

我们在2.6节中描述的关系代数是一种函数式查询语言关系代数构成了SQL查询语言的理论基础。
我们在第27章描述的元组关系演算和域关系演算是声明性的。

这些查询语言简洁而正式，缺乏商业语言的“语法糖”，但它们演示了从数据库中提取数据的基本技术。

在实践中使用的查询语言，如SQL查询语言，包括命令式、函数式和声明式方法的元素。在第三章到第五章中，我们会学习使用非常广泛的查询语言SQL。

The Relational Algebra 关系代数

alt text

The Select Operation

select操作返回一个关系，该关系包含从输入关系中选择的元组。这些元组由选择条件指定。如果选择条件为空，则输出关系将包含与输入关系相同的元组。如果输入关系为空，则输出关系也为空。

The Project Operation

project操作返回一个关系，该关系包含从输入关系中选择的属性的元组。这些属性由属性列表指定。如果输入关系中有多个元组具有相同的属性值，则输出关系中只包含一个这样的元组。如果属性列表为空，则输出关系将包含一个元组，该元组的属性值为空。如果输入关系为空，则输出关系也为空。

Composition of Relational Operations

关系代数操作可以组合在一起。例如，可以将选择操作和投影操作组合在一起，以便选择一个关系的属性的子集，并且只包含满足某些条件的元组。这种组合称为查询计划。查询计划是一个关系代数表达式，它描述了如何从输入关系生成输出关系。查询计划可以包含一个或多个关系代数操作，这些操作以某种顺序应用于输入关系。例如，可以选择一个关系的属性的子集，然后选择满足某些条件的元组。这种组合称为查询计划。查询计划是一个关系代数表达式，它描述了如何从输入关系生成输出关系。查询计划可以包含一个或多个关系代数操作，这些操作以某种顺序应用于输入关系。

The Cartesian-Product Operation

笛卡尔积操作返回一个关系，该关系包含两个输入关系的所有可能的元组的组合。笛卡尔积操作是关系代数中最基本的操作之一。如果两个输入关系都为空，则输出关系也为空。

The Join Operation

join操作返回一个关系，该关系包含两个输入关系的元组的连接。连接是两个元组的笛卡尔积的子集，这两个元组满足某些连接条件。连接条件是两个关系的属性之间的等式。如果两个关系的属性之间没有等式，则连接条件为空，输出关系将包含两个输入关系的笛卡尔积。如果两个输入关系都为空，则输出关系也为空。

Set Operations

关系代数支持集合操作，例如并集、交集和差集。并集操作返回两个关系的并集，交集操作返回两个关系的交集，差集操作返回两个关系的差集

The Assignment Operation

assignment操作将一个关系的结果分配给一个关系变量。关系变量是一个关系的名称，它可以用于表示关系的结果。关系变量可以用作关系代数表达式的输入。例如，可以将一个关系的结果分配给一个关系变量，然后使用该关系变量作为另一个关系的输入。关系变量可以用作关系代数表达式的输入。例如，可以将一个关系的结果分配给一个关系变量，然后使用该关系变量作为另一个关系的输入。

The Rename Operation

rename操作返回一个关系，该关系与输入关系相同，但是属性的名称可能不同。重命名操作用于更改属性的名称。如果输入关系为空，则输出关系也为空。

Equivalent Queries

在关系代数中，可以使用等价关系代数表达式来表示相同的查询。等价关系代数表达式是指两个关系代数表达式，它们返回相同的结果。例如，可以使用选择操作和投影操作来表示一个查询，也可以使用连接操作来表示该查询。在关系代数中，可以使用等价关系代数表达式来表示相同的查询。等价关系代数表达式是指两个关系代数表达式，它们返回相同的结果。例如，可以使用选择操作和投影操作来表示一个查询，也可以使用连接操作来表示该查询。

chapter 27 Other Data Models

Document Data Model

The document data model is a collection of record documents containing a hierarchy of named field/value
pairs. A field’s value can be either a scalar type, an array of values, or a pointer to another document.
Modern implementations use JSON. Older systems use XML or custom object representations.
The document model avoid ”relation-object impedance mismatch” by tightly coupling objects and database.
While there are certainly use cases for this model, it still runs into many of the problems discussed in the
flat file strawman example discussed earlier.

Vector Data Model

The vector data model represents one-dimensional arrays used for nearest-neighbor search (exact or approximate). Vector databases are generally used for semantic search on embeddings generated by MLtrained transformer models (think ChatGPT), and native integration with modern ML tools and APIs (e.g.,
LangChain, OpenAI). At their core, these systems use specialized indexes to perform NN searches quickly.
Recently, many relational DBMSs have shipped vector index features or extensions (pgvector) that allow
NN search within the relational model

Chapter 3: Introduction to SQL

3.1 Overview of the SQL Query Language

The SQL language has several parts:

Data-definition language (DDL). The SQL DDL provides commands for defining relation schemas, deleting relations, and modifying relation schemas. / SQL DDL提供了用于定义关系模式、删除关系和修改关系模式的命令。
Data-manipulation language (DML). The SQL DML provides the ability to query information from the database and to insert tuples into, delete tuples from, and modify tuples in the database. / SQL DML提供了从数据库查询信息以及将元组插入到数据库中、从数据库中删除元组和修改数据库中的元组的能力。
Integrity. The SQL DDL includes commands for specifying integrity constraints that the data stored in the database must satisfy. Updates that violate integrity constraints are disallowed. SQL DDL包括用于指定存储在数据库中的数据必须满足的完整性约束的命令。不允许违反完整性约束的更新。
View definition. The SQL DDL includes commands for defining views. SQL DDL包括用于定义视图的命令。
Transaction control. SQL includes commands for specifying the beginning and end points of transactions. SQL包括用于指定事务开始点和结束点的命令。
Embedded SQL and dynamic SQL. Embedded and dynamic SQL define how SQL statements can be embedded within general-purpose programming languages, such as C, C++, and Java. 嵌入式和动态SQL定义了如何将SQL语句嵌入到通用编程语言(如C、c++和Java)中
Authorization. The SQL DDL includes commands for specifying access rights to relations and views. SQL DDL包括用于指定对关系和视图的访问权限的命令。
3.2 SQL Data Definition
The set of relations in a database are specified using a data-definition language (DDL).
The SQL DDL allows specification of not only a set of relations, but also information about each relation, including:
The schema for each relation. / 每个关系的模式。
The types of values associated with each attribute. / 与每个属性关联的值的类型。
The integrity constraints. / 完整性约束。
The set of indices to be maintained for each relation. / 要为每个关系维护的索引集。
The security and authorization information for each relation. / 每个关系的安全性和授权信息。
The physical storage structure of each relation on disk. / 磁盘上每个关系的物理存储结构。

我们在这里讨论基本模式定义和基本类型；对其他SQL DDL特性的讨论推迟到第4章和第5章。

Basic Types

alt text

Basic Schema Definition

SQL支持许多不同的完整性约束。在本节中，我们只讨论其中的几个:

主键约束
外键约束
not null 约束
create、drop、delete、alter
3.3 Basic Structure of SQL Queries
SQL查询的基本结构由三个子句组成:select、from 和 where。

查询将 from 子句中列出的关系作为输入，按照 where 和 select 子句中指定的方式对它们进行操作，然后生成一个关系作为结果。我们将通过示例介绍 SQL 语法，并在后面描述 SQL 查询的一般结构。

Queries on a Single Relation 单关系查询

在 select 后面加上：

distinct 强制删除重复
all 显式指定不删除重复
select 子句还可带有 +、-、*、/ 等算术运算符，运算对象可以是常数或者记录的属性。
where 子句允许我们只选出那些在 from 子句的结果关系中满足特定谓词的元组
SQL 允许在 where 子句中使用逻辑连词 and、or 和 not。逻辑连词的运算对象可以是包含比较运算符的表达式。SQL 允许使用比较运算符来比较字符串、算术表达式和以及日期等特殊类型。

我们使用 alter table 命令向现有关系添加属性。关系中的所有元组都被指定为 null作为新属性的值。

Queries on Multiple Relations 多关系查询

查询通常需要访问来自多个关系的信息。
例如，假设我们想要回答“检索所有教员的姓名，以及他们的部门名称和部门大楼名称”这个查询。查看关系指导器的模式，我们意识到可以从属性dept name获得部门名称，但是部门构建名称出现在关系部门的属性构建中。要回答查询，教员关系中的每个元组必须与部门关系中dept name值与教员元组的dept name值匹配的元组相匹配。

在SQL中，为了回答上述查询，我们在from子句中列出需要访问的关系，并在where子句中指定匹配条件。上面的查询可以用SQL编写为

1
2
3

select name, instructor.dept name, building
from instructor, department
where instructor.dept name= department.dept name;

自然连接

自然连接作用于两个关系，结果为一个关系
只考虑那些在两个关系模式中都出现的属上取值相同的元组对
没有公共属性的时候退化为笛卡尔积
为了发扬自然连接的优点，同时避免不必要的相等属性带来的危害，SQL提供了自然连接的构造形式，允许用户明确指定连接属性（需哪些列相等）：
1
2
select name,title
from(instrucor natural join teaches) join course using (course id);
danger of nartual join
3.4 Additional Basic Operations 附加的基本运算
the rename operation
as 子句既可以出现在 select 子句中，也可以出现在 from 子句中
String Operations 字符串运算
Attribute Specification in the Select Clause
* 在 select 子句中代表所有属性
Ordering the Display of Tuples
order by 子句可以让查询结果中的元组按照排列顺序显示，默认是升序
可以用 desc 关键字指定降序，asc 关键字指定升序
where 子句谓词
为了简化 where， between 和 not between 可以用来指定一个范围
sql 允许我们用 (v1,v2,v3) 来表示一个分量值分别为 v1,v2,v3 的元组，在其上可以按照字典顺序进行比较
集合运算
交并差都是默认去重的，如果不想去重，可以使用 union all等。
交 union
并 intersect
差 except / minus
用法差不多，都是类似 () union ()。
Null Values 空值
由于where子句中的谓词可以涉及布尔操作，如and、or，而不是对比较的结果，因此布尔操作的定义被扩展为处理 unknown。

The result of any arithmetic expression involving null is null 任何包含 null 的算术表达式的结果都是 null
Any comparison with null returns unknown，如 1<null 是unknown 任何与 null 的比较都返回 unknown

and: The result of true and unknown is unknown, false and unknown is false, while unknown and unknown is unknown.
or: The result of true or unknown is true, false or unknown is unknown, while unknown or unknown is unknown.
not: The result of not unknown is unknown
sql 在谓词中采用特殊的 null 测试空值。is null 和 is not null
null = null 是 unknown
3.7 Aggregate Functions
聚合函数是接受值的集合(一组或多组)作为输入并返回单个值的函数。SQL提供了五个标准的内置聚合函数:
Average: avg
Minimum: min
Maximum: max
Total: sum
Count: count
sum 和 avg 的输入必须是数字的集合，但其他操作符也可以操作非数字数据类型的集合，比如字符串。

Basic Aggregation

Aggregation with Grouping

1
2
3

select dept name, avg (salary) as avg salary
from instructor
group by dept_name;

当SQL查询使用分组时，重要的是要确保出现在select语句中而不被聚合的属性是那些出现在group by子句中的属性。换句话说，group by子句中没有出现的任何属性都可能只作为聚合函数的参数出现在select子句中，否则该查询将被视为错误。例如，下面的查询是错误的，因为ID没有出现在group by子句中，但是它出现在select子句中而没有被聚合:

/* erroneous query */
select dept name, ID, avg (salary)
from instructor
group by dept name;

在前面的查询中，特定组(由dept name定义)中的每个教练可以有不同的ID，并且由于每个组只输出一个元组，因此没有唯一的方法来选择输出哪个ID值。因此，SQL不允许这样的情况。

The Having Clause

having 子句中的谓词在分组形成后才起作用

有时，声明一个适用于组而不是元组的条件是有用的。例如，我们可能只对教师平均工资超过4.2万美元的院系感兴趣。此条件不适用于单个元组；相反，它适用于group by子句构造的每个组。为了表达这样的查询，我们使用SQL的having子句。SQL在组形成后在having子句中应用谓词，因此可以在having子句中使用聚合函数。

select dept name, avg (salary) as avg salary
from instructor
group by dept name
having avg (salary) > 42000;

SQL关键字执行顺序

>slect A1, agg_fun as X
>from a,b
>where P1
>gruop by A1
>Having P2

Aggregation with Null and Boolean Values 对空值和布尔值的聚集

聚集函数根据以下原则处理空值: 除了count()之外的所有聚集函数都忽略空值。规定空集的count()返回0。

3.8 Nested Subqueries 嵌套子查询

Set Membership

SQL 允许测试元组是否属于某个关系。IN 连接符用于测试集合成员资格，其中集合是由 SELECT 子句生成的值的集合。NOT IN 连接符用于测试集合成员资格的缺失。

Set Comparison

Test for Empty Relations

SQL包含一个特性，用于测试子查询的结果中是否有任何元组。如果参数子查询非空，exists构造返回值true。使用exists结构，我们可以用另一种方式编写查询“查找2017年秋季学期和2018年春季学期教授的所有课程”:

select course id
from section as S
where semester= 'Fall' and year= 2017 and
    exists(select *
        from section as T
        where semester= 'Spring' and year= 2018 and 
        S.course id= T.course_id);

上面的查询还说明了SQL的一个特性，即可以在where子句中的子查询中使用来自外部查询(上面查询中的S)的关联名称。

使用来自外部查询的关联名称的子查询称为相关子查询。

Test for the Absence of Duplicate Tuples

todo!()

Subqueries in the From Clause

todo!()

The With Clause

with子句提供了一种定义临时关系的方法，该临时关系的定义仅对出现with子句的查询可用。
考虑以下查询，该查询查找预算最大的部门。

with max budget (value) as
(select max(budget)
from department)
select budget
from department, max budget
where department.budget = max budget.value;

当然，我们可以创建一个不使用with子句的等效查询，但这样做会更复杂，也更难以理解。您可以编写等效的查询作为练习。

Scalar Subqueries

只要允许表达式返回值，SQL就允许子查询，只要子查询只返回一个包含单个属性的元组；这样的子查询称为标量子查询。例如，可以在 select 子句中使用子查询，如下面的示例所示，该子查询列出了所有部门以及每个部门的教师数量:

select dept name,
(select count(*)
from instructor
where department.dept name = instructor.dept name)
as num instructors
from department;

select count (distinct ID)
from takes
where (course_id,sec_id,semester,year) in
(select course_id, sec_id, semester, year from teaches
where teaches.1D= 10101);

用with子句重写

with T as
(select course id, sec id, semester, year
from teaches
where teaches.ID= 10101)
select count (distinct ID)
from takes
where (course_id, sec_id, semester, year) in T;

Scalar Without a From Clause

某些查询需要计算，但不需要引用任何关系。类似地，某些查询可能具有包含from子句的子查询，而顶级查询不需要from子句。

作为一个例子，假设我们希望找到每个教师教授的平均节数(无论学年或学期)，每个教师计算一次由多个教师教授的节数。我们需要计算教学中的元组数量来找到教学的总节数，并计算教师中的元组数量来找到教师的数量。然后一个简单的除法就得到了我们想要的结果。可以这样写:

1 2	select count() / (select count() from instructor) as avg class size from teaches;

3.9 Modification of the Database

Deletion

注意，虽然一次只能从一个关系中删除元组，但是可以在delete的where子句中嵌套的select-from-where中引用任意数量的关系。删除请求可以包含一个嵌套的选择，该选择引用要从中删除元组的关系。例如，假设我们想要删除所有工资低于大学平均水平的教师的记录。我们可以这样写:

1 2	delete from instructor where salary < (select avg (salary) from instructor);

delete语句首先测试关系教员中的每个元组，以检查其工资是否低于大学教员的平均工资。然后，删除所有通过测试的元组(即代表工资低于平均水平的教员)。在执行任何删除之前执行所有测试是很重要的——如果在测试其他元组之前删除了一些元组，则平均薪水可能会发生变化，并且删除的最终结果将取决于处理元组的顺序！

Insertion

Update

chapter 4：Intermediate SQL 中级SQL

4.1 Join Expressions

join condition

考虑下面的查询，它有一个包含on条件的连接表达式。

1 2	select * from student join takes on student.ID= takes.ID;

上面的 on 条件指定，如果 student 的元组与 takes 的元组 ID 值相等，则这两个元组匹配。本例中的连接表达式与 student 自然连接 takes 的连接表达式几乎相同，因为自然连接操作也要求 student 元组和 takes 元组匹配。唯一的区别是，在连接结果中，结果的 ID 属性列出了两次，一次是 student，一次是 takes，尽管它们的 ID 值必须相同。

In fact, the above query is equivalent to the following query (in other words, they generate exactly the same results):

1
2
3

select *
from student, takes
where student.ID= takes.ID;

on 条件可以表示任何 SQL 谓词(predicate)，因此使用on条件的连接表达式可以表示比自然连接更丰富的连接条件类。但是，正如前面的示例所示，使用带on条件的连接表达式的查询可以被不带on条件的等效表达式替换，并将on子句中的谓词移动到where子句中。因此，on条件似乎是SQL的一个冗余特性。

然而，引入on条件有两个很好的理由。首先，我们将很快看到，对于一种称为外连接的连接，on条件的行为方式与where条件不同。其次，如果在on子句中指定连接条件，而其余条件出现在where子句中，那么SQL查询通常更容易被人读懂。

outer joins

假设我们希望显示所有学生的列表，显示他们的ID、姓名、专业名称、学分以及他们修过的课程。下面的SQL查询可以检索所需的信息:

1	select * from student natural join takes;

不幸的是，上面的查询并没有像预期的那样工作。假设有一个学生没有上过课。那么，该特定学生的student关系中的元组将不满足与takes关系中的任何元组进行自然连接的条件，并且该学生的数据将不会出现在结果中。因此，我们不会看到没有参加考试的学生的任何信息

更一般地说，连接的关系中的一个或两个关系中的一些元组可能会以这种方式“丢失”。外部连接操作的工作方式类似于我们已经研究过的连接操作，但是通过在结果中创建包含空值的元组来保留那些在连接中丢失的元组。外部连接操作有三种类型:左外连接、右外连接和完全外连接。

左外连接仅在左外连接操作之前(在其左边)命名的关系中保留元组。
右外连接仅在以右外连接操作的右侧命名的关系中保留元组。
完整的外部连接保留两个关系中的元组。
left outer join
right outer join
full outer join
完全外连接是左外连接和右外连接类型的组合。

操作计算出内连接的结果后，它会将左侧关系中与右侧关系中不匹配的元组扩展为空值，并将它们添加到结果中。同样，它会将右侧关系中与左侧关系中不匹配的元组扩展为空值，并将它们添加到结果中。

作为使用完整外部连接的一个示例，请考虑以下查询:“显示Comp. Sci.数据库中所有学生的列表。”以及他们在2009年春季修过的课程部分(如果有的话);从2009年春季开始的所有课程部分必须显示，即使没有学生来自 the Comp.Sci。系里已经有了课程部分。”这个查询可以写成:

select *
from (select *
from student
where dept name= ’Comp. Sci’)
natural full outer join
(select *
from takes
where semester = ’Spring’ and year = 2009);

inner join

我们前面研究的不保留不匹配元组的连接操作称为内部连接操作，以区别于外部连接操作。

Join Types and Conditions

为了区分普通连接和外部连接，普通连接在SQL中称为内连接。因此，join clause 可以指定内部连接而不是外部连接，以指定要使用普通连接。关键字 inner 是可选的。当不使用外部前缀的连接子句时，默认的连接类型是内部连接。

类似地，natural join is equivalent to natural inner join。

图4.6显示了我们讨论过的各种连接类型的完整列表。
alt text
从图中可以看出，任何形式的连接(内连接、左外连接、右外连接或全外连接)都可以与任何连接条件(自然连接、使用连接或on连接)组合。

4.2 Views

到目前为止，在我们的示例中，我们一直在逻辑模型级别进行操作。也就是说，我们假设给定的集合中的关系是存储在数据库中的实际关系。

除了安全问题之外，我们可能希望创建一个个性化的关系集合，它比逻辑模型更符合特定用户的直觉。

可以计算并存储查询的结果，然后将存储的关系提供给用户。但是，如果我们这样做了，并且关系讲师、课程或部分中的基础数据发生了变化，那么存储的查询结果将不再与对关系重新执行查询的结果相匹配。一般来说，计算和存储诸如上述示例中的查询结果是一个坏主意(尽管有一些例外，我们将在后面研究)。

相反，SQL允许查询定义“虚拟关系”，并且关系在概念上包含查询的结果。虚拟关系不是预先计算和存储的，而是在使用虚拟关系时通过执行查询来计算的。

任何这样的关系，如果不是逻辑模型的一部分，但作为虚拟关系对用户可见，则称为视图。在任何给定的一组实际关系之上支持大量视图是可能的。

View Definition

我们使用create view命令在SQL中定义视图。要定义视图，我们必须给视图一个名称，并且必须说明计算视图的查询。create view命令的格式是:

1	create view v as <query expression>;

Using Views in SQL Queries

一个视图可以在定义另一个视图的表达式中使用。

Materialized Views 物化视图

物化视图是数据库中的一种特殊视图，它将视图查询的结果存储在磁盘上，而不是像普通视图一样每次查询时动态计算结果。物化视图常用于提高复杂查询的性能，尤其是在处理需要频繁执行、代价较高的查询时。

某些数据库系统允许存储视图关系，但它们确保，如果视图定义中使用的实际关系发生变化，则视图保持最新状态。这样的视图称为物化视图。

例如，考虑视图部门的总工资。如果实现了上述视图，其结果将存储在数据库中。但是，如果向讲师关系添加或删除了讲师元组，则定义视图的查询结果将发生变化，因此必须更新物化视图的内容。类似地，如果更新了教员的工资，则必须更新与该教员所在部门相对应的部门总工资中的元组。

物化视图需要与基础表数据保持一致性，更新方式主要有以下两种：

即时刷新（Immediate Refresh）：在基础表发生更新时立即更新视图。
延迟刷新（Deferred Refresh）：定期或按需刷新视图。
一些数据库系统允许数据库管理员控制对每个物化视图使用上述方法中的哪一个。

Update of a View

虽然视图是查询的有用工具，但是如果用视图表示更新、插入或删除，则会出现严重的问题。困难在于，用视图表示的对数据库的修改必须转换为对数据库逻辑模型中实际关系的修改。

由于诸如此类的问题，通常不允许修改视图关系，除非在有限的情况下。不同的数据库系统指定不同的条件来允许视图关系的更新;详细信息请参见数据库系统手册。通过视图修改数据库的一般问题一直是大量研究的主题，书目注释提供了一些这方面研究的指针。

一般来说，如果定义视图的查询满足以下条件，则SQL视图是可更新的(即可以在视图上应用插入、更新或删除操作):

select子句只包含关系的属性名，不包含任何表达式、聚合或不同的规范。
任何未在select子句中列出的属性都可以设置为null;也就是说，它没有非空约束，也不是主键的一部分。
查询中没有group by或having子句

即使有了可更新性的条件，以下问题仍然存在。
假设用户试图将元组(‘ 25566 ‘，’ Brown ‘， ‘ Biology ‘， 100000)插入到历史教师视图中。这个元组可以插入到讲师关系中，但它不会出现在历史讲师视图中，因为它不满足视图强加的选择。
默认情况下，SQL将允许进行上述更新。但是，可以在视图定义的末尾使用with check选项子句来定义视图;然后，如果插入到视图中的元组不满足视图的where子句条件，则数据库系统将拒绝插入。同样，如果新值不满足where子句条件，则拒绝更新。
SQL:1999对于在视图上执行插入、更新和删除操作有更复杂的规则集，这允许通过更大的视图类进行更新;然而，这些规则太复杂了，无法在这里讨论。

Transactions
事务由一系列查询和/或更新语句组成。SQL标准指定在执行SQL语句时隐式地开始事务。下列SQL语句之一必须结束事务:

Commit work
提交当前事务;也就是说，它使事务执行的更新在数据库中成为永久性的。事务提交后，将自动启动一个新事务。
Rollback work
导致当前事务回滚;也就是说，它撤销事务中SQL语句执行的所有更新。因此，数据库状态将恢复到执行事务的第一条语句之前的状态。
Integrity Constraints
完整性约束确保授权用户对数据库所做的更改不会导致数据一致性的丢失。因此，完整性约束可以防止对数据库的意外损坏。

通常，完整性约束可以是属于数据库的任意谓词。但是，任意谓词的测试成本可能很高。因此，大多数数据库系统允许指定可以用最小开销测试的完整性约束。

完整性约束通常被标识为数据库模式设计过程的一部分，并作为用于创建关系的create table命令的一部分声明。但是，也可以使用alter table table-name add constraint命令将完整性约束添加到现有关系中，其中的约束可以是关系上的任何约束。当执行这样的命令时，系统首先确保关系满足指定的约束。如果是，则将约束添加到关系中;如果不是，则拒绝该命令。

Constraints on a Single Relation

Not Null Constraint

1	name varchar(20) not null

禁止在关系模式的主键上出现空值
Unique Constraint
unique 指出属性形成了一个候选码；
然而候选码能为 null，除非显示定义 not null
The check Clause

check 子句允许用户指定一个谓词，该谓词必须为真，才能插入或更新关系中的元组

create table student
(ID varchar(5),
name varchar(20) not null,
dept name varchar(20),
tot cred numeric(3,0) default 0,
primary key (ID),
check (tot cred >= 0 and tot cred <= 200));

Referential Integrity 参照完整性

级联 cascade

create table t_user(
    id int not null primary key,
    name varchar(20),
    group_id int,
    foreign key (group_id) references t_group(id) on delete cascade on update cascade
);

那么

1
2

delete from t_group where id=2; // 从表中有相关引用，导致 t_user 中 groupid 为2的记录，被删除
update t_group set id=2 where id=1; // 从表中有相关引用，导致 t_user 中 groupid 为1的记录，被级联修改为2

置空 set null

create table t_user(
    id int not null primary key,
    name varchar(20),
    group_id int,
    foreign key (group_id) references t_group(id) on delete set null on update set null
);

那么

1
2

delete from t_group where id=2; // 从表中有相关引用，导致 t_user 中 groupid 为2的记录，groupid 被设置为NULL
update t_group set id=2 where id=1; // 从表中有相关引用，导致 t_user 中 groupid 为1的记录，groupid 被设置为NULL

禁止 no action

create table t_user(
    id int not null primary key,
    name varchar(20),
    group_id int,
    foreign key (group_id) references t_group(id) on delete no action on update no action
);

那么

1
2

delete from t_group where id=1; // 错误，从表中有相关引用，因此主表中无法删除
update t_group set id=2 where id=1; // 错误，从表中有相关引用，因此主表中无法更新

外键中的属性允许为 null ，只要他们没有被声明为 not null。如果给定元组中外码的所有列上均取非空值，则对该元组采用外码约束的通常定义。如果某外码列为 null，则该元组自动被认为满足约束。

integrity constraints Violations During Transactions

事务可能由几个步骤组成，并且在一个步骤之后可能会暂时违反完整性约束，但是后面的步骤可能会删除该违反。

为了处理这种情况，SQL标准允许将最初延迟的子句添加到约束规范中;然后在事务结束时检查约束，而不是在中间步骤中检查约束。约束也可以指定为可延迟的，这意味着默认情况下立即检查约束，但在需要时可以延迟。对于声明为可延迟的约束，执行作为事务一部分延迟的语句set constraints constraint-list会导致对指定约束的检查延迟到该事务的末尾。

但是，您应该意识到默认行为是立即检查约束，并且许多数据库实现不支持延迟约束检查。

复杂 check 条件和断言

assert
SQL Data Types and Schemas
Date and Time Types in SQL
Default Values
SQL允许为属性指定默认值，如下面的create table语句所示:
1
2
3
4
5
6
create table student
(ID varchar (5),
name varchar (20) not null,
dept name varchar (20),
tot cred numeric (3,0) default 0,
primary key (ID));
将tottcred属性的默认值声明为0。因此，当将元组插入到student关系中时，如果没有为tottcred属性提供值，则将其值设置为0。下面的插入语句说明了插入如何省略tottcred属性的值。
1
insert into student values ('12345', 'Smith', 'Biology');
Index Creation
许多查询只引用文件中一小部分记录。例如，像“查找物理系的所有教师”或“查找ID为22201的学生的学分值”这样的查询只引用学生记录的一小部分。对于系统来说，读取每条记录并检查ID字段是否为ID“32556”，或者检查building字段是否为值“Physics”是低效的。

关系属性上的索引是一种数据结构，它允许数据库系统在关系中有效地找到具有该属性指定值的元组，而无需扫描关系的所有元组。

例如，如果我们在student关系的属性ID上创建索引，数据库系统可以直接找到具有任意指定ID值的记录，例如22201或44553，而无需读取student关系的所有元组。索引还可以在属性列表上创建，例如属性名称和学生的部门名称。

稍后，我们将在第11章中学习索引是如何实际实现的，包括一种特别广泛使用的索引，称为B+树索引。

尽管SQL语言没有正式定义任何用于创建索引的语法，但是许多数据库支持使用下面所示的语法创建索引。

1	create index studentID index on student(ID);

上面的语句在关系student的属性ID上创建了一个名为studentID的索引。

当用户提交可以从使用索引中获益的SQL查询时，SQL查询处理器将自动使用该索引。例如，给定一个选择ID为22201的学生元组的SQL查询，SQL查询处理器将使用上面定义的索引studententid索引来查找所需的元组，而无需读取整个关系。

Large-Object Types

当前一代的许多数据库应用程序需要存储的属性可能很大(数千字节)，例如照片，也可能非常大(许多兆字节甚至千兆字节)，例如高分辨率医学图像或视频剪辑。因此SQL为字符数据(clob)和二进制数据(blob)提供了大对象数据类型。这些数据类型中的字母“lob”代表“大型对象”。clob和blob数据类型的值可以存储在数据库中，也可以存储在数据库外部的文件中。在后一种情况下，数据库中存储的值是指向外部文件的指针。

1
2
3

book review clob(10KB)
../image/image blob(10MB)
movie blob(2GB)

对于包含大型对象(多个兆字节到千兆字节)的结果元组，将整个大型对象检索到内存中是低效或不切实际的。相反，应用程序通常使用SQL查询来检索大型对象的“定位器”，然后使用定位器从编写应用程序本身的宿主语言操作该对象。例如，JDBC应用程序接口(见5.1.1节)允许获取一个定位符，而不是整个大对象;然后，可以使用定位器来获取小块的大对象，而不是一次性全部获取，这很像使用read函数调用从操作系统文件读取数据。

User-Defined Types

SQL支持两种形式的用户定义数据类型。我们在这里讨论的第一种形式被称为不同类型。另一种形式，称为结构化数据类型，允许创建复杂的数据类型，包括嵌套的记录结构、数组和多重集。本章不涉及结构化数据类型。

同样，将直接以美元表示的货币价值与以英镑表示的货币价值进行比较也几乎肯定是一个编程错误。一个好的类型系统应该能够检测到这样的赋值或比较。为了支持这种检查，SQL提供了不同类型的概念。

create type子句可用于定义新类型。例如，下列语句:

1 2	create type Dollars as numeric(12,2) final; create type Pounds as numeric(12,2) final;

(关键字finalis在这种情况下并没有真正的意义，但SQL:1999标准要求它，原因我们在这里不讨论;有些实现允许省略final关键字。)然后可以使用新创建的类型，例如，作为关系的属性类型。例如，我们可以将部门表声明为:

create table department
(dept name varchar (20),
building varchar (15),
budget Dollars);

尝试将类型为dollar的值赋给类型为Pounds的变量会导致编译时错误，尽管两者是相同的数字类型。这样的赋值很可能是由于程序员的错误，程序员忘记了货币的差异。为不同的货币声明不同的类型有助于捕获此类错误。

SQL provides drop type and alter type clauses to drop or modify types that
have been created earlier.

Domain Types

甚至在将用户定义类型添加到SQL之前(在SQL:1999中)，SQL就有一个类似但略有不同的域概念(在SQL-92中引入)，它可以向底层类型添加完整性约束。例如，我们可以像下面这样定义域ddollar。

1	create domain DDollars as numeric(12,2) not null;

域 ddollar 可以用作属性类型，就像我们使用类型dollar 一样。然而，类型和领域之间存在两个显著差异:

Domain 可以在其上指定约束，例如非null，并且可以为域类型的变量定义默认值，而 User-Defined Types 不能在其上指定约束或默认值。User-Defined Types 不仅用于指定属性类型，而且还用于可能无法强制执行约束的SQL过程扩展。
Domain 不是强类型的。因此，只要底层类型兼容，一种域类型的值就可以分配给另一种域类型的值。

当应用于域时，check子句允许模式设计器指定一个谓词，声明来自该域的任何属性都必须满足该谓词。

Create Table Extensions

应用程序通常需要创建与现有表具有相同模式的表。SQL提供了一个类似创建表的扩展来支持这个任务。

1	create table temp instructor like instructor;

当编写一个复杂的查询时，将查询结果存储为一个新表通常是有用的;这个表通常是临时的。需要两条语句，一条用于创建表(包含适当的列)，第二条用于将查询结果插入到表中。SQL:2003提供了一种更简单的技术来创建包含查询结果的表。例如，下面的语句创建了一个包含查询结果的表t1。

create table t1 as
(select *
from instructor
where dept name= ’Music’)
with data;

根据SQL:2003标准的定义，如果省略with data子句，则创建表，但不填充数据。然而，即使省略了with data子句，也有许多实现在默认情况下用数据填充表。

上面的 create table ... as 语句与 create view 语句非常相似，两者都是通过查询定义的。主要区别在于表的内容是在创建表时设置的，而视图的内容总是反映当前查询结果。

Authorization

Granting and Revoking of Privileges

SQL标准包括选择、插入、更新和删除特权。特权all privileges可以用作所有允许的特权的缩写形式。

1	grant <privilege list> on <relation name> to <user list>;

要撤销授权，可以使用revoke语句。它的形式几乎与grant相同:

1	revoke <privilege list> on <relation name> from <user list>;

roles

在数据库中创建了一组角色。可以将授权授予角色，其方式与授予单个用户的方式完全相同。每个数据库用户被授予一组角色(可能是空的)，她被授权执行这些角色。

1
2
3

create role <role name>;
grant <privilege list> on <relation name> to <role name>;
grant <role name> to <user list>;

请注意，可以有一个角色链;例如，教学助理的角色可以授予所有教师。反过来，讲师的角色被授予所有院长。

因此，除了直接授予院长的特权外，院长角色继承了授予讲师和助教角色的所有特权。

Authorization on Views

Authorizations on Schema

Transfer of Privileges

Revoking of Privileges

chapter 6: Database Design and the E-R Model

The Entity-Relationship Model

Entity Sets

entity 实体是现实世界中可区别于所有其他对象的一个“事物”或“对象”。
entity set 实体集是具有相同属性的实体的集合。
实体通过一组 attributes 属性来表示。每个实体的每个属性都有一个值。
Relationship Sets
relationship 联系是指实体间的相互关联。
relationship set 联系集是指具有相同类型联系的集合。
实体集之间的关联称为参与（participate）。 that is, the entity sets E1, E2,…, En participate in relationship set R.
relationship instance 联系实例是指实体集的实体之间的实际联系。
实体在联系中扮演的功能称为角色（role）。
联系也可以具有描述性属性（descriptive attributes）。
参与联系集的实体的个数称为联系集的度（degree）。

Attributes

simple and composite attributes 简单和复合属性
- composite attributes 能够被分解为更小的子属性，使得相关属性聚集起来，模型更加清晰
single-valued and multivalued attributes 单值和多值属性
- 一个实体的属性可能有多个值，比如一个人可能有多个电话号码。这样的属性称为多值属性。为了区分多值属性和单值属性，我们用大括号括起来，如{电话号码}。在适当的情况下，可以对一个多值属性的取值数目设置上下界。
- 通常情况下，E-R图中的一个实体会被映射到单一的关系模式中。然而，如果一个实体包含“多值”（multi-valued）属性，那么这个实体可能需要被映射到多个关系模式中。
derived 派生属性
- 这类属性的值可以从别的相关属性或实体派生出来。比如，一个人的年龄可以从出生日期和当前日期计算出来。派生属性的值不存储，而是在需要的时候计算出来。
  
  图7.11还演示了一个多值属性电话号码，用“{电话号码}”表示，以及一个派生属性年龄，用“age()”表示。
  建表的时候，多值属性的和主键单独建张表，其他剩下的统一建表。
  Constraints
  映射基数 (Mapping Cardinalities)
一对一
一对多
多对一
多对多
参与约束 (Participation Constraints)
total participation
partial participation
从实体集中删除冗余属性

E-R Diagrams

E-R图可以用图形表达数据库的整体逻辑结构。E-R图简单而清晰，这在很大程度上解释了E-R模型被广泛使用的原因。
E-R关系图

Basic Structure

分成两部分的矩形表示实体集。第一部分(在本教科书中是蓝色阴影部分)包含实体集的名称。第二部分包含实体集的所有属性的名称。
菱形表示关系集。
未分割的矩形表示关系集的属性。作为主键一部分的属性加下划线。
双菱形表示链接到弱实体集的识别关系集
线将实体集**链接*到关系集*
虚线将关系集的属性链接到关系集。
双线表示关系集中实体的全部参与。
弱实体集的标识符用虚线下划线表示。
概念：
弱实体集
- 没有足够的属性形成主键的实体集，其存在必须关联另一个称为标识实体集（identifying 标识）或属主实体集的实体集。弱实体集合的实体通常没有唯一标识符，或者它们的唯一标识符是与其所属的实体集合的标识符相关的。
- 我们称标识实体集拥有他所标识的弱实体集。将弱实体集与其标识实体集联系在一起的联系称为标识联系（identifying relationship）。
- 标识联系是从弱实体集到标识实体集多对一的，并且弱实体集在联系中的参与是全部的。
- 标识联系集不应该有任何描述性属性。
- 弱实体集的主键是由其标识实体集的主键和弱实体集的标识符（discriminator）组成的。
  Mapping Cardinality
  一对一、一对多、多对一、多对多

类似于uml的类图，E-R图还提供了一种方法来指示关系集中每个实体参与关系的次数的更复杂约束。一行可以有关联的最小和最大基数，如l..h所示，其中l是最小基数，h是最大基数。最小值为1表示实体集在关系集中的总参与;也就是说，实体集中的每个实体至少出现在该关系集中的一个关系中。最大值为1表示实体最多参与一个关系，而最大值*表示没有限制。

roles

我们通过标记连接菱形和矩形的线来指示E-R图中的角色。课程实体集和prereq关系集之间的角色指标course id和prereq id如图7.12所示。

Weak Entity Sets

alt text

弱实体的鉴别符用虚线下划线，而不是实线。
连接弱实体集和识别强实体集的关系集用双菱形表示

Reduction to Relational Schemas 转换为关系模式

Representation of Relationship Sets 联系集的表示

为二元联系集选择主键：

多对多，参与实体集的主键属性的并集作为主键
一对一，任意一个实体集的主键属性作为主键
一对多，多的实体集的主键属性作为主键
Redundancy of Schemas 模式的冗余
将弱实体集连接到相应的强实体集的关系集被特殊处理。正如我们在第7.5.6节中提到的，这些关系是多对一的，没有描述性属性。此外，弱实体集的主键包含强实体集的主键。在图7.14的E-R图中，弱实体集区段通过关系集区段依赖于强实体集区段。section的主键是{course id, sec id, semester, year}， course的主键是course id。由于sec course没有描述性属性，因此sec course模式具有course id、sec id、semester和year属性。实体集部分的模式包括course id、sec id、semester和year(以及其他)属性。sec课程关系中的每个(course id, sec id, semester, year)组合也会出现在模式部分上的关系中，反之亦然。因此，sec课程模式是多余的。

通常，将弱实体集链接到其对应的强实体集的关系集模式是冗余的，并且不需要出现在基于E-R图的关系数据库设计中。

Combination of Schemas 模式的组合

假设实体集 A 在关系AB中的参与是完全的；也就是说，实体集 A 中的每个实体 a 都必须参与关系 AB。那么我们可以将模式 A 和 AB 结合起来，形成一个包含两个模式的属性并集的单一模式。组合模式的主键是合并关系集模式的实体集的主键。

Total and partial participation：全参与和部分参与

是全体参与的，那么必须合并
不是全体参与的，那么可以合并也可以不合并；如果合并，那么属性在某些行上的值将是空值NULL
联系属性的布局
建表优化：
一对一，一对多的联系集的属性可以放到一个参与该联系集的实体集中，而不是放到联系集中
有全参与的联系要优化
- course_dept, inst_dept,stu_dept,sec_class,sec_time_slot
- 去掉冗余 1-1，1-m（remove redundant）
标识联系，不参与建表，不优化
- sec_course
部分参与的可保留不优化
- advisor
m:n 的联系，建表，不优化
- takes, teaches
  Entity-Relationship Design Issues
  Extended E-R Features
  特化 (Specialization)
  在实体集内部进行分组的过程称为特化。特化是将实体集分解为子实体集的过程。实体集中的实体子集可能具有不为实体集中的所有实体共享的属性。
  概化 (Generalization)
  概化是特化的逆过程。在概化中，将几个实体集合并为一个更一般的实体集。
  属性继承 (Attribute Inheritance)
  由特化和概化所产生的高层和低层实体的一个重要特性是属性继承。高层实体的属性通常被继承到低层实体。例如 employee 和 student 继承自 person。
  概化上的约束 (Constraints on Generalizations)
一类约束是判定哪些实体能够成为给定低层实体集的成员。
- 条件定义的：例如，只有那些年龄大于 65 岁的人才能成为退休人员。
- 用户定义的：例如，根据个人观点进行决策分配员工到某一个工作组。
另一类约束涉及在一个概化中一个实体是否可以属于多个底层实体集
- 不相交 disjoint：一个实体只能属于一个底层实体集。例如一个实体可以是本科生或研究生，但不能同时是两者。
- 重叠 overlapping：一个实体可以属于多个底层实体集。例如某些雇员同时参与到多个工作组中。
最后一类约束是对概化的完全性约束（completeness constraint）。定义高层实体集中的一个实体是否必须至少属于该特化/概化中的一个低层实体集。
- 完全性约束 total：一个高层实体的实体必须属于低层实体集。例如，每个人必须是学生或教师。
- 部分约束 partial
  部分概化是默认的，可以在 E-R 图中用 total 来表示完全概化。
  聚集 (Aggregation)
  为了表达联系之间的联系，E-R 模型引入了聚集的概念。聚集是一个抽象的概念，将联系视为高层实体，将联系集看作是实体集一样来处理。
  表示法
  （6th）chapter 8: Relational Database Design
  一般来说，关系数据库设计的目标是生成一组关系模式，这些模式允许我们存储信息而没有不必要的冗余，同时也允许我们轻松地检索信息。这是通过设计具有适当标准形式的模式来实现的。要确定关系模式是否为理想的标准形式之一，我们需要关于我们正在使用数据库建模的真实企业的信息。其中一些信息存在于设计良好的E-R图中，但可能还需要有关企业的其他信息。

在本章中，我们将介绍一种基于功能依赖概念的关系数据库设计的形式化方法。然后，我们根据功能依赖关系和其他类型的数据依赖关系定义标准形式。然而，首先，我们从由给定 E-R 设计派生的模式的角度来看待关系设计问题。

8.1 Features of Good Relational Designs 好的关系设计特征

Design Alternative: Larger Schemas 大型模式

Design Alternative: smaller Schemas 小型模式

8.2 Atomic Domains and First Normal Form 原子域和第一范式

8.3 Decomposition Using Functional Dependencies 使用函数依赖进行分解

8.3.1 Keys and Functional Dependencies 键和函数依赖

Given an instance of r(R), we say that the instance satisfies the functional dependency A → B if for all pairs of tuples t1 and t2 in the instance such that t1[A] = t2[B], it is also the case that t1[A] = t2[B].

我们说函数依赖在模式r(r)上成立，如果在r(r)的每个合法实例中都满足函数依赖。

8.3.2 Boyce–Codd Normal Form

我们所能得到的较为理想的范式之一是 Boyce-Codd 范式(BCNF)。它消除了基于功能依赖可以发现的所有冗余。
如果对于 $F+$ 中 $α→β$ 形式的所有函数依赖关系，其中 $α⊆R$ 和 $β⊇R$ 至少满足以下条件之一，则关系模式 $R$ 在 BCNF 中与函数依赖关系集 $F$ 相关:

$α→β$ 是一个非平凡函数依赖（即，$β⊆α$）。
$α$ 是$R$的一个 Superkey。

现在我们陈述一个 分解不在 BCNF 中的模式的一般规则。设 $R$ 是一个不在 BCNF 中的模式。那么至少存在一个非平凡的函数依赖关系 $α→β$，使得 $α$ 不是 $R$ 的超键。我们用两个模式替换 $R$：

$(α∪β)$
$(R − (β−α))$
当我们分解不属于 BCNF 的模式时，产生的模式中可能有一个或多个不属于 BCNF 的模式。我们继续对这些模式进行分解，直到所有模式都属于 BCNF 为止。最终结果是一个 BCNF 模式集合。

BCNF 分解后的判定方法：
当我们在 ( R ) 的分解中测试关系 ( R_i ) 是否违背 BCNF 时，使用 ( F ) 是不够的。例如，考虑关系模式 ( R (A, B, C, D, E) )，函数依赖项 ( F ) 包含 ( A \to B ) 和 ( BC \to D )，假设将其分解为 ( R1 (A, B) ) 和 ( R2 (A, C, D, E) )。现在，( F ) 中的两个依赖项都不包含来自 ( (A, C, D, E) ) 的属性，因此我们可能会被误导认为 ( R2 ) 满足 BCNF。事实上，( F^+ ) 中有一个依赖关系 ( AC \to D )（可以使用 ( F ) 中的两个依赖关系的伪传递性规则来推断），表明 ( R2 ) 不在 BCNF 中。因此，我们可能需要一个在 ( F^+ ) 中，但不在 ( F ) 中的依赖项，以表明分解的关系不在 BCNF 中。

另一种 BCNF 测试方法有时比计算 ( F^+ ) 中的每个依赖项更容易。要检查 ( R ) 的分解中的关系 ( R_i ) 是否在 BCNF 中，我们应用以下测试：

对于 ( R_i ) 中的每个属性子集 ( \alpha )，检查 ( \alpha^+ )（在 ( F ) 下的属性闭包）是否包含 ( R_i - \alpha ) 的任何属性，或者包含 ( R_i ) 的所有属性。如果某个属性集 ( \alpha ) 在 ( R_i ) 中违反了该条件，请考虑以下函数依赖关系，可以证明它存在于 ( F^+ ) 中：
[
\alpha \to (\alpha^+ - \alpha) \cap R_i
]
上述依赖关系表明 ( R_i ) 违反了 BCNF。

BCNF and Dependency Preservation BCNF和保持依赖

事实上，按照定义，任何只包含两个属性的模式都属于 BCNF。
由于希望保持依赖，因此我们考虑另外一种比 BCNF 更弱的范式，称为第三范式(3NF)。3NF 允许我们保持依赖。

Third Normal Form 第三范式

BCNF要求所有的非平凡依赖都是α→β的形式，其中α是一个超键。第三范式（3NF）通过允许某些左边不是超键的非平凡函数依赖，稍微放宽了这个约束。

对于 $F+$ 中的每个非平凡函数依赖 $α→β$，其中 $α⊆R$ 和 $β⊆R$，至少满足以下条件之一，则关系模式 $R$ 在第三范式中与函数依赖关系集 $F$ 相关:

$α→β$ 是一个平凡函数依赖。
$α$ 是 $R$ 的一个超键。
$β-α$ 中的每个属性 A 都包含在某个 R 的 candidate 中。
Higher Normal Forms 高级范式
8.4 Functional-Dependency Theory 函数依赖理论
我们已经看到，作为BCNF或3NF模式测试过程的一部分，能够系统地推断功能依赖关系是很有用的。

Closure of a Set of Functional Dependencies 函数依赖集的闭包

设 $F$ 是函数依赖项的集合。$F$ 的闭包用 $F+$ 表示，是由 $F$ 逻辑暗示的所有函数依赖的集合。给定 $F$，我们可以直接从函数依赖的形式定义中计算 $F+$。如果 $F$ 很大，这个过程将是漫长而困难的。这样的 $F+$ 计算需要的参数类型正好用来表明 $a→H$ 在我们的依赖关系示例集的闭包中。

公理或推理规则提供了一种更简单的方法来推理功能依赖性。在接下来的规则中，我们使用希腊字母（$\alpha$，$\beta$， $\gamma$，…）表示属性集，而对于单个属性，则使用字母表开头的大写罗马字母。我们用 $\alpha\beta$ 表示属性集 $\alpha$ 和 $\beta$ 的并集。

我们可以使用以下三个规则来查找逻辑上隐含的功能依赖项。通过重复应用这些规则，我们可以找到给定 $F$ 的所有的 $F+$，这组规则被称为 Armstrong’s axioms，以纪念第一个提出它的人。

alt text
虽然 Armstrong 的公理是完备的，但是直接用它们来计算 $F+$ 是令人厌烦的。为了进一步简化问题，我们列出了附加规则。

alt text
图8.7显示了一个过程，它正式地演示了如何使用 Armstrong 公理来计算 $F+$ 。在这个过程中，当一个函数依赖项被添加到 $F+$ 时，它可能已经存在了，在这种情况下，$F+$ 没有变化。我们将在第8.4.2节看到计算 $F+$ 的另一种方法。
alt text

初始化 $F+$，将 $F$ 中已知的函数依加入 $F+$
递归推导，不断应用 Armstrong 公理包括附加规则，直到无法推导出新的依赖为止。
Closure of Attribute Sets 属性集的闭包
计算 属性集的闭包（Closure of Attribute Sets） 是数据库规范化中的重要步骤，用来确定某个属性集能函数确定的所有属性。这在确定候选键、分解表模式等场景中至关重要。

给定一个属性集 ( X \subseteq R ) 和一组函数依赖 ( F )，( X^+ ) 是属性集 ( X ) 的闭包，表示由 ( X ) 根据 ( F ) 可以唯一确定的所有属性集合。

算法

初始化闭包：
将 ( X^+ ) 初始化为 ( X )，即 ( X^+ = X )。
逐步扩展闭包：
对 ( F ) 中的每个函数依赖 ( Y \to Z )：
- 如果 ( Y \subseteq X^+ )，则将 ( Z ) 加入 ( X^+ )。
重复检查：
- 不断重复步骤 2，直到 ( X^+ ) 不再扩展。
停止条件：
- 当所有函数依赖 ( Y \to Z ) 中，( Z \subseteq X^+ ) 时结束。

alt text

Computing the Canonical Cover 正则覆盖

如果去除函数依赖中一个属性不改变函数依赖集的闭包，则称该属性是无关（extraneous）的。
此处形式化定义和检验省略。

F_c = F
  repeat
    使用合并律将 F_c 中所有形如 X -> Y, X -> Z 替换为 X -> YZ
    在 F_c 中寻找一个函数依赖 X -> Y，它在 X 或者 Y 中具有一个无关属性
    /* 注意，使用 F_c 而非 F 检验无关属性*/
    如果找到一个无关属性，则将其从 F_c 中的 X -> Y 中删除
  until F_c 保持不变

8.4.4 Lossless Decomposition

lossy decompositions：有损分解
有损分解例子Kim

8.4.5 Dependency Preservation

8.5 分解算法

BCNF Decomposition Algorithm

BNCF 分解伪代码

3NF Decomposition Algorithm

3NF 分解伪代码

8.6 使用多值依赖的分解

其他范式

Fourth Normal Form 第四范式

4NF 和 BCNF 之间的主要区别在于，4NF要求每个多值依赖都是一个超键，而BCNF要求每个非平凡多值依赖都是一个超键。因此，BCNF是4NF的一个特例。

chapter 10

chapter 11

basic concept

Search Key - attribute to set of attributes used to look up records in a file. / 用于查找文件中记录的属性或属性集。
An index file consists of records (called index entries) of the form / 索引文件由以下形式的记录（称为索引条目）：
- pairs
- pairs
  Index files are typically much smaller than the original file
Two basic kinds of indices:
- Ordered indices: search keys are stored in sorted order / 搜索键按排序顺序存储
- Hash indices: search keys are distributed uniformly across “buckets” using a “hash function” / 使用哈希函数将搜索键均匀分布在“桶”中
Access types supported efficiently. E.g.,
- 特值查找: records with a specified value in the attribute
- 范围查找: or records with an attribute value falling in a specified range of values.
Access time
Insertion time
Deletion time
Space overhead
Ordered Indices 有序索引
In an ordered index, index entries are sorted on the search key value. E.g., author catalog in library.
Primary index 主索引: in a sequentially ordered file, the index whose search key specifies the sequential order of the file. / 在顺序文件中，指定文件顺序的搜索键的索引。
- Also called clustering index(聚集索引)
- The search key of a primary index is usually but not necessarily the primary key. / 主索引的搜索键通常但不一定是主键。
Secondary index: an index whose search key specifies an order different from the sequential order of the file. Also called non-clustering index. / 搜索键指定与文件的顺序不同的顺序的索引。也称为非聚集索引。
- 一个文件可以有多个二级索引
Index-sequential file / 索引顺序文件: ordered sequential file with a primary index. / 具有主索引的有序顺序文件。

clustering index

alt text

sencondary index

alt text

索引记录指向一个存储桶，该存储桶包含指向具有该特定 search-key 值的所有实际记录的指针
二级索引必须密集
Dense Index Files
Dense index — Index record appears for every search-key value in the file. / 索引记录出现在文件中的每个搜索键值。
Sparse Index Files
Sparse Index: contains index records for only some search-key values. 包含了部分搜索键值的索引记录。
Applicable when records are sequentially ordered on search-key，即当记录按搜索键顺序排列时，稀疏索引是适用的。

要查找搜索键值为 K 的记录，请执行下列操作：

查找搜索键值最大的索引记录 < K
从索引记录指向的记录开始按顺序搜索文件

alt text

与 Dense Index 相比：

更少的空间和更少的插入和删除维护开销。
查找记录的速度通常比 dense 索引慢。

Good tradeoff：稀疏索引，文件中每个块都有一个索引条目，对应于块中的最小 search-key 值。

alt text

Multilevel Index 多级索引

如果 primary index 不适合内存，则访问成本会变得很高。
解决方案：将保存在磁盘上的 primary index 视为顺序文件，并在其上构建稀疏索引。
- outer index – 主索引的稀疏索引
- inner index （内部索引） – 主索引文件
如果 outer index 太大而无法放入主内存，则可以创建另一级索引，依此类推。
从文件中插入或删除时，必须更新所有级别的索引。

alt text

Index Update：Deletion

单级索引条目删除：
- 密集索引，删除 search-key 类似于文件记录删除。
- 稀疏索引
- 如果索引中存在搜索键的条目，则通过将索引中的条目替换为文件中的下一个搜索键值（按搜索键顺序）来删除该条目。
- 如果下一个 search-key 值已具有索引条目，则删除该条目，而不是替换该条目。
  Index Update：Insertion
单级索引插入：
- 使用要插入的记录中显示的 search-key 值执行查找。
Dense indices （密集索引） – 如果 search-key 值未出现在索引中，请插入它。
Sparse indices – 如果 index 为文件的每个块存储一个条目，则除非创建新块，否则无需对索引进行任何更改。
- 如果创建了新块，则新块中出现的第一个 search-key 值将插入到索引中。
多级插入和删除：算法是单级算法的简单扩展
B+ Tree Index Files

(Click的指针位置错了，要放到前面一个位置，每个块的最后一个指针指向下一个块)
B+ Tree structure
每个非叶子节点有 $⌈n/2⌉$ ~ $n$ 个子节点
允许叶节点包含的值的最少个数为 $⌈(n-1)/2⌉$
一个非叶子节点可以最多容纳 $n$ 个指针，同时必须至少容纳 $⌈n/2⌉$ 个指针
根节点和其他非叶子节点不同，它包含的指针数可以少于 $⌈n/2⌉$个；但是，除非根节点是唯一的节点，否则根节点必须至少包含两个指针。
Queries on B+ Trees
在处理一个查询的过程中，我们需要遍历树中从根到某个叶子节点的一条路径。如果文件中有 N 个 Search-key 值，那么树的高度不超过 $⌈log_{⌈n/2⌉}N⌉$。其中，$⌈n/2⌉$ 是每个非叶子节点的最小子节点数，$n$ 是每个非叶子节点的最大子节点数，$N$ 是文件中的搜索键值数目。

B+ 树的节点很大，一般是一个磁盘块的大小：4KB。因此，B+ 树的高度通常很小，通常为 3 到 4。

Updating B+ Trees

插入和删除比查找更复杂，因为可能需要拆分由于插入而变得太大的节点，或者如果节点变得太小（少于 ⌈n/2⌉ 指针）则需要合并节点（即组合节点）。此外，当一个节点被拆分或一对节点被合并时，我们必须确保保持平衡。为了介绍B+树中插入和删除背后的思想，我们暂时假设节点不会变得太大或太小。在此假设下，插入和删除将按照下面的定义执行。

插入
- 使用与find（）函数查找相同的技术（图11.11），我们首先找到搜索键值将出现在其中的叶节点。然后，我们在叶节点中插入一个条目（即搜索键值和记录指针对），使得插入后 search key 仍然有序。
删除
- 使用与查找相同的技术，我们通过对已删除记录的搜索键值执行查找，找到包含要删除条目的叶节点；如果有多个具有相同搜索键值的条目，我们搜索具有相同搜索键值的所有条目，直到找到指向要删除的记录的条目。然后我们从叶节点中删除条目。叶子节点中位于被删除条目右侧的所有条目都会向左移动一个位置，这样在条目被删除后，条目中就不会出现空白。
  hash index
  static hash
  dynamic hash
  chapter 12 Query Processing
  查询处理是指从数据库中提取数据所涉及的一系列活动。这些活动包括将高级数据库语言中的查询转换为可用于文件系统物理层的表达式、各种查询优化转换以及查询的实际求值。
  12.1 Overview
  处理查询所涉及的步骤如图12.1所示。
  基本步骤是：

解析和翻译
优化
评估

在开始查询处理之前，系统必须将查询转换为可用的形式。像SQL这样的语言适合人类使用，但不适合作为查询的系统内部表示。更有用的内部表示是基于扩展关系代数的表示。

因此，系统在查询处理中必须采取的第一个动作是将给定的查询转换为其内部形式。这个翻译过程类似于编译器的解析器所执行的工作。在生成查询的内部形式时，解析器检查用户查询的语法，验证查询中出现的关系名称是否为数据库中关系的名称，等等。系统构造查询的解析树表示，然后将其转换为关系代数表达式。如果查询是用视图表示的，那么转换阶段还会用定义视图的关系代数表达式替换视图的所有使用。

steps in query processing

12.2 Measures of Query Cost

查询评估的成本可以通过多种不同的资源来衡量，包括磁盘访问、执行查询的 CPU 时间以及在分布式或并行数据库系统中的通信成本（我们将在第 18 章和第 19 章中讨论）。

在大型数据库系统中，从磁盘访问数据的成本通常是最重要的成本，因为与内存操作相比，磁盘访问速度较慢。此外，CPU速度的提高比磁盘速度快得多。

因此，花费在磁盘活动上的时间很可能继续占执行查询的总时间的主导地位。执行任务所需的CPU时间很难估计，因为它依赖于执行代码的底层细节。尽管现实生活中的查询优化器确实考虑了CPU成本，但为了简单起见，在本书中我们忽略了CPU成本，只使用磁盘访问成本来衡量查询评估计划的成本。

我们使用从磁盘传输的块数和磁盘查找次数来估算查询评估计划的成本。如果磁盘子系统平均需要 (t_T) 秒来传输一个数据块，并且平均块访问时间（磁盘查找时间加上旋转延迟）为 (t_S) 秒，那么一个传输 (b) 个块并执行 (S) 次查找的操作将花费 (b \times t_T + S \times t_S) 秒。(t_T) 和 (t_S) 的值必须根据所使用的磁盘系统进行校准，但对于当今高端磁盘的典型值为 (t_S) = 4 毫秒和 (t_T) = 0.1 毫秒，假设4 千字节块大小和40 兆字节每秒的传输速率。

12.3 Selection Operation

使用文件扫描和索引的选择

示例查询：

A1：
- select * from instructor where name="Einstein";
A2:
- select *from instructor where ID="007"，其中 ID 是一个主索引；
A3：
- select * from instructor where name="Einstein"，其中 name 是一个主索引；
- b 表示需要读取的磁盘块数，可能大于 1，因为可能需要读取多个叶节点块来获取所有符合条件的记录
A4：
- select *from instructor where name="Einstein"，
A5：
- select *from instructor where ID <= "9999"，其中 ID 是一个主索引；
A6：
- select *from instructor where name >= "Einstein"

	算法	开销公式	原因
A1.1	线性搜索	$t_s + b_r \times t_T$	一次初始索引加上 $b_r$ 个块的传输
A1.2	线性搜索，键属性等值比较	平均情况下，$t_s + (b_r/2) \times t_T$	因为最多只有一条记录满足情况，所以平均只需扫描一半的块就能找到，扫描终止
A2	B+ 树主索引，键属性等值比较	$（h_i+1）\times（ t_s + t_T ）$	根据主索引穿越树的高度找到叶子节点，再加上一次磁盘访问来获取记录，每次访问的开销为 $t_s + t_T$
A3	B+ 树主索引，非键属性等值比较	$h_i \times（ t_s + t_T ）+ b \times t_T$	b 为包含匹配记录的块数
A4.1	B+ 树辅助索引，键属性等值比较	$(h_i+1)\times（ t_s + t_T ）$	和 A2 主索引类似
A4.2	B+ 树辅助索引，非键属性等值比较	$(h_i+n)\times（ t_s + t_T ）$	n 为所取的记录数	索引查找的代价和 A3 相似，但是每条记录可能在不同的块上，这需要每条记录一次搜索。如果 𝑛 值比较大，代价可能会非常高。
A5	B+ 树主索引，比较	$h_i \times（ t_s + t_T ）+ b \times t_T$	和 A3 非键属性等值比较类似
A6	B+ 树辅助索引，比较	$(h_i+n)\times（ t_s + t_T ）$	和 A4.2 非键属性等值比较类似

12.4 sort

12.5 JOIN Operation

本节中所用示例：
• Number of records of student: n_student = 5, 000.
• Number of blocks of student: b_student = 100.
• Number of records of takes: n_takes = 10, 000.
• Number of blocks of takes: b_takes = 400.

Nested-Loop Join

NLJ
（1）$tr·ts$ 代表二者级联形成的元组
（2）r 称为 outer relation，s 称为 inner relation
（3）不需要索引，不论连接条件是什么都可以用，但代价高
（4）此算法可扩展为自然连接，只要多加一步将形成元组中重复属性删掉再放入结果集就行
（5）最坏：需要考虑 $N_r \times N_s$个可能的元组对，如果一次只读一个关系的一个块，需要 $N_r \times B_s + B_r$ 次块传输，每次扫描内层关系所有块需要一次 Seek(因为连续存储吗，BNL同理)，外层每个块一次，共 $N_r+B_r$ 次 seek。

（6）最好：如果能一次放入内存，则只需要 2 次 seek 和 $B_r+B_s$ 次块传输。
（7）将以上公式带入例子：最坏情况 2000100 次块传输和5100 次搜索；最好情况 500 次块传输和 2 次 seek
NLJ

Block Nested-Loop Join

BNLJ
（1）对外层关系的一个块考虑内层关系的每个块，再考虑其中的元组对
（2）buffer 无法容纳一个关系
（3）最坏情况下：对于外层关系的每个块要读一次内层关系的所有块，即$B_r \times B_s+Br$次块传输，内层每扫描一次需要 seek 一次，外层每个块需要 seek 一次，即 $2B_r$次。显然不能完全放入内层的话用小关系做外层会更好
（4）最好情况下：全部放入内存，2 次seek，$B_r+B_s$ 次块传输
（5）带入例子：最坏 40100 次块传输和 200 次 seek，最好 2 次 seek 和 500 次传输，和原来一样
（6）两种算法可以改进：
① 如果判断条件中的属性是内层关系的 KEY，则对每个外层元组内层找到首条匹配元组就可以停止
② 对于块循环：外层可以不以块为单位，而是在留出内层空间和输出结果空间的情况下，以内存中能容纳的最大块数为单位。
1）如果内存中有 M 个可用块，一次可以读取 M-2 个外层关系块，使用剩下的两个块缓冲内部关系并输出结果
2）可以将内层的扫描次数从 $B_r$ 次减少到 $B_r/(M-2)$向上取整次，将传输次数变为$(B_r + B_s \times B_r/(M-2)$向上取整)，seek 次数变为 $2B_r/(M-2)$向上取整
③ 对内层的扫描可以轮流采取向前和向后的方式，使得上一次留在内存中的数据重用减少磁盘I/O
④ 存在的话用内层连接的索引(下一节)

Indexed Nested-Loop Join

（1）在嵌套查询(第一种)的情境下，如果内层循环的连接属性上有索引，可以使用索引查找来替代文件扫描：对于外层中的每个$t_r$，利用索引查找 s 中满足和 $t_r$ 连接条件的元组。
（2）本质是对 s 做了个 selection
（3）代价如下：对于外层 r 的每个元组需要在内层 s 上进行索引查找
① 最坏：buffer 只能容纳 r 的一个块和索引的一个块。此时读取 r 需要 $B_r$ 次 I/O，每次 I/O 需要一次 seek 和一次磁盘传输。则连接操作的代价为：$B_r(t_T+t_S)+N_r \times c$。其中 𝑐 是遍历索引并获取与 𝑟 中的一个元组匹配的所有 𝑠 元组的成本。显然在两个关系都有索引可用的情况下把小的放外层更好。
② $c$ 可以用前面选择操作算法的代价估计
（4）带入例子：假设内层 takes 的每个索引节点包含 20 个索引项，takes 有一万个元组，故 B+ 树树高为4，获取实际记录还需要一次磁盘I/O，则 c 中有 5 次磁盘访问的代价，获取外层 100 个块，故 100+5*5000=25100 次访问，每次访问一个块传输，一个寻道

Sort-Merge-join

对两个关系的连接属性进行排序（如果它们尚未按连接属性排序）。
合并排序后的关系以进行连接操作。
连接步骤类似于排序-合并算法的合并阶段。
主要区别在于处理连接属性中的重复值-必须匹配具有相同连接属性值的每个对。

① 算法如图：
1）JoinAttrs为R∩S；ts ⨝ tr表示具有相同JoinAttrs属性值的两个关系中元组的级联(去除重复属性)；ps和pr为两个指向关系中元组的指针，从开头遍历关系；
2）将s按JoinAttrs分为一组放入Ss
3）将r中JoinAttrs值小于Ss中JoinAttrs的部分跳过(因为排序了)，将每个等于的与Ss中的每一个进行连接，ts ⨝ tr放入结果集
4）然后找s中的下一个JoinAttrs相同的组更新Ss，重复以上步骤直到外层遍历完、
② 此算法要求每个Ss都能放入主存
③ 如果对于某些Ss大于可用内存，则可以在Ss与r具有相同JoinAttrs的元组之间使用块嵌套循环连接
④ 如果没有事先排好序，就先排序
⑤ 要扩展到一般等值连接只要不删除重复属性就行
（3）Cost Analysis
① 由于关系是排好序的，连接属性值相同的元组都是连续存放的，所以每个块只需要读一次，两个文件一共读Br+Bs次
② 假设为每个关系分配Bb个内存块(一次性只能读这么多块)，则需要seek次数为：每次去获取都要seek一次
Br/Bb向上取整 + Bs/Bb向上取整
③ 需要排序的情况下要算上排序的代价
④ 带入例子：假设已经排好序，则需要块传输500次，假设两个关系的Bb=1，则需要500次seek。
英文P556 中文P316 (12.5.4.2)有个综合的排序代价的例子。
（4）Hybrid Merge Join混合归并连接
① 当两个关系存在辅助索引时，可以对未排序的元组执行这个算法的变体版本。
② 假设两个关系中有一个排了序一个没有，但未排序的关系在连接属性上有有B+树辅助索引，此混合算法将已排序关系与B+树辅助索引节点进行归并，得到的结果为一个文件，其中包含已排序关系的元组和未排序关系的元组地址，将这个文件按未排序关系元组地址排好序，然后可以按照物理存储顺序去获取这些元组，完成连接运算。

Hash Join

（1）用于实现等值连接和自然连接，此算法中用哈希函数h划分两个关系的元组，基本思想为将关系中的元组分成在连接属性上有相同哈希值的元组集合。
（2）假设：
① h为将JoinAttrs值映射到{0,1,…,nk}的哈希函数
② r0,r1,…,rnh表示r的划分，一开始每个都是空集，r中的元组会被放入ri，其中i=h( tr [JoinAttrs] )
③ s0,s1,…,snh同上
（3）基本思想：
① 如果r和s中的元组满足连接条件，即在连接属性上有相同的值，则它们经过哈希映射到i，则关系r的该元组一定在ri中，s的该元组一定在si中，因此只需要比较这两个集合中的元组即可，不需要与其他划分中的部分比较。
② 即当h(c)≠h(d)时，不需要比较c和d，哈希值不同cd不可能相同，h(c)=h(d)时需要进一步比较cd，因为可能存在冲突。
③ 算法：
alt text

1）JoinAttrs为R∩S；ts ⨝ tr表示具有相同JoinAttrs属性值的两个关系中元组的级联(去除重复属性)
2）将s按连接属性散列成划分
3）将r按连接属性散列成划分
4）对每个i划分进行索引嵌套循环连接：先读si并建立内存中的哈希索引，然后对ri中的每个r元组，探查s上的哈希索引找到匹配的s元组，将所有匹配的s元组与r元组连接然后加入结果集

最后这个步骤的术语：builds a hash index on each si，probes with tuples from ri (即looks up si)，关系s为build input，r为probe input
s的哈希索引是在内存中建立的，所以不需要访问磁盘检索元组，用于构造这个哈希索引的函数必须与h不同，但仍只对连接属性进行哈希，最后的循环连接中，系统使用这个索引来检索与probe input匹配的记录。
nk要选大一点，使得对于任意i，内存中可以容纳si中的元组及其上的哈希索引。(划分够多每个划分的内容就会少)
如果s(build input)有Bs个块，要使得每个划分≤M，nk至少为Bs/M向上取整，而且最好更大一些

（4）Recursive Partitioning递归划分

如果划分数n大于内存块数M，关系划分无法一趟完成
分成多趟，一开始分成较大的划分，然后在下一趟中被分成更小的划分
注意每一趟用的哈希函数要跟上一趟不一样
直到build input的每个划分都能放入内存为止

（5）Handling of Overflows

当si的散列索引大于主存时，s的划分i发生hash-table overflow
选的散列函数不合适导致某些划分中所含元组明显多于平均而有些明显少于，则称这种划分为skewed(偏斜的)
少量的偏斜可以通过增加划分个数，使划分的期望大小(包括其上的哈希索引)比内存容量略小，划分数会因此有少量增加，增加的数目称为”fudge factor”避让因子，通常为计算出前面计算出合适划分数的百分之二十
即使增加了划分数也依然有可能溢出，有两个方法进行处理：
1）Overflow resolution溢出分解：在build阶段发现溢出，则进行溢出分解。若发现任意si太大了，则用另一个哈希函数将其分成更小的划分，将ri也进行同样的处理，这样还是在匹配的划分中找可以连接的元组
2）Overflow avoidance溢出避免：创建划分时谨慎一点保证构造阶段不会出现溢出。首先将s分成许多小的划分，然后把后写划分组合到一起，但是要确保每个组合都能放入内存，r必须按照与s上的划分组合相同的方式进行划分，但ri的大小不重要(不用进内存)。
解决方式不起效果的情况下就不创建哈希索引了，用其他连接方法来连接划分。

（6）Cost of Hash Join

如果不需要递归划分：
3 ( Br+Bs ) + 4 nh 块传输 + 2 * ( Br/Bb向上取整 + Bs/Bb向上取整 )次seek
如果需要递归划分：
1）划分build relation s需要的趟数：logM-1(Bs) -1向上取整
2）块传输次数：2( Br+Bs ) (logM-1(Bs) -1向上取整) + Br+ Bs
3）seek次数：2 ( Br/Bb向上取整 + Bs/Bb向上取整 ) (logM-1(Bs) -1向上取整)
Evaluation of Expressions
通过上面的内容，我们知道了对于单个操作的算法，我们有两个主要方法来执行整个表达式树:
- 物化计算(Materialization evaluation)
- 流水线(Pipeline)
  Materialization evaluation
  逐个操作地执行查询，从最低级别开始。使用中间结果物化(Materailize)为临时关系，以执行下一级别的操作。
  示例：
  1
  2
  3
  Select name
  from instructor natural join department
  Where building=“watson”
- 这种方法经常是实用的
- 会带来额外的开销，因为要把中间结果写磁盘
- 双缓冲(double buffering)(即使用两个缓冲区,其中一个用于连续执行算法,另一个用于写出结果)允许 CPU 活动与 I/O 活动并行,从而提高算法执行速度。
  Pipeling
- 不储存中间结果，而是把中间结果直接传输到下一个要执行的操作上
- 管道传输不一定总是可行的，例如排序和哈希连接。为了使管道传输有效，使用评估算法，在接收到输入操作的元组时生成输出元组。
- 管道传输可以通过两种方式执行：
- 需求驱动（demand driven）
- 生产者驱动（producer driven）
- 另一种名称：拉取（pull）和推送（push）模型的管道传输。
- 在需求驱动或惰性(lazy)管道传输中：
- 系统会反复从顶层操作请求下一个元组。
- 每个操作根据需要从子操作请求下一个元组，以便输出其下一个元组。
- 在调用之间，操作必须维护“状态”，以便知道要返回什么。
- 在生产者驱动或渴望型(eager)管道传输中：
- 操作符会主动生成元组并将它们传递给它们的父级。
- 在操作符之间维护缓冲区，子操作符将元组放入缓冲区，父操作符从缓冲区中移除元组。
- 如果缓冲区已满，子操作符将等待，直到缓冲区有空间，然后生成更多的元组。
- 系统调度具有输出缓冲区空间和能够处理更多输入元组的操作符。
  课后习题
1. 12.2

12.3
To estimate the number of block transfers and seeks for the join ( r1 \bowtie r2 ), let’s analyze each join strategy given the properties:

Assumptions and Calculations

Tuples per block:
- ( r1 ): 25 tuples per block → ( \text{blocks for } r1 = \lceil 20000 / 25 \rceil = 800 ) blocks.
- ( r2 ): 30 tuples per block → ( \text{blocks for } r2 = \lceil 45000 / 30 \rceil = 1500 ) blocks.
I/O cost components:
- Block transfer: The number of block reads/writes from/to disk.
- Seeks: The number of disk head movements required to access blocks.

a. Nested-Loop Join

Algorithm:

For each block of ( r1 ) (outer relation):
- Read all blocks of ( r2 ) (inner relation).
Compare tuples and output matches.

I/O cost:

( r1 ) requires ( 800 ) block transfers (read once).
For each block of ( r1 ), all ( 1500 ) blocks of ( r2 ) are read:
[
\text{Total transfers} = 800 + (800 \times 1500) = 1,200,800 \text{ block transfers}.
]
Seeks:
- 1 seek for each block of ( r_1 ) (( 800 ) seeks).
- 1 seek for each pass over ( r_2 ) (( 800 \times 1 = 800 ) seeks).
  [
  \text{Total seeks} = 800 + 800 = 1,600.
  ]

b. Block Nested-Loop Join

Algorithm:

Divide ( r1 ) into ( B-2 ) blocks, where ( B ) is the number of available buffer blocks.
For each group of ( B-2 ) blocks of ( r1 ), scan all blocks of ( r2 ).

Assume ( B = 10 ) buffer blocks (( 8 ) for ( r1 ), ( 1 ) for ( r2 ), and ( 1 ) for output).

Outer relation: ( \lceil 800 / 8 \rceil = 100 ) passes over ( r1 ).
Inner relation: ( r2 ) (1500 blocks) is scanned during each pass.

I/O cost:

( r1 ): Read once, ( 800 ) blocks.
( r2 ): Read once per pass of ( r1 ):
[
\text{Total transfers} = 800 + (100 \times 1500) = 150,800 \text{ block transfers}.
]
Seeks:
- ( r1 ): ( 800 ) seeks.
- ( r2 ): ( 100 ) seeks (1 seek per pass).
  [
  \text{Total seeks} = 800 + 100 = 900.
  ]

c. Merge Join

Algorithm:

Sort ( r1 ) and ( r2 ) on ( C ).
Merge the sorted relations.

Sorting Cost:

External sorting (2-pass, assume sufficient memory for ( \sqrt{B} )):
- ( r1 ): ( 2 \times 800 = 1600 ) block transfers.
- ( r2 ): ( 2 \times 1500 = 3000 ) block transfers.
  [
  \text{Total sorting cost} = 1600 + 3000 = 4600 \text{ block transfers}.
  ]

Merge Cost:

Both relations are scanned once.
[
\text{Total merge cost} = 800 + 1500 = 2300 \text{ block transfers}.
]

I/O cost:
[
\text{Total transfers} = 4600 + 2300 = 6900 \text{ block transfers}.
]

Seeks:

Sorting: 1 seek per block (1600 for ( r1 ), 3000 for ( r2 )).
Merge: 1 seek per block (800 for ( r1 ), 1500 for ( r2 )).
[
\text{Total seeks} = 1600 + 3000 + 800 + 1500 = 6900.
]

d. Hash Join

Algorithm:

Partition ( r1 ) and ( r2 ) into buckets using a hash function.
Join tuples from matching buckets.

Cost:

Partition phase:
- ( r1 ): Read and write ( 800 ) blocks → ( 2 \times 800 = 1600 ) block transfers.
- ( r2 ): Read and write ( 1500 ) blocks → ( 2 \times 1500 = 3000 ) block transfers.
Probing phase:
- Both relations are scanned once:
  [
  \text{Total probing cost} = 800 + 1500 = 2300 \text{ block transfers}.
  ]

I/O cost:
[
\text{Total transfers} = 1600 + 3000 + 2300 = 6900 \text{ block transfers}.
]

Seeks:

Partition phase: 1 seek per block (1600 for ( r1 ), 3000 for ( r2 )).
Probing phase: 1 seek per block (800 for ( r1 ), 1500 for ( r2 )).
[
\text{Total seeks} = 1600 + 3000 + 800 + 1500 = 6900.
]

Summary of Costs

Join Strategy	Block Transfers	Seeks
Nested-Loop Join	1,200,800	1,600
Block Nested-Loop Join	150,800	900
Merge Join	6,900	6,900
Hash Join	6,900	6,900

chapter 13 Query Optimization

chapter 16 Recovery System

16.4 Recovery Algorithm

16.4.1 Transaction Rollback

16.4.2 Recovery After a System Crash

alt text

chapter 17 Transactions

ACID：原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）和持久性（Durability）。

atomicity and consistency

commited / 已提交
compensating transaction / 补偿事务
建立一个简单的抽象事务模型，事务必须处于以下状态之一：
Active / 活动：初始状态，事务执行时处于这个状态
Partially Committed / 部分提交：最后一条指令执行后
Failed / 失败：发现正常的执行不能继续后
Aborted / 中止：事务回滚并且数据库恢复到事务开始前的状态后
Committed / 已提交：事务成功完成后
如果事务是提交的或者中止的，那么事务称为 terminated / 终止的。

系统判断事务不能继续正常执行后，事务进入失败状态。在失败状态下，事务可以回滚并且数据库恢复到事务开始前的状态，这样就进入了 Aborted 状态。此时系统可以选择重新执行（restart）事务或者放弃(kill)事务。
restart：当且仅当引起事务 Aborted 的原因是硬件错误而不是内部逻辑错误时，系统才会重新执行事务。重启的事务被看作是一个新事务。
kill：当事务因为内部逻辑错误而失败时，系统会放弃事务。
Serializability / 串行
在考虑数据库系统的并发控制组件如何确保可串行化之前，我们先考虑如何确定一个调度何时是可串行化的。当然，串行调度是可串行化的，但是如果多个事务的步骤是交错的，则很难确定调度是否可串行化。

Conflict Serializability / 冲突可串行化

冲突：如果两个事务 $T_i$ 和 $T_j$ 访问同一数据项，并且至少有一个是写入操作，则 $T_i$ 和 $T_j$ 之间存在冲突。如果 $T_i$ 和 $T_j$ 之间没有冲突，则称 $T_i$ 和 $T_j$ 是不冲突的。
冲突等价：如果调度可以经过一系列的非冲突指令交换转换成 S’，那么 S 和 S’ 是冲突等价的。
冲突可串行化：如果一个调度 S 与一个串行调度冲突等价，那么 S 是冲突可串行化的。
冲突图：冲突图是一个有向图，图中的节点是事务，如果两个事务之间存在冲突，则有一条从一个事务到另一个事务的有向边。如果冲突图是有向无环图（DAG），则调度是冲突可串行化的。
事务隔离性和原子性
为了应对并发执行过程中事务故障所产生的影响，从事务故障恢复的角度看什么样的调度是可接受的。
可恢复调度 / Recoverable Schedules
可恢复调度应满足：对于每一对事务 $T_i$ 和 $T_j$，如果 $T_j$ 读取了 $T_i$ 写入的数据项，则 $T_i$ 的提交时间早于 $T_j$。
无级联调度 / Noncascading Schedules
因单个事务故障导致一系列事务回滚的现象称为级联回滚（cascading rollback）。为了避免级联回滚，我们需要无级联调度：对于每一对事务 $T_i$ 和 $T_j$，如果 $T_j$ 读取了 $T_i$ 写入的数据项，则 $T_i$ 必须在 $T_j$ 这一个读操作之前提交。容易证明，无级联调度也是可恢复调度。
事务隔离级别
Read Uncommitted / 读未提交：最低隔离级别，允许事务读取未提交的数据。
Read Committed / 读已提交：确保事务只能看到已提交的数据。
Repeatable Read / 可重复读：确保事务在执行期间看到的数据是一致的。
Serializable / 可串行化：最高隔离级别，确保事务是串行执行的。
所有的隔离级别都不支持脏写（dirty write），即如果一个数据项被一个事务写入但未提交或中止，另一个事务不能写该数据项。
许多数据库系统的默认隔离级别是 Read Committed。
隔离级别的实现
锁
时间戳
多版本和快照隔离 snapshot isolation
chapter 18 Concurrency Control 并发控制
Lock-Based Protocols
确保隔离的一种方法是要求以互斥的方式访问数据项；也就是说，当一个事务访问数据项时，其他事务不能修改该数据项。用于实现此需求的最常用方法是允许事务仅在当前持有数据项的锁时才能访问该数据项。
Locks

共享锁 Shared. If a transaction Ti has obtained a shared-mode lock (denoted by S) on
item Q, then Ti can read, but cannot write, Q. / 如果事务 Ti 在项目 Q 上获得了共享模式锁（用 S 表示），则 Ti 可以读取但不能写入 Q。
排他锁 Exclusive. If a transaction Ti has obtained an exclusive-mode lock (denoted by X)
on item Q, then Ti can both read and write Q. / 如果事务 Ti 在项目 Q 上获得了排他模式锁（用 X 表示），则 Ti 可以读取和写入 Q。
锁的授权 / Lock Granularity
当事务 $T_i$ 申请对 Q 数据项加 M 型锁时，并发控制管理器授权加锁的条件是
不存在在数据项 Q 上持有与 M 型锁冲突的锁的其他事务。
不存在等待对数据项 Q 加锁且先于 $T_i$ 申请加锁的其他事务。
The Two-Phase Locking Protocol
增长阶段 Growing Phase. 事务可以获得锁，但不能释放锁。
缩减阶段 Shrinking Phase. 事务可以释放锁，但不能获得新锁。
我们可以证明，两阶段锁定协议确保了冲突的可串行性。

考虑任何事务。事务在调度中获得最终锁的点（增长阶段的结束）称为事务的 lock point。

现在，可以根据它们的锁点对事务进行排序——这种排序实际上是事务的可序列化性排序。

除了冲突可串行化之外，调度还应该是无级联的。在两阶段封锁协议中，级联回滚是可能发生的。

级联回滚可以通过 严格两阶段锁定 Strict Two-Phase Locking 避免。
- 这个协议除了要求封锁是两阶段的之外，还要求事务持有的所有排他锁必须在事务提交后方可释放。这个要求保证未提交事务所写的任何数据在该事务提交之间都以排他方式加锁，防止其他事务读这些数据。
强两阶段锁定协议 rigorous two-phase locking protocol
- 要求事务在提交之前不得释放任何锁。在强两阶段封锁协议中，事务都会按照提交的顺序串行执行。
  基于图的协议
  死锁处理
  多粒度
  基于时间戳的协议
  基于有效性检查的协议
  多版本机制
  快照隔离
  chapter 19 Recovery System
  存储器
volatile storage / 易失性存储器
nonvolatile storage / 非易失性存储器
stable storage / 稳定存储器
稳定存储器在恢复算法中起到至关重要的作用。
恢复与原子性
日志记录
使用日志来重做和撤销事务
在 immediate update 策略中，事务的修改在事务提交之前就被写入数据库。在 deferred update 策略中，事务的修改在事务提交之后才被写入数据库。
immendiate update的情况下：
- 出现，没见到或者，undo
- 出现和，redo
In deferred database modification schema, the only operation used in the recovery procedure is: redo.
真题解析
13

17年

part2

(a) Explain what is view materialization. (b) Please define a view in SQL num_employed(company_name, num), giving the number of the employess in each company.
(a) Explain what is sequential index. (b) Compare sequential index with hash index, and describe the advantanges and disadvantage of sequential index.
(a) Nested block loop join algorithm is one effective algorithm to inplement the JOIN operation in database processing. Please explain the main steps of the algorithm. (b) Please estimate the cost of the relational algebra by using the nested block loop join algorithm : visitor natural join teaches. Suppose the relation vistructor has 1000 block. The relation teaches has 500 blocks. The main memory has 5 data blocks. The cost is measured in number of block transfer and disk seeks.
(a) explain what is a serializable schedule. (b) Detect if the following schedule of two transactions is serializable. Please justify your answer.

Step	T1 Operations	T2 Operations
1	Read(A)
2	Read(B)
3	if A = 0 then B = B + 1
4		Read(B)
5		Read(A)
6	Write(B)
7		if B = 0 then A = A + 1
8		Write(A)

Chapter 1

view of Data

Data Modles

Relational Model 关系模型

Entity-Relationship Model 实体关系（E-R）模型

Semi-structured Data Model 半结构化数据模型

Object-Based Data Model 基于对象的数据模型

Relational Model

Data Abstraction

Instances and Schemas 实例和模式

Database Languages

DDL

The SQL Data-Definition Language

Data-Manipulation Language

Database Access from Application Programs

Database Design

Database Engine

Storage Manager

Query Processor

Transaction Manager

Database and Application Architecture

Database Users and Administrators

Database Users and User Interfaces

Database Administrator

History of Database Systems

Chapter 2: Introduction to the Relational Model

Structure of Relational Databases

Database Schema

Keys

Schema Diagrams

Relational Query Languages

The Relational Algebra 关系代数

The Select Operation

The Project Operation

Composition of Relational Operations

The Cartesian-Product Operation

The Join Operation

Set Operations

The Assignment Operation

The Rename Operation

Equivalent Queries

chapter 27 Other Data Models

Document Data Model

Vector Data Model

Chapter 3: Introduction to SQL

3.1 Overview of the SQL Query Language

3.2 SQL Data Definition

Basic Types

Basic Schema Definition

3.3 Basic Structure of SQL Queries

Queries on a Single Relation 单关系查询

Queries on Multiple Relations 多关系查询

自然连接

danger of nartual join

3.4 Additional Basic Operations 附加的基本运算

the rename operation

String Operations 字符串运算

Attribute Specification in the Select Clause

Ordering the Display of Tuples

where 子句谓词

集合运算

Null Values 空值

3.7 Aggregate Functions

Basic Aggregation

Aggregation with Grouping

The Having Clause

Aggregation with Null and Boolean Values 对空值和布尔值的聚集

3.8 Nested Subqueries 嵌套子查询

Set Membership

Set Comparison

Test for Empty Relations

Test for the Absence of Duplicate Tuples

Subqueries in the From Clause

The With Clause

Scalar Subqueries

Scalar Without a From Clause

3.9 Modification of the Database

Deletion

Insertion

Update