数据库系统概念学习笔记 学习目标： 学习内容：

学习目标：

由浅入深系统性的学习数据库基本概念，以及前沿数据库技术

学习内容：

一，基本概念

1.1 数据库管理系统（DataBase-Management System DBMS）是有互相关联的数据集合和一组用以访问这些数据的程序组成。这个数据集合通常称作数据库。

1.2 数据模型

        数据库结构的基础是数据模型，数据模型是描述数据，数据联系，数据语义及一致性约束概念工具的集合，数据模型提供了一种描述物理层，逻辑层，视图层数据库设计的方法。

数据模型可划分为四类：

        1.关系模型（relational model）：关系型模式用表的集合来描述数据与数据之间的关系，每个表有多列，每列有唯一的列名。每个表包含某种特定类型的记录，每个记录类型定义了固定数目的字段（或属性）

        2.实体-联系模型（entity-relational model）：实体-联系模型（E-R）基于对现实世界的这样一种认识：现实世界是由一组称作实体的对象以及实体对象之间的联系组成。实体是现实世界可区别于其他对象的一种“物体”或者“事物”。

        3.基于对象的数据模型：面对对象的数据模型可以看成是E-R模型增加了封装，方法和对象标识等概念的拓展

        4.半结构化的数据模型：半结构化的数据模型允许相同类型的数据项拥有不同的属性集的数据定义

二，关系查询处理和查询优化

基本概念

• 关系型数据库查询处理可以分为四个阶段：查询分析、查询检查、查询优化和查询执行。

• 查询优化按照其优化层次分为代数优化和物理优化。其总目标是选择有效的策略，求得给定关系表达式的值，使得查询代价最小（实际上是较小）。代数优化通过改变代数表达式的操作顺序和组合，使得查询更加高效；物理优化是指存取路径和底层操作算法的选择，一般有基于规则（rule based）的、基于代价（cost based）的和基于语义（semantic based）**的。

• 选择操作的主要实现算法有：全表扫描方法和索引（散列）扫描方法；连接操作的主要实现算法有：嵌套循环方法、排序-合并方法、索引连接方法和Hash Join 方法。

代数优化

代数优化的启发式规则

• 典型的代数优化启发式规则有：

  1. 选择运算应尽可能先做。

  2. 把投影运算和选择运算同时进行。

  3. 把投影运算和其前后的双目运算结合起来。

  4. 把某些选择和其前面的笛卡尔积结合起来成为一个连接运算。

  5. 找出公共子表达式。

物理优化

物理优化的启发式规则

• 选择操作的启发式规则：

  1. 对于小关系，使用全表顺序扫描，即使选择列上有索引。

  2. 对于选择条件是主键=值的查询，选择主码索引。

  3. 对于选择条件是非主键=值的查询、非等值查询、范围查询，估计查询结果的规模，比例较小（<10%）使用索引扫描，否则全表扫描。

  4. 对于使用AND连接的合取选择查询，优先索引扫描，否则使用全表扫描。

  5. 对于使用OR连接的析取选择查询，一般使用全表顺序扫描。

• 连接操作的启发式规则：

  1. 若两表均已按照连接属性排序，选用排序-合并方法。

  2. 若某一表在连接属性上有索引，选用索引连接方法。

  3. 若上述两条规则不适用，且其中一表较小，选用Hash Join 方法。

  4. 最后选用嵌套循环方法，选择占用块数较少的表作为外表。

三，事务

• 事务：用户定义的一个数据库操作序列，这些操作要么全做、要么全不做，是一个不可分割的工作单位。在SQL语言中，定义事务的语言有三条BEGIN TRANSACTION、COMMIT和ROLLBACK，其使用方式如下：

  BEGIN TRANSACTION
      DO SOMETHING;
      IF @@error <> 0  --发生错误
         BEGIN
           ROLLBACK;
         END
      ELSE
         BEGIN
           COMMIT;
         END

• 事务具有四个特性：原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）和持续性（Durability），简称ACID特性（ACID properties）。

• 事务的ACID特性遭到破坏的原因包括事务运行中强行停止和交叉并发。

• 数据库系统可能出现的故障大概分为四类：事务内部故障、系统故障、介质故障和计算机病毒。其中，系统故障又称为软故障，介质故障又称为硬故障。

• 数据恢复机制的基本原理是冗余，涉及到的两个关键问题是如何建立冗余数据和如何通过冗余数据实施数据库恢复。

• 事务故障的恢复策略是利用日志文件进行事务撤销（UNDO）操作，具体流程为：

  1. 反向扫描日志文件，查找该事务的更新操作。

  2. 执行该事务更新操作的逆操作。

  3. 继续反向扫描日志文件，查找该事务的其他更新操作并执行逆操作。

  4. 反复执行上述操作，直到读到此事务的开始标记，完成事务故障的恢复。

• 系统故障的恢复策略如下：

  1. 正向扫描日志文件，找出故障发生前已执行完成的事务，加入REDO队列；同时找出故障发生时为执行完成的事务，加入UNDO队列。

  2. 对UNDO队列中所有事务进行撤销处理。

  3. 对REDO队列中所有事物进行重做处理。

• 介质故障的恢复策略如下：

  1. 装入最新的数据库后备副本，使数据库恢复到最近一次转储时的一致性状态。

  2. 装入相应的日志文件副本，重做已完成的事务。

  • 建立冗余数据的常用技术是数据转储和登录日志文件。

  • 数据转储即DBA定期地将整个数据库复制到磁带或另一个磁盘上保存起来的过程，这些备用数据称为后备副本（backup）或后援副本。按照转储时数据库工作状态可以将数据转储分为静态转储和动态转储；按照转储方式可将数据转储分为海量转储和增量转储。

  • 日志文件是用来记录事务对数据库的更新操作的文件。日志文件可以用来实施事务故障和系统故障的恢复，也可以结合后备副本进行介质故障的恢复。

  • 为保证日志文件可恢复，登记日志文件应遵循两条原则：

    1. 等级次序严格按照并发事务执行的时间次序。

    2. 必须先写日志文件，后写数据库。

事务管理
事务（transaction）：是数据库应用中完成单一逻辑功能的操作集合。每一个事务是一个既具有原子性，也具有一致性的单元。

ACID： 数据库管理系统（DBMS）在寫入或更新資料的過程中，為保證事务是正確可靠的，所必須具備的四个特性：

原子性（atomicity）：一個事务（transaction）中的所有操作，或者全部完成，或者全部不完成，不会结束在中间某个环节。事务在执行过程中发生错误，会被回滚（Rollback）到事务开始前的状态，就像这个事务从来没有执行过一样。即，事务不可分割、不可约简。
一致性（consistency）：在事务开始之前和事务结束以后，数据库的完整性没有被破坏。这表示写入的资料必须完全符合所有的预设约束、触发器、级联回滚等。
隔离性（Isolation）：数据库允许多个并发事务同时对其数据进行读写和修改的能力，隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致。事务隔离分为不同级别，包括未提交读（Read uncommitted）、提交读（read committed）、可重复读（repeatable read）和串行化（Serializable）。
持久性（durability）：事务处理结束后，对数据的修改就是永久的，即便系统故障也不会丢失。
 

事务管理器包括的组件有：

恢复管理器（recovery manager）需要保持数据库的原子性+持久性：
没有故障发生==》所有事务均成功完成 ===》保持原子性很容易

有故障发生==》事务不总能成功执行 ===》为了保证原子性，失败的事务必须对数据库状态不产生任何影响===》数据库需要恢复到该失败事务开始执行前的状态===》因此，需要进行故障恢复（failure recovery），即：检查系统故障并将数据库恢复到故障发生以前的状态。

并发管理控制器（concurrency-control manager）：
控制并发事物间的相互影响，保证数据库的一致性

四，索引与散列
1.1 基本概念
数据库系统中的文件索引的作用是加速查询。

两种基本类型的索引：

顺序索引：基于值的顺序排序
散列索引：基于将值平均分道若干散列桶中。一个值所属的散列桶是由散列函数（hash function）决定的。
多索引的评价包括：

访问类型（access type）：能有效支持的访问类型，可以包括：找到具有特定属性值的记录，以及找到属性值落在某个特定范围内的记录。
访问时间（access time）：在查询中使用该技术找到一个特定数据项或数据项集所需的时间。
插入时间（insertion time）：插入一个新数据项的时间。包括：插入新数据项到正确位置所需的时间+更新索引结构的时间。
删除时间（deletion time）：删除一个数据项所需的时间。包括：找到待删除项所需的时间+更新索引结构的时间。
空间开销（space overhead）：索引结构所占用的额外的存储空间。倘若索引结构占用的空间适合，通常可以牺牲一定的空间的额代价换时间。
搜索码（search key）：用于在文件中查找记录的属性或属性集。一个文件可以有多个搜索码。

1.2 顺序索引
一个文件可以有多个索引，分别基于不同的搜索码。

聚集索引(clustering index)/主索引(primary index)：如果包含记录的文件是按照某个搜索码指定的顺序排序，那么该搜索码对应的索引称为聚集索引/主索引。

非聚集索引(nonclustering index)/辅助索引(secondary index)：搜索码定义的顺序与文件中记录的物理顺序不同的索引，称为非聚集索引/辅助索引。

在搜索码上有聚集索引的文件 称作 索引顺序文件（index-sequential file）。

顺序索引的缺点：随着文件的增大，索引查找西能和数据顺序扫描性能都会下降。

1.3， 稠密索引和稀疏索引
索引项(index entry)或索引记录(index record): 由 一个搜索码值 + 指向具有该搜索码值的一条或多条记录的指针 构成。

指向记录的指针，包括：磁盘块的标识+表示磁盘块内记录的块内偏移量。

顺序索引分为两类：

稠密索引（dense index）：稠密索引中，文件中的每个搜索码值都有一个索引项。
稠密聚集索引：索引项包括搜索码值 + 指向具有该搜索码值的第一条记录的指针，具有相同搜索码值的记录 顺序地存储在第一条数据记录之后。记录根据搜索码值进行排序。
稠密非聚集索引：索引项必须存储指向所有具有相同搜索码值的记录。
稀疏索引（sparse index）：稀疏索引中，只为搜索码的某些值建立索引项。只有当关系按照搜索码顺序存储时才能使用稀疏索引，换句话说，只有聚集索引才能使用稀疏索引。索引项由 搜索码值+指向具有该搜索值的第一条记录的指针。
为了定位一条记录，先找到最大搜索码值小于所查找记录的搜索码值的索引指针，然后从该指针指向的记录开始顺序查找，直到找到记录为止。
 

稠密索引 VS 非稠密索引

稠密索引定位记录更快，但是非稠密索引占据的空间较小，并且插入和删除时维护索引的开销也较小

1.4 多级索引
如果索引项小到可以放到主存中，搜索一个索引项的时间就会很短。

如果索引项过大而不能放到主存中，那么当需要时就必须从磁盘中读出索引块，于是会导致搜索一个索引项需要多次读取磁盘块。

顺序稠密索引 VS 多级顺序索引

顺序稠密索引：
可以利用二分法来定位索引项，复杂度为log2(b)，其中b为索引占据的磁盘块的数量。
例如：占用10，000个块的索引，需要14次读块操作。假设读取一个块10毫秒，那么搜索将耗时140毫秒。
注意：如果使用了溢出块，则不能使用二分搜索。
多级(multilevel)顺序索引：
二级索引：除了构建稠密索引作为内层索引外，还在外层构建了稀疏索引。通常外层索引能够存储在主存中
定位一条记录，首先二分法查找外层索引，找到其最大搜索码值小于或等于所需搜索码值的记录，指针指向一个内层索引块。直到找到最大搜索码小于或者等于所查记录的文件块。
例如，占用10，000个块的索引，内层索引10，000个。假设外层索引已经存储在主存中，那么使用多级索引时，一次查询只需读取1个块，远小于顺序稠密索引的14个块。
多级索引：若外层索引无法存储在主存中，可以创建多级索引。

最后

以上就是瘦瘦乐曲为你收集整理的数据库系统概念学习笔记 学习目标： 学习内容：的全部内容，希望文章能够帮你解决数据库系统概念学习笔记 学习目标： 学习内容：所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。