数据库基础知识总结

---

关系数据库的三级结构模式

并行数据库体系结构

并行数据库要求尽可能的并行执行所有的数据库操作，从而在整体上提高数据库系统的性能。根据所在的计算机的处理器（Processor）、内存（Memory）及存储设备（Storage）的相互关系，并行数据库可以归纳为三种基本的体系结构（这也是并行计算的三种基本体系结构），即：

1. 共享内存结构（Shared-Memory)
2. 共享磁盘结构（Shared-Disk）
3. 无共享资源结构（Shared-Nothing）

共享内存（Shared-Memory)结构

该结构包括多个处理器、一个全局共享的内存（主存储器）和多个磁盘存储，各个处理器通过高速通讯网络（InterconnectionNetwork）与共享内存连接，并均可直接访问系统中的一个、多个或全部的磁盘存储，在系统中，所有的内存和磁盘存储均由多个处理器共享。

• 提供多个数据库服务的处理器通过全局共享内存来交换消息和数据，通讯效率很高，查询内部和查询间的并行性的实现也均不需要额外的开销；
• 数据库中的数据存储在多个磁盘存储上，并可以为所有处理器访问；
• 在数据库软件的编制方面与单处理机的情形区别也不大。

这种结构由于使用了共享的内存，所有可以基于系统的实际负荷来动态地给系统中的各个处理器分配任务，从而可以很好地实现负荷均衡。

共享磁盘（Shared-Disk)结构

该结构有多个具有独立内存（主存储器）的处理器和多个磁盘存储构成，各个处理器相互之间没有任何直接的信息和数据的交换，多个处理器和磁盘存储由高速通信网络连接，每个处理器都可以读写全部的磁盘存储。

这种结构常用语实现数据库集群，硬件成本低、可扩充性好、可用性强，且可容易地从单处理器系统迁移，还可以容易地在多个处理器之间实现负载均衡。

无共享资源（Shared-Nothing）结构

该结构由多个完全独立的处理节点构成，每个处理节点具有自己独立的处理器、独立的内存（主存储器）和独立的磁盘存储，多个处理节点在处理级由高速通信网络连接，系统中的各个处理器使用自己的内存独立地处理自己的数据。

这种结构中，每一个处理节点就是一个小型的数据库结构，多个节点一起构成整个的分布式的并行数据库系统。由于每个处理器使用自己的资源处理自己的数据，不存在内存和磁盘的争用，提高的整体性能。另外这种结构具有优良的可扩展性——只需增加额外的处理节点，就可以以线性的比例增加系统的处理能力。

这种结构中，由于数据是各个处理器私有的，因此系统中数据的分布就需要特殊的处理，以尽量保证系统中各个节点的负载基本平衡，但在目前的数据库领域，这个数据分布问题已经有比较合理的解决方案。

由于数据是分布在各个处理节点上的，因此，使用这种结构的并行数据库系统，在扩展时不可避免地导致数据再整个系统范围内的重分布（Re-Distribution）问题。

事务调度

事务的执行由 DBMS 进行调度，在执行事务的过程中加入相关锁指令以控制事务满足 ACID 属性。常用的方式是两段锁协议 2PL ，即事务的加锁和解锁分为两个阶段，第一阶段为所增长阶段，只能加锁不能解锁，第二阶段为锁减少阶段，只能解锁不能加锁。

以阶段划分的编译

词法分析阶段

是编译过程的第一阶段，其任务是对源程序从前到后（从左到右）逐个字符扫描，从中识别出一个个”单词“符号。
词法分析过程的依据是语言的词法规则，即描述”单词“结构的规则。

语法分析阶段

其任务是在词法分析的基础上，根据语言的语法规则将单词符号序列分解成各类语法单位。
通常语法分析是确定整个输入串是否构成一个语法上正确的程序。
一般来说，通过编译的程序，不存在语法上的错误。

语义分析阶段

其任务主要检查源程序是否包含静态语义错误，并收集类型信息供后面的代码生成阶段使用。
语义分析的一个主要工作是进行类型分析和检查。

中间代码生成

其任务是根据语义分析的输出生成中间代码。

目标代码生成

是编译器工作的最后一个阶段。其任务是把中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或汇编指令代码。本阶段与具体机器密切相关。

事务的并发操作

并发操作可能导致：丢失更新、不可重复读、读”脏”数据等问题。

丢失更新是指两个事务 T1 和 T2 读入同一数据并修改， T2 提交的结果破坏了 T1 提交的结果，导致 T1 的修改被丢失。

不可重复读是指事务 T1 读取数据后，事务 T2 执行更新操作，使 T1 无法再现前一次读取结果。

• 事务 T1 ，事务 T2 对其做了修改，事务 T1 再次读。
• 事务 T1 按一定条件从数据库中读，事务 T2 删除了其中部分记录，当 T1 再次按相同的条件读。
• 事务 T1 按一定条件从数据库中读，事务 T2 插入了一些记录，当 T1 再次按照相同条件读。

读“脏”数据是指事务 T1 修改某一数据并将其写回磁盘，事务 T2 读取同一数据后， T1 由于某种原因被撤销，这时 T1 修改过的数据恢复原值，T2 读到的数据就与数据库中的数据不一致，即 T2 读到了“脏”数据。

为了避免出现并发的几种情况，在标准 SQL 规范中，定义了 4 个事务隔离级别，不同的隔离级别对事务的处理不同。

• 未授权读取：也称为读未提交（Read Uncommitted），允许脏数据，但不允许更新丢失。如果一个事务已经开始写数据，则另外一个事务则不允许同时进行写操作，但允许其他事务读此行数据，该隔离级别可以通过“排他写锁”实现。
• 授权读取“也称为读提交（Read Committed），允许不可重复读，但不允许脏数据。这可以通过”瞬间共享读锁“和”排他写锁“实现。读取数据的事务允许其他事务继续访问该行数据，但是未提交的写事务将会禁止其他事务访问该行。
• 可重复读取（Repeatable Read）；禁止不可重复读取和脏读取，但是有时可能出现幻影数据。这可以通过”共享读锁“和”排他写锁
  “实现。读取数据的事务将会禁止写事务（但允许读事务），写事务则禁止任何其他事务。
• 序列化（Serializable）：提供严格的事务隔离。它要求事务序列化执行，事务只能一个接着一个地执行，但不能并发执行。如果仅仅通过”行级锁“是无法实现事务序列化的，必须通过其他机制保证新插入的数据不会被刚执行查询操作的事务访问到。

隔离级别越高，越能保证数据的完整性和一致性，但是对并发性能影响也越大。

软件的可移植性（Portability）

软件的可移植性是指一个软件从一个环境转移到另一个环境运行的能力有关的一组属性。包括：

• 适应性（Adaptability）是指与软件无需采用有别于为该软件准备的活动或手段就可能适应不同的规定环境有关的软件属性。
• 可安装性（Installability）是指与应指定环境下安装软件所需的有关软件的属性。
• 遵循性（一致性，Conformance）是指软件遵循与可移植性有关的标准或约定的软件属性。
• 可替换性（Replaceability）是指与软件在该软件环境中用来替代指定的其他软件的机会和努力有关的软件属性。为避免可能与互操作性（互用性）的含义相混淆，此处用易替换性而不用兼容性。特定软件的易替换性并不隐含此软件可由所考虑的软件所替代。易替换性可能包含易安装性和适应性这两个属性。

二叉排序树

二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：

• 若它的左子树非空，则其左子树上所有的关键字均小于根节点的关键字；
• 若它的右子树非空，则其右子树上所有的关键字均大于根节点的关键字；
• 左、右子树本身就是两棵二叉排序树。

分布式数据库全局概念层

分布式数据库的全局概念层应具有三种模式描述信息；

• 全局概念模式描述分布式数据库全局数据的逻辑结构，是分布式数据库的全局概念视图。
• 分片模式描述全局数据逻辑划分的视图，是全局数据的逻辑结构根据某种条件的划分，每一个逻辑划分就是一个片段或分片。
• 分配模式描述局部逻辑的局部物理结构，是划分后的片段或分片的物理分配视图。

进程间同步与互斥

在系统中，多个进程竞争同一资源可能会发生死锁，若无外力作用，这些进程将永远不能再向前推进。为此，在操作系统的进程管理中最常用的方法是采用信号量（Semaphore）机制。

信号量是表示资源的实体，是一个与队列有关的整型变量，其值仅能由 P、V 操作改变。 “P” 操作是检测信号量是否为正值，若不是，则阻塞调用进程； “V” 操作是唤醒一个阻塞进程恢复执行。根据用途不同，信号量分为公用信号量和私用信号量。公用信号量用于实现进程间的互斥，初值通常设为 1 ，它所联系的一组并行进程均可对它实施 P、V 操作，私用信号量用于实现进程间的同步，初始值通常设为 0 或 n 。

面向对象的分析（OOA)

面向对象的分析是一种面向对象范型的半形式化描述技术。面向对象的分析包括3个步骤：

• 第一步是用例建模。它决定了如何由产品得到各项计算结果，并以用例图和相关场景的方式展现出来。
• 第二步是类建模，它决定了类及其属性，然后确定类之间的关系和交互。
• 最后一步是动态建模，它决定了类或每个子类的行为，并以状态图的形式进行表示。

音频信号的频率范围

人耳能听得到的声音频率范围为 20 ~ 20kHz 。但是根据奈奎斯特定理，如果要保证声音基本不失真， PC 机进行采样时用的频率，应是声音的两倍，计算机对这个声音进行采样用到的频率；范围是： 20 ~ 44.1 KhZ 。

网络规划与设计

以太网交换机根据数据链路层 MAC 地址进行帧交换；
帧中继和 ATM 都是面向连接的通信网，交换机根据预先建立的虚电路标识进行交换。
帧中继的虚电路号是 DLCI ，进行交换的协议数据单元是“帧”；而 ATM 网的虚电路号为 VPI 和 VCI ，进行交换的协议数据单元为“信元”。
三层交换机是指因特网中使用的高档交换机，这种设备把 MAC 交换的高带宽和低延迟优势与网络层分组路由技术结合起来，其工作原理可以概括为：一次路由，多次交换。就是说，当三层交换机第一次收到一个数据包时必须通过路由功能寻找转发端口，同时记住目标 MAC 地址和源 MAC 地址，以及其他相关信息，当再次收到目标地址和源地址相同的帧时就直接进行交换了，不再调用路由功能。所以三层交换机不但具有路由功能，而且比通常的路由器转发得更快。

数据库设计

• 需求分析阶段的任务是：对现实世界要处理的对象（组织、部门、企业等）进行详细调查，在了解现行系统的概况，确定新系统功能的过程中，确定系统边界、搜集支持系统目标的基础数据及其处理方法。
• 逻辑设计阶段的任务之一是对关系模式进一步的规范化处理。因为生成的初始关系模式并不能完全符合要求，还有会数据冗余、更新异常存在，这就需要根据规范化理论对关系模式分解之后，消除冗余和更新异常。

需求分析阶段完成数据流图和数据字典；概念设计阶段完成 E-R 图设计；逻辑设计阶段完成关系模式设计和视图设计；物理设计确定数据的存储结构，并设计索引，以提高查询效率。

开发模型

瀑布模型将软件生存周期各个活动规定为线性顺序连接的若干阶段的模型，规定了由前至后，相互衔接的固定次序，如同瀑布流水，逐级下落。这种方法是一种理想的现象开发模式，缺乏灵活性，特别是无法解决软件需求不明确或不准确的问题。

原型模型从初始的原型逐步演化成最终软件产品，特别适用于对软件需求缺乏准确认识的去情况。

增量开发是把软件产品作为一系列的增量构建来设计、编码、集成和测试，可以在增量开发过程中逐步理解需求。

螺旋将瀑布模型与快速原型模型结合起来，并且加入两种模型均忽略了的风险分析，适用于复杂的大型软件。

运算器与控制器

寄存器是 CPU 中的一个重要组成部分，它是 CPU 内部的临时存储单元。寄存器既可以用来存放数据和地址，也可以存放控制信息或 CPU 工作时的状态。在 CPU 中增加寄存器的数量，可以使 CPU 把执行程序所需的数据尽可能地放在寄存器件中，从而减少访问内存的次数，提高其运行速度。但是寄存器的数目也不能太多，除了增加成本外，由于寄存器地址编码增加也会增加指令的长度。CPU 中的寄存器通常分为存放数据的寄存器、存放地址的寄存器、存放控制信息的寄存器、存放状态信息的寄存器和其他寄存器等类型。

程序计数器用于存放指令的地址。令当程序顺序执行时，每取出一条指令，PC 内容自动增加一个值，指向下一条要取的指令。当程序出现转移时，则将转移地址送入 PC ，然后由 PC 指向新的程序地址。

程序状态寄存器用于记录运算中产生的的标志信息，典型的标志位为有进位标志、零标志位、符号标志位、溢出标志位、奇偶标志位等。

地址寄存器通常简称为累加器，它是一个通用寄存器。其功能是当运算器的算术逻辑单元执行算术或逻辑运算时，为 ALU 提供一个工作区。例如，在执行一个减法运算前，先将被减数取出放在累加器中，再从内存储器取出减数，然后同累加器的内容相减，所得的结果送回累加器中。累加器在运算过程中暂时存放被操作数和中间运算结果，累加器不能用于长时间地保存一个数据。

指令寄存器：一般用来保存当前正在执行的一条指令。
地址寄存器：一般用来保存当前 CPU 所访问的内存单元的地址，以方便对内存的读写操作。

设计 RISC

在设计 RISC 时，需要遵循如下一些基本的原则：

• 指令条数少，一般为几十条指令。
• 寻址方式尽可能少。
• 采用等长指令，不管功能复杂的指令还是简单的指令，均用同一长度。
• 设计尽可能多的通用寄存器。

风险管理

风险是一种具有负面后果的、人们不希望发生的事件。风险管理是软件项目管理的一项重要任务。在进行风险管理时，根据风险的优先级来确定风险控制策略，而优先级是根据风险暴露来确定的。风险暴露是一种量化风险影响的指标，等于风险影响乘以风险概率。风险影响是当风险发生时造成的损失。风险概率是风险发生的可能性。风险控制是风险管理的一个重要活动。

数据挖掘常用的技术

• 离群点：在样本空间中，与其他样本点的一般行为或特征不一致的点。
• 分类：分类分析的内容有分析在此样本情况下能够被分类的程度，并且依据此分析重新分布数据，使得数据更容易被分析，相关技术有多类别分析、主成分分析。
• 聚类：聚类分析是指将物理或抽象的集合分组成为由类似的对象组成的多个类的分析过程。它是一种重要的人类行为。聚类分析的目标就是在相似的基础上收集数据来分类。聚类与分类的不同在于，聚类所要求划分的类是未知的。分类和聚类的区别：分类要靠学习，聚类要靠启发式搜索。
• 关联规则：其核心是基于两阶段频繁集思想的递推算法。该关联规则在分类上属于单维、单层及布尔关联规则，典型的算法是 Aprior 算法。Aprior 算法将发现关联规则的过程分为两个步骤：第一步通过迭代，检索出事务数据库中所有频繁项集，即支持度不低于用户设定的阈值的项集；第二步利用频繁项集构造出满足用户最小信任度的规则。其中，挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。

电子邮件协议

• POP3(Post Office Protocol 3) 协议是适用于 C/S 结构的脱机模型的电子邮件协议。
• SMTP(Simple Mail Transfer Protocol) 协议是简单邮件传输协议。
• IMAP(Internet Message Access Protocol) 是由美国华盛顿大学所研发的一种邮件获取协议。
• MPLS(Multiprotocol Label Switch) 即多协议标记交换，是一种标记（label）机制的交换技术。

编译与解释

• 符号表：符号表是一种用于语言翻译器（例如编译器和解释器）中的数据结构。在符号表中，程序源代码中的每个标示符都和它的声明或使用信息绑定在一起，比如数据类型、作用域以及内存地址。
• 哈希表：也叫散列表，是根据关键码（key value）而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
• 动态查找表：动态查找表的表结构本身是在查找过程中动态生成的，即对于给定值 key，若表中存在其关键字等于 key 的记录，则查找成功返回，否则插入关键字等于 key 的记录。
• 栈和队列：基本的数据结构。栈的基本特点是“后进先出”，而队列的基本特点是“先进先出”。

ARP

ARP 协议的作用是由目标地址的 IP 地址发现对应的 MAC 地址。如果源站要和一个新的目标通信，首先由源站发出 ARP 请求广播包，其中包含目标的 IP 地址，然后目标返回 ARP 应答包，其中包含了自己的 MAC 地址。这时，源站一方面把目标的 MAC 地址装入要发送的数据帧中，一方面把得到的 MAC 地址添加到自己的 ARP 表中。当一个站与多个目标进行了通信后，在其 ARP 表就积累了多个事项，每一项都是 IP 地址与 MAC 地址的映射关系。 ARP 表通常用于由 IP 地址查找对应的 MAC 地址。

编译程序与解释程序

编译程序的功能是把高级语言书写的源程序翻译成与之等价的目标程序。编译过程划分成词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成 6 个阶段。目标程序可以独立于源程序运行。

解释程序是一种语言处理程序，在词法、语法和语义分析方面与编译程序的工作原理基本相同，但在运行用户程序程序时，它是直接执行源程序或源代码的内部形式（中间代码）。因此，解释程序并不产生目标程序，这是它和编译程序的主要区别。

概念结构设计

数据库的设计阶段分为四个阶段：需求分析阶段、概念结构设计阶段、逻辑结构设计阶段和物理结构设计阶段。数据库概念结构设计阶段是在需求分析的基础上，依照用户需求对信息进行分类、聚集和概括，建立概念模型。

E-R 模型

在扩展 E-R 图设计方法中，联系可以被看做实体，参与另一个联系；联系只能产生于实体（或被当作实体的联系）之间；属性只能依附于实体或联系用以刻画该实体或联系；语义上不属于某个实体或联系的属性不能作为其属性。E-R 图是对现实的描述，符合现实语义。联系对应的是事件，三元联系的事件既有三个参与方，而两两联系是两个参与方，描述的现实语义不同。

防火墙技术

包过滤防火墙工作在网络协议 IP 层，它只对 IP 包的源地址、目标地址及相应端口进行处理，因此速度比较快，能够处理的并发连接比较多，缺点是对应用层的攻击无能为力，包过滤成本与它的安全性能没有因果关系，而应用程序和用户对于包过滤的过程并不需要了解，因此该技术对应用和用户是透明的。
代理服务器防火墙收到的 IP 包还原成高层协议的通讯故障，比如 http 连接信息，因此能够对基于高层协议的攻击进行拦截。缺点是处理速度比较慢，能够处理的并发数比较少，所以不能提高网络整体性能，而代理对于用户认证可以设置。

UML 语言

• 类图（class diagram）：展现了一组对象、接口、协作和它们之间的关系。在面向对象系统的建模中所建立的最常见的图就是类图。类图给出系统的静态设计视图。包含主动类的类图给出了系统的静态进程视图。
• 对象图（object diagram）：展现了一组对象以及它们之间的关系。对象图描述了在类图中所建立的事物实例的静态快照。和类图相同，这些图给出系统的静态设计视图或静态进程视图，但它们是从真实的或原型实例的角度建立的。
• 用例图（user case diagram）：展现了一组用例、参与者（actor）以及它们之间的关系。用例图给出系统的静态用例视图。这些图对系统的行为进行组织和建模是非常重要的。
• 序列图（use case diagram）：是场景（scenario）的图形化表示，描述了以时间顺序组织的对象之间的交互活动。
• 协作图（callaboration diagram 或 communication diagram）：强调收发消息的对象的结构组织。序列图和协作图都是交互图（interaction diagram）。交互图展现了一种交互，它由一组对象和它们之间的关系组成，包括它们之间可能发送的消息。交互图关注系统的动态视图。序列图和协作图是同构的，它们之间可以相互转换。
• 状态图（statechart diagram）：展现了一个状态机，它由状态、转换、事件和活动组成。状态图关注系统的动态视图，它对于接口、类和协作的行为建模尤为重要，它强调对象行为的时间顺序。
• 活动图（activity diagram）：是一种特殊的状态图，它展现了在系统内从一个活动到另一个活动的流程。活动图专注于系统的动态视图。它对于系统的功能建模特别重要，并强调对象间的控制流程。
• 构件图（component diagram）：展现了一组构件之间的组织和依赖。构件图专注于系统的静态实现视图。它与类图相关，通常把构件映射为一个或多个类、接口或协作。
• 部署图（deployment diagram）：展现了运行处理节点以及其中构件的配置。部署图给出了体系结构的静态实施视图。它与构件视图相关，通常一个节点包含一个或多个构件。

寻址方式

指令中的寻址方式就是如何对指令中的地址字段进行解释，以获得操作数的方法或获得程序转移地址的方法。常用的寻址方式有：

• 立即寻址：操作数就包含在指令中
• 直接寻址：操作数存放在内存单元中，指令中直接给出操作数所在的存储单元的地址
• 寄存器寻址：操作数存放在某一寄存器中，指令中给出存放操作数所在的寄存器名
• 寄存器间接寻址：操作数存放在内存单元中，操作数所在存储单元的地址在某个寄存器中
• 间接寻址：指令中给出操作数地址的地址
• 相对寻址：指令地址码给出的是一个偏移量（可正可负），操作数地址等于本条指令的地址加上偏移量
• 变址寻址：操作数地址等于变址寄存器的内容加偏移量

软件测试

• 回归测试是指修改了旧代码后，重新进行测试以确认修改没有引入新的错误或导致其他代码产生错误。
• 接受测试是基于客户或最终用户的规格书的最终测试，或基于用户一段时间的使用后，看软件是否满足客户要求。一般从功能、用户界面、性能、业务关联性进行测试。
• Installing testing（安装测试），确保该软件在正常情况和异常情况的不同条件下，例如，进行首次安装、升级、完整的或自定义的安装都能进行安装。异常情况包括磁盘空间不足、缺少目录创建权限等。核实软件在安装后可立即正常运行。安装测试包括测试安装代码以及安装手册。安装手册提供如何进行安装，安装代码提供安装一些程序能够进行的基础数据。
• 单元测试（unit testing），是指对软件中的最小可测试单元进行检查和验证。