DBMS - 快速指南

上一个
下一个

DBMS - 概述

数据库是相关数据的集合，数据是事实和数字的集合，可以对其进行处理以产生信息。

大多数数据表示可记录的事实。数据有助于产生信息，信息基于事实。例如，如果我们有所有学生获得的分数数据，我们就可以得出关于尖子生和平均分数的结论。

数据库管理系统以一种更容易检索、操作和生成信息的方式存储数据。

特征

传统上，数据以文件格式组织。DBMS 当时是一个新概念，所有研究都致力于使其克服传统数据管理方式的不足。现代 DBMS 具有以下特征：

  • 现实世界实体- 现代 DBMS 更贴近现实，并使用现实世界实体来设计其架构。它也使用行为和属性。例如，学校数据库可以使用学生作为实体，并将他们的年龄作为属性。

  • 基于关系的表格- DBMS 允许实体以及它们之间的关系形成表格。用户只需查看表名即可了解数据库的架构。

  • 数据和应用程序的隔离- 数据库系统与其数据完全不同。数据库是一个活动实体，而数据被认为是被动实体，数据库对其进行操作和组织。DBMS 还存储元数据（即关于数据的数据），以简化其自身的过程。

  • 冗余度低- DBMS 遵循规范化规则，当任何属性的值存在冗余时，就会拆分关系。规范化是一个数学上丰富且科学的过程，可以减少数据冗余。

  • 一致性- 一致性是指数据库中每个关系保持一致的状态。存在可以检测到数据库处于不一致状态的尝试的方法和技术。与早期的数据存储应用程序（如文件处理系统）相比，DBMS 可以提供更高的一致性。

  • 查询语言- DBMS 配备了查询语言，这使得检索和操作数据更加高效。用户可以根据需要应用任意数量和任意不同的过滤选项来检索一组数据。传统上，在使用文件处理系统的地方这是不可能的。

  • ACID 属性- DBMS 遵循原子性、一致性、隔离性和持久性的概念（通常缩写为 ACID）。这些概念应用于操作数据库中数据的交易。ACID 属性有助于数据库在多事务环境中以及在发生故障时保持健康。

  • 多用户和并发访问- DBMS 支持多用户环境，并允许他们并行访问和操作数据。尽管当用户尝试处理相同的数据项时，对事务有一些限制，但用户始终没有意识到这些限制。

  • 多视图- DBMS 为不同的用户提供多个视图。销售部门的用户对数据库的视图将与生产部门的工作人员不同。此功能使用户能够根据自己的需求获得数据库的集中视图。

  • 安全性- 多视图等功能在一定程度上提供了安全性，用户无法访问其他用户和部门的数据。DBMS 提供了在将数据输入数据库和稍后检索数据时强制约束的方法。DBMS 提供了许多不同级别的安全功能，这使得多个用户可以拥有具有不同功能的不同视图。例如，销售部门的用户无法查看属于采购部门的数据。此外，还可以管理应向用户显示多少销售部门的数据。由于 DBMS 不是像传统文件系统那样保存在磁盘上，因此不法分子很难破解代码。

用户

典型的 DBMS 具有具有不同权限和许可的用户，他们出于不同的目的使用它。一些用户检索数据，一些用户备份数据。DBMS 的用户可以大致分为以下几类：

  • 管理员- 管理员维护 DBMS，并负责管理数据库。他们负责查看其使用情况以及谁应该使用它。他们为用户创建访问配置文件并应用限制以维护隔离并强制执行安全性。管理员还负责 DBMS 资源，例如系统许可证、所需工具以及其他与软件和硬件相关的维护。

  • 设计人员- 设计人员是实际负责数据库设计工作的人员。他们密切关注应该保存哪些数据以及以何种格式保存。他们识别和设计实体、关系、约束和视图的整个集合。

  • 最终用户- 最终用户是实际受益于 DBMS 的用户。最终用户可以从简单地关注日志或市场价格的查看者到复杂的商业分析师不等。

DBMS - 架构

DBMS 的设计取决于其架构。它可以是集中式、分散式或分层式。DBMS 的架构可以视为单层或多层。n 层架构将整个系统划分为相关的但独立的n个模块，这些模块可以独立地修改、更改或替换。

在 1 层架构中，DBMS 是唯一的实体，用户直接坐在 DBMS 上并使用它。此处进行的任何更改都将直接在 DBMS 本身上进行。它没有为最终用户提供方便的工具。数据库设计人员和程序员通常更喜欢使用单层架构。

如果 DBMS 的架构是 2 层，则它必须有一个应用程序，通过该应用程序可以访问 DBMS。程序员在使用 2 层架构时，通过应用程序访问 DBMS。在此，应用程序层在操作、设计和编程方面完全独立于数据库。

3 层架构

3 层架构根据用户的复杂性和他们如何使用数据库中存在的数据，将各层彼此分离。它是设计 DBMS 时使用最广泛的架构。

  • 数据库（数据）层- 在此层，数据库及其查询处理语言驻留。我们还在此级别拥有定义数据及其约束的关系。

  • 应用程序（中间）层- 在此层驻留应用程序服务器和访问数据库的程序。对于用户而言，此应用程序层提供了数据库的抽象视图。最终用户不知道数据库在应用程序之外的存在。另一方面，数据库层不知道应用程序之外的任何其他用户。因此，应用程序层位于中间，充当最终用户和数据库之间的中介。

  • 用户（表示）层- 最终用户在此层上操作，他们不知道数据库在此层之外的存在。在此层，应用程序可以提供数据库的多个视图。所有视图均由驻留在应用程序层的应用程序生成。

多层数据库架构具有很强的可修改性，因为几乎所有组件都是独立的，可以独立更改。

DBMS - 数据模型

数据模型定义了数据库的逻辑结构是如何建模的。数据模型是引入 DBMS 抽象的基本实体。数据模型定义了数据如何相互连接以及如何在系统内部处理和存储。

第一个数据模型可能是平面数据模型，其中所有使用的数据都保存在同一平面上。早期的数据模型不够科学，因此容易引入大量重复和更新异常。

实体关系模型

实体关系 (ER) 模型基于现实世界实体及其之间关系的概念。在将现实世界场景转化为数据库模型时，ER 模型会创建实体集、关系集、一般属性和约束。

ER 模型最适合用于数据库的概念设计。

ER 模型基于：

  • 实体及其属性。

  • 实体之间的关系。

下面解释这些概念。

  • 实体- ER 模型中的实体是具有称为属性的属性的现实世界实体。每个属性都由其称为域的值集定义。例如，在学校数据库中，学生被视为实体。学生具有各种属性，例如姓名、年龄、班级等。

  • 关系- 实体之间的逻辑关联称为关系。关系以各种方式映射到实体。映射基数定义了两个实体之间的关联数量。

    映射基数：

    • 一对一
    • 一对多
    • 多对一
    • 多对多

关系模型

DBMS 中最流行的数据模型是关系模型。它比其他模型更科学。此模型基于一阶谓词逻辑，并将表定义为n 元关系。

Relational Model Table

此模型的主要亮点包括：

  • 数据存储在称为关系的表中。
  • 关系可以被规范化。
  • 在规范化的关系中，保存的值是原子值。
  • 关系中的每一行都包含唯一的值。
  • 关系中的每一列都包含来自同一域的值。

DBMS - 数据模式

数据库模式

数据库模式是表示整个数据库逻辑视图的骨架结构。它定义了数据如何组织以及它们之间关系是如何关联的。它制定了要应用于数据的所有约束。

数据库模式定义了它的实体以及它们之间的关系。它包含数据库的描述性细节，可以通过模式图来描述。它是数据库设计人员设计模式来帮助程序员理解数据库并使其发挥作用。

数据库模式可以大致分为两类：

  • 物理数据库模式 - 此模式涉及数据的实际存储及其存储形式，例如文件、索引等。它定义了数据将如何存储在辅助存储器中。

  • 逻辑数据库模式 - 此模式定义了需要应用于存储数据的全部逻辑约束。它定义了表、视图和完整性约束。

数据库实例

区分这两个术语非常重要。数据库模式是数据库的骨架。它是在数据库根本不存在时设计的。一旦数据库开始运行，对其进行任何更改都非常困难。数据库模式不包含任何数据或信息。

数据库实例是在任何给定时间包含数据的正在运行的数据库的状态。它包含数据库的快照。数据库实例往往会随着时间而改变。DBMS 通过勤奋地遵循数据库设计人员施加的所有验证、约束和条件，确保其每个实例（状态）都处于有效状态。

DBMS - 数据独立性

如果数据库系统不是多层级的，那么在数据库系统中进行任何更改都会变得困难。正如我们前面了解到的，数据库系统是多层级设计的。

数据独立性

数据库系统通常除了用户数据外还包含大量数据。例如，它存储有关数据的数据，称为元数据，以便轻松定位和检索数据。一旦元数据存储在数据库中，修改或更新它就相当困难。但是随着 DBMS 的扩展，它需要随着时间的推移而改变以满足用户的需求。如果所有数据都存在依赖关系，那么这将成为一项繁琐且极其复杂的工作。

Data independence

元数据本身遵循分层架构，因此当我们在一个层级更改数据时，它不会影响另一个层级的数据。这些数据是独立的，但彼此映射。

逻辑数据独立性

逻辑数据是关于数据库的数据，也就是说，它存储有关数据如何在内部管理的信息。例如，存储在数据库中的表（关系）及其应用于该关系的所有约束。

逻辑数据独立性是一种机制，它使自身从磁盘上实际存储的数据中解放出来。如果我们对表格式进行一些更改，它不应该更改驻留在磁盘上的数据。

物理数据独立性

所有模式都是逻辑的，实际数据以位格式存储在磁盘上。物理数据独立性是在不影响模式或逻辑数据的情况下更改物理数据的能力。

例如，如果我们想更改或升级存储系统本身——假设我们想用 SSD 替换硬盘——它不应该对逻辑数据或模式有任何影响。

ER 模型 - 基本概念

ER 模型定义了数据库的概念视图。它围绕现实世界中的实体及其之间的关联。在视图级别，ER 模型被认为是设计数据库的良好选择。

实体

实体可以是现实世界中的对象，无论是生物还是非生物，都可以轻松识别。例如，在学校数据库中，学生、教师、班级和提供的课程可以被视为实体。所有这些实体都具有一些属性或特性，这些属性或特性赋予了它们身份。

实体集是相同类型实体的集合。实体集可能包含具有共享相似值的属性的实体。例如，一个学生集可能包含一所学校的所有学生；同样，一个教师集可能包含一所学校来自所有院系的所有教师。实体集不必是不相交的。

属性

实体通过其称为属性的特性来表示。所有属性都有值。例如，学生实体可能具有姓名、班级和年龄作为属性。

存在可以分配给属性的值域或范围。例如，学生的姓名不能是数字值。它必须是字母的。学生的年龄不能为负数，等等。

属性类型

  • 简单属性 - 简单属性是原子值，不能进一步细分。例如，学生的电话号码是 10 位的原子值。

  • 复合属性 - 复合属性由多个简单属性组成。例如，学生的完整姓名可能包含 first_name 和 last_name。

  • 派生属性 - 派生属性是不存在于物理数据库中的属性，但其值是从数据库中存在的其他属性派生的。例如，部门的 average_salary 不应直接保存在数据库中，而是可以派生出来。再举一个例子，年龄可以从 data_of_birth 派生出来。

  • 单值属性 - 单值属性包含单个值。例如 - Social_Security_Number。

  • 多值属性 - 多值属性可能包含多个值。例如，一个人可以拥有多个电话号码、电子邮件地址等。

这些属性类型可以以如下方式组合：

  • 简单单值属性
  • 简单多值属性
  • 复合单值属性
  • 复合多值属性

实体集和键

键是唯一标识实体集中实体的属性或属性集合。

例如，学生的 roll_number 使他/她能够在学生中被识别。

  • 超键 - 一组（一个或多个）属性，它们共同标识实体集中的一个实体。

  • 候选键 - 最小的超键称为候选键。实体集可能有多个候选键。

  • 主键 - 主键是数据库设计人员选择用于唯一标识实体集的候选键之一。

关系

实体之间的关联称为关系。例如，员工在部门工作，学生注册课程。这里，Works_at 和 Enrolls 被称为关系。

关系集

一组相同类型的关系称为关系集。与实体一样，关系也可以具有属性。这些属性称为描述性属性。

关系度

关系中参与实体的数量定义了关系的度。

  • 二元 = 度 2
  • 三元 = 度 3
  • n 元 = 度

映射基数

基数定义了一个实体集中实体的数量，可以通过关系集与另一个实体集中的实体数量相关联。

  • 一对一 - 实体集 A 中的一个实体最多可以与实体集 B 中的一个实体相关联，反之亦然。

    • One-to-one relation

  • 一对多 - 实体集 A 中的一个实体可以与实体集 B 中的多个实体相关联，但是实体集 B 中的一个实体最多可以与一个实体相关联。

    • One-to-many relation

  • 多对一 - 实体集 A 中的多个实体最多可以与实体集 B 中的一个实体相关联，但是实体集 B 中的一个实体可以与实体集 A 中的多个实体相关联。

    • Many-to-one relation

  • 多对多 - A 中的一个实体可以与 B 中的多个实体相关联，反之亦然。

    • Many-to-many relation

ER 图表示

现在让我们学习如何通过 ER 图来表示 ER 模型。任何对象，例如实体、实体的属性、关系集和关系集的属性，都可以借助 ER 图来表示。

实体

实体通过矩形来表示。矩形用它们所代表的实体集命名。

Entities in a school database

属性

属性是实体的特性。属性通过椭圆来表示。每个椭圆代表一个属性，并直接连接到其实体（矩形）。

Simple Attributes

如果属性是复合的，则它们将进一步划分为树状结构。然后每个节点都连接到其属性。也就是说，复合属性由连接到椭圆的椭圆表示。

Composite Attributes

多值属性由双椭圆表示。

Multivalued Attributes

派生属性由虚线椭圆表示。

Derived Attributes

关系

关系由菱形框表示。关系的名称写在菱形框内。所有参与关系的实体（矩形）都通过一条线连接到它。

二元关系和基数

两个实体参与的关系称为二元关系。基数是关系中实体的一个实例可以与关系关联的数量。

  • 一对一 - 当只有一个实体实例与关系相关联时，它被标记为“1:1”。下图反映了每个实体只有一个实例应该与关系相关联。它描述了一对一关系。

    • One-to-one

  • 一对多 - 当一个实体的多个实例与关系相关联时，它被标记为“1:N”。下图反映了左侧实体只有一个实例，右侧实体有多个实例可以与关系相关联。它描述了一对多关系。

    • One-to-many

  • 多对一 - 当一个实体的多个实例与关系相关联时，它被标记为“N:1”。下图反映了左侧实体有多个实例，右侧实体只有一个实例可以与关系相关联。它描述了多对一关系。

    • Many-to-one

  • 多对多 - 下图反映了左侧实体有多个实例，右侧实体有多个实例可以与关系相关联。它描述了多对多关系。

    • Many-to-many

参与约束

  • 完全参与 - 每个实体都参与关系。完全参与由双线表示。

  • 部分参与 - 不是所有实体都参与关系。部分参与由单线表示。

Participation Constraints

泛化聚合

现在让我们学习如何通过 ER 图来表示 ER 模型。任何对象，例如实体、实体的属性、关系集和关系集的属性，都可以借助 ER 图来表示。

实体

实体通过矩形来表示。矩形用它们所代表的实体集命名。

Entities in a school database

属性

属性是实体的特性。属性通过椭圆来表示。每个椭圆代表一个属性，并直接连接到其实体（矩形）。

Simple Attributes

如果属性是复合的，则它们将进一步划分为树状结构。然后每个节点都连接到其属性。也就是说，复合属性由连接到椭圆的椭圆表示。

Composite Attributes

多值属性由双椭圆表示。

Multivalued Attributes

派生属性由虚线椭圆表示。

Derived Attributes

关系

关系由菱形框表示。关系的名称写在菱形框内。所有参与关系的实体（矩形）都通过一条线连接到它。

二元关系和基数

两个实体参与的关系称为二元关系。基数是关系中实体的一个实例可以与关系关联的数量。

  • 一对一 - 当只有一个实体实例与关系相关联时，它被标记为“1:1”。下图反映了每个实体只有一个实例应该与关系相关联。它描述了一对一关系。

    • One-to-one

  • 一对多 - 当一个实体的多个实例与关系相关联时，它被标记为“1:N”。下图反映了左侧实体只有一个实例，右侧实体有多个实例可以与关系相关联。它描述了一对多关系。

    • One-to-many

  • 多对一 - 当一个实体的多个实例与关系相关联时，它被标记为“N:1”。下图反映了左侧实体有多个实例，右侧实体只有一个实例可以与关系相关联。它描述了多对一关系。

    • Many-to-one

  • 多对多 - 下图反映了左侧实体有多个实例，右侧实体有多个实例可以与关系相关联。它描述了多对多关系。

    • Many-to-many

参与约束

  • 完全参与 - 每个实体都参与关系。完全参与由双线表示。

  • 部分参与 - 不是所有实体都参与关系。部分参与由单线表示。

Participation Constraints

泛化聚合

实体关系模型（ER Model）能够以概念上的层次结构方式表达数据库实体。随着层次结构向上，它概括了实体的视图；当我们深入层次结构时，它提供了每个包含实体的详细信息。

向上遍历这种结构称为泛化，其中实体被组合在一起以表示更通用的视图。例如，一个名为Mira的特定学生可以与所有学生一起泛化。实体将是一个学生，并且进一步，学生是一个人。反之则称为特化，即人是一个学生，而那个学生是Mira。

泛化

如上所述，将实体泛化的过程称为泛化，其中泛化实体包含所有被泛化实体的属性。在泛化中，许多实体基于其相似特征被组合成一个泛化实体。例如，鸽子、麻雀、乌鸦和斑鸠都可以泛化为鸟类。

Generalization

特化

特化与泛化相反。在特化中，一组实体根据其特征被划分为子组。以“人”组为例。一个人有姓名、出生日期、性别等。这些属性在所有人，即人类中都是通用的。但在公司中，可以根据他们在公司中扮演的角色将人员识别为雇员、雇主、客户或供应商。

Specialization

类似地，在学校数据库中，可以根据人员在学校中扮演的角色（作为实体）将其特化为教师、学生或职员。

继承

为了在面向对象编程中创建对象类，我们使用ER模型的所有上述特性。实体的细节通常对用户隐藏；此过程称为抽象。

继承是泛化和特化的一个重要特性。它允许低级实体继承高级实体的属性。

Inheritance

例如，Person类的属性（如姓名、年龄和性别）可以被低级实体（如Student或Teacher）继承。

Codd的12条规则

Edgar F. Codd博士在其对数据库系统关系模型的广泛研究之后，提出了他自己的12条规则，他认为，为了被视为真正的关系数据库，数据库必须遵守这些规则。

这些规则可以应用于任何仅使用其关系功能管理存储数据的数据库系统。这是一个基础规则，作为所有其他规则的基础。

规则1：信息规则

存储在数据库中的数据，无论是用户数据还是元数据，都必须是某个表单元格的值。数据库中的所有内容都必须以表格格式存储。

规则2：保证访问规则

每个数据元素（值）都保证可以通过表名、主键（行值）和属性名（列值）的组合进行逻辑访问。不能使用其他方法（如指针）访问数据。

规则3：对NULL值的系统化处理

数据库中的NULL值必须得到系统化和统一的处理。这是一个非常重要的规则，因为NULL可以解释为以下含义之一：数据丢失、数据未知或数据不适用。

规则4：活动联机目录

整个数据库的结构描述必须存储在联机目录中，称为数据字典，授权用户可以访问该目录。用户可以使用与访问数据库本身相同的查询语言来访问目录。

规则5：综合数据子语言规则

数据库只能使用具有线性语法的语言访问，该语言支持数据定义、数据操作和事务管理操作。此语言可以直接使用，也可以通过某些应用程序使用。如果数据库允许在没有任何此语言帮助的情况下访问数据，则认为违反了此规则。

规则6：视图更新规则

数据库的所有理论上可以更新的视图都必须由系统可更新。

规则7：高级插入、更新和删除规则

数据库必须支持高级插入、更新和删除。这不能仅限于单行，也就是说，它还必须支持联合、交集和差集运算以产生数据集记录。

规则8：物理数据独立性

存储在数据库中的数据必须独立于访问数据库的应用程序。数据库物理结构的任何更改都不应影响外部应用程序访问数据的方式。

规则9：逻辑数据独立性

数据库中的逻辑数据必须独立于用户的视图（应用程序）。逻辑数据的任何更改都不应影响使用它的应用程序。例如，如果合并两个表或将一个表拆分为两个不同的表，则不应影响或更改用户应用程序。这是最难应用的规则之一。

规则10：完整性独立性

数据库必须独立于使用它的应用程序。所有完整性约束都可以独立修改，而无需对应用程序进行任何更改。此规则使数据库独立于前端应用程序及其接口。

规则11：分布独立性

最终用户不能看到数据分布在各个位置。用户应该始终认为数据仅位于一个站点。此规则被认为是分布式数据库系统的基础。

规则12：非颠覆规则

如果系统具有提供对低级记录访问的接口，则该接口不能能够颠覆系统并绕过安全性和完整性约束。

关系数据模型

关系数据模型是主要的数据模型，在全球范围内广泛用于数据存储和处理。此模型简单，并且具有处理数据并提高存储效率所需的所有属性和功能。

概念

表 - 在关系数据模型中，关系以表的格式保存。此格式存储实体之间的关系。表有行和列，其中行表示记录，列表示属性。

元组 - 表的一行，包含该关系的单个记录称为元组。

关系实例 - 关系数据库系统中的一组有限的元组表示关系实例。关系实例不包含重复的元组。

关系模式 - 关系模式描述关系名称（表名）、属性及其名称。

关系键 - 每行具有一或多个属性，称为关系键，可以唯一地识别关系（表）中的行。

属性域 - 每个属性都具有一些预定义的值范围，称为属性域。

约束

每个关系都有一些条件必须满足才能成为有效的关系。这些条件称为关系完整性约束。主要有三种完整性约束：

  • 键约束
  • 域约束
  • 引用完整性约束

键约束

关系中必须至少存在一个最小子集的属性，可以唯一地识别元组。此属性的最小子集称为该关系的键。如果存在多个这样的最小子集，则称为候选键。

键约束强制：

  • 在具有键属性的关系中，没有两个元组可以对键属性具有相同的值。

  • 键属性不能具有NULL值。

键约束也称为实体约束。

域约束

属性在现实世界场景中具有特定值。例如，年龄只能是正整数。已尝试在关系的属性上使用相同的约束。每个属性都必须具有特定范围的值。例如，年龄不能小于零，电话号码不能包含0-9以外的数字。

引用完整性约束

引用完整性约束基于外键的概念。外键是关系的一个键属性，可以在其他关系中引用。

引用完整性约束规定，如果关系引用不同关系或相同关系的键属性，则该键元素必须存在。

关系代数

关系数据库系统应配备查询语言，以帮助其用户查询数据库实例。查询语言有两种：关系代数和关系演算。

关系代数

关系代数是一种过程式查询语言，它以关系实例作为输入，并以关系实例作为输出。它使用运算符执行查询。运算符可以是一元或二元的。它们接受关系作为输入，并以关系作为输出。关系代数递归地对关系执行，中间结果也被视为关系。

关系代数的基本操作如下：

  • 选择
  • 投影
  • 并集
  • 差集
  • 笛卡尔积
  • 重命名

我们将在以下部分讨论所有这些操作。

选择操作（σ）

它从关系中选择满足给定谓词的元组。

表示法 - σp(r)

其中σ表示选择谓词，r表示关系。p是命题逻辑公式，可以使用and、or和not等连接词。这些术语可以使用关系运算符，如 - =、≠、≥、<、>、≤。

例如 -

σsubject="database"(Books)

输出 - 选择主题为“数据库”的书籍元组。

σsubject="database" and price="450"(Books)

输出 - 选择主题为“数据库”且“价格”为450的书籍元组。

σsubject="database" and price < "450" or year > "2010"(Books)

输出 - 选择主题为“数据库”且“价格”为450的书籍元组，或2010年后出版的书籍元组。

投影操作（∏）

它投影满足给定谓词的列。

表示法 - ∏A1, A2, An (r)

其中A1、A2、An是关系r的属性名称。

由于关系是集合，因此会自动消除重复的行。

例如 -

 ∏subject, author (Books)

从Books关系中选择并投影名为subject和author的列。

并集操作（∪）

它对两个给定关系执行二元并集，定义如下：

 r ∪ s = { t | t ∈ r or t ∈ s}

表示法 - r U s

其中r和s是数据库关系或关系结果集（临时关系）。

为了使并集操作有效，必须满足以下条件：

  • r和s必须具有相同数量的属性。
  • 属性域必须兼容。
  • 重复的元组会自动消除。
 ∏ author (Books) ∪ ∏ author (Articles)

输出 - 投影已编写书籍或文章或两者的作者的姓名。

差集（-）

差集操作的结果是存在于一个关系中但不存在于第二个关系中的元组。

表示法 - r - s

查找存在于r中但不存在于s中的所有元组。

 ∏ author (Books) − ∏ author (Articles)

输出 - 提供已编写书籍但未编写文章的作者的姓名。

笛卡尔积（Χ）

将两个不同关系的信息组合成一个。

表示法 - r Χ s

其中r和s是关系，它们的输出将定义为：

r Χ s = { q t | q ∈ r and t ∈ s}

 ∏ author = 'tutorialspoint'(Books Χ Articles)

输出 - 生成一个关系，显示tutorialspoint编写的所有书籍和文章。

重命名操作（ρ）

关系代数的结果也是关系，但没有名称。重命名操作允许我们重命名输出关系。“重命名”操作用希腊字母rho ρ表示。

表示法 - ρ x (E)

表达式E的结果以x命名进行保存。

其他操作包括：

  • 集合交集
  • 赋值
  • 自然连接

关系演算

与关系代数相反，关系演算是一种非过程查询语言，即它说明做什么，但从不解释如何做。

关系演算存在两种形式：

元组关系演算 (TRC)

过滤元组上的变量范围

表示法 - {T | 条件}

返回满足条件的所有元组 T。

例如 -

{ T.name |  Author(T) AND T.article = 'database' }

输出 - 返回 Author 中撰写关于“数据库”文章的 'name' 字段对应的元组。

TRC 可以进行量化。我们可以使用存在量词 (∃) 和全称量词 (∀)。

例如 -

{ R| ∃T   ∈ Authors(T.article='database' AND R.name=T.name)}

输出 - 上述查询将产生与前一个查询相同的结果。

域关系演算 (DRC)

在 DRC 中，过滤变量使用属性的域而不是整个元组值（如上面提到的 TRC 中所做的那样）。

表示法 -

{ a1, a2, a3, ..., an | P (a1, a2, a3, ... ,an)}

其中 a1、a2 是属性，而P表示由内部属性构建的公式。

例如 -

{< article, page, subject > |  ∈ TutorialsPoint ∧ subject = 'database'}

输出 - 从 TutorialsPoint 关系中生成 Article、Page 和 Subject，其中 subject 为 database。

就像 TRC 一样，DRC 也可以使用存在量词和全称量词来编写。DRC 还涉及关系运算符。

元组关系演算和域关系演算的表达能力等价于关系代数。

ER 模型到关系模型

ER 模型，当概念化为图表时，提供了实体关系的良好概述，更容易理解。ER 图可以映射到关系模式，也就是说，可以使用 ER 图创建关系模式。我们不能将所有 ER 约束导入关系模型，但可以生成一个近似的模式。

有几种可用于将 ER 图转换为关系模式的过程和算法。其中一些是自动化的，另一些是手动的。我们可能在这里关注将图表内容映射到关系基础知识。

ER 图主要包括：

  • 实体及其属性
  • 关系，即实体之间的关联。

实体映射

实体是具有某些属性的现实世界对象。

Mapping Entity

映射过程（算法）

  • 为每个实体创建一个表。
  • 实体的属性应成为表中具有各自数据类型的字段。
  • 声明主键。

关系映射

关系是实体之间的关联。

Mapping relationship

映射过程

  • 为关系创建一个表。
  • 将所有参与实体的主键作为表中具有各自数据类型的字段添加。
  • 如果关系有任何属性，则将每个属性作为表的字段添加。
  • 声明一个主键，该主键由所有参与实体的主键组成。
  • 声明所有外键约束。

弱实体集映射

弱实体集是没有与其关联的任何主键的实体集。

Mapping Weak Entity Sets

映射过程

  • 为弱实体集创建一个表。
  • 将所有属性作为字段添加到表中。
  • 添加识别实体集的主键。
  • 声明所有外键约束。

层次实体映射

ER 特化或泛化以层次实体集的形式出现。

Mapping hierarchical entities

映射过程

  • 为所有高级别实体创建表。

  • 为低级别实体创建表。

  • 在低级别实体的表中添加高级别实体的主键。

  • 在低级别表中，添加低级别实体的所有其他属性。

  • 声明高级别表的主键和低级别表的主键。

  • 声明外键约束。

SQL 概述

SQL 是一种用于关系数据库的编程语言。它是在关系代数和元组关系演算的基础上设计的。SQL 与所有主要 RDBMS 发行版捆绑在一起。

SQL 包含数据定义语言和数据操纵语言。使用 SQL 的数据定义属性，可以设计和修改数据库模式，而数据操纵属性允许 SQL 从数据库中存储和检索数据。

数据定义语言

SQL 使用以下命令集来定义数据库模式：

CREATE

从 RDBMS 创建新的数据库、表和视图。

例如 -

Create database tutorialspoint;
Create table article;
Create view for_students;

DROP

从 RDBMS 删除命令、视图、表和数据库。

例如-

Drop object_type object_name;
Drop database tutorialspoint;
Drop table article;
Drop view for_students;

ALTER

修改数据库模式。

Alter object_type object_name parameters;

例如-

Alter table article add subject varchar;

此命令在article关系中添加一个名为subject的字符串类型属性。

数据操纵语言

SQL 配备了数据操纵语言 (DML)。DML 通过插入、更新和删除其数据来修改数据库实例。DML 负责数据库中所有形式的数据修改。SQL 在其 DML 部分包含以下命令集：

  • SELECT/FROM/WHERE
  • INSERT INTO/VALUES
  • UPDATE/SET/WHERE
  • DELETE FROM/WHERE

这些基本结构允许数据库程序员和用户将数据和信息输入数据库，并使用许多筛选选项高效地检索数据。

SELECT/FROM/WHERE

  • SELECT - 这是 SQL 的基本查询命令之一。它类似于关系代数的投影操作。它根据 WHERE 子句描述的条件选择属性。

  • FROM - 此子句以关系名称作为参数，从中选择/投影属性。如果给出了多个关系名称，则此子句对应于笛卡尔积。

  • WHERE - 此子句定义谓词或条件，必须匹配才能使属性有资格被投影。

例如 -

Select author_name
From book_author
Where age > 50;

此命令将生成book_author关系中年龄大于 50 的作者的姓名。

INSERT INTO/VALUES

此命令用于将值插入表的行（关系）。

语法-

INSERT INTO table (column1 [, column2, column3 ... ]) VALUES (value1 [, value2, value3 ... ])

或

INSERT INTO table VALUES (value1, [value2, ... ])

例如 -

INSERT INTO tutorialspoint (Author, Subject) VALUES ("anonymous", "computers");

UPDATE/SET/WHERE

此命令用于更新或修改表（关系）中列的值。

语法 -

UPDATE table_name SET column_name = value [, column_name = value ...] [WHERE condition]

例如 -

UPDATE tutorialspoint SET Author="webmaster" WHERE Author="anonymous";

DELETE/FROM/WHERE

此命令用于从表（关系）中删除一行或多行。

语法 -

DELETE FROM table_name [WHERE condition];

例如 -

DELETE FROM tutorialspoints
   WHERE Author="unknown";

DBMS - 规范化

函数依赖

函数依赖 (FD) 是关系中两个属性之间的一组约束。函数依赖表示如果两个元组在属性 A1、A2、...、An 上具有相同的值，则这两个元组必须在属性 B1、B2、...、Bn 上具有相同的值。

函数依赖用箭头符号 (→) 表示，即 X→Y，其中 X 函数决定 Y。左侧属性决定右侧属性的值。

阿姆斯特朗公理

如果 F 是一组函数依赖，则 F 的闭包，表示为 F+，是由 F 逻辑推导出的所有函数依赖的集合。阿姆斯特朗公理是一组规则，当重复应用时，会生成函数依赖的闭包。

  • 自反规则 - 如果 alpha 是一组属性，而 beta 是 alpha 的子集，则 alpha 包含 beta。

  • 增广规则 - 如果 a → b 成立，而 y 是属性集，则 ay → by 也成立。也就是说，在依赖项中添加属性不会改变基本依赖项。

  • 传递规则 - 与代数中的传递规则相同，如果 a → b 成立且 b → c 成立，则 a → c 也成立。a → b 称为函数决定 b。

平凡函数依赖

  • 平凡 - 如果函数依赖 (FD) X → Y 成立，其中 Y 是 X 的子集，则称为平凡 FD。平凡 FD 始终成立。

  • 非平凡 - 如果 FD X → Y 成立，其中 Y 不是 X 的子集，则称为非平凡 FD。

  • 完全非平凡 - 如果 FD X → Y 成立，其中 x 与 Y 的交集 = Φ，则称其为完全非平凡 FD。

规范化

如果数据库设计不完美，则可能包含异常，这对于任何数据库管理员来说都像噩梦一样。管理包含异常的数据库几乎是不可能的。

  • 更新异常 - 如果数据项分散并且未正确相互链接，则可能导致奇怪的情况。例如，当我们尝试更新一个数据项时，该数据项的副本分散在多个位置，一些实例得到正确更新，而另一些则保留旧值。此类实例使数据库处于不一致状态。

  • 删除异常 - 我们尝试删除记录，但由于不知道数据也保存在其他地方，因此部分记录未被删除。

  • 插入异常 - 我们尝试在根本不存在的记录中插入数据。

规范化是一种消除所有这些异常并将数据库置于一致状态的方法。

第一范式

第一范式在关系（表）本身的定义中定义。此规则定义关系中的所有属性都必须具有原子域。原子域中的值是不可分割的单元。

unorganized relation

我们如下重新排列关系（表），以将其转换为第一范式。

Relation in 1NF

每个属性只能包含来自其预定义域的单个值。

第二范式

在学习第二范式之前，我们需要了解以下内容：

  • 主属性 - 候选键的一部分的属性称为主属性。

  • 非主属性 - 不是主键一部分的属性称为非主属性。

如果我们遵循第二范式，则每个非主属性都应完全函数依赖于主键属性。也就是说，如果 X → A 成立，则 X 的任何真子集 Y 不应存在，对于该子集 Y → A 也成立。

Relation not in 2NF

我们在此处在 Student_Project 关系中看到，主键属性是 Stu_ID 和 Proj_ID。根据规则，非键属性，即 Stu_Name 和 Proj_Name 必须依赖于两者，而不是单独依赖于任何一个主键属性。但我们发现 Stu_Name 可以独立地由 Stu_ID 识别，Proj_Name 可以独立地由 Proj_ID 识别。这称为部分依赖，第二范式不允许这种情况。

Relation in 2NF

我们如上图所示将关系分成两个。因此，不存在部分依赖关系。

第三范式

要使关系处于第三范式，它必须处于第二范式，并且必须满足以下条件：

  • 非主属性不传递依赖于主键属性。
  • 对于任何非平凡函数依赖 X → A，则：
      X 是超键，或
    • A 是主属性。
Relation not in 3NF

我们发现在上面的 Student_detail 关系中，Stu_ID 是键并且是唯一的主键属性。我们发现 City 可以由 Stu_ID 和 Zip 本身识别。Zip 既不是超键，City 也不是主属性。此外，Stu_ID → Zip → City，因此存在传递依赖。

为了将此关系转换为第三范式，我们将关系分成两个关系，如下所示：

Relation in 3NF

Boyce-Codd 范式

Boyce-Codd 范式 (BCNF) 是对第三范式在严格意义上的扩展。BCNF 指出：

  • 对于任何非平凡函数依赖 X → A，X 必须是超键。

在上图中，Stu_ID 是关系 Student_Detail 的超键，Zip 是关系 ZipCodes 的超键。因此，

Stu_ID → Stu_Name, Zip

以及

Zip → City

这证实了这两个关系都处于 BCNF 状态。

DBMS - 连接

我们了解获取两个关系的笛卡尔积的好处，它为我们提供了所有配对在一起的可能的元组。但在某些情况下，获取笛卡尔积可能不可行，例如遇到包含数千个元组且具有相当大量属性的大型关系。

连接是笛卡尔积和选择过程的组合。只有当满足给定的连接条件时，连接操作才会将来自不同关系的两个元组配对。

我们将在以下部分简要描述各种连接类型。

θ 连接

θ 连接组合来自不同关系的元组，前提是它们满足 θ 条件。连接条件用符号θ表示。

符号

R1 ⋈θ R2

R1 和 R2 是具有属性 (A1, A2, .., An) 和 (B1, B2,.. ,Bn) 的关系，其中属性之间没有任何共同点，即 R1 ∩ R2 = Φ。

θ 连接可以使用各种比较运算符。

学生
SID 姓名 Std
101 Alex 10
102 Maria 11
科目
班级 科目
10 数学
10 英语
11 音乐
11 体育

Student_Detail =

STUDENT ⋈Student.Std = Subject.Class SUBJECT

学生详细信息
SID 姓名 Std 班级 科目
101 Alex 10 10 数学
101 Alex 10 10 英语
102 Maria 11 11 音乐
102 Maria 11 11 体育

等值连接

当 θ 连接仅使用等于比较运算符时，称为等值连接。以上示例对应于等值连接。

自然连接（⋈)

自然连接不使用任何比较运算符。它不像笛卡尔积那样进行连接。只有当两个关系之间至少存在一个公共属性时，我们才能执行自然连接。此外，这些属性必须具有相同的名称和域。

自然连接作用于那些匹配的属性，其中两个关系中属性的值相同。

课程
CID 课程 系
CS01 数据库 CS
ME01 力学 ME
EE01 电子学 EE
系主任
系 主任
CS Alex
ME Maya
EE Mira
Courses ⋈ HoD
系 CID 课程 主任
CS CS01 数据库 Alex
ME ME01 力学 Maya
EE EE01 电子学 Mira

外连接

θ 连接、等值连接和自然连接称为内连接。内连接仅包含具有匹配属性的元组，其余元组在结果关系中被丢弃。因此，我们需要使用外连接将参与关系中的所有元组包含在结果关系中。外连接有三种类型：左外连接、右外连接和全外连接。

左外连接(R Left Outer Join S)

左关系 R 中的所有元组都包含在结果关系中。如果 R 中存在任何元组在右关系 S 中没有匹配元组，则结果关系的 S 属性将设为 NULL。

左
A B
100 数据库
101 力学
102 电子学
右
A B
100 Alex
102 Maya
104 Mira
Courses Left Outer Join HoD
A B C D
100 数据库 100 Alex
101 力学 --- ---
102 电子学 102 Maya

右外连接: ( R Right Outer Join S )

右关系 S 中的所有元组都包含在结果关系中。如果 S 中存在任何元组在 R 中没有匹配元组，则结果关系的 R 属性将设为 NULL。

Courses Right Outer Join HoD
A B C D
100 数据库 100 Alex
102 电子学 102 Maya
--- --- 104 Mira

全外连接: ( R Full Outer Join S)

两个参与关系中的所有元组都包含在结果关系中。如果两个关系都没有匹配的元组，则它们各自的未匹配属性将设为 NULL。

Courses Full Outer Join HoD
A B C D
100 数据库 100 Alex
101 力学 --- ---
102 电子学 102 Maya
--- --- 104 Mira

DBMS - 存储系统

数据库存储在文件格式中，其中包含记录。在物理层面上，实际数据以电磁格式存储在某些设备上。这些存储设备可以大致分为三种类型：

Memory Types

  • 主存储器 - CPU 可以直接访问的内存存储属于此类别。CPU 的内部内存（寄存器）、高速缓存（缓存）和主内存（RAM）都可以被 CPU 直接访问，因为它们都放置在主板上或 CPU 芯片组上。这种存储器通常非常小、速度极快且易失。主存储器需要持续供电才能保持其状态。如果发生断电，其所有数据都会丢失。

  • 辅助存储器 - 辅助存储设备用于存储数据以备将来使用或作为备份。辅助存储器包括不属于 CPU 芯片组或主板的内存设备，例如磁磁盘、光盘（DVD、CD 等）、硬盘、闪存驱动器和磁带。

  • 三级存储器 - 三级存储器用于存储海量数据。由于此类存储设备位于计算机系统外部，因此速度最慢。这些存储设备主要用于备份整个系统。光盘和磁带被广泛用作三级存储器。

内存层次结构

计算机系统具有明确定义的内存层次结构。CPU 可以直接访问其主内存以及其内置寄存器。主内存的访问时间显然小于 CPU 速度。为了最大程度地减少这种速度差异，引入了缓存。缓存提供最快的访问时间，并且包含 CPU 最常访问的数据。

访问速度最快的内存也是最昂贵的。较大的存储设备提供较慢的速度，并且价格较低，但是与 CPU 寄存器或缓存相比，它们可以存储海量数据。

磁磁盘

硬盘驱动器是当前计算机系统中最常见的辅助存储设备。之所以称为磁磁盘，是因为它们使用磁化概念来存储信息。硬盘由涂有可磁化材料的金属磁盘组成。这些磁盘垂直放置在主轴上。读/写磁头在磁盘之间移动，用于磁化或去磁化其下方的点。磁化点可以识别为 0（零）或 1（一）。

硬盘以明确定义的顺序格式化，以便有效地存储数据。硬盘盘片上有许多同心圆，称为磁道。每个磁道进一步细分为扇区。硬盘上的扇区通常存储 512 字节的数据。

RAID

RAID 代表Redundant Array of Independent Disks，这是一项连接多个辅助存储设备并将它们用作单个存储介质的技术。

RAID 由一个磁盘阵列组成，其中多个磁盘连接在一起以实现不同的目标。RAID 级别定义了磁盘阵列的使用。

  • RAID 0 - 在此级别，实现了磁盘的条带化阵列。数据被分解成块，这些块分布在磁盘之间。每个磁盘接收一个数据块以并行写入/读取。它提高了存储设备的速度和性能。级别 0 没有奇偶校验和备份。

RAID 0

  • RAID 1 - RAID 1 使用镜像技术。当数据发送到 RAID 控制器时，它会将数据副本发送到阵列中的所有磁盘。RAID 级别 1 也称为镜像，在发生故障时提供 100% 的冗余。

RAID 1

  • RAID 2 - RAID 2 使用汉明距离记录其数据的纠错码，并将其条带化到不同的磁盘上。与级别 0 类似，单词中的每个数据位都记录在单独的磁盘上，并且数据单词的 ECC 代码存储在不同的磁盘集上。由于其结构复杂且成本高昂，RAID 2 并非商用。

RAID 2

  • RAID 3 - RAID 3 将数据条带化到多个磁盘上。为数据字生成的奇偶校验位存储在不同的磁盘上。此技术使其能够克服单个磁盘故障。

RAID 3

  • RAID 4 - 在此级别，将整个数据块写入数据磁盘，然后生成奇偶校验并存储在不同的磁盘上。请注意，级别 3 使用字节级条带化，而级别 4 使用块级条带化。级别 3 和级别 4 都需要至少三个磁盘才能实现 RAID。

RAID 4

  • RAID 5 - RAID 5 将整个数据块写入不同的磁盘，但为数据块条带生成的奇偶校验位分布在所有数据磁盘上，而不是存储在不同的专用磁盘上。

RAID 5

  • RAID 6 - RAID 6 是级别 5 的扩展。在此级别，生成两个独立的奇偶校验并以分布式方式存储在多个磁盘上。两个奇偶校验提供额外的容错能力。此级别需要至少四个磁盘驱动器才能实现 RAID。

DBMS - 文件结构

相对数据和信息以文件格式集体存储。文件是以二进制格式存储的一系列记录。磁盘驱动器被格式化为多个可以存储记录的块。文件记录映射到这些磁盘块上。

文件组织

文件组织定义了如何将文件记录映射到磁盘块上。我们有四种文件组织类型来组织文件记录：

File Organization

堆文件组织

使用堆文件组织创建文件时，操作系统会为该文件分配内存区域，而无需任何其他会计详细信息。文件记录可以放置在该内存区域的任何位置。软件负责管理记录。堆文件本身不支持任何排序、排序或索引。

顺序文件组织

每个文件记录都包含一个数据字段（属性）来唯一标识该记录。在顺序文件组织中，记录根据唯一的键字段或搜索键以某种顺序放置在文件中。实际上，不可能以物理形式顺序存储所有记录。

哈希文件组织

哈希文件组织对记录的某些字段使用哈希函数计算。哈希函数的输出确定要放置记录的磁盘块的位置。

聚簇文件组织

聚簇文件组织不适用于大型数据库。在这种机制中，来自一个或多个关系的相关记录保存在同一个磁盘块中，也就是说，记录的排序不是基于主键或搜索键。

文件操作

数据库文件上的操作可以大致分为两类：

  • 更新操作

  • 检索操作

更新操作通过插入、删除或更新来改变数据值。另一方面，检索操作不改变数据，而是在可选的条件过滤后检索数据。在这两种类型的操作中，选择都起着重要的作用。除了创建和删除文件之外，还可以在文件上执行其他一些操作。

  • 打开 - 文件可以以两种模式之一打开，读取模式或写入模式。在读取模式下，操作系统不允许任何人更改数据。换句话说，数据是只读的。以读取模式打开的文件可以在多个实体之间共享。写入模式允许修改数据。以写入模式打开的文件可以读取，但不能共享。

  • 定位 - 每个文件都有一个文件指针，它指示要读取或写入数据的当前位置。此指针可以相应地调整。使用查找（查找）操作，可以向前或向后移动它。

  • 读取 - 默认情况下，当文件以读取模式打开时，文件指针指向文件的开头。用户可以选择在打开文件时告诉操作系统将文件指针定位到哪里。读取文件指针后面的下一个数据。

  • 写入 - 用户可以选择以写入模式打开文件，这使他们能够编辑其内容。它可以是删除、插入或修改。文件指针可以在打开时定位，如果操作系统允许，也可以动态更改。

  • 关闭 - 从操作系统的角度来看，这是最重要的操作。当生成关闭文件的请求时，操作系统

    • 删除所有锁（如果处于共享模式），
    • 将数据（如果已更改）保存到辅助存储介质，以及
    • 释放与文件关联的所有缓冲区和文件句柄。

文件内部数据的组织在这里起着主要作用。定位文件指针到文件内所需记录的过程取决于记录是顺序排列还是聚簇排列。

DBMS - 索引

我们知道数据以记录的形式存储。每个记录都有一个键字段，可以帮助它唯一地识别。

索引是一种数据结构技术，可以根据已对其进行索引的一些属性有效地从数据库文件中检索记录。数据库系统中的索引类似于我们在书籍中看到的索引。

索引是根据其索引属性定义的。索引可以是以下类型：

  • 主索引 - 主索引定义在有序数据文件上。数据文件根据键字段排序。键字段通常是关系的主键。

  • 次索引 - 次索引可以从候选键字段生成，该字段在每条记录中都有唯一值，或者是非键字段，具有重复值。

  • 聚簇索引 - 聚簇索引定义在有序数据文件上。数据文件根据非键字段排序。

有序索引有两种类型：

  • 稠密索引
  • 稀疏索引

稠密索引

在稠密索引中，数据库中的每个搜索键值都有一个索引记录。这使得搜索更快，但需要更多空间来存储索引记录本身。索引记录包含搜索键值和指向磁盘上实际记录的指针。

Dense Index

稀疏索引

在稀疏索引中，并非为每个搜索键创建索引记录。此处的索引记录包含一个搜索键和一个指向磁盘上数据的实际指针。要搜索记录，我们首先通过索引记录进行，并到达数据的实际位置。如果我们正在寻找的数据不在我们通过遵循索引直接到达的位置，那么系统将开始顺序搜索，直到找到所需的数据。

Sparse Index

多级索引

索引记录包含搜索键值和数据指针。多级索引与实际的数据库文件一起存储在磁盘上。随着数据库大小的增长，索引的大小也会增长。迫切需要将索引记录保存在主内存中，以加快搜索操作。如果使用单级索引，则大型索引无法保存在内存中，这会导致多次磁盘访问。

Multi-level Index

多级索引有助于将索引分解成多个较小的索引，以便使最外层索引足够小，可以保存在单个磁盘块中，该磁盘块可以轻松地容纳在主内存中的任何位置。

B+树

B+树是一种平衡二叉搜索树，遵循多级索引格式。B+树的叶子节点表示实际数据指针。B+树确保所有叶子节点保持相同的高度，从而保持平衡。此外，叶子节点使用链接列表链接；因此，B+树可以支持随机访问以及顺序访问。

B+树的结构

每个叶子节点与根节点的距离相等。B+树的阶数为n，其中n对于每个B+树都是固定的。

B+ tree

内部节点 -

  • 内部（非叶子）节点至少包含⌈n/2⌉个指针，根节点除外。
  • 最多，一个内部节点可以包含n个指针。

叶子节点 -

  • 叶子节点至少包含⌈n/2⌉个记录指针和⌈n/2⌉个键值。
  • 最多，一个叶子节点可以包含n个记录指针和n个键值。
  • 每个叶子节点都包含一个块指针P指向下一个叶子节点，并形成一个链接列表。

B+树插入

  • B+树从底部填充，每个条目都在叶子节点完成。

  • 如果叶子节点溢出 -

    • 将节点分成两部分。

    • 在i = ⌊(m+1)/2⌋处进行分区。

    • 前i个条目存储在一个节点中。

    • 其余的条目（从i+1开始）移动到一个新节点。

    • ith键在叶子的父节点中重复。

  • 如果非叶子节点溢出 -

    • 将节点分成两部分。

    • 在i = ⌈(m+1)/2⌉处对节点进行分区。

    • 最多i个条目保存在一个节点中。

    • 其余的条目移动到一个新节点。

B+树删除

  • B+树条目在叶子节点处删除。

  • 搜索并删除目标条目。

    • 如果它是内部节点，则删除并替换为左侧位置的条目。

  • 删除后，测试下溢，

    • 如果发生下溢，则从其左侧的节点分配条目。

  • 如果无法从左侧分配，则

    • 从其右侧的节点分配。

  • 如果无法从左侧或右侧分配，则

    • 将节点与其左右合并。

DBMS - 哈希

对于庞大的数据库结构，几乎不可能通过所有级别搜索所有索引值，然后到达目标数据块以检索所需数据。哈希是一种有效的技术，可以计算磁盘上数据记录的直接位置，而无需使用索引结构。

哈希使用搜索键作为参数的哈希函数来生成数据记录的地址。

哈希组织

  • 桶 - 哈希文件以桶格式存储数据。桶被认为是存储单元。一个桶通常存储一个完整的磁盘块，而一个磁盘块又可以存储一个或多个记录。

  • 哈希函数 - 哈希函数h是一个映射函数，它将所有搜索键K的集合映射到放置实际记录的地址。它是一个从搜索键到桶地址的函数。

静态哈希

在静态哈希中，当提供搜索键值时，哈希函数始终计算相同的地址。例如，如果使用模4哈希函数，则它只能生成5个值。对于该函数，输出地址始终相同。提供的桶数始终保持不变。

Static Hashing

操作

  • 插入 - 当需要使用静态哈希输入记录时，哈希函数h计算搜索键K的桶地址，记录将存储在此处。

    桶地址 = h(K)

  • 搜索 - 当需要检索记录时，可以使用相同的哈希函数检索存储数据所在的桶的地址。

  • 删除 - 这只是一个搜索后跟删除操作。

桶溢出

桶溢出的情况称为冲突。这对任何静态哈希函数来说都是一个致命的状态。在这种情况下，可以使用溢出链接。

  • 溢出链接 - 当桶满时，为相同的哈希结果分配一个新桶，并在上一个桶之后链接。这种机制称为闭合哈希。

Overflow chaining

  • 线性探测 - 当哈希函数生成一个数据已存储的地址时，将为其分配下一个空闲桶。这种机制称为开放哈希。

Linear Probing

动态哈希

静态哈希的问题在于，它不会随着数据库大小的增长或缩小而动态扩展或收缩。动态哈希提供了一种机制，可以在其中动态且按需添加和删除数据桶。动态哈希也称为扩展哈希。

在动态哈希中，哈希函数被设计为产生大量值，并且最初只使用其中一部分。

Dynamic Hashing

组织

整个哈希值的开头部分作为哈希索引。只有哈希值的一部分用于计算桶地址。每个哈希索引都有一个深度值，表示用于计算哈希函数的位数。这些位可以寻址2n个桶。当所有这些位都被使用时 - 即当所有桶都满时 - 深度值线性增加，并分配两倍的桶。

操作

  • 查询 - 查看哈希索引的深度值，并使用这些位来计算桶地址。

  • 更新 - 执行如上所述的查询并更新数据。

  • 删除 - 执行查询以定位所需数据并删除相同的数据。

  • 插入 - 计算桶的地址

    • 如果桶已满。
      • 添加更多桶。
      • 向哈希值添加额外的位。
      • 重新计算哈希函数。
    • 否则
      • 将数据添加到桶中，
    • 如果所有桶都满了，则执行静态哈希的补救措施。

当数据以某种顺序组织并且查询需要一定范围的数据时，哈希是不利的。当数据离散且随机时，哈希表现最佳。

哈希算法的复杂度高于索引。所有哈希操作都在恒定时间内完成。

DBMS - 事务

事务可以定义为一组任务。单个任务是最小的处理单元，不能再进一步细分。

让我们以一个简单的交易为例。假设一位银行职员将500卢比从A的账户转到B的账户。这个非常简单的小额交易涉及到几个低级别的任务。

A的账户

Open_Account(A)
Old_Balance = A.balance
New_Balance = Old_Balance - 500
A.balance = New_Balance
Close_Account(A)

B的账户

Open_Account(B)
Old_Balance = B.balance
New_Balance = Old_Balance + 500
B.balance = New_Balance
Close_Account(B)

ACID属性

事务是程序的一个非常小的单元，它可能包含多个低级任务。数据库系统中的事务必须维护**原子性**、**一致性**、**隔离性**和**持久性**——通常称为ACID属性——以确保准确性、完整性和数据完整性。

  • **原子性**——此属性规定事务必须被视为一个原子单元，即要么所有操作都执行，要么都不执行。数据库中不应存在事务部分完成的状态。状态应在事务执行之前或事务执行/中止/失败之后定义。

  • **一致性**——在任何事务之后，数据库都必须保持一致的状态。任何事务都不应对数据库中驻留的数据产生任何不利影响。如果数据库在事务执行之前处于一致状态，则在事务执行之后也必须保持一致状态。

  • **持久性**——即使系统发生故障或重新启动，数据库也应该足够持久以保留其所有最新更新。如果事务更新数据库中的一部分数据并提交，则数据库将保留修改后的数据。如果事务提交但系统在数据写入磁盘之前发生故障，则系统恢复运行后将更新该数据。

  • **隔离性**——在数据库系统中，如果多个事务同时并行执行，则隔离性属性规定所有事务都将被执行，就好像它是系统中唯一的事务一样。任何事务都不会影响任何其他事务的存在。

可串行化

当多个事务在多编程环境中由操作系统执行时，有可能一个事务的指令与其他事务的指令交错执行。

  • **调度**——事务的按时间顺序执行序列称为调度。一个调度可以包含许多事务，每个事务包含多个指令/任务。

  • **串行调度**——它是一种调度，其中事务以这样一种方式排列，即一个事务首先执行。当第一个事务完成其循环后，则执行下一个事务。事务一个接一个地排序。这种类型的调度称为串行调度，因为事务以串行方式执行。

在多事务环境中，串行调度被认为是基准。事务中指令的执行顺序不能更改，但两个事务可以以随机方式执行其指令。如果两个事务相互独立并在数据的不同段上工作，则此执行不会造成任何损害；但如果这两个事务正在处理相同的数据，则结果可能会有所不同。这种不断变化的结果可能会导致数据库进入不一致的状态。

为了解决此问题，如果事务的可串行化或它们之间存在某种等价关系，则允许并行执行事务调度。

等价调度

等价调度可以是以下类型：

结果等价

如果两个调度在执行后产生相同的结果，则称它们为结果等价。它们可能对某些值产生相同的结果，而对另一组值产生不同的结果。这就是为什么这种等价通常不被认为是重要的。

视图等价

如果两个调度中的事务以类似的方式执行类似的操作，则这两个调度将是视图等价的。

例如：

  • 如果T在S1中读取初始数据，则它也在S2中读取初始数据。

  • 如果T读取J在S1中写入的值，则它也读取J在S2中写入的值。

  • 如果T在S1中对数据值执行最终写入，则它也在S2中对数据值执行最终写入。

冲突等价

如果两个调度具有以下属性，则它们将发生冲突：

  • 两者都属于单独的事务。
  • 两者都访问相同的数据项。
  • 至少其中一个是“写”操作。

如果且仅当以下条件成立时，具有多个包含冲突操作的事务的两个调度才被称为冲突等价：

  • 两个调度包含相同的交易集。
  • 两个调度都保持冲突操作对的顺序。

**注意**——视图等价调度是视图可串行化的，冲突等价调度是冲突可串行化的。所有冲突可串行化调度也是视图可串行化的。

事务的状态

数据库中的事务可以处于以下状态之一：

Transaction States

  • **活动**——在此状态下，正在执行事务。这是每个事务的初始状态。

  • **部分提交**——当事务执行其最终操作时，据说它处于部分提交状态。

  • **失败**——如果数据库恢复系统进行的任何检查失败，则事务被认为处于失败状态。失败的事务不能再继续进行。

  • **中止**——如果任何检查失败并且事务已达到失败状态，则恢复管理器将撤消其在数据库上的所有写操作，以将数据库恢复到事务执行之前的原始状态。处于此状态的事务称为中止。数据库恢复模块可以在事务中止后选择两个操作之一：

    • 重新启动事务
    • 终止事务

  • **提交**——如果事务成功执行了所有操作，则称其已提交。其所有影响现在都永久地建立在数据库系统上。

DBMS - 并发控制

在可以同时执行多个事务的多编程环境中，控制事务的并发性非常重要。我们有并发控制协议来确保并发事务的原子性、隔离性和可串行化。并发控制协议可以大致分为两类：

  • 基于锁的协议
  • 基于时间戳的协议

基于锁的协议

配备基于锁的协议的数据库系统使用一种机制，通过该机制，任何事务在获取适当的锁之前都不能读取或写入数据。锁有两种：

  • **二元锁**——数据项上的锁可以处于两种状态；它要么被锁定，要么未锁定。

  • **共享/排他**——这种类型的锁定机制根据其用途区分锁。如果获取数据项上的锁以执行写操作，则它是排他锁。允许多个事务写入相同的数据项将导致数据库进入不一致的状态。读取锁是共享的，因为没有更改任何数据值。

有四种类型的锁定协议可用：

简单的锁定协议

简单的基于锁的协议允许事务在执行“写”操作之前获取每个对象上的锁。事务可以在完成“写”操作后解锁数据项。

预声明锁定协议

预声明协议评估其操作并创建一个需要锁定的数据项列表。在开始执行之前，事务会事先向系统请求它需要的所有锁。如果所有锁都被授予，则事务执行并在所有操作完成后释放所有锁。如果所有锁都没有被授予，则事务回滚并等待直到所有锁都被授予。

Pre-claiming

两阶段锁定 2PL

此锁定协议将事务的执行阶段分为三个部分。在第一部分，当事务开始执行时，它会请求它所需的锁的许可。第二部分是事务获取所有锁的地方。一旦事务释放其第一个锁，第三阶段就开始了。在此阶段，事务不能要求任何新的锁；它只释放获取的锁。

Two Phase Locking

两阶段锁定有两个阶段，一个是**增长**阶段，其中所有锁都由事务获取；第二个阶段是收缩阶段，其中事务持有的锁被释放。

要声明排他（写）锁，事务必须首先获取共享（读）锁，然后将其升级为排他锁。

严格的两阶段锁定

严格-2PL的第一阶段与2PL相同。在第一阶段获取所有锁后，事务继续正常执行。但与2PL相反，严格-2PL不会在使用后释放锁。严格-2PL持有所有锁直到提交点，并在同一时间释放所有锁。

Strict Two Phase Locking

严格-2PL 没有像 2PL 那样的级联中止。

基于时间戳的协议

最常用的并发控制协议是基于时间戳的协议。此协议使用系统时间或逻辑计数器作为时间戳。

基于锁的协议在执行时管理事务之间冲突对的顺序，而基于时间戳的协议在创建事务时就开始工作。

每个事务都有一个与其关联的时间戳，并且排序由事务的年龄决定。在0002时钟时间创建的事务将比其后所有其他事务都旧。例如，任何在0004进入系统的交易“y”都年轻两秒，并且优先级将给予较旧的交易。

此外，每个数据项都会获得最新的读取和写入时间戳。这使系统能够知道上次对数据项执行“读取和写入”操作的时间。

时间戳排序协议

时间戳排序协议确保事务在其冲突的读取和写入操作中的可串行化。这是协议系统负责确保冲突的任务对应根据事务的时间戳值执行。

  • 事务Ti的时间戳表示为TS(Ti)。
  • 数据项X的读取时间戳表示为R-timestamp(X)。
  • 数据项X的写入时间戳表示为W-timestamp(X)。

时间戳排序协议的工作原理如下：

  • 如果事务Ti发出read(X)操作：

    • 如果TS(Ti) < W-timestamp(X)
      • 操作被拒绝。
    • 如果TS(Ti) >= W-timestamp(X)
      • 操作执行。
    • 所有数据项时间戳更新。

  • 如果事务Ti发出write(X)操作：

    • 如果TS(Ti) < R-timestamp(X)
      • 操作被拒绝。
    • 如果TS(Ti) < W-timestamp(X)
      • 操作被拒绝，并且Ti回滚。
    • 否则，执行操作。

Thomas 写规则

此规则规定，如果 TS(Ti) < W-timestamp(X)，则操作被拒绝，并且 Ti 回滚。

时间戳排序规则可以修改以使调度视图可序列化。

与其让 Ti 回滚，不如忽略“写”操作本身。

DBMS - 死锁

在多进程系统中，死锁是在共享资源环境中出现的一种不希望出现的情况，其中一个进程无限期地等待另一个进程持有的资源。

例如，假设有一组事务 {T0, T1, T2, ...,Tn}。T0 需要资源 X 来完成其任务。资源 X 由 T1 持有，而 T1 正在等待资源 Y，该资源由 T2 持有。T2 正在等待资源 Z，该资源由 T0 持有。因此，所有进程都等待彼此释放资源。在这种情况下，没有一个进程能够完成其任务。这种情况称为死锁。

死锁对系统不利。如果系统陷入死锁，则参与死锁的事务将被回滚或重新启动。

死锁预防

为了防止系统中出现任何死锁情况，DBMS 会积极检查所有事务即将执行的操作。DBMS 会检查这些操作并分析它们是否会造成死锁情况。如果发现可能发生死锁情况，则永远不允许执行该事务。

有一些死锁预防方案使用事务的时间戳排序机制来预先确定死锁情况。

等待-死亡方案

在这种方案中，如果一个事务请求锁定一个资源（数据项），而该资源已被另一个事务以冲突锁持有，则可能发生以下两种情况之一：

  • 如果 TS(Ti) < TS(Tj) - 即请求冲突锁的事务 Ti 比 Tj 旧 - 则允许 Ti 等待，直到数据项可用。

  • 如果 TS(Ti) > TS(tj) - 即 Ti 比 Tj 新 - 则 Ti 死亡。Ti 稍后以随机延迟重新启动，但使用相同的timestamp。

此方案允许较旧的事务等待，但会终止较新的事务。

伤害-等待方案

在这种方案中，如果一个事务请求锁定一个资源（数据项），而该资源已被另一个事务以冲突锁持有，则可能发生以下两种情况之一：

  • 如果 TS(Ti) < TS(Tj)，则 Ti 强制 Tj 回滚 - 即 Ti 伤害 Tj。Tj 稍后以随机延迟重新启动，但使用相同的timestamp。

  • 如果 TS(Ti) > TS(Tj)，则 Ti 被迫等待，直到资源可用。

此方案允许较新的事务等待；但是，当较旧的事务请求较新的事务持有的项时，较旧的事务会强制较新的事务中止并释放该项。

在这两种情况下，后来进入系统的交易都会被中止。

死锁避免

中止事务并非总是实用方法。相反，可以使用死锁避免机制来提前检测任何死锁情况。“等待图”等方法可用，但它们仅适用于那些事务轻量级且资源实例较少的系统。在庞大的系统中，死锁预防技术可能效果更好。

等待图

这是一种简单的可用方法，用于跟踪是否可能出现任何死锁情况。对于进入系统的每个事务，都会创建一个节点。当事务 Ti 请求对某个项目（例如 X）进行锁定，而该项目由另一个事务 Tj 持有时，就会从 Ti 到 Tj 创建一条有向边。如果 Tj 释放项目 X，则它们之间的边将被删除，并且 Ti 会锁定该数据项。

系统为每个等待其他事务持有的某些数据项的事务维护此等待图。系统会不断检查图中是否存在任何循环。

Wait-for Graph

在这里，我们可以使用以下两种方法之一：

  • 首先，不允许任何对已被另一个事务锁定的项目的请求。这并非总是可行的，并且可能导致饥饿，即事务无限期地等待数据项并且永远无法获取它。

  • 第二个选项是回滚其中一个事务。回滚较新的事务并非总是可行的，因为它可能比较旧的事务更重要。借助某些相对算法，可以选择一个要中止的事务。此事务称为**受害者**，该过程称为**受害者选择**。

DBMS - 数据备份

易失性存储丢失

易失性存储（如 RAM）存储所有活动日志、磁盘缓冲区和相关数据。此外，它还存储当前正在执行的所有事务。如果这种易失性存储突然崩溃会发生什么？它显然会带走所有日志和数据库的活动副本。这使得恢复几乎不可能，因为恢复数据所需的一切都丢失了。

在发生易失性存储丢失的情况下，可以采用以下技术：

  • 我们可以在多个阶段设置**检查点**，以便定期保存数据库内容。

  • 易失性内存中活动数据库的状态可以定期**转储**到稳定存储中，其中可能还包含日志和活动事务以及缓冲区块。

  • 每当数据库内容从非易失性内存转储到稳定存储时，都可以在日志文件中标记<dump>。

恢复

  • 当系统从故障中恢复时，它可以恢复最新的转储。

  • 它可以维护重做列表和撤销列表作为检查点。

  • 它可以通过查阅撤销-重做列表来恢复所有事务的状态，直到最后一个检查点。

数据库备份和灾难性故障恢复

灾难性故障是指稳定的辅助存储设备损坏的情况。随着存储设备的损坏，存储在其中的所有宝贵数据都将丢失。我们有两种不同的策略来从这种灾难性故障中恢复数据：

  • 远程备份；此处数据库的备份副本存储在远程位置，以便在发生灾难时可以从中恢复。

  • 或者，可以在磁带上进行数据库备份，并将其存储在更安全的地方。此备份以后可以传输到新安装的数据库中，以将其恢复到备份点。

成熟的数据库过于庞大，无法频繁备份。在这种情况下，我们有一些技术，我们可以仅通过查看其日志来恢复数据库。因此，我们在这里需要做的就是定期备份所有日志。数据库可以每周备份一次，而日志非常小，可以每天或尽可能频繁地备份。

远程备份

如果数据库所在的主要位置遭到破坏，远程备份可以提供安全感。远程备份可以是脱机、实时或在线的。如果它是脱机的，则手动维护。

Remote Data Backup

在线备份系统更实时，并且是数据库管理员和投资者的救星。在线备份系统是一种机制，其中每个实时数据位都会同时在两个不同的位置备份。其中一个直接连接到系统，另一个作为备份保存在远程位置。

一旦主数据库存储失败，备份系统就会感知到故障并将用户系统切换到远程存储。有时这非常迅速，以至于用户甚至意识不到故障。

DBMS - 数据恢复

崩溃恢复

DBMS 是一个高度复杂的系统，每秒执行数百个事务。DBMS 的持久性和鲁棒性取决于其复杂的架构及其底层硬件和系统软件。如果它在事务过程中发生故障或崩溃，则预计系统将遵循某种算法或技术来恢复丢失的数据。

故障分类

为了查看问题发生在哪里，我们将故障概括为以下几个类别：

事务失败

当事务无法执行或到达无法继续执行的点时，它必须中止。这称为事务失败，其中只有少数事务或进程受到影响。

事务失败的原因可能是：

  • **逻辑错误** - 事务由于存在一些代码错误或任何内部错误条件而无法完成。

  • **系统错误** - 数据库系统本身终止活动事务，因为 DBMS 无法执行它，或者它必须由于某些系统条件而停止。例如，在死锁或资源不可用时，系统会中止活动事务。

系统崩溃

存在一些外部问题可能导致系统突然停止并导致系统崩溃。例如，电源中断可能导致底层硬件或软件故障。

示例可能包括操作系统错误。

磁盘故障

在技术发展的早期，硬盘驱动器或存储驱动器经常出现故障，这是一个常见问题。

磁盘故障包括坏扇区的形成、无法访问磁盘、磁盘磁头损坏或任何其他导致所有或部分磁盘存储损坏的故障。

存储结构

我们已经描述了存储系统。简而言之，存储结构可以分为两类：

  • 易失性存储器 −顾名思义，易失性存储器无法在系统崩溃后保留数据。易失性存储设备放置在非常靠近CPU的位置；通常它们嵌入到芯片组本身。例如，主存储器和缓存存储器是易失性存储器的例子。它们速度很快，但只能存储少量信息。

  • 非易失性存储器 −这些存储器能够在系统崩溃后保留数据。它们的数据存储容量很大，但访问速度较慢。示例可能包括硬盘、磁带、闪存和非易失性（电池备份）RAM。

恢复和原子性

当系统崩溃时，可能有多个事务正在执行，并且为它们打开了各种文件以修改数据项。事务由各种操作组成，这些操作本质上是原子的。但根据DBMS的ACID特性，必须维护事务整体的原子性，即要么所有操作都执行，要么都不执行。

当DBMS从崩溃中恢复时，它应该维护以下内容：

  • 它应该检查所有正在执行的事务的状态。

  • 事务可能处于某个操作的中间；在这种情况下，DBMS必须确保事务的原子性。

  • 它应该检查事务现在是否可以完成，或者是否需要回滚。

  • 不允许任何事务使DBMS处于不一致的状态。

有两种类型的技术可以帮助DBMS恢复以及维护事务的原子性：

  • 维护每个事务的日志，并在实际修改数据库之前将其写入某个稳定存储中。

  • 维护影子分页，其中更改在易失性存储器上进行，稍后更新实际数据库。

基于日志的恢复

日志是一系列记录，维护事务执行的操作记录。重要的是，日志在实际修改之前写入并存储在稳定的存储介质上，该介质是故障安全的。

基于日志的恢复的工作原理如下：

  • 日志文件保存在稳定的存储介质上。

  • 当事务进入系统并开始执行时，它会写入关于它的日志。

<Tn, Start>

  • 当事务修改项目X时，它会按如下方式写入日志：

<Tn, X, V1, V2>

它读取Tn已将X的值从V1更改为V2。

  • 当事务完成时，它记录：
<Tn, commit>

可以使用两种方法修改数据库：

  • 延迟数据库修改 −所有日志都写入稳定存储，并在事务提交时更新数据库。

  • 立即数据库修改 −每个日志都跟随实际的数据库修改。也就是说，在每次操作之后立即修改数据库。

并发事务的恢复

当多个事务并行执行时，日志会交错。在恢复时，恢复系统很难回溯所有日志，然后开始恢复。为了简化这种情况，大多数现代DBMS使用“检查点”的概念。

检查点

实时和真实环境中保留和维护日志可能会耗尽系统中所有可用的内存空间。随着时间的推移，日志文件可能会变得太大而无法处理。检查点是一种机制，它会从系统中删除所有以前的日志并将其永久存储在存储磁盘中。检查点声明一个点，在此之前DBMS处于一致状态，并且所有事务都已提交。

恢复

当具有并发事务的系统崩溃并恢复时，它会以以下方式运行：

Recovery

  • 恢复系统从最后到最后一个检查点的末尾反向读取日志。

  • 它维护两个列表，一个撤消列表和一个重做列表。

  • 如果恢复系统看到一个带有<Tn, Start>和<Tn, Commit>或仅<Tn, Commit>的日志，则它将事务放入重做列表中。

  • 如果恢复系统看到一个带有<Tn, Start>但未找到提交或中止日志的日志，则它将事务放入撤消列表中。

然后撤消撤消列表中的所有事务并删除其日志。重做列表及其先前日志中的所有事务将被删除，然后在保存其日志之前重新执行。

打印页面
上一页
下一页
广告