【笔记】数据库系统概念
引言
数据库管理系统（DBMS）由一个互相关联的数据的集合（数据库）和一组用以访问这些数据的程序组成。
数据库系统的一个主要目的是为用户提供数据的抽象视图，系统隐藏数据存储和维护的细节。
数据库结构的基础是数据模型：一个用于描述数据、数据之间的联系、数据语义和数据约束的概念工具的集合。
关系数据模型是最广泛使用的将数据存储到数据库中的模型。其他的数据模型有面向对象模型、对象-关系模型和半结构化数据模型。
数据操纵语言（DML）是使得用户可以访问和操纵数据的语言。数据定义语言（DDL）是说明数据库模式和数据的其他特征的语言。
数据库设计主要包括数据库模式的设计。实体-联系（E-R）数据模型是广泛用于数据库设计的数据模型，提供一种方便的图形化的方式来观察数据、联系和约束。
数据库设计流程：
- 制定出用户需求的规格文档
- 在概念设计阶段开发出来的模式提供企业的详细概述：描述数据以及它们之间的联系，而不是指定无力的存储细节
- 逻辑设计阶段：设计者将高层的概念模式映射到要使用的数据库系统的设计数据模式上
- 物理设计阶段：指定数据库中的物理特性，这些特性包括文件组织的形式以及内部的存储结构
数据库系统由几个子系统构成：1、存储管理器子系统在数据库中存储的低层数据与应用程序和向系统提交的查询之间提供借口。2、查询处理器子系统编译和执行DDL和DML语句。
事务是数据库应用中完成单一逻辑功能的操作结合。每个事务是一个既具有原子性又具有一致性的单元。原子性和持久性的保证是数据库系统自身的职责。事务管理负责保证不管是否有故障发生，数据库都要处于一致的（正确的）状态。事务管理器还保证并发事务的执行互不冲突。
数据库系统的体系结构受支持其运行的计算机系统的影响很大。数据库系统可以是集中式的。或是客户-服务器方式的，即一个服务器及其为多个客户机执行工作。数据库系统还可以设计成具有能充分利用并行计算系统结构的能力。分布式数据库跨越多个地理上分布的互相分离的计算机。
典型地，数据库应用可被分为运行在客户机上的前端和运行在后端的部分。在两层的系统结构中，前端直接和后端运行的数据库进行通信。在三层结构上，后端又被分为应用服务器和数据库服务器。
知识发现技术试图自动地从数据中发现统计规律和模式。数据挖掘领域将人工智能和统计分析研究人员创造的知识发现技术，与使得知识发现技术能够在极大地数据库上高效实现的技术结合起来。数据挖掘指半自动地分析大型数据库并从中找出有用的模式的过程。
关系数据库
关系模型介绍
数据模型是描述数据、数据联系、数据语义以及一致性约束的概念工具的集合。数据库模式是指数据库的逻辑设计，数据库实例是指给定时刻数据库中数据的一个快照。
关系数据模型建立在表的集合的基础上。数据库系统的用户可以对这些表进行查询，可以插入新元组、删除元组以及更新（修改）元组。表达这些操作的语言又几种。
关系的模式是指它的逻辑设计。而关系的实例是指它的特定时刻的内容。数据库的模式和实例的定义的类似的。关系的模式包括它的属性，还可能包括属性类型和关系上的约束，比如主码和外码约束。
关系的超码是一个或多个属性的集合，这些属性上的取值保证可以唯一识别出关系中的元组。候选码是一个最小的超码，也就是说，它是一组构成超码的属性集，但这组属性的任意子集都不是超码。关系的一个候选码被选作主码。
在参照关系中的外码是这样的一个属性集合：对于参照关系中的每个元组来说，它在外码属性上的取值肯定等于被参照关系中某个元组在主码上的取值。
模式图是数据库中模式的图形化表示，它显示了数据库中的关系，关系的属性、主码和外码。
关系查询语言定义了一组运算集，这些运算可以作用于表上，并输出表作用结构。这些运算可以组合成表达式，表达所需的查询。
关系代数提供了一组运算，它们以一个或多个关系为输入，返回一个关系作为输出。诸如SQL这样的实际查询语言的基于关系代数的，但增加了一些有用的句法特征。
SQL
SQL是最有影响力的商用市场化的关系查询语言。包括以下几个部分：1、数据定义语言（DDL），提供了定义关系模式、删除关系以及修改关系模式的命令；2、数据操作语言（DML），提供查询语言，以及往数据库中插入元组、从数据库中删除元组修改数据库中元组的命令。
SQL的数据定义语言用于创建具有特定模式的关系。除了声明关系属性的名称和类型之外，SQL还允许声明完整性的约束，例如主码约束和外码约束。
SQL提供多种用于查询数据库的语言结构，其中包括select、form和where子句。SQL支持自然连接操作。
SQL还提供了对属性的关系重命名，以及对查询结果按特定属性进行排序的机制。
SQL支持关系上的基本集合运算，包括并、交和差运算。
SQL通过在通用真值true和false外增加增值“unknown”，来处理对包含空值进行排序的机制。
SQL支持在外层查询的where和from子句中嵌套子查询。它还在一个表达式返回的单个值所允许出现的任何地方支持标量子查询。
SQL提供了用于更新、插入、删除信息的结构。
中级SQL
SQL支持包括内连接、外连接在内的几种连接类型，以及几种形式的连接条件。
视图关系可以定义为包含查询查询结果的关系。视图可以隐藏不需要的信息，可以把信息从多个关系收集到一个单一的视图中。
事务是一个查询的更新的序列，它们共同执行某项任务。事务可以被提交或回滚。当一个事务被回滚，该事务执行的所有更新所带来的影响将被撤销。
完整性约束保证授权用户对数据库所做的改变不会导致数据一致性的破坏。
参照完整性约束保证出现在一个关系的给定属性集上的值同样出现在另一个关系的特定属性集上。
域约束指定了在一个属性上可能取值的集合。这种约束也可以禁止在特定属性上使用空值。
断言是描述性表达式，它指定了我们要求总是为真的谓词。
SQL数据定义语言提供对定义诸如date和time那样的固有域类型以及用户定义域类型的支持。
通过SQL授权机制，可以按照在数据库中不同数据值上数据库用户所允许的访问类型对他们进行区分。
获得了某种形式授权的用户可能允许将此授权传递给其他用户。但是，对于权限怎样在用户间传递我们必须很小心，以保证这样的权限在将来的某个时候可以被收回。
角色有助于根据用户在组织机构中扮演的角色，把一组权限分配给用户。
高级SQL
SQL查询可以从宿住语言通过嵌入和动态SQL激发。ODBC和JDBC标准给C、Java等语言的应用程序定义接入SQL数据库的应用程序接口。
函数和过程可以用SQL提供的过程来定义，它允许迭代和条件语句。
触发器定义了当某个事件发生而且满足相应条件时自动执行的动作。触发器有很多用处，例如实现业务规则、审计日志，甚至执行数据库系统外的操作。
联机分析处理（OLAP）工具帮助分析人员用不同的方式查看汇总数据。
- OLAP工具工作在以维属性和度量属性为特性的多维数据之上。
- 数据立方体由以不同方式汇总的多维度数据构成。预先计算数据立方体有助于提高汇总数据的查询数据。
- 交叉表的显示允许用户一次查看多维数据的两个维及其汇总数据。
- 下钻、上卷、切片和切块是用户使用OLAP工具时执行的一些操作。
形式化关系查询语言
关系代数定义了一套在表上运算且输出结果也是表的代数运算。这些运算可以凝合使用来得到表达所希望查询的表达式。关系代数定义了关系查询语言中使用的基本运算。
关系代数运算可以分为：
1、基本运算；
关系代数基本运算有：选择、投影、并、集合差、笛卡尔积和更名。选择、投影和更名运算是一元运算符。选择：选出满足给定谓词的元组。
二元运算自然连接使得我们可以将某些选择和笛卡尔积运算合并为一个运算。自然连接运算首先形成它的两个参数的笛卡尔积，然后基于两个关系模式中都出现的属性上相等性进行选择，最后还要去除重复属性。
2、附加的运算，可以用基本运算的表达；
包括集合交、自然连接和赋值。
3、扩展的运算，其中的一些扩展了关系代数的表达能力。
广义投影：允许在投影列表中使用算术运算和字符串函数等来对投影进行扩展。
以下三种等价：
- 基本关系代数（不包含扩展关系代数运算）
- 限制在安全表达式范围内的元组关系演算
- 限制在安全表达式范围内的域关系演算
没有任何一个域关系演算等价于聚集运算，但是它可以扩展支持聚集。
关系代数式一中简洁的、形式化的语言，不适合于那些偶尔使用数据库系统的用户。因此，商用数据库系统采用有更多“语言修饰”的语言。
元组关系演算和域关系演算使非过程化语言，代表了关系查询语言所需的基本能力。基本关系代数式一种过程化语言，在能力上等价于被限制在安全表达式范围内的关系演算的这两种形式。
关系演算的简洁的、形式化的语言，并不适合于那些偶尔使用数据库系统的用户。
数据库设计
数据库设计与E-R模型
- 数据库设计的最初阶段需要完整地刻画未来数据库用户的数据需求
- 设计者选择数据模型，并采用所选数据模型的概念将这些需求转化为数据库的概念模式。在概念设计阶段所产生的模式提供了一个对企业的详细综述。
- 完善的该你那模式还指明企业的功能需求。
- 从抽象数据模型到数据库的实现的转化在最后两个设计阶段中进行
- 逻辑设计阶段：将高层概念模式映射到将使用的数据库系统的实现数据模式上。
- 物理设计简单：指明数据库的物理特征。
在设计一个数据库模式时，需要确保避免两个主要缺陷：冗余、不完整。
数据库设计主要涉及数据库模式的设计。实体-联系（E-R）数据库模型是一个广泛用于数据库设计的数据模型。提供了一个方便的图形化表示方法以查看数据、联系和约束。
E-R模型主要用于数据库设计过程。它的发展是为了帮助数据库设计，这是通过允许定义企业模式实现的。这种企业模式代表数据库的全局逻辑结构，可以用E-R图形化表示。
实体是在现实世界中存在并且区别于其他对象的对象。通过把每个实体同描述该实体的一组属性相关联来表示区别。
联系是多个实体间的关联。相同类型的联系的集合为联系集，相同类型的实体的集合为实体集。
每个属性都有一个可取值的集合，称为该属性的域，或者值集。
术语超码、候选码以及主码同适用于关系模式一样适用于实体和联系集。
映射的基数表示通过联系集可以和另一实体相关联的实体的个数。
不具有足够属性构成的主码的实体集称为弱实体集。具有主码的实体集称为强实体集。
E-R模型的各种性质为数据库设计者提供了大量的选择，使设计人员可以最好地表示被建模的企业。在某些情况下，概念和对象可以用实体、联系或属性来表示。企业总体结构的各方面可以用弱实体集、概化、特化或聚集很好地描述。设计者通常需要在简单的、紧凑的模型与更精确但也更复杂的模型之间进行权衡。
用E-R图定义的数据库设计可以用关系模式的集合来表示。数据库的每个实体集和联系集都有唯一的关系模式与之对应，其名称即为相应的实体集或联系集的名称。这是从E-R图转换为关系数据库设计的基础。
特化和概化定义了一个高层实体集和一个或多个低层实体集之间的包含关系。特花是取出高层实体集的一个子集来形成一个低层实体集。概化湿用两个或者多个不相交的（低层）实体集的并集形成一个高层实体集。高层实体集的属性被低层实体集继承。
聚集是一种抽象，其中联系集（和它们相关的实体集一起）被看作高层实体集，并且可以参与联系。
UML是一种常见的建模语言。UML类图广泛用于对类建模以及一般的数据建模。
关系数据库设计
冗余存储则存在不一致的风险。
如果该域的元素被认为是不可分的单元，这个域是原子的。如果关系模式R的所有属性的域都是原子的，那么称R属于第一范式（1NF）。
在许多含有复杂结构的实体域中，强制使用第一范式会给应用程序员造成不必要的负担。设计与开发时需要从当前业务考虑。
一个关系的满足所有现实世界的约束的实例，称为关系的合法实例（满足业务要求的实例）。
使用F+符号表示F集合的闭包，能够从给定F集合推导出所有函数依赖的集合。F+包含了F的所有函数依赖。
具有函数依赖集F的关系模式R属于BCNF的条件是，对于F+中所有形如a->b的函数依赖（其中a与b都包含于R），下面至少一项成立：1、a->b是平凡的函数依赖（即b包含于a）；2、a是模式R的一个超码。一个数据库设计属于BCNF的条件是，构成该设计的关系模式集中的每种模式都属于BCNF。
第三范式：对于F+中所有形如a->b的函数依赖（其中a，b都包含于R）以下至少一项成立：1、a->b是一个平凡的函数依赖；2、a是R的一个超码；3、b-a中的每个属性A都包含于R的一个候选码中（候选码是最小的超码，且任意子集都不是超码）。
给定关系模式r(R)，如果r(R)的每一个满足F的实例都满足f，则R上的函数依赖f被r上的函数依赖F逻辑蕴涵。F的闭包是被F逻辑蕴涵的所有函数依赖的集合（F+）。
函数依赖和多值依赖集为D的关系模式r(R)属于第四范式的条件是，对于D+中所有形如a–>b的多值依赖（其中a和b都包含于R），以下至少一项成立：1、a–>b是一个平凡的多值依赖；2、a是R的一个超码。
应用设计和开发
数据存储和查询
存储和文件结构
最快的存储介质（如高速缓冲存储器和主存储器）称为基本存储。层次结构中的基本存储介质的下一层介质（如磁盘）称为辅助存储或联机存储。层次结构中最底层的介质（如磁带机和自动光盘机）称为三级存储或脱机存储。
易失性存储在设备断电后将丢失所有的内容。
存储介质的可靠性由两个因素决定：1、电源故障或系统崩溃是否导致数据丢失；2、存储设备发生物理故障的可能性有多大。
通过保留数据的多个拷贝，可以减少物理故障的可能性。对磁盘来说可以使用镜像技术。或者可以使用更复杂的基于独立磁盘冗余阵列（RAID）的方法。通过将数据拆分到多张磁盘上，可以提高大数据量访问的吞吐率；通过引入多张磁盘上的冗余存储，可以显著提高可靠性。
可以把一个文件从逻辑上组织成映射到磁盘块上的一个记录序列。把数据库映射到文件的一种方法是使用多个文件，每个文件只存储固定长度的记录。另一种方法是构造文件。使之能适应多种长度的记录。分槽的页方法广泛应用于在磁盘块中处理变长记录。
通过在多张磁盘上进行数据拆分来提高传速率。数据拆分最简单的形式是将每个字节按比特分开，存储到多个磁盘上。这种拆分称为比特级拆分。块级拆分是将块拆分到多张磁盘。
磁盘系统并行有两个主要目的：1、负载平衡多个小的访问操作（块访问），以提高这种访问操作的吞吐量；2、并行执行大的访问操作，以减少大访问的响应时间。
大对象常常存储到一个特殊的文件（或文件的集合）中而不是与记录的其他（短）属性存储在一起。然后一个指向该对象的（逻辑）指针存储到包含该大对象的记录中。
顺序文件是为了高效处理按某个搜索码的顺序排序的记录而设计的。搜索码是任何的一个属性或者属性的集合。
多表聚簇文件组织是一种在每一块中存储两个或者更多个关系的相关记录的文件结构。
数据库系统的一个主要目的就是尽量减少磁盘和存储器之间传输的块数目。负责缓冲区空间分配的子系统称为缓冲区管理器。缓冲的是块而非数据。
索引与散列
数据库系统首先查找索引，找到相应记录所做的磁盘块，然后取出该磁盘块，得到所需的记录。
如果包含记录的文件按照某个搜索码指定的顺序排序，那么该搜索码碎影的索引称为聚集索引。
索引顺序文件是数据库系统中最古老的索引模式之一。为了允许按搜索码顺序快速检索记录，记录按顺序存储，而无序记录链接在一起。为了允许快速的随机访问，使用了索引结构。
可以使用的索引类型有两种：稠密索引和稀疏索引。稠密索引对每个搜索码值都有索引项，而稀疏索引只对某些搜索码值包含索引项。利用稠密索引通常可以比稀疏索引更快地定位一条记录。但是，稀疏索引所占空间较小，并且插入和删除时所需的维护开销也较小。（折中方案：为每个块建一个索引项的稀疏索引）
利用多级索引搜索记录与用二分法搜索记录相比需要的I/O操作要少得多。
如果搜索码的排序序列和关系的排序序列相匹配，则该搜索码上的索引称为聚集索引，其他索引称为非聚集缩影或辅助索引。辅助索引可以提高不以聚集索引的搜索码作为搜索码的查询的性能。但是，辅助索引增加了修改数据库的开销（辅助索引必须是稠密索引，对每个搜索码值都有一个索引项，而且对文件中的每条记录都有一个指针）。
候选码上的辅助索引看起来和稠密聚集索引没有太大区别，只不过索引中一系列的连续值执行的记录不是连续存放的。
索引顺序文件组织的主要缺点是随着文件的增大，性能会下降。为了克服这个缺点，可以使用B+树索引。
B+树索引采用平衡树的形式，即从树根到树叶的所有路径长度相等。B+树的高度与以关系中的记录数N为底的对数成正比，其中每个非叶子结点存储N个指针，N值通常约为50～100。因此，B+树比其他的平衡二叉树（比如AVL树）要矮喝多，故定位记录所需的磁盘访问次数也较少。
B+树上的查询是直接而且高效的。然而插入和删除要更复杂一些，但是仍然很有效。在B+树中，查询、插入和删除所需的操作数与以关系中的记录数N为底的对数成正比，其中每个非叶子结点存储N个指针。
可以用B+树去索引包含记录的文件，也可以用它组织文件中的记录。
B树索引和B+树索引类型。B树的主要优点在于它去除了搜索码值存储中的冗余（当搜索码值唯一的情况下，只允许搜索码值出现一次）。主要缺点在于整体的复杂性以及节点大小给定时减小了扇出（直接连接下级个数，节点大导致扇出小，深度增加）。在实际应用中，系统设计者几乎无一例外的倾向于使用B+树索引。
R树是B+树的扩展，用于处理在多个维度上的索引。
覆盖索引存储一些属性（但不是搜索码属性）的值以及指向记录的职责。存储附加的属性值对于辅助索引是非常有用的，仅仅使用索引就能够回答一些查询，甚至不需要找到实际的记录。
顺序文件组织需要一个索引结构来定位数据。相比之下，基于散列的文件组织允许我们通过计算所需记录搜索码值上的一个函数直接找出一个数据项的地址。由于设计时我们不能精确知道哪些搜索码值将存储在文件中，因此一个好的散列函数应该能均匀且随机地将搜索码值分散到各个桶中。
静态散列所用散列函数和桶地址集合是固定的。这样的散列函数不容易适应数据库随时间的显著增长。有几种允许修改散列函数的动态散列技术。可扩充散列是其中之一，它可以在数据库增长或缩减时通过分裂或合并桶来应付数据库大小的变化。
也可以用散列技术创建辅助索引：这样的索引称为散列索引。为使记法简便，假定散列文件组织中用户散列的搜索码上有一个隐式的散列索引。
可扩充散列可以通过桶的分裂或合并来适应数据库的大小的变化。由于重组每次仅作用于一个桶，因此所带来的性能开销较低，可以接受。可扩充散列的最主要优点是其性能不随文件的增长而降低，其空间开销是最小的。缺点在于查找涉及一个附加的间接层。
像B+树和散列索引这样的有序索引可以用作涉及单个属性且基于相等条件的选择操作。当一个选择条件中涉及多个属性时，可以取多个索引中检索到的记录标示符的交。
对于索引属性只有少数几个不同值的情况，位图索引提供了一种非常紧凑的表达方式。位图索引的交操作相当得快，使得它成为一种支持多属性上的查询的理想方式（属性有限变量下）。
查询处理
对于一个查询，系统首先要做的事就是将之翻译成系统内部的表示形式。对于关系数据库系统而言，内部形式通常是基于关系代数的。在产生查询的内部形式的过程中，语法分析器检查用户查询语句的语法，验证出现在查询语句中的关系名是数据库中的关系名等。如果查询语句是用视图表达的，语法分析器把所有对视图名的引用替换成计算该视图的关系代数表达式。
查询处理步骤：1、语法分析与翻译；2、优化；3、执行。
加了“如何执行”注释的关系代数运算称为计算原语。用于执行一个查询的原语操作序列称为查询执行计划或者查询计算计划。查询执行引擎接受一个查询执行计划，执行该计划并把结果返回给查询。
给定一个查询，通常有许多计算它的方法。将用户输入的查询语句转化成等价的、执行效率更高的查询语句，这是优化器的责任。优化器通常努力去尽可能降低查询计划总的资源消耗，而不是尽可能缩低响应时间。
辅助索引存储的是B+树文件组织中作为码值的属性值。通过这种辅助索引存取一条记录的代价将更大：首先必须搜索辅助索引以找到主索引的搜索码值，然后查找主索引来找到记录。
对于包含简单选择的查询语句，可以通过线性扫描或者利用索引来处理。通过计算简单选择结果的并和交，可以处理复杂选择操作。
数据排序：1、SQL查询会指明对结果进行排序；2、当输入的关系已排序时，关系运算中的一些运算（如连接运算）能够得到高效实现。
可以用外部归并排序算法对大内存的关系进行排序。
设计自然连接的查询语句可以有多种处理方法，如果处理取决于是否有索引可用以及关系的物理存储形式。
- 若连接的结果大小几乎和两个关系的笛卡尔积相当，可以采用嵌套循环连接策略较好。
- 若存在索引，则可用索引嵌套循环连接。
- 若关系已排序，则归并连接比较可取。在连接计算前对关系排序是有利的（为了能使用归并连接算法）。
- 散列连接算法把关系划分成多个部分，使每个部分都能被内存所容纳。划分过程是通过连接属性上的散列函数来进行的，这样相应的划分对可以独立地进行连接。
嵌套循环连接算法不要求有索引，并且不管连接的条件是什么，该算法均可以使用。块嵌套循环连接是以块的方式而不是以元组的方式处理关系，可以减少不少块读写次数。索引嵌套循环连接，可以在已有索引或者为了计算该连接而专门建立临时索引的情况下使用。归并连接算法（排序-归并-连接算法）可用于计算自然连接和等值连接。混合归并-连接算法把已排序关系与B+树辅助索引叶结点进行归并。散列连接算法可用于实现自然连接和等值连接，基本思想是把这两个关系的元组划分成连接属性值上具有相同散列值的元组集合。
去除重复、投影、集合操作（并、交、差）、聚集操作都可以用排序和散列实现。
外连接操作可以通过对连接算法的简单扩展来实现。
散列与排序在某种意义下是对偶的。因为任何能用散列实现的操作（如去除重复、投影、聚集、连接、外连接）也可用排序来实现，反之亦然；即任何能用排序来实现的操作也能用散列实现。
可以采用物化方法进行表达式的计算。系统计算每个子表达式的结果并将其存在磁盘上，然后用它进行父表达式的计算。
流水线方法在子表达式产生输出的同时就在父表达式的计算中使用其输出结果，帮助我们避免了将许多子查询的结果写到磁盘的操作。
由于去除重复的代价相对较大，因此SQL查询语言要求用户显示指明需要去除重复，若不指明则保留重复。
每次计算的结果都被物化到一个临时关系中已备后用。这个方法的缺点是需要构造临时关系，这些临时关系必须写到磁盘上（除非很小）。
减少临时文件数是通过将多个关系操作组合成一个操作的流水线来实现的，其中一个操作结果将传送到下一个操作。
查询优化
给定一个查询，一般有多种方法可以计算结果。系统负责将用户输入的查询转换成能够更有效执行的等价查询。为处理查询找出一个好的策略的过程称为查询优化。
复杂查询的执行涉及多次存取磁盘的操作。由于从磁盘中传输数据相对于主存速度和计算机系统的CPU速度要慢，因此进行一定量的处理以选择一个能够从最小化磁盘存取的方法是完全值得的。
查询执行计划的产生有三步：1、产生逻辑上与给定表达式等价的表达式；2、对所产生的表达式以不同方式作注释，产生不同的查询计划；3、估计每个执行计划的代价，选择估计代价最小的一个。
有很多等价规则供我们用于将一个表达式转化成等价表达式。我们使用这些规则系统地产生与所给查询等价的所有表达式。（如果两个关系表达式在每一个有效数据库实例中都会产生相同的元组集，则我们称它们是等价的。）
若一组等价规则中任意一条规则都不能由其他规则联合起来导出，称这组等价规则集为最小等价规则集。
优化器采用两种关键思想可以极大地减少空间和时间上的开销：
- 如果在子表达式e(i)上使用等价规则把表达式E1转化成E‘，则除了e(i)及其转换，E1与E‘有相同的子表达式。而且e(i)及其转换通常也有许多相同的子表达式。可以采用一些表达式表示技术，使两个表达式指向共享的子表达式，这样可以明显减少对空间的需求。
- 不必总是用等价规则产生所有可以产生的表达式。如果考虑估计的执行代价，优化器可以避免检查某些表达式。
每个关系代数表达式都表示某个特定的操作序列。选择查询处理策略的第一步就是找到一个关系代数表达式，使它与所给的表达式等价并且据估计有更小的执行代价。
基于代价的优化器从给定查询等价的所有查询执行计划空间中进行搜索，并选择估计代价最小的一个。
数据库系统为执行一个操作所选择的策略依赖于每个关系的大小和列值的分布情况。数据库系统可以为每个关系r存储统计信息，从而能够基于这些可靠信息选择适合的策略。这些统计信息包括：
- 关系r中的元组数
- 关系r中的一个记录（元组）的大小（按字节计数）
- 关系r中的某个特定属性中出现的不同取值的数目
许多数据库系统使用直方图来存储一个属性在每个区间上的取值个数。直方图通常采用取样来计算。
这些统计信息使得我们可以估计各种操作的结果集的大小和执行操作的代价。当处理一个查询的过程中有多个索引可用于辅助的时候，关系的统计信息特别有用，这些信息对查询处理策略的选择有很大影响。
物理等价规则允许将例如连接这样的逻辑操作转换成像散列连接或嵌套循环连接这样的物理操作。通过将这类规则添加到原来的等价规则中，程序可以产生所有可能的执行计划。
对每个表达式，我们可以用一些等价规则产生多个可选的执行计划，然后从中选择代价最小的执行计划。不少优化技术可以减少需要产生的可选表达式和执行计划的数量。
我们使用启发式方法来减少需要考虑的执行计划的数量，从而减少优化的代价。用于关系代数查询转换的启发式规则包括“尽早执行选择操作”、“尽早执行投影操作”、和“避免笛卡尔积操作”。
用一个具有连接的查询（可能使用临时关系）去替代嵌套查询的过程称为去除相关。
物化视图可以用来加速查询处理。当原关系发生修改时，需要用增量的视图维护来高效地更新物化视图。利用包含一个操作的输入的变化量的代数表达式，能够完成对该操作的变化量的计算。其他与物化视图相关的问题还包括如何借用物化视图进行查询优化和如何选择需要待物化的视图。查询优化器的工作应该包括知道何时可利用物化视图来提高查询处理速度。
一些优化技术，包括top-K优化、连接极小化、更新优化、多查询优化和参数化查询优化。
共享式扫描优化的工作方式如下：不是对于需要扫描一个关系的每一个查询，都从磁盘上重复地读取该关系，而是从磁盘上读取一次数据，然后流水线地传递给每一个查询。（一次读取，多次使用）
如果最优计划受查询中的常数值影响不大，则通过计划缓存重用计划是合理的。然而如果计划受常数的影响，则可以使用参数化查询优化作为替代。
事务管理
事务指的是构建单一逻辑工作单元的操作的集合。
事务
事务时一个程序执行单位，它访问且可能更新不同的数据项。理解事物这个概念对于理解与实现数据库中的数据更新是很关键的，只有这样才能保证并发执行与各种故障不会导致数据库处于不一致状态。
事务具有ACID特性：原子性、一致性、隔离性、持久性。
- 原子性保证事务的所有影响在数据库中要么全部反映出来，要么根本不反应；一个故障不能让数据库处于事务部分执行后的状态。
- 一致性保证若数据库一开始是一致的，则事务（单独）执行后数据库仍处于一致状态。
- 隔离性保证并发执行提高了事务吞吐量和系统利用率，也减少了事务等待时间。
- 持久性保证一旦一个事务提高后，它对数据库的改变不会丢失，即使系统可能出现故障。
事务的并发执行提高了事务吞吐量和系统利用率，也减少了事务等待时间。
计算机中不同存储介质包括异失性存储器、非易失性存储器和稳定性存储器。易失性存储器（例如RAM）中数据当计算机崩溃时丢失。非易失性存储器（如磁盘）中的数据在计算机崩溃时不会丢失，但是可能会由于磁盘崩溃而丢失。稳定性存储器中的数据永远不会丢失。
为了一个事务能够持久，它的修改应该写入稳定性存储器。为了一个事务是原子的，日志记录需要在对磁盘上的数据库做任何改变之前写入稳定性存储器。
必须支持在线访问的稳定性存储器与磁盘镜像或者其他形式的提供冗余数据存储的RAID接近。对于离线或归档的情况，稳定性存储器可以由存储在物理安全位置的数据的多个磁带备份所构成。
撤销已提交事务所造成的影响的唯一方法是执行一个补偿事务。
多个事务在数据库中并发执行时，数据的一致性可能不再维持。因此系统必须控制各并发事务之间的相互作用。
- 由于事务时保持一致性的单元，所以事务的串行执行能保持一致性。
- 调度捕获影响事务并发执行的关键操作，如read和write操作，而忽略事务执行的内部细节。
- 我们要求事务集的并发执行所产生的任何调度的执行效果等价于由这些事务按某种串行顺序执行的效果。
- 保证这个特性的系统称为保证可串行化。
- 存在几种不同的概念，从而引出了冲突可串行化与视图可串行化的概念。
事务并发执行所产生的调度的可串行化可以通过多种并发控制机制中的一种来加以保证。
给定一个调度，我们可以通过为该调度构造优先图几搜索是否无环来判定它是否冲突可串行化。然而，有更好的并发控制机制可用来保证可串行化。
调度必须时可恢复的，以确保：若事务a看到事务b的影响，当b中止时，a也要中止。（一个可恢复调度应该满足：对于每个事务T(i)和T(j)，如果T(j)读取了之前由T(i)所写的数据项，则T(i)先于T(j)提交。）
调度最好是无级联的，这样不会由于一个事务的中止引起其他事务的级联中止。无级联性是通过只允许事务读取已提交数据来保证的。（因单个事务故障导致一系列事务回滚的现象称为级联回滚。（无级联调度=可恢复调度）
- 可串行化：通常保证可串行化调度。
- 可重复读：只允许读取已提交的数据，而且在一个事务两次读取一个数据项期间，其他事务不得更新该数据项。
- 已提交读：只允许读取已提交数据，但不要求可重复读。
- 未提交读：允许读取未提交数据。（脏读）
所有隔离性级别都不允许脏写，即如果一个数据项已经被另一个尚未提交或者中止的事务写入，则不允许对该数据项执行写操作。
数据库的并发控制管理部件复杂处理并发控制机制。
快照隔离可以保证读数据的尝试永远无须等待，但带来的问题是提供了太多的隔离。如果事务多次运用之间数据库发生改变，那么即使是同一个事务，在多次不同运行中也可能会使用不同的数据项。
并发控制
当多个事务在数据库中并发执行时，数据的一致性可能不再维持。系统有必要控制各事务之间的相互作用，这是通过称为并发控制机制的多种机制中的一种来实现的。
为保证可串行性，我们可以使用多种并发控制机制。所以这些机制要么延迟一个操作，要么中止发出该操作的事务。最常用的机制是多种封锁协议、时间戳排序机制、有效性检查技术与多版本机制。
封锁协议是一组规则，这些规则阐明了事务何时对数据库中的数据项进行加速和解锁。
两阶段封锁协议仅在一个事务未曾释放任何数据项上的锁时才允许该书屋封锁新数据项。该协议保证可串行化，但不能避免死锁。在没有关于数据项访问方式信息的情况下，两阶段封锁协议对于保证可串行性既是必要的又是充分的。
两阶段封锁协议：要求每个事务分两个阶段提出加锁和解锁申请。
- 增长阶段：事务可以获得锁，但不能释放锁。
- 缩减阶段：事务可以释放锁，但不能获得新锁。
严格两阶段封锁协议要求事务持有的所有排他锁必须在事务结束时方可释放，其目的是保证结果调度的可恢复性和无级联性，强两阶段封锁协议要求事务持有的所有锁必须在事务结束时方可释放。
锁转换：提供一种将共享锁升级为排他锁，以及将排他锁降级为共享锁的机制。
锁管理器可以实现一个过程，从事务接受消息并反馈消息。数据结构：为目前已加锁的每个数据项维护一个链表，每一个请求为链表中一条记录，按请求到达的顺序排序。
- 当一个锁请求消息到达时，如果相应的数据项的链表存在，在该链表末尾增加一个记录；否则新建一个仅包含该请求记录的链表。
- 在当前没有加锁的数据项上总是授予第一次加锁请求，但当事务向已被加锁的数据项申请加锁时，只有当该请求与当前持有的锁相容，并且所有先前的请求都已授予锁的条件下，锁管理器才为该请求授予锁，否则该请求只好等待。
- 当锁管理器收到一个事务的解锁消息时，它将与该事务相对应的数据项列表中的记录删除，然后检查随后的记录，如果有，如前所述，就看该请求能否被授权，如果能，锁管理器授权该请求并处理气候记录，如果还有，类似地一个接一个处理。
- 如果一个事务中止，锁管理器删除该事务产生的正在等待加锁的所有请求。一旦数据库系统采取适当动作撤销该事务，该中止事务持有的所有锁将被释放。
基于图的封锁协议对访问数据项的顺序加以限制，从而不需要使用两阶段封锁还能够保证可串行性，而且又能够保证不会产生死锁。
许多种封锁协议都不能防止死锁。一种可以防止死锁的方法是使用数据项的一种顺序，并且按与该顺序一致的次序申请加锁。另一种防止死锁的方法是使用抢占的事务回滚。为控制抢占，我们给每个事务赋予一个唯一时间戳，这些时间戳用于决定事务是等待还是回滚。如果一个事务回滚，它在重启时保持原有时间戳。wound-wait机制是一个抢占机制。
如果没有预防死锁，系统必须用死锁检测与恢复机制来处理它们。为此，系统构造了一个等待图。当且仅当等待图包含环时，系统处于死锁状态。当一个检测算法判断死锁存在，系统必须从死锁种恢复。系统通过回滚一个或多个事务来解除死锁。
某些情况下把多个数据项聚为一组，将它们作为聚集数据项来处理，其效果可能更好，这就导致了粒度的多个级别。我们允许各种大小的数据项，并定义数据项的层次，其中小数据项嵌套于大数据项之中。这种层次结构可以图形化地表示为树。封锁按从根结点到叶结点的顺序进行；解锁则按从叶结点到根结点的讯息进行。该协议保证可串行性，但不能避免死锁。
时间戳排序机制通过事先对每对事务之间选择一个顺序来保证可串行性。系统中的每个事务对应一个唯一的固定时间戳。事务的时间戳决定了事务的可串行化顺序。这样，如果事务T(i)的时间戳小于事务T(j)的时间戳，则该机制保证产生的调度等价于事务T(i)出现在事务T(j)之前的一个串行调度。该机制通过回滚违反该次序的事务来保证这一点。
在大部分事务时只读的情形下，冲突频率很低，这种情况下有效性检查机制是一个适当的并发控制机制。系统中的每个事务对应一个唯一的固定时间戳。串行性次序是由事务的时间戳决定的。在该机制中，事务不会延迟。不过，事务要完成必须通过有效性检查。如果事务未通过有效性检查，则该事务回滚到初始状态。
有效性检查协议要求每个事务T(i)在其生命周期中按两个或三个阶段执行，这取决于该事务时一个只读事务还是一个更新事务。
- 读阶段：系统执行事务T(i)。各数据项值被读取并保存在事务T(i)的局部变量中。所有的write操作都是对局部临时变量进行的，并不对数据库进行真正的更新。
- 有效性检查阶段：对事务T(i)进行有效性测试。判断是否可以执行write操作而不违反可串行性。如果事务有效性测试失败，则系统终止这个事务。
- 写阶段：若事务T(i)已通过有效性检查，则保存T(i)任何写操作结果的临时局部变量值被复制到数据库中。只读事务忽略这个阶段。
多版本并发控制机制基于在每个事务写数据项时为该数据项创建一个新版本。读操作发出时，系统选择其中的一个版本进行读取。利用时间戳，并发控制机制保证按确保可串行性的方式选取要读取的版本。读操作总能成功。
- 在多版本时间戳排序中，写操作可能引起事务的回滚。
- 在多版本的两阶段封锁中，写操作可能导致封锁等待或者死锁。
快照隔离时一种基于有效性检验的多版本并发控制协议，与多版本两阶段封锁协议不同，它不需要将事务声明为只读或更新的。快照隔离不保证可串行化，但是许多数据库系统仍然支持它。
仅当要删除元组的事务在该元组上具有排他锁时，delete操作才能够进行。数据库中插入新元组的事务在该元组上被授予排他锁。
插入操作可能导致幻象现象，这是插入操作与查询操作发生逻辑冲突，尽管两个事务可能没有存取共同的元组。如果封锁仅加在事务访问元组上，这种冲突就检测不到。关系中用于查找元组的数据需要加锁，索引封锁技术要求对某些索引结点加锁来解决这个问题。所加的锁保证所有事务在实际的数据项上发生冲突，而不是在幻象上。索引封锁协议运作如下：
- 每个关系至少有一个索引。
- 只有首先在关系的一个或多个索引上找到元组后，事务T(i)才能访问关系上的这些元组。为了达到索引封锁协议的目的，全表扫描看作一个索引上所有叶结点的扫描。
- 进行查找（不管区间查找还是点查找）的事务T(i)必须在它要访问的所有索引叶结点上获得共享锁。
- 在没有更新关系r上的所有索引之前，事务T(i)不能插入、删除或更新关系r中的元组t(i)。该事务必须获得插入、删除或更新所影响的所有索引叶结点上的排他锁。对于插入和删除，受影响的叶结点时那些（插入后）包含或（删除前）包含元组搜索码值的叶结点。对于更新，受影响的叶结点时那些（修改前）包含搜索码旧值的叶结点，以及（修改后）包含搜索码新值的叶结点。
- 元组照常获得锁。
- 必须遵循两阶段封锁协议规则。
弱级别的一致性用于一些应用中，在这些应用中，查询结果的一致性不是至关重要的，而使用可串行性会使查询对事务的处理起反作用。二级一致性是这种弱级别的一致性之一，游标稳定性是二级一致性的一个特例，而且已被广泛应用。
游标稳定性保证：
- 正被迭代处理的元组被加上共享锁。
- 任何被更改的元组被加上排他锁，直至事务提交。
跨越用户交互的事务并发控制是一个有挑战性的任务。应用程序通常实现一种基于采用元组中存储的版本号来验证写操作的机制。这种机制提供了弱可串行化水平，而且可以实现在应用层，而无需修改数据库。
可以为特殊的数据结构开发特色的并发控制技术。通常，特色的技术用到B+树上，以允许较大的并发性。这些技术允许对B+树进行非可串行化访问，但它们保证B+树结构是正确的，并保证对数据库本身的存取是可串行化的。
恢复系统
数据库系统的一个重要组成部分就是恢复机制，它负责检测故障以及将数据库恢复至故障发生前的某一状态。恢复机制必须提供高可用性，必须将数据库崩溃后不能使用的时间缩减到最短。
计算机中的各种存储器类型有易失存储器、非易失存储器和稳定存储器。易失存储器（如RAM）中的数据在计算机发生故障时会丢失。非易失性存储器（如磁盘）中的数据在计算机发生故障时一般不丢失，只是偶尔由于某些故障如磁盘故障才会丢失。稳定存储器中的数据从不丢失。
必须能联机访问的稳定存储器用镜像磁盘或RAID的其他形式模拟，它提供冗余数据存储。脱机或归档稳定存储器可能是数据的多个磁带备份，并存放在物理安全的地方。
一旦故障发生，数据库系统的状态可能不再一致，即它不能反映数据库试图保存的显示世界的状态。为保持一致性，我们要求每个事务都必须是原子的。恢复机制的责任就是要保证原子性和持久性。
在基于日志的机制中，所有的更新都记入日志，并存放在稳定存储器中。当事务的最后一个日志记录，即该事务的commit的日志记录。输出到稳定存储器时，就认为这个事务已提交。
日志记录包括所有更新过的数据项项的旧值和新值。当系统崩溃后需要对更新进行重做时，就使用新值。如果在正常操作中事务中止，回滚事务所做的更新时需要用到旧值；在事务提交之前发生系统崩溃的情况下，回滚事务所做的更新也需要用到旧值。
在演出修改机制下，事务执行时所有write操作都要延迟到事务提交时才执行，那时，系统在执行延迟写中会用到日志中与该事务有关的信息。在延迟修改机制中，日志记录不需要包含已更新的数据项的旧值。
为减少搜索日志和重做事务的开销，我们可以使用检查点技术。（a）在执行检查点操作的过程中不允许执行任何更新，（b）在执行检查点的过程中将所有更新过的缓冲块都输出到磁盘中。检查点执行过程如下：1、将当前位于主存的所有日志记录输出到稳定存储器；2、将所有修改的缓冲块输出到磁盘；3、将一个日志记录
当前恢复算法基于重复历史的概念，在恢复的重做简单重演（自最后一个已完成的检查点以来）正常操作中所做的所有动作。重复历史的做法将系统状态恢复到系统崩溃之前的最后一个日志记录输出到稳定存储器时的系统状态。然后从这个状态开始执行一个撤销阶段，反向处理未完成事务的日志记录。
不完全事务的撤销写出特殊的redo-only日志记录和一个abort日志记录。然后就认为该事务已完成，不必再对它进行撤销。
在事务处理所基于的存储模型中，主存储器中有一个日志缓冲区，一个数据库缓冲区和一个系统缓冲区。系统缓冲区中有系统目标码页面和事务的局部工作区域。
恢复机制的高效实现需要尽可能减少向数据库和稳定存储器写出的数目。日志记录在开始时可以保存在易失性的日志缓冲区中，但是当下述情况之一发生时必须写到稳定性存储器中：
- 在<T(i), commit>日志记录可以输出到稳定存储器之前，在事务T(i)相关的所有日志记录必须已经输出到稳定存储器中。
- 在主存中的一个数据库输出到（非易失性存储器中的）数据库之前，与该块中的数据相关的所有日志记录必须已经输出到稳定存储器中。
当前的恢复技术支持高并发性封锁技术，例如用户B+树并发控制的封锁记录。这些技术允许提前释放通过插入或删除这样的操作获得的低级别的锁，低级别的锁允许别的事务其他的这些操作可以执行。低级别的锁被释放之后，不能进行物理undo，而需要进行逻辑undo，例如，用删除来对一个插入操作undo。事务保持高级别的锁以确保并发的事务不会执行这样的动作，它可能导致一个操作的逻辑undo是不可能的。
为从造成非易失性存储器中数据丢失的故障中恢复，我们必须周期性地将整个数据库的内容转储到稳定存储器中–例如每天一次。如果发生了导致物理数据库块丢失的故障，我们使用最近一次转储将数据库恢复至前面的某个一致状态。一旦完成该恢复，我们再用日志将数据库系统恢复至最当前的一致状态。
ARIES恢复机制支持一些提供更大并发性，削减日志开销和最小化恢复时间的特性。它也是基于重复历史的，并允许逻辑undo操作。该机制连续不断地清洗页，从而不需要检查点时清洗所有页。它使用日志顺序号（LSN）来实现各种优化从而减少恢复所花的时间。从系统崩溃中恢复的过程经历三个阶段：1、分析阶段：决定哪些事务要撤销，哪些页在崩溃时时脏的，以及重做阶段应从哪个LSN开始；2、redo阶段：从分析阶段决定的位置开始，执行重做，重复历史，将数据库恢复到发生崩溃前的状态；3、undo阶段：回滚在发生崩溃时那些不完全的事务。
远程备份系统提供了很高程度的可用性，允许事务处理即使在主站点遭受火灾、洪水或地震的破坏时也能继续。主站点上的数据和日志记录连续不断地备份到远程备份站点。如果主站点发生故障，远程备份站点就执行一定的恢复动作，然后接管事务处理。
系统体系结构
数据库系统体系结构
集中式数据库系统完全运行在单台计算机上。随着个人计算机和局域网的发展，数据库前端功能不断移向客户机，而后端功能由服务器系统提供。客户-服务器接口协议推动了客户-服务器数据库系统的发展。
服务器可以是事务服务器，也可以是数据服务器。尽管在提供数据库服务方面，事务服务器的使用大大超过数据服务器的使用。
- 事务服务器有多个进程，可能运行在多个处理器上。所以这些进程要访问公共数据，比如数据库缓冲区，系统将这些数据存放在共享内存中。除了处理查询的进程，还有执行诸如锁和日志管理以及检查点等任务的系统进程。
- 数据服务器系统提供给用户的是为加工的数据。这样的系统通过把数据和锁高速缓存在客户端，来努力使客户端和服务器之间的通信最小化。并行数据库系统使用类似的优化。
并行数据库系统由通过高数互联网连接在一起的多台处理器和多张硬盘构成。加速比衡量通过增加并行性可以得到的对单个事务的处理数据的增长。扩展比衡量通过增加并行性可以的带的处理大量事务的能力。干扰、偏斜和启动代价是得到理想的加速比和扩展比的障碍。
并行数据库系统结构包括共享内存、共享硬盘、无共享以及层次的体系结构。这些体系结构在可扩展性以及通信速度方面各有千秋。
- 共享内存的优点在于处理器之间的通信效率极高，存放在共享内存中的数据可以被任何处理器访问，而不需要由软件来移动。共享内存机器的缺点是这种体系结构的规模不能超过32个或64个处理器。因为总线或互联网络会变成瓶颈（因为它是所有处理器共享的）。
- 共享硬盘体系结构有两个优点：1、由于每个处理器都有自己的主存储器，因此存储器总线不再是瓶颈了；2、这种体系结构给出了一个经济的方法来提供一定程度的容错性（如果一个处理器或者它的主存储器发生故障，其他处理器可以代替它的工作，这是因为数据库驻留在磁盘上，而磁盘是所有处理器都可以访问的）。虽然存储器总线不再是瓶颈，但与磁盘子系统互连现在成为了瓶颈。
- 无共享提供的主要缺点是通信的代价和非本地磁盘访问的代价，这些代价比共享内存或共享硬盘体系结构中的代价要高，因为数据传送涉及两端的软件交互。
- 层次的体系结构综合了共享内存、共享硬盘和无共享体系结构的特点。
分布式数据库系统是部分独立的一组数据库系统，它们共享一个公共模式（理想情况下），并且协调地处理访问非本地数据库的事务。系统之间通过通信网络来相互通信。
局域网连接分布在小的地理范围内的结点，比如连接单个建筑或几个相邻建筑。广域网连接分布在大的地理范围内的结点。现在Internet是使用最广泛的广域网。
存储区域网是一种特殊形式的局域网，是为大型存储设备和多台计算机之间提供快速互连而设计的。
并行数据库
在I/O并行中，把关系划分到多张可用的磁盘中，从而使检索速度更快。三种常用的划分技术使轮转法划分，散列划分和范围划分。（一般而言，更倾向于使用散列划分和范围划分，而不是轮转法划分）
- 轮转法：适合于希望对每个查询顺序地读取整个关系的应用。
- 散列划分：适合于机遇划分属性的点查询。
- 范围划分：适合于在划分属性上的点查询和范围查询。
偏斜是一个主要的问题，特别是当并行度增高时。平衡的划分向量、使用直方图以及虚处理器划分是用于减少偏斜的技术。属性值偏斜指的是某些值出现在许多元组的划分属性中。划分偏斜指的是，即使不存在属性值偏斜，划分也可能会出现负载不均衡。
- 通过为每个关系的每个属性创建和存储该属性值的频率表或直方图，可以降低由于构建平衡的范围划分向量而产生的I/O开销。
- 使用虚处理器，特别是针对范围划分带来的偏斜，可以使偏斜的影响达到最小。核心思想是：即使由于偏斜使得在一个范围内有比其他范围更多的元组，这些元组也将划分到多个虚处理器的范围上。
在查询间并行中，并发地运行不同的查询以提高吞吐量。共享磁盘系统中协议保证，当事务对页面设置共享锁或排查锁时，能够得到该页面的正确版本：1、事务对一个页面进行任何读或写访问之前，先用相应的共享或排他模式封锁该页面。一旦事务获得了页面的共享锁或排他锁后，它立刻从共享磁盘中读取该页面的最新版本；2、在事务释放一个页面的排他锁之前，它将该页面刷新到共享磁盘中，然后释放锁。
查询内并行指的是单个查询在多个处理器和磁盘上并行执行，试图减少运行查询的代价。两类查询内并行：1、操作内并行，通过并行地执行每一个运算来加快一个查询的处理速度；2、操作间并行，通过并行地执行一个查询表达式中的多个不同的运算，来加快一个查询的处理速度。
采用操作内并行来并行地执行关系运算，例如排序和连接。因为关系运算是面向集合的，所以操作内并行对关系运算是很自然的。
对于像连接这样的二元运算，有两种基本的并行化的方法（这两种并行技术都可以与任何一种连接技术结合使用）：
- 在基于划分的并行中，两个关系分成几个部分，而且r(i)中的元组仅与s(i)中的元组进行连接。基于划分的并行仅适用于自然连接和等值连接。
- 在分片和复制中，两个关系都被划分，并且每个划分都被复制。在非对称的分片和复制中，一个关系被复制，而另一个关系被划分。与机遇划分的并行不同，分片和复制以及非对称的分片和复制对于任何连接条件都是用。
在独立的并行中，互不依赖的多个不同的操作按并行方式执行。
在流水线并行中，处理器在计算一个操作结果的同时将结果发送给另一个操作，无须等待整个操作的完成。
两个常用启发式方法来减少需要考虑的并行执行计划的数目：
- 仅考虑那些利用所有的处理器，对每个运算都并行化，并且不采用任何流水线的执行计划。
- 选择最搞笑的串行执行计划，然后将该执行计划中的运算并行化。
分布式数据库
分布式数据库系统由站点的集合构成，每个站点维护一个本地数据库系统。各个站点能够处理局部事务：这些事务访问的数据仅位于该单个站点上。此外，站点可以参与到全局事务的执行中：这些全局事务访问多个站点上的数据。全局事务的执行需要在站点之间进行通信。
分布式数据库可能是同构的，其中所有站点拥有共同的模式和数据库系统代码，或者是异构的，其中模式和系统代码可能不同。
关于在分布式数据库中存储关系涉及几个问题，包括复制和分片。系统应尽量减小用户需要了解关系如何存储的程度。
- 水平分片：通过将r的每个元组分给一个或多个分片来划分关系
- 垂直分片：通过对关系r的模式R进行分解来划分关系
数据透明性：
- 分片透明性：用户不要求知道关系是如何分片的
- 复制透明性：在用户看来，每个数据对象逻辑上都是唯一的。分布式系统可能为了提高系统性能或者数据可用性而复制对象，用户不必关系什么数据对象被复制了，也不必关系副本存放在何处。
- 位置透明性：用户无须知道数据的物理位置。只要用户事务提供数据标示符，分布式数据库系统应能够找到任何数据。
局部事务是那些只在一个局部数据库中访问和更新数据的事务；全局事务是那些多个局部数据库中访问和更新数据的事务。
每个站点都有其自身的局部事务管理器，其功能是保证在该站点上执行的那些事务的ACID特性。各个事务管理器相互协作以执行全局事务。
- 事务管理器：管理那些访问存储在一个局部站点中的数据的事务（或子事务）的执行。注意每个这样的事务既可以是局部事务也可以是全局事务的一部分。
- 维护一个用于恢复目的的日志
- 参与到一个合适的并发控制方案，以协调在该站点上执行的事务的并发执行
- 事务协调器：协调在该站点上发起的各个事务的执行。
- 启动事务的执行
- 将事务分成一些子事务，并将这些子事务分派给合适的站点去执行
- 协调事务的中止，这可能导致事务在所有站点上都提交或者所有站点上都中止
分布式系统可能遭受与集中式系统相同类型的故障。但是，分布式环境中还有另外一些需要处理的故障，包括站点故障、链路故障、消息丢失以及网络划分。在分布式故障恢复模式的设计中需要考虑每个这样的问题。
为了保证原子性，执行事务T的所有站点必须在执行的最终结果上取得一致。T要么在所有站点上提交，要么在所有站点上中止。为了保证这一特性，T的事务协调器必须执行一种提交协议。使用最广泛的提交协议是两阶段提交协议。
两阶段提交协议可能导致阻塞，在这种情况下，事务的命运必须等到故障站点（协调器）恢复后才能确定。为了减少阻塞的可能性，可以使用三阶段提交协议。
持久消息为分布式事务处理提供了一种可选模式。该模式将单个事务拆分成在不同数据库执行的多个部分。持久消息（无论是否发生故障。都保证正好只传送一次）被传送到需要采取动作的远程站点。虽然需要持久消息避免阻塞问题，但是应用程序开发者必须编写代码来处理各种类型的故障。
在集中式系统中使用各种并发控制方案修改后可用于分布式环境。
- 就封锁协议而言，须做的唯一改变是锁管理器的实现方式。可以采用一个或多个中央协调器。如果拆用分布式锁管理器，复制数据就必须特殊对待。
- 处理已复制数据的协议包括主副本协议、多数协议、有偏协议和法定人数同意协议。它们在开销方面和发生故障时工作的能力方面各有不同的取舍权衡。
- 就时间戳和有效性演奏方案而言，所需的唯一修改是开发一种产生全局唯一性时间戳的机制。
- 许多数据库系统支持延迟复制，其中更新被传播到执行更新的事务的范围之外的副本。这样的工具必须小心使用，因为他们可能导致不可串行化的执行。
分布式锁管理器环境中的死锁检测需要多个站点之间的合作，因为甚至在没有局部死锁的情况下也可能有全局死锁。
为了提高可用性，分布式诗句哭必须检测故障，重构系统以使计算机能够继续进行，并在处理器或链路修复之后能够恢复。由于要在网络划分和站点股掌之间进行区分是很困难的，因此这个任务就变得非常复杂。通过使用版本号，可以对多数协议进行扩展使其即使存在故障的情况下仍允许进行事务处理。虽然该协议代价昂贵，但它无论在何种类型的故障下都能工作。可以使用较小代价的协议来处理站点故障，但是它们艰涩不会发生网络划分。
一些分布式算法需要使用协调器。为了提供高可用性，系统必须维护一个准备好的在协调器故障时能继续其支者的备份副本。另一种方法是在协调器发生故障后选出新的协调器。确定哪个站点应该作为协调器的算法称为选举算法。
分布式数据库上的查询可能需要访问多个站点。可以使用集中优化技术来识别需要访问的最佳站点集。查询可以依据关系的分片来自动重写没然后可以在每个分片的副本之间做出选择。可以应用半连接技术减少跨不同站点的关系（或相应的分片或副本）连接中所涉及的数据传输。
异构分布式数据库允许站点有它们自己的模式和数据库系统代码。多数数据库系统提供了一种环境，在其中新的数据库应用可以访问位于多重易购软硬件环境的各个先前存在数据库中的数据。局部数据库系统可以采用不同的逻辑模型以及数据定义和数据操纵语言，并且可以在它们的并发控制和事务管理机制上存在差别。多数据库系统虚拟了逻辑上的数据库集成，不需要物理上的数据库集成。
为了响应超大规模Web应用对数据存储的需求，近年来在云上构建了大量数据存储系统。这些数据存储系统允许扩展到地里上分布的数千个结点上，而且具有高可用性。然而，它们并不支持通常的ACID特性，而且在划分时以副本一致性为代价来获得可用性。
目录系统可视为一何总特殊形式的数据库，其中信息按照一种分层的方式组织，类似于文件系统中文件的组织方式。目录通过标准化目录访问协议（例如LDAP）来访问。目录可以分布到多个站点上来提供各个站点的自治。目录可以包含对其他目录的引用，这有助于建立集成视图，借此查询被发送给单个目录，并且在所有相关的目录上透明地执行。
数据仓库、数据挖掘和信息检索
数据仓库与数据挖掘
数据仓库是从多个数据源种进行数据采集，并以一种共同的、统一的数据库模式进行存储的数据仓储。存放在数据仓库中的数据将用于各种复杂聚集和统计分析。
决策支持系统分析由事务处理系统收集的在线数据，以帮助人们做出商业决策。由于现在大多数组织结构都进行了广泛的计算机化，因此有非常大量的信息可用于决策支持。决策支持系统有不同的形式，包括OLAP系统和数据挖掘系统。
数据仓库有助于收集和归档重要的操作数据。数据仓库用于基于历史数据的决策支持和分析，例如趋势预测。对来自输入数据源的数据进行清理通常是数据仓库中的一项重要任务。数据仓库的模式一般是多维的，包括一个或一些非常大的事实表以及几个小得多的维表。
在很多数据仓库应用程序中，面向列的存储系统能提供良好的性能。
数据挖掘是一个能半自动地分析大型数据库以找出有用的模式的过程。数据挖掘的引用有许多，比如基于以往示例的数值预测，购买行为关联的发现，以及人和电影的自动聚类。
分类处理的事：基于训练用例的属性和训练用例实际所属的类，通过利用测试用例的属性来预测测试用例所属类。分类器类型有很多种：
- 决策树分类器。这种分类器通过基于训练用例所构造的一棵树来执行分裂，该树的叶节点具有类别标签。对每个测试用例遍历这棵树以找到一个叶节点，该叶节点所属的类即是预测的类。有几种技术可用于构造决策树，其中大部分是基于贪心的启发式方法。
- 贝叶斯分类器放入构造比决策树分类器更简单，并且在属性值缺失或为空的情况下工作得更好。
- 支持向量机是另一种广泛应用的分类技术。
关联规则识别经常同时出现的项，比如同一位孤苦可能购买的一些商品。相互关联找出与期望关联等级的偏离。
其他类型的数据挖掘包括聚类、文本挖掘和数据可视化。
信息检索
信息检索系统用于存储和查询如文档那样的文本数据。与数据库系统相比，它们使用更将蛋的数据模型，但能够在首先的模型里提供更强大的查询能力。
查询试图通过指定关键字集合来定位用户感兴趣的文档。用户心里所想的查询往往不能精确的表述，因此，信息检索系统基于潜在的相关性对答案的排名。
相关性排名利用多种类型的信息。1、术语频率：每个术语对美分文档的重要性；2、逆文档频率；3、流行度排名。
文档相似性用于检索与一个示例文档相似的文档。余弦度量值用于定义相似度，它基于向量空间模型。
PageRank和链接中心/权威页排名是基于指向页面的链接对页面威望度赋值的两种方法。PageRank度量可以用随机游走模型来直观地理解。锚文本信息也可以用来计算单个关键字意义上的流行度。信息检索系统需要整合多种因素（包括TF-IDF和PageRank）来获得对页面的全局评分。
搜索引擎作弊试图使一个页面得到高的（但不是应得的）排名。
同义词和多义词使信息检索的任务复杂化。基于概念的查询旨在找到含有指定概念的文档，而与指定该概念所使用的确切的词（以及语言）无关。本体利用诸如is-a或者part-of这样的关系将概念联系起来。
倒排索引用来对关键字查询做出应答。
查准率和查全率是信息检索系统有效性的两种度量。
Web搜索引擎使用爬虫搜索Web找到网页，然后分析它们以计算其威望度度量，并为它们建立索引。
目录结构和分类用来将文档和其他相似的文档归类到一起。
特种数据库
基于对象的数据库
XML
高级主题
高级应用开发
调整数据库系统参数和更高级别的数据库设计（如模式、索引和事务）对于实现高性能至关重要。查询可以进行调整以提高集合面向性，而批量加载功能可以大大加快数据导入到数据库中的速度。
- 调整的最好方法就是确定瓶颈所在，然后消除瓶颈。数据库系统通常有多种可调参数，如缓冲区大小、内存大小和磁盘数量。可以选择适当的缩影和物化试图集合，以使总体代价达到最小。可以调整事务使锁竞争达到最小。快照隔离和支持早起锁释放的序号编号功能是减少读写和写写竞争的有用工具。
性能基准程序在对数据库系统进行比较方面扮演了重要的角色，尤其在数据库系统变得越来越与标准兼容时。TPC基准程序集使用广泛，不同的TPC基准程序可以用于不同的工作负载下的数据库系统性能比较。
应用程序在开发时和部署前需要进行大量大测试。测试用来捕获错误的，以及确保到达性能目标。
遗产系统是基于老一代技术（如非关系数据库或甚至直接基于文件系统）的系统。当运行关键人物系统时，遗产系统与新一代系统之间的连接通常是很重要的。从遗产系统到新一代系统的移植必须非常小心以避免破坏，这种移植是非常昂贵的。
由于数据库系统的复杂性和互操作的需要，标准对数据库系统来说很重要。SQL有其正式标准。事实标准（如ODBC和JDBC）和被行业组织所采纳的标准（如CORBA），在客户-服务器数据库系统的发展中发挥了重要作用。
时空数据和移动性
存储关于真实世界的时间经历状态的信息的数据库叫做时态数据库。
时态关系中的事实与当它们有效时的时间相关联，而时间可以用时段的并来表示。时态查询语言简化了时间建模以及与时间相关的查询。
设计数据主要以矢量数据的形式存储；地理数据包含矢量数据和光栅数据的结合。空间完整性约束对于设计数据库十分重要。光栅数据由二维或更高维的位图或像素图组成。矢量数据由基本集合对象构成，如点、线段、折线、三角形和其他二维多边形，以及圆柱体、球体、立方体和其他三维多面体。
矢量数据库可以编码成第一范式，或者用非第一范式结构来存储，如列表。专用索引结构对于访问空间数据和处理空间查询尤为重要。
R树是B树的多维扩展；它和它的变体（如R+树和R*树）在空间数据库中得到了广泛的应用。将空间以某种固定方式进行划分和索引结构（如四叉树）有助于处理空间连接查询。