时间过得很快，四季轮回的过程中，一年忙碌的工作时间结束。在这一年的工作中，大家通过工作，可学到更多方面的工作知识，也留下了众多的学习回忆。为记录这一年的成长，可编写一份年终总结。以下是小编精心整理的《数据库考试期末总结》相关资料，欢迎阅读！
第一篇：数据库考试期末总结
数据库考试期末总结
第1章 数据库系统概述
1、基本概念
• 数据库、数据库管理系统、数据库系统 • 数据库系统的特点和功能 • 数据抽象
– 三种数据抽象能力 – 三种数据库模式 – 两种数据独立性
• 数据库系统的用户 • 数据模型、数据库语言 • 数据库管理系统的结构
2、重点
• 数据库、数据库管理系统、数据库系统 • 两种数据独立性
第2章 关系数据库系统
1、知识点
• 关系数据模型
– 数据结构 – 完整性约束 – 操作
• 关系运算的安全性
• 关系代数、元组关系演算、域关系演算的等价性 • SQL – 交互式 – 嵌入式
2、基本概念
• 关系、属性、元组、关系模式、关系实例 • 关系的性质
• 候选键、主键、键属性、非键属性、外部键 • 实体完整性约束、关联完整性约束 • 关系代数操作的定义
• 关系代数的基本操作和附加操作 • 专门的关系运算 • SQL语言的子语言
• 每个SQL语句的功能及语法格式
3、重点
• 关系数据模型 • 关系代数 • SQL语句
第3章 数据库的安全性与完整性
1、知识点 • 安全性
– 定义
– 需要解决的问题 – 解决的方法
• 完整性
– 定义 – 类型
– 定义和验证方法
2、基本概念 • 安全性的定义 • 完整性的定义 • 完整性的类型
第4章 数据库设计概述与需求分析
1、基本概念 • DB设计的任务 • DB的生命周期 • DB的设计过程 • DB的需求分析的任务、目标、步骤
第5章 概念数据库设计
1、知识点
• 实体联系模型(ER模型) • 实体、实体型
• 实体的属性、实体的属性值、复合属性、单值属性、多值属性、导出属性、空值
• 键、简单键、复合键 • 实体间的联系
• 实体对应约束(1:
1、1:n、m:n)、实体关联约束(全域关联约束、部分关联约束)
• 弱实体型、弱实体、识别实体型、识别联系 • 弱实体型的部分键 • ER图
2、基本概念
• 复合属性、多值属性、导出属性 • 1:
1、1:n、m:n联系 • 概念数据库设计的任务 • 概念数据库设计的目标 • 概念数据库设计的步骤
• 概念数据库设计的方法、视图综合设计方法 • 概念数据库设计的策略
3、重点 • ER图
第6章 逻辑数据库设计
1、知识点
• 形成初始关系模式
– 普通实体、弱实体、多值属性、各种联系
• 函数依赖、完全函数依赖、部分函数依赖、传递函数依赖 • 给定关系实例，求函数依赖集 • Armstrong公理系统、三条推理规则 • 求属性闭包、求候选键
• 两个函数依赖集等价的判定、求最小函数依赖集 • 关系模式的规范形式
– 1NF、2NF、3NF、BCNF • 关系模式的规范化方法
– 无损连接性、函数依赖保持性、判别方法 – 关系模式的分解算法
2、基本概念
• 逻辑数据库设计的任务 • 逻辑数据库设计的目标 • 逻辑数据库设计的步骤 • 初始关系模式可能存在的问题
• 函数依赖、完全函数依赖、部分函数依赖、传递函数依赖 • Armstrong公理系统、三条推理规则 • 1NF、2NF、3NF、BCNF •
3、重点
• 形成初始关系模式，并指出每个关系模式的主键和外键 • 给定关系实例，求函数依赖集 • 求属性闭包、求候选键 • 判断两个函数依赖集等价
• 求与给定函数依赖集等价的最小函数依赖集 • 判断一个关系模式最高属于几范式 • 判断给定的分解是否具有无损连接性 • 关系模式的3NF、BCNF分解算法
第7章 物理数据库设计
1、知识点 • 物理数据库设计的任务 • 物理数据库设计的步骤
第8章 物理存储结构
1、知识点
• 物理存储设备
– 磁盘的存储特性和访问特性
• 磁盘冗余技术 • 文件和文件记录
• 各种文件结构的存储空间和查询时间的计算 • 各种索引的存储空间和查询时间的计算
2、基本概念 • 记录
• 定长记录文件、边长记录文件 • 跨块记录、非跨块记录 • 无序文件、有序文件 • 索引域、索引文件、索引记录 • 稀疏索引、稠密索引 • 主索引、辅助索引、聚集索引 • B树、B+树
3、重点
• 各种文件和索引占用的空间计算 • 利用各种文件和索引的查询时间的计算
第9章 数据库管理系统的数据字典
1、重点
• 数据字典的概念 • 数据字典中存储的信息
• 把数据字典作为普通关系处理具有两个优点
第10章 关系代数操作的实现算法
1、重点
• 查询处理的过程
• 各个关系代数操作的算法及代价分析
第11章 查询优化技术
1、知识点
• 关系代数的等价变换规律 • 启发式代数优化规则 • 初始关系代数表达式
• 关系代数表达式到查询树的转换 • 启发式关系代数优化算法 • 基于复杂性估计的查询优化算法 • 语义查询优化方法
2、重点
• 关系代数的等价变换规律 • 启发式代数优化规则 • 初始关系代数表达式
• 关系代数表达式到查询树的转换 • 启发式关系代数优化算法
第12章 并发控制技术
1、知识点 • 事务
• 不对并发事务进行控制导致的问题 • 事务的性质
• 事务的调度、串行调度、并行调度 • 可串行的调度 • 冲突 • 冲突等价 • 冲突可串行
• 冲突可串行的测试方法 • 两段锁协议
2、基本概念
• 事务处理包括哪两方面的内容 • 不对并发事务进行控制导致的问题
• 事务、事务的状态、事务的性质、事务的原子性 • 调度、串行调度、并行调度、可串行调度 • 冲突、冲突等价、冲突可串行
3、重点 • 基本概念
• 冲突可串行的测试方法
• 两段锁协议
第13章 数据库恢复技术
1、知识点 • 日志 • 日志的内容 • 日志的产生过程
• 使用日志进行系统恢复的方法
2、重点
• 使用推迟更新技术(REDO日志技术)和即时更新技术(UNDO/REDO日志)进行系统恢复的方法，包括恢复时所做的操作以及恢复后数据库中数据项的值。
第二篇： 2012年数据结构期末考试题及答案
一、选择题
1．在数据结构中，从逻辑上可以把数据结构分为
C
。
A．动态结构和静态结构
B．紧凑结构和非紧凑结构
C．线性结构和非线性结构
D．内部结构和外部结构
2．数据结构在计算机内存中的表示是指 A
。
A．数据的存储结构
B．数据结构
C．数据的逻辑结构
D．数据元素之间的关系
3．在数据结构中，与所使用的计算机无关的是数据的
A 结构。
A．逻辑
B．存储
C．逻辑和存储
D．物理
4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储
C
。
A．数据的处理方法
B．数据元素的类型
C．数据元素之间的关系
D．数据的存储方法
5．在决定选取何种存储结构时，一般不考虑
A 。
A．各结点的值如何
B．结点个数的多少
C．对数据有哪些运算
D．所用的编程语言实现这种结构是否方便。
6．以下说法正确的是 D
。
A．数据项是数据的基本单位
B．数据元素是数据的最小单位
C．数据结构是带结构的数据项的集合
D．一些表面上很不相同的数据可以有相同的逻辑结构
7．算法分析的目的是 C ，算法分析的两个主要方面是 A
。
（1）A．找出数据结构的合理性
B．研究算法中的输入和输出的关系
C．分析算法的效率以求改进
C．分析算法的易读性和文档性
（2）A．空间复杂度和时间复杂度
B．正确性和简明性
C．可读性和文档性
D．数据复杂性和程序复杂性
8．下面程序段的时间复杂度是 O（n2）
。
s ＝0；
for（ I ＝0； i＜n； i＋＋）
for（j＝0；j＜n；j＋＋）
s ＋＝B[i][j]；
sum ＝ s ；
9．下面程序段的时间复杂度是 O（n*m）
。
for（ i ＝0； i＜n； i＋＋）
for（j＝0；j＜m；j＋＋）
A[i][j] ＝ 0；
10．下面程序段的时间复杂度是 O（log3n）
。
i ＝ 0；
while（i＜＝n）
i ＝ i * 3；
11．在以下的叙述中，正确的是
B 。
A．线性表的顺序存储结构优于链表存储结构
B．二维数组是其数据元素为线性表的线性表
C．栈的操作方式是先进先出
D．队列的操作方式是先进后出
12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 B 。
A．数据元素具有同一特点
B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致
C．每个数据元素都一样
D．数据元素所包含的数据项的个数要相等
13．链表不具备的特点是
A 。
A．可随机访问任一结点
B．插入删除不需要移动元素
C．不必事先估计存储空间
D．所需空间与其长度成正比
14．不带头结点的单链表head为空的判定条件是
A
。
next ＝＝NULL
C．head－＞next ＝＝head
D head！＝NULL
15．带头结点的单链表head为空的判定条件是
B
。
next ＝＝NULL
C．head－＞next ＝＝head
D head！＝NULL
16．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用
D
存储方式最节省运算时间。
A．单链表
B．给出表头指针的单循环链表
C．双链表
D．带头结点的双循环链表
17．需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是
B 。
A．单链表
B．静态链表
C．线性链表
D．顺序存储结构
18．非空的循环单链表head的尾结点（由p所指向）满足 C 。
A．p－＞next ＝＝ NULL
B．p ＝＝ NULL
C．p－＞next ＝＝head
D．p ＝＝ head
19．在循环双链表的p所指的结点之前插入s所指结点的操作是
D 。
A．p－＞
prior－＞
prior
B．p－＞
prior－＞
prior
C．s－＞
prior－＞next ＝ s
D．s－＞
prior－＞
prior ＝ s
20．如果最常用的操作是取第i个结点及其前驱，则采用 D 存储方式最节省时间。
A．单链表
B．双链表
C．单循环链表
D．顺序表
21．在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 B 。
A．O（1）
B．O（n）
C．O（n2）
D．O（nlog2n）
22．在一个长度为n（n＞1）的单链表上，设有头和尾两个指针，执行
B 操作与链表的长度有关。
A．删除单链表中的第一个元素
B．删除单链表中的最后一个元素
C．在单链表第一个元素前插入一个新元素
D．在单链表最后一个元素后插入一个新元素
23．与单链表相比，双链表的优点之一是 D 。
A．插入、删除操作更简单
B．可以进行随机访问
C．可以省略表头指针或表尾指针
D．顺序访问相邻结点更灵活
24．如果对线性表的操作只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用
B 。
A．只有表头指针没有表尾指针的循环单链表
B．只有表尾指针没有表头指针的循环单链表
C．非循环双链表
D．循环双链表
25．在长度为n的顺序表的第i个位置上插入一个元素（1≤ i ≤n＋1），元素的移动次数为：
A 。
A．n – i ＋
1B．n – i
C．i
D．i – 1
26．对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为
C
。
A．顺序表
B．用头指针表示的循环单链表
C．用尾指针表示的循环单链表
D．单链表
27．下述哪一条是顺序存储结构的优点?
C
。
A插入运算方便
B可方便地用于各种逻辑结构的存储表示
C存储密度大
D删除运算方便
28．下面关于线性表的叙述中，错误的是哪一个?
B
。
A线性表采用顺序存储，必须占用一片连续的存储单元
B线性表采用顺序存储，便于进行插入和删除操作。
C线性表采用链式存储，不必占用一片连续的存储单元
D线性表采用链式存储，便于进行插入和删除操作。
29．线性表是具有n个
B 的有限序列。
A．字符
B．数据元素
C．数据项
D．表元素
30．在n个结点的线性表的数组实现中，算法的时间复杂度是O（1）的操作是
A 。
A．访问第i（1＜＝i＜＝n）个结点和求第i个结点的直接前驱（1＜i＜＝n）
B．在第i（1＜＝i＜＝n）个结点后插入一个新结点
C．删除第i（1＜＝i＜＝n）个结点
D．以上都不对
31．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为C。
A．O（0）
B．O（1）
C．O（n）
D．O（n2）
32．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为
C
。
A．O（n） O（n）
B．O（n） O（1）
C．O（1） O（n）
D．O（1） O（1）
33．线性表（a1，a2， „，an）以链式方式存储，访问第i位置元素的时间复杂度为
C
。
A．O（0）
B．O（1）
C．O（n）
D．O（n2）
34．单链表中，增加一个头结点的目的是为了 C
。
A．使单链表至少有一个结点
B．标识表结点中首结点的位置
C．方面运算的实现
D．说明单链表是线性表的链式存储
35．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是
B 。
A．p－＞
next＝p－＞
next＝p－＞
next＝s；
C．p－＞
next＝s－＞
next＝s－＞next；p－＞next＝s
36．线性表的顺序存储结构是一种 A 。
A．随机存取的存储结构
B．顺序存取的存储结构
C．索引存取的存储结构
D．Hash存取的存储结构
37．栈的特点是
B ，队列的特点是 A
。
A．先进先出
B．先进后出
38．栈和队列的共同点是 C 。
A．都是先进后出
B．都是先进先出
C．只允许在端点处插入和删除元素
D．没有共同点
39．一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是
C 。
A．edcba
B．decba
C．dceab
D．abcde
40．设有一个栈，元素依次进栈的顺序为A、B、C、D、E。下列
C 是不可能的出栈序列。
A．A，B，C，D，E
B．B，C，D，E，A
C．E，A，B，C，D
D．E，D，C，B，A
41．以下
B 不是队列的基本运算?
A．从队尾插入一个新元素
B．从队列中删除第i个元素
C．判断一个队列是否为空
D．读取队头元素的值
42．若已知一个栈的进栈序列是1，2，3，，n，其输出序列为p1，p2，p3，„，pn，若p1＝n，则pi为
C
。
A．i
B．n－i
C．n－i＋
1D．不确定
43．判定一个顺序栈st（最多元素为MaxSize）为空的条件是 B 。
A．st－＞top ！
top ＝＝－1
C．st－＞top ！
top ＝＝ MaxSize
44．判定一个顺序栈st（最多元素为MaxSize）为满的条件是 D 。
A．st－＞top ！
top ＝＝－1
C．st－＞top ！
top ＝＝ MaxSize
45．一个队列的入队序列是1，2，3，4，则队列的输出序列是 B 。
A．4，3，2，1
B．1，2，3，4
C．1，4，3，
2D．3，2，4，1
46．判定一个循环队列qu（最多元素为MaxSize）为空的条件是 C 。
A．qu－＞rear – qu－＞
rear – qu－＞front －1＝＝MaxSize
C．qu－＞
front －1
47．在循环队列中，若front与rear 分别表示对头元素和队尾元素的位置，则判断循环队列空的条件是
C
。
A．front＝＝rear＋1
B．rear＝＝front＋1
C．front＝＝rear
D．front＝＝0
48．向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行 D 操作。
A．h－＞
next＝h ；
C．s－＞
next＝h－＞
next＝s ；
49．输入序列为ABC，可以变为CBA时，经过的栈操作为
B 。
A．push，pop，push，pop，push，pop
B．push，push，push，pop， pop， pop
C．push，push，pop， pop，push，pop
D．push，pop，push，push，pop， pop
50．若栈采用顺序存储方式存储，现两栈共享空间V[1 m]，top[1]、top[2]分别代表第1和第2个栈的栈顶，栈1的底在V[1]，栈2的底在V[m]，则栈满的条件是
B 。
A．|top[2]－top[1]|＝0
B． top[1]＋1＝top[2]
C．top[1]＋top[2]＝m
D．top[1]＝top[2]
51．设计一个判别表达式中左、右括号是否配对出现的算法，采用 D 数据结构最佳。
A．线性表的顺序存储结构
B．队列
C．线性表的链式存储结构
D．栈
52．允许对队列进行的操作有 D
。
A．对队列中的元素排序
B．取出最近进队的元素
C．在队头元素之前插入元素
D．删除队头元素
53．对于循环队列
D
。
A．无法判断队列是否为空
B．无法判断队列是否为满
C．队列不可能满
D．以上说法都不对
54．若用一个大小为6的数值来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为
B 。
A．1和
5 B．2和
4 C．4和
2D．5和1
55．队列的“先进先出”特性是指
D
。
A．最早插入队列中的元素总是最后被删除
B．当同时进行插入、删除操作时，总是插入操作优先
C．每当有删除操作时，总是要先做一次插入操作
D．每次从队列中删除的总是最早插入的元素
56．和顺序栈相比，链栈有一个比较明显的优势是 A 。
A．通常不会出现栈满的情况
B．通常不会出现栈空的情况
C．插入操作更容易实现
D．删除操作更容易实现
57．用不带头结点的单链表存储队列，其头指针指向队头结点，尾指针指向队尾结点，则在进行出队操作时
C
。
A．仅修改队头指针
B．仅修改队尾指针
C．队头、队尾指针都可能要修改
D．队头、队尾指针都要修改
58．若串S＝‘software’，其子串的数目是
B 。
A．8
B．37
C．36
D．9
59．串的长度是指 B 。
A．串中所含不同字母的个数
B．串中所含字符的个数
C．串中所含不同字符的个数
D．串中所含非空格字符的个数
60．串是一种特殊的线性表，其特殊性体现在 B 。
A．可以顺序存储
B．数据元素是一个字符
C．可以链式存储
D．数据元素可以是多个字符
61．设有两个串p和q，求q在p中首次出现的位置的运算称为 B
。
A．连接
B．模式匹配
C．求子串
D．求串长
62．数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放的存储器内，该数组按行存放，元素A[8][5]的起始地址为
C 。
A．SA＋141 B． SA＋14
4 C．SA＋22
2D．SA＋225
63．数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放的存储器内，该数组按行存放，元素A[5][8]的起始地址为
C 。
A．SA＋141 B． SA＋180
C．SA＋222
D．SA＋225
64．若声明一个浮点数数组如下： froat average[]＝new float[30]；
假设该数组的内存起始位置为200， average[15]的内存地址是 C
。
A．214
B．21
5C．260
D．256
65．设二维数组A[1„ m，1„ n]按行存储在数组B中，则二维数组元素A[i，j]在一维数组B中的下标为
A 。
A．n*（i－1）＋j B． n*（i－1）＋j－
1C．i*（j－1）
D．j*m＋i－1
66．有一个100×90的稀疏矩阵，非0元素有10，设每个整型数占2个字节，则用三元组表示该矩阵时，所需的字节数是
B
。
A．20
B． 66
C．18 000
D．33
67．数组A[0 „ 4，－1 „－3，5 „7]中含有的元素个数是 A
。
A．55
B． 45
C．36
D．16
68．对矩阵进行压缩存储是为了
D
。
A．方便运算 B．方便存储
C．提高运算速度
D．减少存储空间
69．设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a1，1为第一个元素，其存储地址为1，每个元素占1个地址空间，则a8，5的地址为 B 。
A．13 B． 3
3 C．18
D．40
70．稀疏矩阵一般的压缩存储方式有两种，即 C 。
A．二维数组和三维数组
B． 三元组和散列
C．三元组和十字链表
D． 散列和十字链表
71．树最适合用来表示
C 。
A．有序数据元素
B．无序数据元素
C．元素之间具有分支层次关系的数据
D．元素之间无联系的数据
72．深度为5的二叉树至多有
C 个结点。
A．16
B． 32
C． 31
C．
73．对一个满二叉树，m个叶子，n个结点，深度为h，则 D 。
A．n ＝ h＋m
B h＋m ＝ 2n
C m ＝ h－1
D n ＝ 2h－1
74．任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序
A 。
A．不发生改变
B．发生改变
C．不能确定
D．以上都不对
75．在线索化树中，每个结点必须设置一个标志来说明它的左、右链指向的是树结构信息，还是线索化信息，若0标识树结构信息，1标识线索，对应叶结点的左右链域，应标识为__ D __。
A．00
B．0
1C．10
D．11
76．在下述论述中，正确的是
D 。
①只有一个结点的二叉树的度为0；②二叉树的度为2；③二叉树的左右子树可任意交换；
④深度为K的顺序二叉树的结点个数小于或等于深度相同的满二叉树。
A．①②③
B．②③④
C．②④
D．①④
77．设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树的结点个数为n，森林F中第一棵树的结点的个数是
A
。
A．m－n
B．m－n－1
C．n＋1
D．不能确定
78．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是 B 。
A．9
B．11
C．1
5D．不能确定
79．具有10个叶子结点的二叉树中有
B 个度为2的结点。
A．8
B．9
C．10
D．11
80．在一个无向图中，所有顶点的度数之和等于所有边数的 C 倍。
A．1/
2B 1
C 2
D 4
81．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 B 倍。
A．1/2
B 1
C 2
D 4
82．某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为：
C
A．
3 B．2
C．
4 D．5
83．已知一算术表达式的中缀形式为A＋B *C–D/E，后缀形式为ABC *＋DE/–，其前缀形式为
D
。
A．–A＋B*C/DE
B．–A＋B*CD/E
C –＋*ABC/DE
D．–＋A*BC/DE
84．已知一个图，如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为____D___；按广度搜索法进行遍历，则可能得到的一种顶点序列为___A___；
①A．a，b，e，c，d，f
B．a，c，f，e，b，d C．a，e，b，c，f，d，
D．a，e，d，f，c，b
②A．a，b，c，e，d，f
B．a，b，c，e，f，d C．a，e，b，c，f，d，
D．a，c，f，d，e，b
85．采用邻接表存储的图的深度优先遍历算法类似于二叉树的___A____。
A．先序遍历
B．中序遍历
C．后序遍历
D．按层遍历
86．采用邻接表存储的图的广度优先遍历算法类似于二叉树的___D____。
A．先序遍历
B．中序遍历
C．后序遍历
D．按层遍历
87．具有n 个结点的连通图至少有
A 条边。
A． n－1
B． n
C． n（n－1）/2
D． 2n
88．广义表（（a），a）的表头是 C ，表尾是 C 。
A．a
B （）
C （a）
D （（a））
89．广义表（（a））的表头是 C ，表尾是 B 。
A．a
B （）
C （a）
D （（a））
90．顺序查找法适合于存储结构为
B 的线性表。
A 散列存储
B 顺序存储或链式存储
C 压缩存储
D 索引存储
91．对线性表进行折半查找时，要求线性表必须 B
。
A 以顺序方式存储
B 以顺序方式存储，且结点按关键字有序排列
C 以链式方式存储
D 以链式方式存储，且结点按关键字有序排列
92．采用折半查找法查找长度为n的线性表时，每个元素的平均查找长度为
D 。
A O（n2）
B O（nlog2n）
C O（n）
D O（log2n）
93．有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当折半查找值为82的结点时， C
次比较后查找成功。
A． 11
B 5
C
4D
94．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法
B 。
A 正确
B 错误
95．下面关于B树和B＋树的叙述中，不正确的结论是
A
。
A B树和B＋树都能有效的支持顺序查找
B B树和B＋树都能有效的支持随机查找
C B树和B＋树都是平衡的多叉树
D B树和B＋树都可用于文件索引结构
96．以下说法错误的是
B
。
A．散列法存储的思想是由关键字值决定数据的存储地址
B．散列表的结点中只包含数据元素自身的信息，不包含指针。
C．负载因子是散列表的一个重要参数，它反映了散列表的饱满程度。
D．散列表的查找效率主要取决于散列表构造时选取的散列函数和处理冲突的方法。
97．查找效率最高的二叉排序树是 C
。
A．所有结点的左子树都为空的二叉排序树。
B．所有结点的右子树都为空的二叉排序树。
C．平衡二叉树。
D．没有左子树的二叉排序树。
98．排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为
C
。
A．希尔排序
B。冒泡排序
C插入排序
D。选择排序
99．在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是 D 。
A．希尔排序
B．冒泡排序
C．直接插入排序
D．直接选择排序
100．堆是一种有用的数据结构。下列关键码序列
D 是一个堆。
A．94，31，53，23，16，7
2 B．94，53，31，72，16，23
C．16，53，23，94，31，72
D．16，31，23，94，53，72
101．堆排序是一种
B
排序。
A．插入
B．选择
C．交换
D．归并
102．
D 在链表中进行操作比在顺序表中进行操作效率高。
A．顺序查找
B．折半查找
C．分块查找
D．插入
103．直接选择排序的时间复杂度为
D 。（n 为元素个数）
A．O（n）
B．O（log2n）
C．O（nlog2n）
D． O（n2）
二、填空题。
1．数据逻辑结构包括 线性结构 、 树形结构 和 图状结构 三种类型，树形结构和图状结构合称非线性结构 。
2．数据的逻辑结构分为
集合
、线性结构 、 树形结构 和 图状结构 4种。
3．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点没有 后续结点，其余每个结点有且只有 1 个后续结点。
4．线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在 多对多 关系。
5．在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点可以 任意多个 。
6．数据结构的基本存储方法是顺序 、 链式 、 索引 和 散列 存储。
7．衡量一个算法的优劣主要考虑正确性、可读性、健壮性和时间复杂度与空间复杂度。
8．评估一个算法的优劣，通常从 时间复杂度 和 空间复杂度 两个方面考察。
9．算法的5个重要特性是 有穷性 、 确定性、 可行性 、输入和输出。
10．在一个长度为n的顺序表中删除第i个元素时，需向前移动 n－i－1 个元素。
11．在单链表中，要删除某一指定的结点，必须找到该结点的 前驱 结点。
12．在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。
13．在顺序表中插入或删除一个数据元素，需要平均移动 n 个数据元素，移动数据元素的个数与位置有关。
14．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是，应采用 顺序 存储结构。
15．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成
单链表 和双链表。
16．顺序存储结构是通过下标 表示元素之间的关系的；链式存储结构是通过 指针表示元素之间的关系的。
17．带头结点的循环链表L中只有一个元素结点的条件是 L－＞next－＞next＝L 。
18． 栈 是限定仅在表尾进行插入或删除操作的线性表，其运算遵循 后进先出 的原则。
19．空串是零个字符的串 ，其长度等于零。空白串是由一个或多个空格字符组成的串，其长度等于其包含的空格个数。
20．组成串的数据元素只能是单个字符 。
21．一个字符串中任意个连续字符构成的部分称为该串的子串。
22．子串”str”在主串”datastructure”中的位置是
5。
23．二维数组M的每个元素是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要 540个字节；M的第8列和第5行共占108个字节。
24．稀疏矩阵一般的压缩存储方法有两种，即三元组表 和 十字链表。
25．广义表（（a），（（b），c），（（（d））））的长度是 3 ，深度是 4 。
26．在一棵二叉树中，度为零的结点的个数为n0，度为2 的结点的个数为n2，则有n0＝
n2＋1 。
27．在有n个结点的二叉链表中，空链域的个数为__n＋1__。
28．一棵有n个叶子结点的哈夫曼树共有__2n－1_个结点。
29．深度为5的二叉树至多有 31 个结点。
30．若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为
69 。
31．某二叉树的前序遍历序列是abdgcefh，中序序列是dgbaechf，其后序序列为 gdbehfca 。
32．线索二叉树的左线索指向其遍历序列中的前驱
，右线索指向其遍历序列中的后继 。
33．在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 散列查找法 。
34．在分块索引查找方法中，首先查找 索引表
，然后查找相应的 块表 。
35．一个无序序列可以通过构造一棵 二叉排序树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
36．具有10个顶点的无向图，边的总数最多为__45__。
37．已知图G的邻接表如图所示，其从顶点v1出发的深度优先搜索序列为_v1v2v3v6v5v4_，其从顶点v1出发的广度优先搜索序列为_v1v2v5v4v3v6__。
38．索引是为了加快检索速度而引进的一种数据结构。一个索引隶属于某个数据记录集，它由若干索引项组成，索引项的结构为 关键字和关键字对应记录的地址。
39．Prim 算法生成一个最小生成树每一步选择都要满足边的总数不超过n－1 ， 当前选择的边的权值是候选边中最小的，选中的边加入树中不产生回路 三项原则。
40．在一棵m阶B树中，除根结点外，每个结点最多有 m 棵子树，最少有 m/2 棵子树。
三、判断题。
1．在决定选取何种存储结构时，一般不考虑各结点的值如何。（√）
2．抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。（√）
3．抽象数据类型与计算机内部表示和实现无关。（√ ）
4．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（× ）
5．线性表采用链式存储结构时，结点和结点内部的存储空间可以是不连续的。（×）
6．对任何数据结构链式存储结构一定优于顺序存储结构。（× ）
7．顺序存储方式只能用于存储线性结构。（× ）
8．集合与线性表的区别在于是否按关键字排序。（× ）
9．线性表中每个元素都有一个直接前驱和一个直接后继。（× ）
10．线性表就是顺序存储的表。（× ）
11．取线性表的第i个元素的时间同i的大小有关。（× ）
12．循环链表不是线性表。（× ）
13．链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序表中效率高。（√ ）
14．双向链表可随机访问任一结点。（× ）
15．在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面：p－＞
next；（×）
16．队列是一种插入和删除操作分别在表的两端进行的线性表，是一种先进后出的结构。（× ）
17．串是一种特殊的线性表，其特殊性体现在可以顺序存储。（×）
18．长度为1的串等价于一个字符型常量。（× ）
19．空串和空白串是相同的。（×）
20．数组元素的下标值越大，存取时间越长。（×）
21．用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。（√）
22．一个广义表的表头总是一个广义表。（× ）
23．一个广义表的表尾总是一个广义表。（√）
24．广义表（（（ a ）， b）， c ）的表头是（（ a ）， b），表尾是（ c ）。（√）
25．二叉树的后序遍历序列中，任意一个结点均处在其孩子结点的后面。（√）
26．度为2的有序树是二叉树。（×）
27．二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。（√）
28．用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（×）
29．若已知一棵二叉树的前序遍历序列和后序遍历序列，则可以恢复该二叉树。（×）
30．在哈夫曼树中，权值最小的结点离根结点最近。（×）
31．强连通图的各顶点间均可达。（√ ）
32．对于任意一个图，从它的某个结点进行一次深度或广度优先遍历可以访问到该图的每个顶点。（× ）
33．在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，称这种排序为稳定排序。（√ ）
34．在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。（√ ）
35．拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。（×）
36．冒泡排序算法关键字比较的次数与记录的初始排列次序无关。（×）
37．对线性表进行折半查找时，要求线性表必须以链式方式存储，且结点按关键字有序排列。（×）
38．散列法存储的思想是由关键字值决定数据的存储地址。（√ ）
39．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。（× ）
40．具有n个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。（√）
41．直接选择排序算法在最好情况下的时间复杂度为O（n）。（× ）
第三篇：空间数据库期末复习重点总结
一、数据管理的发展阶段
1、人工管理阶段
2、文件系统阶段
3、数据库管理阶段
注意了解各阶段的背景和特点
二、数据库系统的特点
1、面向全组织的复杂的数据结构
2、数据的冗余度小，易扩充
3、具有较高的数据和程序的独立性：数据独立性
数据的物理独立性 数据的逻辑独立性
三、数据结构模型三要素
1、数据结构
2、数据操作
3、数据的约束性条件
四、数据模型反映实体间的关系
1、一对一的联系(1：1)
2、一对多的联系(1：N)
3、多对多的联系(M：N)
五、数据模型：
是数据库系统中用于提供信息表示和操作手段的形式构架。
数据库结构的基础就是数据模型。数据模型是描述数据(数据结构)、数据之间的联系、数据语义即数据操作，以及一致性(完整性)约束的概念工具的集合。 概念数据模型：按用户的观点来对数据和信息建模。ER模型
结构数据模型：从计算机实现的观点来对数据建模。层次、网状模型、关系
六、数据模型的类型和特点
1、层次模型：
优点：结构简单，易于实现
缺点：支持的联系种类太少，只支持二元一对多联系
数据操纵不方便，子结点的存取只能通过父结点来进行
2、网状模型：
优点：能够更为直接的描述世界，结点之间可以有很多联系
具有良好的性能，存取效率高 缺点：结构比较复杂
网状模型的DDL、DML复杂，并且嵌入某一种高级语言，不易掌握，不易使用
3、关系模型：
特点：关系模型的概念单一;(定义、运算)关系必须是规范化关系;
在关系模型中，用户对数据的检索操作不过是从原来的表中得到一张新的表。 优点：简单，表的概念直观，用户易理解。
非过程化的数据请求，数据请求可以不指明路径。
数据独立性，用户只需提出“做什么”，无须说明“怎么做”。 坚实的理论基础。
缺点：由于存储路径对用户透明，存储效率往往不如非关系数据模型
4、面向对象模型
5、对象关系模型
七、三个模式和二级映像
1、外模式(Sub-Schema)：用户的数据视图。是数据的局部逻辑结构，模式的子集。
2、模式(Schema)：所有用户的公共数据视图。是数据库中全体数据的全局逻辑结构和特性的描述。
3、内模式(Storage Schema)：又称存储模式。数据的物理结构及存储方式。
4、外模式/模式映象：定义某一个外模式和模式之间的对应关系，映象定义通常包含在各外模式中。当模式改变时，修改此映象，使外模式保持不变，从而应用程序可以保持不变，称为逻辑独立性。
5、模式/内模式映象：定义数据逻辑结构与存储结构之间的对应关系。存储结构改变时，修改此映象，使模式保持不变，从而应用程序可以保持不变，称为物理独立性。
八、数据视图
数据库管理系统的一个主要作用就是隐藏关于数据存储和维护的某些细节，而为用户提供数据在不同层次上的抽象视图，即不同的使用者从不同的角度去观察数据库中的数据所得到的结果—数据抽象。
九、规范化
1、几个概念
候选码(候选关键字)：如果一个属性(组)能惟一标识元组，且又不含有其余的属性，那么这个属性(组)称为关系的一个候选码(候选关键字)。 码(主码、主键、主关键字)：从候选码中选择一个唯一地标识一个元组候选码作为码 主属性：任何一个候选码中的属性(字段)非主属性：除了候选码中的属性外码：关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外部码，简称外码。
2、函数依赖
(1)设R(U)是一个属性集U上的关系模式，X和Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称 “X函数确定Y”或“Y函数依赖于X”，记作X→Y。 X称为这个函数依赖的决定属性集(Determinant)。Y=f(x)
(2)在关系模式R(U)中，对于U的子集X和Y，
如果X→Y，但Y X，则称X→Y是非平凡的函数依赖 若X→Y，但Y X,
则称X→Y是平凡的函数依赖 (3)在关系模式R(U)中，如果X→Y，并且对于X的任何一个真子集X’，都有X’/ →Y, 称Y完全函数依赖于X，记作XF→Y。若X→Y，但Y不完全函数依赖于X，则称Y部分函数依赖于X，记作XP→Y。
(4)在关系模式R(U)中，如果X→Y，Y→Z，且Y X，Y→X，则称Z传递函数依赖于X。记为X传递→Z。注: 如果Y→X， 即X←→Y，则Z直接函数依赖于X。
3、范式
范式是符合某一种级别的关系模式的集合
(1)范式种类：第一范式(1NF)、第二范式(2NF)、第三范式(3NF)、BC范式(BCNF)、第四范式(4NF)、第五范式(5NF)
1NF2NF3NFBCNF4NF5NF(2)各种范式之间的联系：
(3)定义：
1NF：如果一个关系模式R的所有属性都是不可分的基本数据项，则R∈1NF。
存在的问题：插入异常、删除异常、数据冗余度大、修改复杂
2NF：若关系模式R∈1NF，并且每一个非主属性都完全函数依赖于R的码，则R∈2NF。(所有非主属性完全依赖每个候选关键字。)
3NF：关系模式R 中若不存在这样的码X、属性组Y及非主属性Z(Z Y), 使得X→Y，Y→Z成立，Y→X，则称R ∈ 3NF。(所有非主属性既不部分依赖于码也不传递函数依赖码。)
BCNF：设关系模式R∈1NF，如果对于R的每个函数依赖X→Y，若Y不属于X，则X必含有候选码，那么R∈BCNF。(每一个决定属性集(因素)都包含(候选)码，R中的所有属性(主，非主属性)都完全函数依赖于码，R∈3NF。) 性质：a、所有非主属性都完全函数依赖于每个候选码
b、所有主属性都完全函数依赖于每个不包含它的候选码 c、没有任何属性完全函数依赖于非码的任何一组属性
多值依赖：设R(U)是一个属性集U上的一个关系模式， X、 Y和Z是U的子集，并且Z=U-X-Y，多值依赖 X→→Y成立当且仅当对R的任一关系r，r在(X，Z)上的每个值对应一组Y的值，这组值仅仅决定于X值而与Z值无关
平凡多值依赖和非平凡的多值依赖：若X→→Y，而Z=φ，则称X→→Y为平凡的多值依赖，否则称X→→Y为非平凡的多值依赖。
4NF：关系模式R(U，F)∈1NF，如果对于R的每个非平凡多值依赖XY(Y不包含于X)，X都含有候选码，则R ∈ 4NF
范式关系：
十、数据库
数据库：数据库就是为了一定的目的，在计算机系统中以特定的结构组织、存储、管理和应用的相关联的数据集合。空间数据库：空间数据库是存取、管理空间信息的数据库。 空间数据库管理系统：空间数据库管理系统是指能够对物理介质上存储的地理空间数据进行语义和逻辑上的定义;
1、提供必须的空间数据查询、检索和存取功能;
2、能够空间数据进行有效的维护和更新的一套软件系统。 空间数据库应用系统：提供给用户访问和操作空间数据库的用户界面，是应用户数据处理需求而建立的具有数据库访问功能的应用软件。 一般需要进行二次开发。
数据库系统组成：数据库、数据库管理系统、应用系统、数据库管理员
空间信息的特征：
(1)几何信息：描述了事物在空间中的位置及所占据的范围
将地球表面以投影方式转换为平面
通过平面几何来抽象描述和研究事物的位置和范围 用图形和符号的方式来描绘这些空间相关的事物
(2)拓扑信息：研究空间相关的事物本身或者事物之间的在空间坐标变换下的不变性质
事物本身的内外关系
事物之间的相离、相接、相交 事物之间相连的布局
(3)属性信息：与位置范围无关的其它信息
描述了事物本身的内在性质和外在表现 事物之间的非位置关系
空间数据库管理系统三层体系结构及每层的代表软件：
标准DBMS存储空间数据的局限性
(1)空间数据记录是变长的(如点数的可变性)，而一般的数据库都只允许把记录的长度设定为固定;
(2)在存储和维护空间数据拓扑关系方面存在着严重缺陷;
(3)一般都难以实现对空间数据的关联、连通、包含、叠加等基本操作; (4)不能支持复杂的图形功能;
(5)单个地理实体的表达需要多个文件、多条记录，一般的DBMS也难以支持; (6)难以保证具有高度内部联系的GIS数据记录需要的复杂的安全维护。
GIS的发展演化
空间数据库管理系统与传统数据库的区别： (1)数据量大
(2)需要处理与传统数据库中数据性质相似的属性数据和空间位置数据及它们之间的联系 3)对数据的检索涉及空间分析方法(4)数据应用广泛，不局限于某个部门
GIS发展三个阶段
1、 第一代GIS(从60年代中期到80年代的中后期，是GIS软件从无到有、从原型到产品的阶段)
技术特点：以图层作为处理的基础
以系统为中心 单机、单用户
全封闭结构支持二次开发能力非常弱
在主要实现技术上，以文件系统来管理几何数据与属性数据 应用领域基本上集中在资源与环境领域的管理类应用
2、第二代GIS(从80年代末到90年代中期，是GIS软件成熟和应用快速发展的时期) 技术特点：以图层作为处理基础
引入网络技术，多机、多用户 以系统为中心
支持二次开发的能力有所增强
以商用DBMS管理属性数据，但几何数据仍用文件系统管理 应用领域开始有较大范围的扩展，但基本上是管理类应用。
3、第三代GIS(90年代中期开始，估计将延续10年或稍长的时间) 技术特点：仍然以图层为处理的基础，但面临不断演化
引入了Internet技术，开始向以数据为中心的方向过渡，实现了初步的(浏览型或简单查询型)的B/S结构
开放程度大幅度增加，组件化技术改造逐步完成
逐渐重视元数据问题，空间数据共享、服务共享和GIS系统互连技术不断发展 GIS的标准化问题备受重视
实现空间数据与属性数据的一体化存储和初步的一体化查询，并将不断完善 应用领域迅速扩大，应用深度不断提高，开始具有初步的分析决策能力。
展望新一代GIS 面向空间实体及其时空关系的数据组织与融合 统一的海量存储、查询和分析处理 有效的分布式空间数据管理和计算 一定的三维和时序处理能力 强大的应用集成能力
灵活的操纵能力和一定的虚拟现实表达
空间数据库管理系统与GIS的联系和区别 空间数据库管理系统一般由专业GIS软件提供
GIS—处理地理数据——以地球表面为基本参照框架的空间数据
SDBMS——处理空间数据( 空间数据包括地理数据，地理数据是空间数据的子集) GIS促进SDBMS的研究与发展
空间信息模型：
基于场的模型：用于表示具有连续的空间变化的情况，形状不定的现象，采用栅格数据结构。
基于对象的模型：用于表示具有固定形状的空间实体/概念，描述空间上离散的空间对象。采用矢量数据结构
空间数据库设计的三个步骤
空间数据库的设计是指在现在数据库管理系统的基础上建立空间数据库的整个过程。 概念模型：按用户的观点从现实应用中抽象出事物以及事物之间的联系 逻辑建模：建立概念和联系的逻辑结构
物理设计建模：对逻辑结构进行具体实现方面的安排和考虑;
存储组织、索引、内存管理……
E-R图：
实体：现实中或者概念上独立存在的事物或者对象，用矩形表示 属性：刻画实体性质的数值或描述，用椭圆表示 联系：表达实体间的关联，用菱形表示 重点：E-R图设计
扩展E-R模型：象形图
1、 实体象形图：
象形图：象形图是一种将对象插在方框内的微缩图表示，这些微缩图用来扩展ER图，并插到实体矩形框中的适当位置。
形状：形状是象形图中的基本图形元素，它代表着空间数据模型中的元素。
基本形状： 复合形状： 导出形状： 备选形状： 任意形状：
用户自定义形状：
2、 联系象形图：
联系象形图用来构建实体间联系的模型
OGIS的4类几何体(4类空间数据模型)： 点——0维对象
线——1维对象，线串——2个或多个点表示 面——2维对象，多边形
几何体集合——表示复杂形状，3类：
多点 多线 多面
几何体集合——保证——几何操作的闭合
常见拓扑属性：
endpoint(point, arc)
点是弧的端点 simple-nonself-intersection(arc)
非自交的弧
on-boundary(point, region)
点在区域的边界上 inside(point, region)
点在区域内部 outside(point, region)
点在区域之外
open(region)
区域是开域(不包括边界) close(region)
区域是闭域(包括边界)
connected(region)
区域是连通域(区域上任2点，都有路径相连) inside(point, loop)
点在环中 crosses(arc, region)
弧穿过区域 touches(region, region)
区域与区域相邻 touches(arc, region)
弧与区域相邻 overlap(region, region)
区域与区域重叠 常见非拓扑属性：
Euclidean-distance(point, point)
2点间的欧氏距离 direction(point, point)
点在点的东面
length(arc)
弧的长度(单位向量长度为1个单位)
perimeter(area)
区域的周长(单位正方形的周长为4个单位) area(region)
区域的面积(单位正方形的面积为1个平方单位)
九交模型：
定义平面上2对象之间的拓扑关系 对象的3个部分： 内部——A° 边界——∂A 外部——A-
九交矩阵：将两个几何形的内部、边界、外部分别两两做相交操作，操作的结果记为矩阵元素取值
矩阵元素取值： ABABAB0——交为空 9(A,B)ABABAB1——交为非空 ABABAB
九交矩阵可确定的二元拓扑关系种类：29=512 可实现的二元拓扑关系种类：8(相离(disjoint)、相接(meet)、交叠(overlap)、相等(equal)、包含(contain)、在内部(inside)、覆盖(cover)、被覆盖(covered by))
关系代数(形式化的语言)
关系代数用到的运算符包括四类：集合运算符、专门的关系运算符、算术比较符、逻辑运算符。
并、差、交、笛卡尔积
选择：满足条件的元组，即行 投影：选取属性列 连接：等值投影
自然连接(特殊的等值连接，要求两个关系中进行比较的分量必须是相同的属性组，在结果中把重复的属性列去掉)
外连接：把舍弃的元组保存在结果中，在其他属性值上填空值(NULL) 左外连接：保留左边关系要舍弃的元组 右外连接：保留右边关系要舍弃的元组 除运算：了解象集
SQL标准每阶段特点和增加的内容 SQL-86 SQL-89：“具有完整性增强的数据库语言SQL”，增加了对完整性约束的支持
SQL-92：“数据库语言SQL”，是SQL-89的超集，增加了许多新特性，如新的数据类型，更丰富的数据操作，更强的完整性、安全性支持等。
SQL-3/SQL99：正在讨论中的新的标准，将增加对面向对象模型的支持
SQL中完成核心功能的9个动词
数据定义：
常用完整性约束： 主码约束：primary key 唯一性约束：unique 非空集约束：not null 参照完整性约束
数据查询：
查询满足条件的元组：
% (百分号) 代表任意长度(长度可以为0)的字符串 _ (下横线) 代表任意单个字符 集函数包括：
COUNT([DISTINCT | ALL] *)统计元组个数
COUNT([DISTINCT | ALL] <列名>)统计一列中值的个数 SUM([DISTINCT | ALL] <列名>)计算一列值的总和 AVG([DISTINCT | ALL] <列名>)计算一列的平均值 MAX([DISTINCT | ALL] <列名>)计算一列的最大值 MAX([DISTINCT | ALL] <列名>)计算一列的最小值 连接查询包括： 广义笛卡尔积
等值(含自然连接) 非等值连接; 自身连接; 外连接; 复合条件连接 嵌套查询
等值连接与自然连接区别
等值连接：在连接条件中使用等于号(=)运算符比较被连接列的列值，其查询结果中列出被连接表中的所有列，包括其中的重复列。
自然连接：在连接条件中使用等于(=)运算符比较被连接列的列值，但它使用选择列表指出查询结果集合中所包括的列，并删除连接表中的重复列。 嵌套查询分类：
不相关子查询：子查询的查询条件不依赖于父查询 相关子查询：子查询的查询条件依赖于父查询 不相关子查询：由里向外逐层处理 相关子查询：首先取外层查询中表的第一个元组，根据它与内层查询相关的属性值处理内层查询
集合查询：并(union)交(intersect)差(minus)
SELECT语句的一般格式： SELECT [ALL|DISTINCT] <目标列表达式> [别名] [ ，<目标列表达式> [别名]] … FROM <表名或视图名> [别名] [ ，<表名或视图名> [别名]] … [WHERE <条件表达式>] [GROUP BY <列名1> [HAVING <条件表达式>]] [ORDER BY <列名2> [ASC|DESC] 完整性规则： 实体完整性 参照完整性
用户定义的完整性：对于有NOT NULL约束的属性列是否提供了非空值
对于有UNIQUE约束的属性列是否提供了非重复值
对于有值域约束的属性列所提供的属性值是否在值域范围内
数据更新： 插入数据： INSERT INTO <表名> [(<属性列1>[，<属性列2 >…)]
VALUES (<常量1> [，<常量2>]
…
) 修改数据：
UPDATE <表名>
SET <列名>=<表达式>[，<列名>=<表达式>]…
[WHERE <条件>]; 删除数据： DELETE
FROM
<表名>
[WHERE <条件>]; 视图的特点
虚表，是从一个或几个基本表(或视图)导出的表 只存放视图的定义，不会出现数据冗余
基表中的数据发生变化，从视图中查询出的数据也随之改变 视图操作：(同表操作差不多) 定义视图 查询视图 更新视图
视图的可更新性：
SQL Server 2000规定：
① 如果一个视图是从多个基本表使用连接操作导出的， 则不允许对这个视图执行更新操作。
② 如果在视图定义中使用了聚集函数或DISTINCT短语或GROUP BY子句， 则不允许对该视图执行更新操作。
③ 如果视图的列的值为表达式或常数， 则不允许该这视图执行更新操作。
④ 如果视图为行列子集视图， 则可以对该视图执行更新操作。 视图作用：
1. 视图能够简化用户的操作
2. 视图使用户能以多种角度看待同一数据
3. 视图对重构数据库提供了一定程度的逻辑独立性 4. 视图能够对机密数据提供安全保护
数据控制
SQL提供了数据控制功能，能在一定程度上保证数据的安全性、完整性、并提供了一定的并发控制和恢复能力。 1. 完整性：定义库结构
2. 安全性：存取控制，规定不同用户对于不同数据对象允许执行的操作，并控制各用户它有权存取的数据。
3. 并发控制和恢复：SQL支持事务、提交、回滚等概念。 功能：
1、权限
2、授权
GRANT <权限>[，<权限>]… [ON <对象类型> <对象名>] TO <用户>[，<用户>]…[WITH GRANT OPTION];
3、收权
REVOKE <权限>[，<权限>]…
[ON <对象类型> <对象名>]
FROM <用户>[，<用户>]…;
SQL语言的空间扩展 OGIS类中操作分3类
1、用于所有几何类型的基本操作
6个 SpatialReference( )
返回几何体的基本坐标系统
Envelope( )
返回包含几何体的最小外接矩形 Export( )
返回以其他形式表示的几何体 IsEmpty( )
若几何体为空集，则返回真
IsSimple( )
若几何体为简单的(不自交的)，则返回真 Boundary( )
返回几何体的边界
2、用于空间对象之间拓扑关系的操作测试
8个
Equal
相等——若2个几何体的内部和边界在空间上都相等，则返回真 Disjoint
相离——若2个几何体的内部和边界都不相交，则返回真 Intersect
交叠——若2个几何体相交，则返回真
Touch
相接——若2个面仅边界相交，而内部不相交，则返回真 Cross
横过——若一条线和面的内部相交，则返回真
Within
在内部——若给定的几何体的内部不与另一个几何体的外部相交，则返回真 Contains
包含——若给定的几何体包含另一个几何体，则返回真
Overlap
覆盖/被覆盖——若2个几何体的内部有非空交集，则返回真
3、用于空间分析的一般操作
7个
Distance
求距离——返回2个几何体之间的最短距离
Buffer
求缓冲区——返回到给定几何体距离小于等于指定值的几何体的点的集合
ConvexHull
求最小闭包—— 返回几何体的最小闭包
Intersection
集合交——返回2个几何体的交集构成的几何体
Union
集合并——返回2个几何体的并集构成的几何体 Difference
集合差——返回几何体与给定几何体不相交的部分
SymmDiff
返回2个几何体与对方互不相交的部分
OGIS标准的局限性
局限用于——对象模型
场模型的操作——正研究 仅支持——基本拓扑的、空间度量的操作
不支持——方位的、动态的、基于形状的、基于可见性的操作 数据字典
定义：用于描述数据库的整体结构、数据内容和定义等。一个好的数据字典可以说是一个数据的标准规范，它可使数据库的开发者依此来实施数据库的建立、维护和更新。 用途：进行详细的数据收集和数据分析所获得的主要结果。 内容：数据项、数据结构、数据流、数据存储、处理过程 空间索引
索引文件——用来提高数据文件查询效率的辅助文件 索引文件的组成：
2个域：主码域
数据文件的页面地址
主索引——数据文件的记录按主码域排序，索引文件中只需保存数据文件的每个磁盘页面的第一个主码域的值。 一维搜索码的索引：B树与B+树 多维索引：
类似散列表的结构
固定网格 网格文件
基于树形的结构
四叉树 R树 R+树
数据库查询语言
两种：关系代数——形式化的语言
组成：1种运算对象——关系(表)
6种运算——选择、投影、并、笛卡尔积、差、交
结构化查询语言(SQL)
事务的概念
事务是并发控制的基本单位。所谓事务，就是一个操作序列，这些操作要么都执行，要么都不执行，它是一个不可分割的工作单位。 SQL Server以下列事务模式运行 (1)自动提交事务 (2)显式事务 (3)隐式事务 事务的特性 原子性 一致性 隔离性 持久性
语法格式为：
BEGIN TRANSACTION COMMIT TRANSACTION ROLLBACK TRANSACTION 锁的概念
锁定是Microsoft SQL Server Database Engine用来同步多个用户同时对同一个数据块的访问的一种机制。
锁的类型 (1)共享锁
共享锁也称为S锁，允许并行事务读取同一种资源，这时的事务不能修改访问的数据。当使用共享锁锁定资源时，不允许修改数据的事务访问数据。(2)排他锁
排他锁也称为X锁，它可以防止并发事务对资源进行访问。 (3)更新锁
更新锁也称为U锁，它可以防止常见的死锁。更新锁用来预定要对资源施加X锁，它允许其他事务读，但不允许再施加U锁或X锁。
活锁
如果事务T1封锁了数据R，事务T2又请求封锁R，于是T2等待。T3也请求封锁R，当T1释放了R上的封锁之后系统首先批准了T3的请求，T2仍然等待。然后T4又请求封锁R，当T3释放了R上的封锁之后系统又批准了T4的请求，...，T2有可能永远等待，这就是活锁的情形。
避免活锁的简单方法是采用先来先服务的策略 死锁
在两个或多个任务中，如果每个任务锁定了其他任务试图锁定的资源，此时会造成这些任务永久阻塞，从而出现死锁。
事务 A 获取了行 1 的共享锁。 事务 B 获取了行 2 的共享锁。
现在，事务 A 请求行 2 的排他锁，但在事务 B 完成并释放其对行 2 持有的共享锁之前被阻塞。
现在，事务 B 请求行 1 的排他锁，但在事务 A 完成并释放其对行 1 持有的共享锁之前被阻塞。
事务 A 必须在事务 B 完成之后才能完成，但事务 B 被事务 A 阻塞。这种情况也称为循环依赖关系：事务 A 依赖于事务 B，而事务 B 又依赖于事务 A，从而形成了一个循环。 除非某个外部进程断开死锁，否则死锁中的两个事务都将无限期等待下去。
Microsoft SQL Server Database Engine死锁监视器定期检查陷入死锁的任务。如果监视器检测到循环依赖关系，将选择其中一个任务作为牺牲品，然后终止其事务并提示错误。
减少死锁的方法：
(1)按同一顺序访问对象 (2)避免事务中的用户交互
(3)保持事务简短并处于一个批处理中 (4)使用较低的隔离级别
(5)使用基于行版本控制的隔离级别 (6)使用绑定连接 存储过程
SQL Server提供了一种方法，它可以将一些固定的操作集中起来由SQL Server数据库服务器来完成，以实现某个任务，这种方法就是存储过程。
在SQL Server中存储过程分为两类：即系统提供的存储过程和用户自定义的存储过程。
可以使用三种方法创建存储过程 ：
1、使用创建存储过程向导创建存储过程。
2、利用SQL Server 企业管理器创建存储过程。
3、使用Transact-SQL语句中的CREATE PROCEDURE命令创建存储过程。 创建命令格式：
CREATE
PROCEDURE
存储过程名
[参数
数据类型
长度] [参数
数据类型
长度
OUTPUT] AS
SQL语句 执行命令格式：
EXEC[ UTE ] 存储过程名
[ 参数名= 参数值 ] [ 参数值1，参数值2，……] 删除存储过程
DROP procedure 存储过程名 触发器
是一种特殊类型的存储过程，是通过事件进行触发而被执行的，而存储过程通过存储过程名被直接调用。触发器是一个功能强大的工具，它使每个站点可以在有数据修改时自动强制执行其业务规则。触发器可以用于SQL Server约束、默认值和规则的完整性检查。
触发器是一种特殊类型的存储过程，不由用户直接调用。创建触发器时会对其进行定义，以便在对特定表或列作特定类型的数据修改时执行。
当创建一个触发器时必须指定：
⑴名称;
⑵在其上定义触发器的表;
⑶触发器将何时激发;
⑷激活触发器的数据修改语句。
使用命令创建触发器
CREATE TRIGGER 触发器名
ON 表/视图名
[WITH
ENCRYPTION]:加密 syscomments 表中包含 REATE TRIGGER 语句文本的条目。使用 WITH ENCRYPTION 可防止将触发器作为 SQL Server 复制的一部分发布,当使用"exec sp_helptext 触发器名"时,查看不了语句
{ FOR|AFTER|INSTEAD OF }指定执行触发器而不是执行触发 SQL 语句，从而替代触发语句的操作
{ [DELETE][,][INSERT][,][UPDATE] }
[ NOT FOR REPLICATION]表示当复制进程更改触发器所涉及的表时，不应执行该触发器。
AS
SQL 语句 删除触发器
DROP TRIGGER { trigger } [ ,...n ]
SQL Server2000安全机制(管理服务器的安全性、角色与用户、管理权限) 数据库的安全性是指保护数据库以防止不合法的使用所造成的数据泄漏、更改或破坏。系统安全保护措施是否有效是数据库系统的主要指标之一。
安全机制：对于数据库管理来说，保护数据不受内部和外部侵害是一项重要的工作。SQL Server 2005的身份验证、授权和验证机制可以保护数据免受未经授权的泄漏和篡改。
SQL Server 2005的安全模型分为3层结构，分别为服务器安全管理、数据库安全管理和数据库对象的访问权限管理。
SQL Server 2005的身份验证模式有两种：Windows身份验证模式和混合模式 SQL Server 2005数据库管理系统利用角色设置，管理用户的权限。这样只对角色进行权限设置便可以实现对该角色中所有用户权限的设置，大大减少了管理员的工作量。
在SQL Server 2005中，具有固定服务器角色、固定数据库角色、用户自定义数据库角色和应用程序角色4种类型的角色
权限用来控制用户如何访问数据库对象。一个用户可以直接分配到权限，也可以作为一个角色中的成员来间接得到权限
SQL Server 2005中的权限分为3种：对象权限、语句权限和隐含权限。对象权限是用来控制一个用户是如何与一个数据库对象进行交互操作的，有5个不同的权限：查询(Select)、插入(Insert)、修改(Update)、删除(Delete)和执行(Execute)。
GIS数据库的设计
数据库设计的基本目标： (1) 满足用户需求 (2) 良好的数据库性能 (3) 准确模拟现实世界
(4) 能够被某个数据库管理系统接受
概念设计应满足的要求：
(1) 提供一个非专家理解的系统结构框架
(2) 包含丰富的结构类型，能够尽可能完整地描述系统的复杂性 (3) 能够转换成与实施相关的模型，以便能够设计和实施该系统 概念设计的核心内容：
(1) 确定数据库的数据组成 (2) 确定数据类型之间的关系 (3) 建立概念数据模型 (4) 形成书面文档
概念设计的一般步骤和方法： (1) 确定应用领域 (2) 确定用户需求 (3) 选择对象类型
(4) 对象类型定义和属性描述 (5) 对象类型的调整 (6) 几何表示 (7) 关系 (8) 质量要求 (9) 编码
空间数据分层依据： (1) 专题内容 (2) 几何表达形式 (3) 拓扑特征的差别
(4) 不同部门的数据通常放在不同的图层，便于维护 (5) 不同安全级别的数据也应该单独存储 (6) 使用目的不同的数据应该单独存放 地理数据模型的发展阶段(3个)： (1) CAD数据模型
(2) Coverage数据模型(第二代地理数据模型) (3) GeoDatabase数据模型(第三代地理数据模型)
要素集：是具有同样几何类型和属性的要素集合。——矢量图层 对象类：是GeoDatabase中存储数据库表——表 要素数据集：具有相同空间参考的要素类的集合
子类：在要素类内部可以划分若干个次一级的组，每个组是一个子类。每个子类有其自己的完整性规则和GIS行为。
拓扑关系：拓扑关系将参与拓扑的各个要素类集成在一个拓扑图中作为一个拓扑单元来管理，规定同一个要素类中各个要素如何与其他要素共享几何，或者不同要素类之间如何共享几何。
ArcGIS中的三个数据库：Personal Database、File Database、ArcSDE(ArcSDE+SQL构成空间数据库)
选择题(12‘)、填空题(10‘)、名词解释(20‘)、写代码(27‘)、简答题(21‘)设计题(10‘)
第四篇：2009年计算机等级考试四级数据库工程师考试知识点总结
《全国计算机等级考试四级教程—数据库工程师》
第一章 引 论
1、 数据库技术产生于20世纪60年代，是信息系统的核心技术和重要基础;
2、 计算机科学与技术学科划分为四个专业方向：计算机科学(CS);计算机工程(CE);软件工程(SE);信息技术(IT)。
1.1 基本概念
1.1.1 信息与数据
1、 信息、物质、能量是组成客观世界并促进社会发展的三大基本要素;
2、 信息(Information)--是客观世界事物的存在方式和运动状态的反映，是对事物之间相互联系、相互作用的描述。信息具有可感知、可存储、可加工、可传递和可再生的自然属性。
3、 数据(Data)--是描述现实世界事物的符号记录，是用物理符号记录下来的可以识别的信息。不同的物理符号体现出数据的不同表现形式。
4、 信息与数据间存在固有联系，数据是信息的符号表示，或称为载体。信息则是数据的语义解释，是数据的内涵，信息以数据的形式表现出来，并为人们理解和接受。
5、 数据处理(Data Processing)--是指对数据进行分类、收集、组织、存储，进而从已数据出发，抽取或推导出新的数据，这些数据表示了新的信息。
6、 数据管理(Data Management)--是指对数据的分类、收集、组织、编码、存储、检索和维护，是数据处理业务的重要环节。
7、 数据处理与数据管理的区别在于，数据处理除了具有数据管理功能外，还可通过数据管理得到的数据进一步深加工，从中获取新的数据和信息。 1.1.2 数据库系统
1、 数据库(DB，DataBase)--是长期存储在计算机内有组织的、大量的、共享的数据集合;
2、 数据库管理系统(DBMS，Database Management System)--是指在计算机系统中，位于用户与操作系统之间的数据管理系统软件，是数据库系统的核心。
3、 数据库系统(DBS，DataBase System)--是指在计算机系统中引入数据库后的软硬件系统构成，DBS一般分成三个层次：(1)计算机硬件平台;(2)系统软件和应用软件;(3)用户;在不引起混淆和歧义的情况下，数据库系统简称为数据库。
4、 (狭义的)数据库系统—是由数据库和数据库管理系统组成的软件系统，主要为用户提供数据存储和查询、插入、修改、删除、更新等数据管理功能。
5、 (狭义的)数据库应用系统(DBAS，DataBase Application System)—是由数据库、数据库管理系统、数据库应用程序组成的软件系统，它面向具体应用领域，提供了更为复杂的数据处理功能。
6、 数据库技术—是研究数据库的结构、存储、设计、管理和使用的一门计算机应用学科。
7、 数据库技术与其它计算机科学有密切关系：
(1) 数据库技术以文件系统为基础发展而来，DBMS需要操作系统的支持，数据库以文件形式存储在外部存储上的;
(2) 数据库与数据结构的关系很密切，数据库技术不仅用到数据结构中的链表、树、图等知识，各种数据模型本身就属于复杂数据结构;
(3) 主流的关系数据库系统，其理论基础是关系数据模型，而该模型是在离散数学集合论中“关系”这一基本概念上发展起来的;
(4) 当用户访问数据库，DBMS对用户提交的查询操作类似于，计算机编译系统对程序的编译过程; (5) 开发一些大型的DBS或DBMS的过程，要遵循软件工程的开发模式。
1.2 数据模型
1.2.1 数据模型概念
1、数据模型(Data Model)--是数据库系统的形式框架，是用来描述数据的一组概念和定义，包括描述数据、数据联系、数据操作、数据语义以及数据一致性的概念工具;
2、数据模型应满足：(1)能够比较真实地模拟现实世界;(2)容易为人们所理解;(3)便于在计算机上实现。
3、 数据模型的组成：
(1) 数据结构：用于描述系统的静态特征，从语法角度表述了客观世界中数据对象本身的结构和数据对象之间的关联关系，是刻画一个数据模型性质最重要的方面。在数据库系统中，通常按照数据结构的类型来区分、命名各种数模，如层次、网状、关系数模。
(2) 数据操作：用于描述系统的动态特征，是一组对数据库中各种数据对象允许执行的操作和操作规则组成的集合。数据操作可以是检索、插入等，数模必须定义这些操作的确切含义、操作符号、操作规则以及实现操作的数据库语言。
(3) 数据完整性约束：是一组完整性规则的集合，它定义了数模必须遵守的语义约束，也规定了数据库中数据内部及数据之间联系所必须满足的语义约束。它限定了数据库的状态以及状态的变化，以便维护数据的正确性、有效性。
1.2.2 数据模型分类
1、 用数据模型这一概念来描述数据库的结构和语义，通过现实世界—信息世界—机器世界的抽象转换过程构建数据库，并根据模型所定义的规范去管理和使用数据。
2、 建模过程：(1)将现实世界的数据对象抽象为信息世界中的某一信息结构;(2)再将信息结构转换为机器世界中某一具体DBMS支持的数据模型，并存储于计算机中。
3、 数据模型分类：
(1) 概念数据模型(概念模型)：按用户的观点对数据和信息进行建模，是现实世界到信息世界的第一层抽象，强调其语义表达功能，易于用户理解，是用户与设计人员交流的语言，主要用于数据库设计。最常用的是实体—联系模型。
(2) 数据结构模型(表示型/实现型)：是机器世界中与具体DBMS相关的数据模型，包括关系模型、网状模型和层次模型
(3) 物理数据模型：属底层数据模型，描述数据的实际存储方式。
1.3 数据视图与模式结构
1.3.1 数据视图与数据抽象
1、 数据视图：指从某个角度看到的客观世界数据对象的特征，是对数据对象某一方面特征的描述。
2、 数据抽象：是一种数据描述和数据库设计原则，是指专注于数据对象的某方面特征，而忽略其他特征。
3、 集和值：集是指对某一类数据的结构和属性的说明，值是集的一个具体赋值;
4、 数据模式：对数据库中数据某方面结构和特征的描述，它仅涉及集的描述，不涉及具体的值。 1.3.2 三级模式结构
1、 数据库三级模式结构—外部级、概念级和内部级，分别定义了外模式、模式和内模式，用于从不同角度描述数据库结构。
2、 模式：
(1) 也称逻辑模式、概念模式;
(2) 对数据库中全体数据的逻辑结构和特征的描述，是所有用户的公共数据视图; (3) 模式不仅定义了数据的逻辑结构，还定义了数据之间的联系、与数据的关的安全性和完整性要求;
(4) 一个数据库只有一个模式，建立在某种数据结构模型基础上。
3、 外模式：
(1) 也称子模式、用户模式、用户视图;
(2) 是对数据库用户能够看见和使用的局部数据的逻辑结构和特征的描述。
(3) 一个数据库可以有多个外模式，每个外模式描述了某个特定用户所使用的局部数据的逻辑结构和特征，是与某一应用有关的数据的逻辑表示。
(4) 外模式还是保证数据安全的有力措施，每个用户只能看见和访问所对应的外模式中的数据，其它数据对他是不可见的。
4、 内模式：
(1) 也称物理模式、存储模式;
(2) 是对数据库中数据的物理结构和存储方式的描述，代表了数据在数据库内部的表示方式和物理组织结构;
1.3.3 二级映象与数据独立性
1、 外模式/模式映象：
(1) 定义了数据库中不同用户的外模式与数据库逻辑模式之间的对应关系;
(2) 可有多个外模式/模式映象，对于每个外模式，需要一个外模式/模式映象来定义该外模式与模式之间的对应关系;
(3) 当模式发生变化时，只需调整外模式/模式间的映象关系，而外模式无需修改，保证了数据与应用程序的逻辑独立性，称为数据的逻辑独立性。
2、 模式/内模式映象：
(1) 定义了数据库中数据全局逻辑结构，与这些数据在系统中的物理存储组织结构之间的对应关系。
(2) 模式/内模式映象是唯一的;
(3) 当内模式发生变化时，只需调整模式/内模式映象关系，而模式无需修改，保证了数据库中的数据与应用程序间的物理独立性，称为数据的物理独立性。
1.4 数据库系统体系结构
1、 数据库系统体系结构：是指数据库系统的组成构件、各构件的功能及各构件间的协同工作方式;
2、 分类：
(1) 集中式：全部数据和数据管理功能均集中在一台计算机上的数据库系统;包括单用户和主从式两种，单用户DBS是指系统由一个用户独占，不同机器间不能共享数据;主从式DBS是指一个主机带多个分时多用户的DBS;
(2) 分布式：数据库中的数据在逻辑上是一个整体，但在物理上却可以分布在网络中不同数据管理节点上;
(3) 客户/服务器：将DBMS和数据库应用分开，网络中某些节点上的计算机专门执行DBMS功能，负责数据管理服务，称为数据库服务器;其他节点的计算机上安装DBMS的外围应用开发工具，支持用户的应用，主要负责数据表示服务，称为客户端;
(4) 并行式：硬件平台是并行计算机系统，使用多个CPU和多个磁盘进行并行数据处理和磁盘访问操作，以提高执行速度; (5) WEB式： 由通过互联网连接起来的客户端、WEB服务器、数据库服务器组成。
1.5 数据库管理系统
1.5.1 数据库管理系统的功能
(1) 数据定义功能：DBMS提供了数据定义语言(DDL)，用户利用DDL定义数据库对象的三级模式结构，描述数据库的结构特征。
(2) 数据操纵功能：DBMS提供数据操纵语言(DML)，用户利用DML对数据进行查询、插入、删除或更新;
(3) 数据库运行管理和控制功能 (4) 数据库的建立和维护功能 1.5.2 数据库系统的全局结构
1、 DBS可分为用户、人机交互界面、DBMS和磁盘四个层次;
2、 用户可分为四类：数据库管理员DBA;专业用户;应用程序员;终端用户;
3、 DBMS可分为两部份：
(1) 查询处理器：面向用户查询请求;包括以下几个功能模块：DML编译器、嵌入式DML的预编译器、DDL编译器、查询执行引擎;
(2) 存储管理器：面向数据存储访问，包括以下几个功能模块：权限和完整性管理器、事务管理器、文件管理器、缓沖区管理器;
4、 磁盘存储的类型：
(1) 以数据库文件方式存储的应用数据; (2) 数据字典;
(3) 为提高查询速度而设置的数据库引擎; (4) DMS运行时的统计分析数据; (5) 日志信息。
1.6数据库技术的发展和应用
1、 第一代DBS：60年代末70年代初，层次型和网状型DBS;
2、 第二代DBS：70年代后期，关系数据库系统;
3、 新型DBS：80年代，分布式数据库系统;90年代，面向对象数据库系统、网络数据库系统
第二章 数据库应用系统生命周期
2.1数据库应用系统生命周期
2.1.1 软件工程与软件开发方法
1、 软件工程：指导计算机软件开发和维护的工程科学，它采用工程化的概念、原理、技术和方法，以及正确的项目管理技术，来开发和维护软件;它将系统化、规范化、定量化方法应用于软件的开发、操作和维护，也就是将工程化应用于软件生产;
2、 软件工程的目标：在给定成本、进度的前提下，开发出满足用户需求并具有下述特征的软件产品：可修改性、有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性。
3、 软件生命周期：指软件产品从考虑其概念开始，到该产品交付使用的整个时期，包括概念阶段、需求阶段、设计阶段、实现阶段、测试阶段、安装部署及交付阶段;
4、 软件项目管理：为了能使软件开发按预定的质量、进度和成本进行，而对成本、质量、进度、人员、风险等进行分析和有效管理的一系列活动。
5、 软件工程以关注软件质量为特征，由方法、工具和过程三部分组成;
6、 软件过程模型(软件开发模型)：是对软件过程的一种抽象表示，表示了软件过程的整体框架和软件开发活动各阶段间的关系，常见的有：瀑布模型、快速原形模型、增量模型和螺旋模型。 2.1.2 DBAS软件组成
1、 数据库应用软件在内部可看作由一系列软件模块/子系统组成，这些模块/子系统可分成两类：
(1) 与数据访问有关的数据库事务模块：利用DBMS提供的数据库管理功能，以数据库事务方式直接对数据库中的各类应用数据进行操作，模块粒度较小;
(2) 与数据访问无直接关联的应用模块：在许多与数据处理有关的应用系统中，对数据库的访问只是整体中的一部分，其他功能则与数据库访问无直接关系，这部分模块粒度可以比较大。
2、 DBAS设计开发的硬件方面：主要涉及根据系统的功能、性能、存储等需求选择和配置合适的计算机硬件平台，并与开发好的DBAS软件系统进行集成，组成完整的数据库应用系统; 2.1.3 DBAS生命周期模型
1、 数据库应用系统的生命周期模型：
(1) 参照软件开发瀑布模型的原理，DBAS的生命周期由项目规划、需求分析、系统设计、实现和部署、运行管理与维护等5个基本活动组成;
(2) 将快速原形模型和增量模型的开发思路引入DBAS生命周期模型，允许渐进、迭代地开发DBAS;
(3) 根据DBAS的软件组成和各自功能，细化DBAS需求分析和设计阶段，引入了数据组织与存储设计、数据访问与处理设计、应用设计三条设计主线，分别用于设计DBAS中的数据库、数据库事务和应用程序;
(4) 将DBAS设计阶段细分为概念设计、逻辑设计、物理设计三个步骤，每一步的设计内容又涵盖了三条设计主线。
2.2 规划与分析
2.2.1 系统规划与定义
1、 定义：系统规划与分析是面向将要开发的DBAS，通过了解用户实际需求，明确该系统需要实现的目标和任务，并从数据管理和数据处理的角度，确定系统中数据库软件的功能、性能范围;
2、 系统规划与定义包括：
(1) 任务陈述：描述所要开发的DBAS的总体目标; (2) 确定任务目标; (3) 确定系统范围和边界; (4) 确定用户视图; 2.2.2 可行性分析
1、 可行性分析包括以下四方面：
(1) 经济可行性：对项目进行成本效益分析;DBAS的成本主要包括：A、软硬件购置费用;B、系统开发费用;C、系统安装、运行、维护费用。
(2) 技术可行性：是根据用户提出的系统功能、性能及实现系统的各项约束条件，对系统软件、硬件、技术方案作出评估和选择建议;
A、 硬件可行性研究是分析DBAS的硬件平台环境和设置;
B、 软件可行性研究包括：对可用的DBMS和操作系统的选型评估，对中间件和开发环境的选型建议，对DBAS开发模式和编程语言的建议;
C、 技术方案的选择是根据系统技术需求，提出DBAS可能采用的合理技术方案和关键技术; (3) 操作可行性：是论证是否具备DBAS开发所需的各类人员资源、软件资源、硬件资源和工作环境等，以及为支持DBAS开发如何去改进加强这几方面资源。
(4) 开发方案选择：目的是提出并评价实现系统的各种开发方案，从中选出一种适用于DBAS软件的开发方案;
2.2.3 项目规划
1、 项目规划是项目管理者对资源、成本和进度做出合理估算，并在此基础上制定切实可行的DBAS项目开发计划。
2、 项目规划包括以下内容： (1) 确定项目的目标和范围;
(2) 根据DBAS软件开发模型，分解和定义整个项目包括的工作活动和任务; (3) 估算完成该项目的规模和所需各种资源; (4) 制定合理的DBAS项目计划
3、项目规划的结果应形成数据库应用系统项目计划文档，即项目计划书。
2.3 需求分析
1、 数据库应用系统需求是指用户对DBAS在功能、性能、行为、设计约束等方面的期望和要求;
2、 DBAS需求分析是在已经明确的DBAS系统范围基础上，通过对应用问题的理解和分析，采用合适的工具和符号，系统地描述DBAS的功能特征、性能特征和约束，并形成需求规范说明文档;
3、 需求分析过程由需求获取、需求分析、需求描述和规范说明、需求验证等组成;
4、 DBAS的需求分析包括：
(1) 数据需求分析; (2) 数据处理需求分析; (3) 业务需求分析;
(4) 分析数据库系统在性能、存储、安全、备份与恢复等方面的要求; 2.3.1 数据与数据处理需求分析
1、 数据需求分析：是从对数据组织与存储的设计角度，辨识应用领域所管理的各类数据项和数据结构，与数据处理需求分析结果一起，组成数据字典;
2、 数据处理需求分析：是从数据访问和处理的角度，明确对各类数据项所需进行的数据访问操作，分析结果可表示为数据流图或事务规范;
3、 事务规范包括：
(1)事务名称;(2)事务描述;(3)事务所访问的数据项;(4)事务用户; 2.3.2 业务规则需求分析
1、业务规则需求分析：是从DBAS高层目标和整体功能出发，分析系统或系统中一些大粒度子系统应具有的业务类型和功能，明确用户或外部系统与DBAS的交互模式; 2.3.3 性能需求分析
1、 DBAS的性能指标：
(1) 数据操作响应时间(或数据访问响应时间)：从提交请求到返回结果的时间; (2) 系统吞吐量：指系统在单位时间内所完成的事务或查询的数量，单位为TPS; (3) 允许并发访问的最大用户数：在保证响应时间的前提下，系统最多允许多少用户同时访问数据库;
(4) 每TPS代价值，用于衡量系统性价比的指标
2、 影响DBAS性能的因素：
(1) 系统硬件资源; (2) 网络通信设备性能; (3) 操作系统环境;
(4) 数据库的逻辑设计和物理设计质量，数据库配置参数; (5) DBAS的配置和性能; (6) 数据库应用程序自身。 2.3.4 其它需求分析
1、 存储需求分析：是指估计DBAS系统需要的数据存储量，包括：(1)初始数据库大小;(2)数据库增长速度;存储总量估算可采用：根据数据字典中每个数据项的结构描述信息，估计每个数据项的容量，将所有数据项的容量累加;
2、 安全性需求分析：
(1) DBAS系统应达到的安全控制级别; (2) 各类用户的数据视图和视图访问权限;
(3) DBAS应有的口令保护机制或其它安全认证机制，用以控制用户登录数据库系统。
3、 备份和恢复需求分析：
(1) DBAS运行过程中备份数据库的时间和备份周期; (2) 所需备份的数据是全部数据库数据，还是一部分; (3) 备份方式是采用完全备份还是采用差异备份。
2.4 系统设计
2.4.1 概念设计
1、 数据库概念模型设计：是根据数据需求分析阶段得到的需求结果，分析辨识需要组织存储在数据库中的各类应用领域数据对象的特征及其相互之间关联关系，并采用概念数据模型表示出来，得到独立于具体DBMS的数据库概念模型;
2、 ER方法：(1)选择局部应用;(2)分别设计各个局部ER图;(3)局部ER图合并;
3、 系统总体设计：
(1) 确定DBAS体系结构;
(2) 系统硬件平台和操作系统、数据库管理系统等系统软件的选型和配置; (3) 应用软件结构设计
(4) 对需求分析阶段识别出的业务规则进行初步设计，细化业务规则流程，明确采用的关键技术和算法;
(5) 对系统采用的关键技术进行方案选型和初步设计。 2.4.2 逻辑设计
1、 数据库逻辑结构设计：指从数据库的概念模型出发，设计表示为逻辑模式的数据库逻辑结构。
(1) ER图转换为初始关系模式; (2) 对初始关系模式进行优化;
(3) 检查关系表对数据库事务的支持性; (4) 确定关系模式的完整性约束;
(5) 从数据安全性和独立性出发，设计用户视图。
2、 应用程序概要设计(II);
3、 数据库事务概要设计; 2.4.3 物理设计
1、 数据库物理结构设计：主要指数据文件在外存上的存储结构和存取方法，它依赖于系统具体的硬件环境、操作系统和DBMS; (1) 数据库逻辑模式调整;
(2) 选择或配置基本关系表的文件组织形式; (3) 数据分布设计; (4) 安全模式设计; (5) 确定系统配置; (6) 物理模式评估;
2、 数据库事务详细设计：根据事务流程，利用SQL语句、数据库访问接口，采用高级程序设计语言或DBMS提供的事务实现机制，设计数据库事务。
3、 应用程序详细设计：
2.5 实现与部署
1、 建立数据库结构;
2、 数据加载;
3、 事务和应用程序的编码及测试;
4、 系统集成、测试与试运行;
5、 系统部署;
2.6 运行管理与维护
2.6.1 日常维护
(1) 数据库的备份与恢复 (2) 完整性维护 (3) 安全性维护 (4) 存储空间管理 (5) 并发控制及死锁处理 2.6.2 系统性能监控和分析
1、 统计数据可以通过两种途径收集：
(1) 由DBMS本身自动收集和存储统计数据 (2) 通过监控系统得到 2.6.3 系统性能优化调整
1、 糸统性能优化的手段有：数据查询调整与优化、索引调整、数据库摸式调整、DBMS和操作系统参数调整等。
2、 模式调整主要涉及逻辑模式调整，可以从下考虑：
(1) 已达到第三范式的基本表，不要进一步规范化为BCNF;
(2) 在分布式数据库中，对一个基本表中某些频繁被访问的数据，可以按水平分区或垂直分区方式拆分基本表。
2.6.4 系统升级
1、 改进应用桯序;
2、 数据库重组;
3、 DBMS和OS版本升级
第3章 需求分析及功能建模方法
3.1 需求分析概述
3.1.1 需求分析概念
1、 所谓需求分折：就是对待开发的系统要做什么，完成什么功能的全面描述。
2、 需求分析的工作：通过对需求的调查、了解、观察和分析，通过对原始数据的收集、分类和抽象，并采用有效的技术、工具，对原始资料进行加工整理，描述开发目标、实现的功能及其相互关系等活动的集合;
3、 需求的定义：客户对一个待开发的系统在实现目标、完成功能、应达到的性能、安全性、可靠性等方面的期望和要求的集合;
4、 需求获取的困难：
(1) 软件功能复杂; (2) 需求的可变性;
5、 需求分析阶段的主要任务：分析当前的业务流程，包括体系结构，各职能部门完成的主要任务、关系及其交流的信息。
6、 需求分析的结果通常以模型等建模工具和方法描述系统的信息流、功能结构及完成各功能需要的数据。
7、 功能模型和软件需求规格说明书是软件开发的依据，将指导后续的开发工作。
8、 需求分析工作是系统分析员与用户不断交互的过程中完成的。 3.1.2 系统分析员的职能
1、 系统分析员的主要要任务：是确定应用信息系统及软件产品应该达到的各项功能性要求和非功能性要求，即用户要做什么。
2、 系统分析员应该具备的素质：
(1) 获取需求的能力; (2) 管理及沟通能力; (3) 技术素养; 3.1.3 需求获取的方法
常用的几种获取需求的方法：(1)面谈;(2)实地观察;(3)问卷调查;(4)查阅资源; 3.1.4 需求分析过程
1、 标识问题：
(1) 需求分析的第一步，通过对问题的识别和标识获得所求解问题及其运行环境的理解; (2) 标识问题从现行系统的业务流程做起，理解现行系统的业务流程; (3) 在标识理解需求的同时，还要注意确定系统的人机界面;
2、建立需求模型：
(1) 模型是对现实原形所作的一种抽象，其本质是只关心与研究内容有关的因素，而忽略无关的因素，其目的是把复杂的事物变得简单，便于认识和分析;
(2) 目前常用的模型方法主要有DFD数据流图和IDEFO，都属于结构化分析方法，其特征是抽象和分解;
(3) 首先对应用领域进行全面的分析，发现并找出同类事物的本质，用抽象方法把这类事物的非主要方面剔除，把握住事物的内部规律或本质，就可以找到解决办法;然后采用自上而下逐步求精的方法对复杂的问题进行分解;
(4) 结构化分析及建模方法的主要优点：
(A) 不过早陷入具体的细节; (B) 从整体或宏观入手分析问题;
(C) 通过图形化的模型对象直观地表示系统要做什么，完成什么功能; (D) 图形化建模方法方便系统分析员理解和描述系统; (E) 模型对象不涉及太多的技术术语，便于用户理解;
3、描述需求：
(1) 需求描述的目标：对软件项目功能性和非功能性的需求全面描述;
(2) 功能性需求：指需要计算机实际解决的问题或实现的具体功能，明确描述系统必须做什么，实现什么功能以及输入输出等;
(3) 非功能性需求：软件项目对实际运行环境的要求;
(4) 需求描述主要由需求模型和需求说明书组成，说明书侧重文字说明，内容如下：需求概述;功能需求;信息需求;性能需求;环境需求;其他需求;
(5) 在对需求进行分析过程中，系统分析员要经常考虑的问题：
(A) 描述的需求是完全的吗? (B) 需求描述是正确的和一致的吗?
(C) 描述的这些需求是可行的、实际可操作的吗? (D) 描述中的每一条需求都是客户需要的吗?
4、确认需求：
1、 评审委员会审核下列内容：功能需求;数据需求;性能;数据管理;其他需求。
3.2 DFD建模方法
3.2.1 DFD方法的基本对象
1、 数据流：具有名字且有流向的数据，用标有名字的箭头表示。
2、 处理：表示对数据的加工和变换，在图中用矩形框表示。
3、 数据存储：表示用数据库形式存储的数据，对其存取分别以指向或离开数据存储的箭头表示;
4、 数据源及数据终点：表示当前系统的数据来源和去向，其图形符号以平行四边形表示。 3.2.2 开发DFD图
1、 DFD图采用自顶而下逐步细化的结构化分析方法表示目标系统;
2、 DFD方法应以软件项目的功能为中心进行抽象和分解，以数据流的变换来分析数据对企业中各类业务活动的影响; 3.2.4 数据字典
1、 数据字典包括以下说明信息：
(1) 源点及终点词条描述; (2) 数据流词条描述; (3) 数据存储; (4) 处理描述;
(5) 数据元素词条描述。
3.3 IDEF0建模方法
3.3.1 概述
1、 IDEF0的基本思想是结构化分析方法，强调自顶而下有控制地逐步地展开细节，全面地描述系统，且通过建模来理解一个系统。一个模型由图形文字说明、词汇表及相互的交叉引用表组成。
2、 IDEF方法的优点：具有模型元素单
一、语义丰富、更易于从全局角度分析考察问题，模型容易理解。
3.3.2 IDEF0方法
1、基本元素
(1) 矩形：代表活动，活动名称标在矩形内，活动编号按要求标在矩形框右下角指定位置; (2) 箭头：左边的输入箭头代表完成活动需要的数据、上方的控制箭头描述了影响活动的执行的事件或约束、右边的输出箭头说明由活动产生的结果及信息、下方进入的机制箭头表示实施该活动的物理手段或资源。
(3) 输入输出箭头描述活动是什么(what)、控制箭头描述为何这么做(why)、机制箭头表示如何做(how)。
2、IDEF0模型
(1) 一个IDEF0模型由一组图形组成，这些图形组成一个由父到子的层次结构图，这组图形把一个复杂事物按自顶向下逐步细化的方式分解成一个个简单的或多个组成部分;
3、 建模规则
(1) 矩形框：用动词为矩形内活动命名，每个矩形要至少有一个控制箭头和输出箭头，可以没有输入，但不可以同时没有输入和控制。
(2) 箭头：箭头代表数据约束，而不是代表流或顺序; (3) 其他：
(A) ICOM码：只有一端与矩形相连的箭头叫边界箭头，这些箭头表示父矩形框的输入、控制和输出。IDEF0用专门的记号ICOM码来说明父子图中的箭头关系。子图中每个边界箭头的开端分别用字母I、C、O、M来标明是输入、控制、输出及机制，再用一个数字表示其在父矩形框中箭头的相对位置。
(B) 结点号：IDEF0模型是一组有一定层次结构的图形，通常用结点号来标志图形或矩形框在层次图中的位置;
(C) 模型名：每个模型有一个名字，通常用名字代表主题，用子名字表示不同的模型。基本名字与子名字间用“/”隔开，如A/B/C，A是主题、B是模型号、C是结点号。
3.3.3 建模过程及步骤
1、 IDEF0建模过程及步骤：
(1) 明确目的，确定范围：在建模前首先要明确目的和意图，确定问题域;
(2) 建立内外关系图A-0图：根据系统目标、功能建立内外关系图A-0图，以确定整个模型的内外关系，确定系统的边界;
(3) 构造顶层图：把A-0图分解成3~6个主要部分得到A0图，A0图是模型真正的顶层图; (4) 开发IDEF0层次结构图：对A0图中的每个矩形框进行分解，就形成了基本的图形层次结构。在分解时要列出所有的数据项和活动表，分解的次序采用以下原则： (A) 保持在同一水平上进行分解，均匀的模型深度; (B) 按困难程序进行选择; (5) 写文字说明; (6) 检查确认图形;
3.4 DFD与IDEF0的比较
1、 DFD与IDEF0共同点：都是结构化分析思想，强调自顶而下逐步求精的方法对现实世界建模，先抓住主要的问题，形成较高层次的抽象，再由粗到细、由表及里地逐步细化，将一个大问题分解成几个小问题，对这小问题再进行分析求解;
2、 DFD与IDEF0区别：
(1) DFD图用箭头(数据流)来描述数据移动的方向、数据处理及处理之间的数据依赖关系。IDEF0图也用箭头代表数据流，但在IDEF0中不是强调流或顺序，而是强调数据约束。
(2) 从表达形式上看，DFD图与IDEF0图都是用箭头和处理表达一个企业或组织的业务流程。但IDEF0图的箭头不仅能够表示数据流，还可以表示控制流和说明处理或实施方式的一些约束;
(3) 从模型元素的组成上来看，DFD模型由4种元素组成，即外部顶、数据流、数据存储和处理。而IDEF0模型元素的组成更加简单，只有2种元素组成，即箭头和活动; (4) 从模型规范上来讲，IDEF方法更加规范; (5) IDEF0模型结构清楚，便于理解和沟通。
第四章 数据库概念设计及数据建模
4.1 数据库概念设计概述
4.1.1 数据库概念设计的任务
1、 定义和描述应用领域涉及的数据范围;
2、 获取应用领域或问题域的信息模型;
3、 描述清楚数据的属性特征;
4、 描述清楚数据之间的关系;
5、 定义和描述数据的约束;
6、 说明数据的安全性要求;
7、 支持用户的各种数据处理需求;
8、 保证信息模型方便地转换成数据库的逻辑结构，同时便于用户理解。 4.1.2 概念设计过程
1、 概念设计的依据：是需求分析阶段的文档，通过对这些文档的分析理解，构造出信息模型，编写数据库概念设计说明书，信息模型和数据库概念设计说明书是数据库逻辑设计的依据;
2、 概念设计的基本步骤：
(1) 确定实体集;
(2) 确定联系和联系类型;
(3) 建立由信息模型表示的企业模型; (4) 确定实体集属性; (5) 对信息模型优化。
4.2 数据建模方法
1、 数据建模方法的共同特点是：
(1) 能够真实客观地描述现实世界中的数据及数据之间的关系; (2) 组成模型的概念少，语义清楚，容易理解; (3) 不同概念的语义不重叠，概念无多义性;
(4) 用图形方式描述数据，数据直观易懂，有利于数据库设计者和用户交流; (5) 这种数据模型容易转换成数据库逻辑设计阶段需要的数据结构。
4.3 ER建模方法
4.3.1 基本概念
1、 实体或实例：指客观存在并可相互区分的事物，可以是一个具体的人或物，也可以是抽象的事件或概念;
2、 实体集：表示一个现实的和抽象事物的集合，这些事物必须具有相同的属性或特征。
3、 属性：用于描述一个实体集的性质和特征;
4、 码：实体集中能惟一标识每一个实例的属性或属性组;
5、 联系：描述现实世界中实体之间的关系。(1)一对一联系;(2)一对多联系;(3)多对多联系 4.3.2 ER方法语法
1、 ER方法中用矩形框表示实体集，矩形框内写上实体集的名称;
2、 ER模型用菱形表示联系，联系名写在菱形框内;
3、 ER模型中实体集的属性用椭圆或圆角矩形框表示，属性名字写在其中。
4.4 IDEF1X 建模方法
4.4.1 IDEF1X概述
1、 IDEF0侧重描述系统功能，被称为功能建模方法;IDEF1X侧重分析、抽象和概括应用领域中的数据，称为数据建模方法;
2、 IDEF1X方法具有丰富的语法和语义;
3、 实体集分为(1)独立标识符实体集;(2)从属标识符实体集;
4、 实体集之间的联系分为：(1)标定型联系;(2)非标定型联系;(3)分类联系;(4)不确定联系 4.4.2 IDEF1X模型元素
1、 实体集：
(1) 实体集语义：如果一个实体集的每一个实例都能被惟一地标识，而不决定于它与其他实体的联系，那么该实体集称为独立实体集;否则就叫从属实体集;
(2) 实体集语法：IDEF1X用矩形框来表示独立实体集，用圆角矩形框来表示从属实体集;
2、 联系：
(1) 联系语义：
(A) 标定型联系：一个“确定型联系”中，如果子女实体集中的每个实例都是由它与双亲的联系而确定的，这个关系称为“标定型联系”;
(B) 非标定型联系：一个“确定型联系”中，如果子女实体集中的每一个实例都能被惟一地确认而无需了解与之相联系的双亲实体集的实例，这个问题关系叫“非标定型联系”。
(C) 分类联系：是两个或多个实体集之间的联系，且在这些实体集中存在一个一般实体集，它的每一个实例都恰好与一个且仅一个分类实体集的一个实例相联系。
(D) 不确定联系：一个非确定联系又称为多对多联系，这种联系关联的两个实体集之间，任一实体集的一个实例都将对应另一实体集的0个、1个或多个实例。
(2) 联系的语法：
(A) 标定联系语法：在IDEF1X图中，联系的语法用直线表示，在一个标定型联系中，子女实体集总是一个从属实体集，用圆角矩形框表示;
(B) 非标定联系语法：如果两个实体集之间有关系，并且是一个非标定联系，就用一条虚线把它们连接起来。
(C) 分类联系语法：一般实体集的一个实例只能与分类实体集的一个实例相对应; (D) 不确定联系m:n的语法：不确定联系用一个两端带有实心圆的线段描述，表示多对多的连接关系。
3、 属性
(1) 属性的语义：用来描述一类现实或抽象事物的特征或性质。一个属性的具体取值叫属性实例，它由属性的类型和值来定义。
(2) 属性的语法
(A) 主码和非主码属性语法：在一个实体集中属性要有惟一的名字，属性名由名词表示，主码属性名后加(PK)标注，被列在属性列表的顶端，并用水平线将主码和其他属性分开。
(B) 外码语法：在外码属性后加“FK”来识别由联系继承得到的外来属性。
4.4.3 建模过程
1、第一阶段：建模规划及准备
(1) 建模目标：
(A) 目标说明：回答将构造的模型完成什么功能，涉及的问题和数据范围，同时说明是一个当前系统模型还是待建模型。
(B) 范围说明：在建模初期要给出模型覆盖的问题范围; (2) 建模计划
(A) 项目说明; (B) 收集数据; (C) 定义实体; (D) 定义联系; (E) 定义码属性; (F) 定义非码属性; (G) 确认模型; (H) 评审验收。
(3) 组织队伍：包括项目负责人、建模者、信息源、课题专家、评审委员会
2、 第二阶段：定义实体集
(1) 目标是标识和定义应用领域中的实体集，方法是分类标识原始材料中的所有名词; (2) 区别实体集名词和非实体集名词的方法，是否具有下列特征：
(A) 它能够被描述或说明吗? (B) 有多少同类的实例吗?
(C) 每个实例可以被标识和区分吗?
3、 第三阶段：定义联系
(1) 标识实体集之间的联系：建立联系矩阵，联系矩阵由一个二维数组表示。把实体集沿水平和垂直两方向列出，分析两个实体间的联系，有联系就用“X”表示，不存在联系用“null”表示。联系只标识直接关系，不标识间接关系。
(2) 定义联系：包括表示依赖、命名联系、关于联系的说明;当实体集之间的依赖关系建立后，就可以命名联系了。联系的名字可以动词表示。原则必须是具体的、简明的和有意义的。
(3) 构造实体级数：实体级图的范围和数目,依赖于建模的规模和建模问题涉及的实体集数目。
4、 第四阶段：定义健
(1) 分解不确定的联系：把实体级图中不确定的关系转换成确定的连接形式，把每一个不确定的联系转换成为两个确定的联系;
(2) 标识码属性：码属性是那些能够惟一识别实体集中每一个实例的属性;
(3) 迁移主码：把一个实体集的主码复制到其他有关实体集的过程，但要遵守以下规则：
(A) 在一个联系中，迁移总是从父到子或从一般实体集移向分类实体集; (B) 主码属性才能被迁移，如主码由多个属性组成，则要全部迁移;
5、 第五阶段：定义属性
(1) 标识和定义非主属性; (2) 建立属性的所有者; (3) 确认属性的定义; (4) 绘制局部数据视图;
(A) 实体集的名称和编号写在矩形框外的上面;
(B) 主码属性写在矩形框内水平线的上面并用“PK”标注; (C) 外码属性写在矩形框内水平线的下面并用“FK”标注; (D) 非主属性也可以写在矩形框内水平线的下面;
第五章 关系数据库逻辑设计
5.1 概述 5.2 基本概念
5.2.1 关系模型
1、 关系模型采用一个二维表格在计算机中组织、存储、处理和管理数据。
(1) 关系名(数据库名)：由字母数字组成; (2) 属性名;
(3) 关系模式和关系：描述模式描述关系的静态结构，由模式名、关系模式所包含的属性及属性值所满足的条件组成模式定义。
(4) 元组：描述关系中的行;
(5) 域：它定义关系的每个属性取值的类型;
(6) 主码：能够惟一标识关系中每一个元组的属性或属性组;
(7) 关系的数学定义：关系模式是建立在集合集论的基础上的，用数学的概念定义关系有;
(A) 定义一：域是值的集合，同一个域中的值具有相同的数据类型; (B) 定义二： (C) 定义三：
(D) 当关系引用了属性名后关系具有以下属性： [1] 不能有重复的元组; [2] 元组上下无序;
[3] 按属性名引用时属性左右无序; [4] 所有属性值都是原子项(不可再分);
(8) 总结：关系是一张二维表，表中的一行被称为一个元组，一列称为属性，由一组域值组成。关系是元组的集合，关系中的每个元组在数学上被定义为这个关系所涉及的全部域值中笛卡儿积的一个元素。 5.2.2 关系数据库
1、 关系数据库是按照二维表组织和存储的相互关联的关系的集合，关系数据库模式是关系模式的集合;
5.2.3 关系的完整性
1、 关系的完整性(完整性约束)：是对关系的某种约束规则和关系满足的定义。通常这组约束规则用来限定和检查数据库所含实例的合法性和正确性;
2、 完整性约束分静态和动态两种，静态完整性约束是基于关系模式的，主要有主码、外码约束和域约束组成;动态完整性约束是基于企业的业务规则的。
3、 静态完整性约束规则：
(1) 主码约束：主码必须满足：
(A) 惟一性：在一个关系中不存在两个元组，它们具有相同的主码值;
(B) 最小性：不存在从组成主码的属性集中去掉一个属性，还仍能保持数据的惟一性; (2) 外码约束：
(3) 用户定义的完整性：
5.3 关系数据库设计理论
5.3.1 问题的提出
究竟一个关系数据库包含哪些属性是合理的，如何评价一个关系模式设计的优劣? 5.3.2 函数依赖
函数依理论利用一个关系中属性之间的依赖关系评价和优化关系模式，以保证存储到数据库中的关系具有较好特性;
1、 函数依赖：
(1) 设R(U)为一关系模式，X和Y为属性全集U的子集，若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称“X函数决定Y”或“Y函数依赖于X”，并记作XY，其中X称为决定因素，因为根据函数依赖定义，给定一个X，就能惟一决定一个Y。
(2) 这里讨论的函数关系与数学上的不同，是不能计算的，是一个关系中属性之间存在的依赖关系;它是一种语义范畴的概念，只能根据两个属性之间的语义来确定一个函数依赖是否存在。
2、 完全与部分函数依赖：
(1) 在关系模式R(U)中，如果XY成立，并且对X的任何真子集X’不能函数决定Y，则称Y对X是完全函数依赖，被记作X---f---Y。 (2) 若XY，但Y不完全函数依赖于X，则称Y对X是部分函数依赖，记作X--pY;
3、 传递函数依赖：
在关系R(U)模式中，如果X决定Y，(Y不属于X)，Y不决定X，Y决定Z，则称Z对X传递函数依赖。
4、 平凡与非平凡函数依赖：
(1) 若X决定Y，但Y属于X，则称XY是平凡函数依赖，否则称非平凡函数依赖; (2) 即平凡函数依赖，仅当其右边的属性集是左边属性集的子集时成立;
(3) 非平凡函数依赖，仅当其右边的属性集至少有一个属性不属于左边有集合时成立; (4) 完全非平凡函数依赖：仅当其右边的属性集中属性都不在左边的集合时成立;
5、 码：
(1) 在关系模式R(U)中，K为R的属性或属性组，若K函数决定A1.A2„.An，则K为关系模式R的候选码，包含在候选码中的属性称为主属性，否则为非主属性;
(2) 若一个关系的候选码不止一个，则选定其中一个作为关系R的主码;
(3) 关系的码属性除了必须完全函数决定关系的所有其他属性外，还必须满足最小化规则，即在关系模式R(U)中，不存在一个K的真子集能够函数决定R的其他属性。
6、 函数依赖的推理规则：
(1) 自反律：若Y(包含于)X(包含于)U，则XY成立; (2) 增广律：若XY，且Z(包含于)U，则XZYZ成立; (3) 传递律：若XY，YZ，则XZ成立; (4) 合并规则：若XY，XZ成立，则XYZ;
(5) 分解规则：若XY和Z(包含于)Y成立，则XZ也成立; (6) 伪传递规则：若XY，YWZ，则XWZ成立;
7、 属性集闭包：
(1) 设F是属性集U上的函数依赖集，X为U的一个子集，那么对于F，属性集X关于F的闭包(用X+表示)为：X+={A|XA} (2) 由属性集团包的定义可知，若想判断函数依赖XY是否成立，只要计算X关于函数依赖集F的闭包，若Y是X闭包中的一个元素则XY成立;
8、 确定关系的码：
(1) 利用迭代算法计算X+，步骤如下：
(A) 选X作为闭包X+的初值X(0);
(B) 由X(i)计算X(i+1)时，它是由X(0)并上属性集合A所组成，其中A满足下列条件：Y(包含于)X(i)，且F中存在函数依赖YZ，而A(包含于)Z。因为U是有穷的，所以会得到X(i)=X(i+1)，此时X(i)为所求的X+。
5.3.3 规范化设计方法
1、 第一范式：
(1) 定义：设关系模式R(F，U)，如果R的每一个属性都是不可分的数据项，则此关系模式为第一范式;
(2) 一个给定关系和第一范式(1NF)的区别：
(A) 一个关系中的数据按照行和列的形式组织，每个元组具有相同数目的属性个数，且每一个元组的属性值具有统一的数据类型和长度;元组或属性的排列与顺序无关，每个元组必须通过一个属性或属性组惟一识别;
(B) 第一范式实际上对关系增加了一个约束，即关系中元组的每个属性都只取一个值，第一范式是对关系模式的基本要求，不满足第一范式的数据库就不是关系数据库。
2、 第二范式：
(1) 定义：若关系模式R(F，U)是1NF，且每个非主属性完全函数依赖于码，则称R为第二范式，即在2NF中不存在非主属性对码的部分依赖;
(2) 仅满足第一范式关系会存在种种问题，要消除必须用更高级的范式标准来设计，称为标准化;
(3) 具体做法是将大的关系分解成多个小的关系，使分解后的关系满足更高级范式的要求。 (4) 第二范式实际上对关系增加了一个约束，就是关系中的每一个属性必须完全依赖于主码，即在第一范式的基础上，消除非主属性对主码的部分函数依赖可达到2NF;
3、 第三范式：
(1) 定义：若关系R(U，F)为第一范式，且不存在非主属性对主码的传递函数依赖，则称R为第三范式;
(2) 第三范式是在第二范式的基础上对关系又增加了一个约束，就是关系中的每一个非主属性必须只依赖于主码。即2NF的基础上，消除非主属性对主码的传递函数依赖可达到3NF。
4、 改进的第三范式：
(1) 定义：如果关系模式R是1NF，且每个属性既不相存在部分函数依赖也不存在传递函数依赖于候选码，则称R是改进的第三范式(BCNF)。
5、 多值依赖与4NF：
(1) 多值依赖：表示关系中属性(如A、B、C)之间的依赖，对于A的每个值，都存在一个B或C的值的集合，而且B和C的值相互独立，记为：AB、AC (2) 第四范式：如果关系模式R属于1NF，对于R的每个非平凡的多值依赖XY(Y不属于X)，X含有候选码，则R是第四范式。即是从BCNF范式中消除主码内的独立依赖集(非平凡多值依赖)可达4NF;
6、 连接依赖与5NF (1) 连锁依赖：设关系模式R，R的属性子集为R
1、R
2、R
3、R
4、R
5、R
6、R7„.，当且仅当R的每个合法值等于R
1、R
2、R
3、R
4、R
5、R
6、R7„的投影连接时，称R满足连接依赖;
(2) 第五范式：设R是一个满足5NF的关系模式，当且仅当R的每一个非平凡连接依赖都被R的候选码所蕴含，即从4NF中消除非候选码所蕴含的连接依赖为5NF;
7、 总结：
(1) 范式表达了关系模式满足的条件，也是衡量关系模式设计优劣的标准;
(2) 利用范式进行规范化设计的目的是消除数据冗余，避免出现异常，使结构更合理; (3) 规范化设计的基本过程是对关系进行的分解，消除属性间不合理的数据依赖，用一组等价的子关系代替原有的关系;
(4) 数据库规范化的程序越高，其关系表就越多，从而增加了表之间连接运算的代价，影响了数据库的执行速度和性能。所以通常关系模式规范化工作仅做到3NF，这样既使关系中不合理的属性基本消除，规范化程度也不太高，保证数据库有较好的性能。
5.4 数据库模式设计
5.4.1 初始关系模式的设计
1、 把ER图转换成关系模式：
(1) 把ER模型中的每个实体集转换成一个同名的关系，实体集的属性就是关系的属性，实体集的码就是关系的码;
(2) 把ER模型中的每个联系转换成一个关系，与该联系相连的各实体集的码以及联系的属性转换成为关系的属性。
(A) 若联系为1：1，则每个实体集的码均是该关系的候选码; (B) 若联系为1：n，则关系的码为n端实体集的码; (C) 若联系为m：n，则关系的码为各实体集码的组合; (3) 合并具有相同码的关系
2、 检查确认对象：检查转换后的每个关系名和属性名是否符合数据库设计关于统一命名的约定; 5.4.2 优化关系模式
1、 模式分解原则： (1) 分解具有无损连接性：分解后的关系能够恢复成原来的关系; (2) 分解保持函数依赖：
(A) 无损连接和保持函数依赖是用于衡量一个模式分解是否导致原有模式中部分信息丢失的两个标准;
(B) 当一个关系被分解后会出现几种结果，既有无损连接，又能保持函数依赖是较理想的分解结果，意味着在分解的过程中没有丢失原有模式的任何信息;
(C) 一般情况下，分解到3NF就足够了，但在3NF关系下，仍存在一定程度上的更新异常或不一致的隐患，但与数据库性能比较起来是可以忽略的，因为在数据库设计过程中通过增加一些数据约束，就可以解决3NF引起的数据问题了。
3、 优化属性：确定各字段的类型和长度;
4、 确认模式满足需要： 5.4.3 数据完整性设计
1、 指定义数据库中存储的数据值满足的约束条件，通过对存储的数据值的约束维护关系的完整性。
2、 数据值满足条件分为：
(1) 域约束：限制指定列的取值及范围;
(2) 主码约束：定义每个关系的主码值不空，且惟一;
(3) 引用完整性约束：定义不同模式的属性间满足的条件，及一个关系模式中属性间可能满足的条件;
5.4.4 安全模式和外模式的设计
1、 根据选定的DBMS支持的安全控制特征来确定;
2、 根据不同用户对数据库存取特点定义相关的外模式;
第六章 存储技术与数据库物理设计
6.1 文件组织
6.1.1 数据库的物理结构
1、 数据库中的应用数据是以文件形式存储在外存上的，文件在逻辑上被组织成记录的序列，即每个DB文件可看作是逻辑记录的集合;
2、 一个文件在磁盘上占有一定的物理存储空间，文件中的每个逻辑记录被映射存储到某个特定的磁盘块上，一个文件在物理上可以看作是由存放文件记录的一系列磁盘块组成，称为物理文件;
3、 文件的逻辑记录与磁盘间的映射关系是由操作系统或DBMS来管理的，当需要对一个文件的逻辑记录进行操作时，先要根据这种映射关系找到该逻辑记录所在的磁盘块，然后再进行操作。
4、 从数据库物理结构角度需要解决如下问题：
(1) 文件的组织; (2) 文件的结构; (3) 文件的存取; (4) 索引技术; 6.1.2 文件组织
1、 数据库与文件的对应关系
(1) 在外存中，数据库以文件形式组织，文件由逻辑记录组成，记录由多个域组成; (2) 一个关系数据库包括一张或多张关系表，关系表与文件的对应关系有如下方式：
(A) 每张关系表单独用一个文件来存储，由DBMS通过OS的文件管理功能来管理; (B) 现代中大型DBMS是由OS直接分配一块大的磁盘空间，DBMS将该磁盘空间作为数据库磁盘文件直接管理，DB的所有关系表都存储在该文件中;
(4) 关系表在逻辑上由一系列元组组成，元组由多个属性组成，每个元组可以用磁盘文件中的一个逻辑记录来存储，记录包括多个域，对应元组的多个属性;
2、文件记录格式：
(1) 数据库文件通常采用两种逻辑记录格式：定长记录格式和变长记录格式;
6.2 文件结构与存取
6.2.1 堆文件
1、 堆文件也称无序文件，记录随机在存储在文件物理空间是，新插入的记录存储在文件的末尾;
2、 堆文件常常用作存储那些将来使用，但目前不清楚如何使用的记录，为了实现文件记录的有效存取，堆文件经常与附加的存取路径一起使用;
3、 查找操行平均需要搜索(B+1)/2个磁盘块，效率比较低;
4、 插入操作十分简单，先读文件头，找到最末磁盘地址，将最末磁盘块读入内存，将需插入的新记录写入磁盘块的末端，最后将修改过的磁盘块写回磁盘;
5、 删除比较复杂，可以先找到被删除记录所在的磁盘块，读入内存后在内存缓冲区删除记录，最后再写回磁盘;也可以在每个记录的磁盘空间增加一个删除标志位，当需要删除记录时，将标示位置1; 6.2.2 顺序文件
1、 顺序文件按照文件记录在查询码上的取值的大小顺序排列各个记录;
2、 顺序文件的每个记录中有一个指针字段，根据查询码大小用指针将各个记录按序连接起来;
3、 文件建立时，应尽量使记录的物理顺序与查找码的顺序一致，以减少访问磁盘块的次数;
4、 根据查询条件对顺序文件进行查询时，如查询条件定义在查找码上，则使用二分法查找技术快速找到记录，如条件不在查找码上，则必须从头到尾依次扫描磁盘块，与堆文件一致，所以顺序文件的访问效率也不高;
5、 顺序文件插入工作包括定位和插入：
(1) 定位：在指针链中找到插入的位置，即插入记录在哪个记录的前面;
(2) 插入：如有自由空间，则在该位置插入新记录，如没有自由空间，则只能插入溢出块中，重新调整记录指针链关系，保证记录顺序;
6.2.3 聚集文件
1、 聚集文件是一种具有多种记录类型文件，存储了来自多个关系表的数据，每个关系表对应文件中的一种记录类型;
2、 当数据库中数据量效大时，对数据库查询需要多次访问磁盘文件，严重影响性能指标，为了降低多表操作时的磁盘访问次数，提高多表查询速度，可采用聚集文件;
3、 聚集文件将不同关系表中有关联关系的记录存储在同一磁盘块内，从而减少多表查询时磁盘块的访问次数，提高处理速度; 6.2.4 索引文件
是一种利用索引技术技术快速文件访问的文件组织和存取方法; 6.2.4 散列文件
是一种利用散列函数支持快速文件访问的文件组织和存取方法;
6.3 索引技术
6.3.1 基本概念
1、 索引技术：是一种快速文件访问技术，它将一个文件的每个记录在某个或某些域(属性)上的取值与该记录的物理地址直接联系起来，提供了一种根据记录域的取值快速访问文件记录的机制;它的关键是建立取值域到记录的物理地址刘的映射关系，这种映射关系叫索引;
2、 索引技术分类：
(1) 有序索引技术：利用索引文件实现记录域(查找码)取值到记录物理地址间的映射关系，索引文件由索引记录组成，每个记录中记载一个索引项，索引项记录了某个特定的查找码值和具有该值的数据文件记录的物理地址;
(2) 散列技术：利用一个散列函数实现记录域取值到记录物理地址间的直接映射关系; (3) 有序索引：有序索引作为基于索引文件的索引技术，需要考虑两个问题：(1)如何组织索引文件中的索引记录;(2)如何从索引文件出发，访问数据文件中的数据记录; (A) 当需要采用有序索引机制快速访问数据文件时，首先要为该数据文件建立一个索引文件，它是索引记录和索引项的集合;
(B) 索引文件建立的方法：首先选定某些记录域作为查找码，然后建立数据记录在查找码上的取值与物理地址间的映射关系，组成索引项。所有索引项作为索引记录存储在索引文件中，索引文件根据某个特定的查找码值的顺序组织为顺序文件;
(C) 一个数据文件可以有多个查找码和索引文件;
6.3.2 有序索引的分类及特点
1、 聚集索引与非聚集索引
(1) 对数据文件和它的一个特定的索引文件，如果数据文件中数据记录的排列顺序与索引文件中索引项的排列顺序相一致，则该索引文件称为聚集索引，否则称为非聚集索引;
(2) 在一个数据文件上除了建立一个聚集索引外，还可建立多个非聚集索引;
2、 稠密索引和稀疏索引
如果数据文件中的每个查找码都在索引文件中都对应一个索引记录，称为稠密索引，如果只一部分对应，则称为稀疏索引;
3、 主索引和辅索引
在数据文件包含主码的属性集上建立索引称为主索引，在非主码属性上建立的索引称为辅索引;
4、单层索引和多层索引
(1) 单层索引(线性索引)：索引项根据键值在索引文件中顺序排列，组织成一维线性结构，每个索引项直接指向数据文件中的数据记录;
(2) 当数据文件很大时，即使采用稀疏索引，建成的索引文件也很大，导致效率低下，为解决该问题，可对索引文件中的索引项本身再建立一级稀疏索引，组成2层索引结构;进一步地，可建立多层树型索引结构来快速定位;
6.4 散列技术
6.4.1 散列文件
1、 散列是一种快速查找技术，它利用定义在文件记录上的查找码，通过计算一个散列函数，以散列函数值作为记录的物理地址，实现对文件记录直接快速访问。
2、 首先指定文件记录的一个域作为查找码(散列域)，然后定义一个查找码上的函数(散列函数)，函数的输入为查找码值，输出为物理地址;
3、 一般使用桶作为基本的存储单位，一个桶可存放多个文件记录，物理地址可以是记录所在的桶号，散列函数的输出可以是桶号; 6.4.2 散列函数
1、 散列方法依赖于好的散列函数，它应该尽可能均匀地将查找码分布到各个桶中，具体要满足如下两个条件：
(1) 地址的分布是均匀的; (2) 地址的分布是随机的; 6.4.3 桶溢出
1、 产生桶溢出的两个原因：
(1) 文件初始设计时，为文件记录预留的存储空间不足; (2) 散列函数的均匀分布性不好;
2、 设计散列函数时，应根据文件大小决定物理空间，一般应有20%余量，再设计合适的桶数目和桶大小，尽可能留有一些空闲桶，降低桶溢出的可能性;
3、 桶溢出的现象是难免的，需要DBS采用相应的桶溢出处理机制;
4、 散列方法的缺点：为了避免桶溢出。必须选一合适的散列函数，但这比较复杂，而且不象索引文件那样可以据数据记录变化动态调整。
6.5 数据字典
1、 数据字典(系统目录)中存储了数据库对象的各类描述信息和DBMS所需的控制信息，全称数据库元数据;
2、 数据库对象的各类描述信息：包括外模式、模式、内模式以及它们之间的映射的描述;
3、 DBMS所需的控制信息：包括查询优化、安全性检查、用户权限验证等;
4、 数据字典主要包括：
(1) 关系模式信息;
(2) 与视图描述有关的信息;
(3) 关系的存储结构和存取方法信息; (4) 完整性约束信息; (5) 安全性有关信息; (6) 数据库运行统计信息;
6.6 数据库物理设计
6.6.1 设计步骤和内容
1、 数据库物理结构设计：在具体的硬件环境、OS、DBMS约束下，根据数据库逻辑设计结果，设计合适的数据库物理结构。目标是存储空间占用少、访问效率高和维护代价低;
2、 一旦选定了硬件平台、OS和DBMS，数据库的数据存储和存取方式等可用的物理模式也就随之确定了;
3、 数据库物理设计主要包括以下步骤：
(1) 数据库逻辑模式调整：将数据库逻辑模式及其视图转换为DBMS支持的基本表和视图，并利用DBMS提供的完整性机制设计业务规则;
(2) 文件组织与存取设计：配置基本表的文件组织形式，据实际情况为基本表设计合适的存取方法和路径;
(3) 数据分布设计： (4) 安全模式设计： (5) 确定系统配置： (6) 物理模式评估： 6.6.2 数据库逻辑模式调整
1、 物理数据库设计首先需要根据数据库逻辑结构信息，设计目标DBMS平台支持的基本表的模式信息，这些模式信息代表了所要开发的具体目标数据库的结构，这个过程称为数据库逻辑模式调整，主要包括如下设计内容：
(1) 实现目标数据库基本表和视图：采用目标DBMS所支持的建表方法，设计基本表及其面向模型的完整性约束;
(2) 设计基本表业务规则; 6.6.3 DB文件组织与存取设计
1、分析事务的数据访问特性
(1) 使用事务-基本表交叉引用矩阵，分析系统内数据库事务对各个基本表的访问情况，确定事务访问了哪些基本表，对这些基本表执行了何种操作，并进一步分析各操作涉及到的基本表属性;
(2) 估计各事务的执行频率;
(3) 对每张基本表，汇总所有作用于该表上的各事务的操作频率信息;
2、 了解并选择数据库文件结构
(1) 如果数据库中的一个基本表中的数据量很少，并且操作非常频繁，该基本表可采用堆文件组织方式;
(2) 顺序文件支持基于查找码的顺序访问，也支持快速二分查找;
(3) 如果用户查询是基于散列域值的等值匹配，特别是如果访问顺序是随机的，散列文件比较合适。但散列文件组织不适合以下情况： (A) 基于散列值域的非精确查询; (B) 基于非散列域进行查询时;
(4) B-树和B+树文件是实际数据库系统中使用非常广泛的索引文件结构，适合于定义在大数据量基本表上、基于查找码的等值查询等;
(5) 如果某此重要而频繁的用户查询经常需要进行多表连接操作，可考虑将这些基本表组织为聚集文件;
3、 设计存取路径：
(1) 为数据库文件设计合理的物理存储位置;
(2) 为基本表设计索引机制：索引可以提高文件存取速度，改善访问性能，但索引由DBMS管理，它的建立、维护需要一定的系统开销，数据的操作会引起索引的重新调整，还占用一定的存储空间，可根据如下原则决定是否为一个基本表建立索引：
(A) 对于经常需要查询、连接、统计操作，且数据量大的基本表可考虑建立索引，而对于经常执行插入、删除、更新操作或小数据量的基本表应尽量不建立索引;
(B) 一个基本表上除了可以建立一个聚集索引外，还可以建立多个非聚集索引，但索引越多，对表内数据更新所需的开销越大，对于一个更新频繁的表应少建或不建索引;
(C) 索引可以由用户根据需要随时创建或删除，以提高数据查询性能;
6.6.4 数据分布设计
1、不同类型数据的物理分布
(1) 各种数据在系统中的作用不同，使用的频率也不一样，应根据实际使用情况放在合适的物理介质上;
(2) 使用频率低但数据量大的，可以放在磁带中，而使用频繁，要求响应时间短的，必须放在支持直接存取的磁盘存储介质上;
2、 应用数据的划分和分布
(1) 根据数据的使用特征划分：可将基本表划分为频繁使用分区和非频繁使用分区，分别存放在不同的磁盘上，对前者可考虑建立B+树等多层索引，而后者不建立或只建立单层索引;
(2) 根据时间、地点划分;
(3) 分布式数据库系统中的数据划分：
3、派生属性数据分布
(1) 派生属性指该属性的取值可根据表中其他属性的取值惟一确定; (2) 对带有派生属性的基本表可采用两种实现方式： (A) 将派生属性作为基本表内单独一列，称为派生列; (B) 派生属性不出现在基本表中;
4、 关系模式的去规范化
(1) 在数据库物理设计阶段，可以对考虑数据库中某些3NF、BCNF模式是否可以降低其规范化程度，以提高查询效率，这称为关系模式的去规范化处理，但不满足3NF的关系模式又可能导致数据库访问异常，因此，设计基本表时，需在规范化和查询效率间权衡;
6.6.5 安全模式设计
1、系统安全设计
(1) 是指为数据库服务器合法用户分配用户名和口令，使其能够正常登录服务器访问所需的数据，还可采用基于CA认证的系统安全控制机制;
2、 数据安全设计
(1) 是指通过数据库系统视图机制和授权机制为用户对数据库对象访问的权限;
(2) 引用数据视图机制，只给用户需求的那部分数据访问权限，防止由合法用户造成信息泄密，另外数据视图还可以防止基本表发生改变时，影响用户的访问;
(3) 权限是允许用户对一给定的数据库对象可执行的操作;
(4) 数据库安全设计需要根据用户需求，采用授权机制，为用户分配合法访问的权限; 6.6.6 确定系统配置
1、 要根据实际应用系统的运行情况配置系统参数; 6.6.7 物理模式评估
1、 在设计过程中，通过对时间效率、空间效率、维护代价和用户要求权衡考虑，择优采用;
2、 评估物理数据库的方法完全依赖所选用的DBMS，主要从定量估算各方案的存储空间、存取时间和维护代价入手;
第七章 数据库应用系统功能设计
7.1 软件体系结构与设计过程
7.1.1 软体体系结构
1、 软件体系结构又称软件架构，软件体系结构={构件，连接件，约束}。
2、 构件是组成系统的具有一定独立功能的不同粒度的程序模块、独立程序或软件子系统，是组成软件的系统元素;
3、 连接件将不同的构件连接起来，表示了构件间的相互作用;
4、 约束一般是对象连接时的规则，或指明了构件连接的条件。
5、 软件体系结构描述了软件系统的总体组织和层次结构、系统元素及其功能分配、全局控制、系统元素间的协调和交互、数据存取等; 7.1.2 软件设计过程
1、 概要设计
(1) 定义：是建立软件系统的总体结构和模块间的关系，定义各功能模块的接口，设计全局数据库、规定设计约束、制定组装测试计划;
(2) 一个好的概要设计要求是：良好的总体结构、功能模块间较低的耦合度和较高的内聚度，并尽量降低模块接口的复杂性;
(3) 可以采用层次结构图表示软件总体结构，图中节点代表功能模块。
2、 详细设计
(1) 是细化概要设计产生的功能模块，形成可编程的程序模块，并用某种过程设计语言设计程序模块的内部细节，为编写软件代码提供依据。
(2) 可选用结构化设计方法、面向对象设计方法等;
3、 关于软件总体设计
(1) 一些大的DBAS可根据逐步抽象和层次化原则，将概要设计分解成两个步骤：
(A) 首先是软件总体结构设计，即对软件需求进行分解;
(B) 第二步是将每个子系统进一步划分为功能模块，定义各模块的数据结构、相互间交互关系;
7.2 DBAS总体设计
7.2.1 系统总体设计
任务：是根据系统规划与分析结果，特别是技术可行性分析，以及系统需求规范，确定系统总体框架，作为后续设计活动的基础。
1、 确定DBAS体系结构
(1) 指将系统从功能、层次结构、地理分布等角度进行分解，划分为多个子系统。定义各子系统应实现的功能，设计全局控制，明确各子系统间的交互和接口关系;
(2) 可以从功能角度进行分解，也可以根据DBAS自身固有的层次结构特征进行分解; (3) 将系统分解为多个子系统后，需选择和设计合适的系统体系结构，将这些子系统组织起来，并设计它们之间的交互关系;
(4) DBAS体系结构可采用一些通用体系结构，也可根据DBAS所属的特定应用领域相关的体系结构。
2、软硬件造型和配置设计 (1) 总体设计阶段需要对系统的软硬件平台、存储设备、操作系统、数据库管理系统等作出合理的选择，并进行初步配置设计;
(2) 还需要选择系统开发采用的合适的中间件和开发工具，确定开发模式和开发语言;
3、应用软件总体设计
根据系统体系结构，确定相应的软件系统模块划分、功能分配，选择合适的软件体系结构;
4、业务规划初步设计 7.2.2 软件总体设计
1、 DBAS软件包括OS、DBMS、开发环境、中间件和应用软件;
2、 应用软件分为数据库事务和应用程序;
3、 数据库事务通过对数据库的直接操作实现数据管理和处理功能;
4、 应用程序一方面对数据库进一步加工处理，或从中抽取新信息实现复杂的数据处理功能;另一方面还可实现与数据库访问无关的功能;
5、 应用软件总体设计：
(1) 从数据流图、事务规范和业务规则需求分析结果出发，将系统分解为一系列子系统，分配相应功能，定义系统间协调交互机制;
(2) 进一步进行子系统结构设计，将各子系统从功能上划分为：数据库事务模块和应用程序模块;
(3) 确定子系统、应用程序模块、数据库事务间的全局控制和调用关系，并按体系结构框架组织起来。
6、总体设计得到的系统总体结构和分层模块结构，可以用模块结构图表示;
6、 模块结构图，是结构化程序设计中描述系统结构的一种图形化工具，它定义了模块的名字、功能和接口，并在模块结构图中反映出结构化设计思想。它只关心模块的外部特性，与模块内部流程无关，它由模块、调用、数据、控制和转接等于种基本符号组成; 7.2.3 客户/服务器体系结构
1、 基于C/S体系结构的DBAS将DBMS数据管理功能与数据库应用相分离，将DBMS数据库管理功能在客户端和服务器之间进行合理的分布和配置;
2、 数据库报务器完成DBMS的核心功能，而客户端负责完成用户交互功能，接收用户数据，生成并向数据库报务器发出数据操作请求，接收数据查询结果并通过客户端反馈给用户;
3、 两层C/S结构的特点是：
(1) DBAS的数据管理和处理功能，被分解并分布在客户端和服务器上; (2) 服务器楞为多个客户端应用提供共享的数据管理功能; (3) 客户端应用可通过网络访问多个不同数据源;
(4) 客户端除了完成人机交互功能外，还需要完成面向应用的数据处理功能，负荷重，属于典型的“胖客户端”;
4、 三层浏览器/服务器(B/S)结构是一种互联网环境下的新型数据库应用系统结构，它将数据处理功能分解并分布在表示层、功能层和数据层三层次上，分别由WEB浏览器、WEB服务器和数据库服务器来实现，其特点是：
(1) 表示层位于客户端，由WEB浏览器实现，其功能单一，没有其他应用程序，属于典型的“瘦客户端”;
(2) 功能层位于WEB服务器，实现面向具体应用领域的业务规则;
(3) 数据层位于数据库服务器，通过DBMS完成具体的数据存储和存取等数据管理功能;
7.3 概要设计
7.3.1 数据库事务概要设计
1、 如数据处理需求分析的结果是数据流图，则可将待设计的事务看作是程序，采用软件工程中面向数据流的程序设计方法，设计事务内部的数据处理流程和结构，也就是设计事务处理逻辑，过程包括：
(1) 从数据流图中识别出该事务对应的子数据流图; (2) 确定子数据流图中的信息流类型，划定流界;
(3) 将子数据流图映射为事务的结构和处理流程，即事务逻辑;
(4) 修正和细化事务设计，识别事务所访问的数据库对象和数据库用户;
2、 如数据处理需求分析的结果表示为事务规范，由于事务规范包括了事务名称、事务描述、访问的数据项、用户等信息，可直接从事务描述出发，根据具体应用领域的知识设计事务逻辑，得到事务概要结果;
3、 一个完整的事务概要设计包括：事务名称、访问的关系表及属性、事务处理逻辑、事务用户;
4、 检查关系表对数据库事务的支持性：
(1) 对每一个事务，根据需求分析阶段的事务分析，列出该事务所访问的各个数据项; (2) 列出事务访问的数据项所在的关系表和对应的属性; (3) 如事务访问的数据项同时出现在多个表中，检查关联关系;
(4) 检查是否存在某些事务，访问的一些数据项未出现在任何关系表中; 7.3.2 应用软件概要设计
1、 应用软件概要设计，按照逐步求精、模块化、信息隐藏和功能细化原则，根据DBAS需求分析阶段得到的系统功能和业务规则描述，在总体设计结构基础上，将DBAS应用软件进一步细化为模块/子模块，组成软件的系统-子系统-模块-子模块层次结构，并对这些系统元素从结构、行为和数据三方面进行设计;
7.4 详细设计
7.4.1 数据库事务详细设计
1、 事务详细设计，是从事务概要设计得到的事务流程出发，在DBMS平台下，采用事务实现机制，和高级程序设计语言，利用SQL语句和数据库访问接口，在DBMS平台和开发环境下，进一步细化事务设计，设计具体的实现模式; 7.4.2 应用软件详细设计
1、根据概要设计中定义的各程序模块功能和输入输出数据需求，结合具体的设计环境和机制，设计各模块的内部处理流程和算法、数据结构、对外接口等;
7.5 人机界面设计
1、 人机界面设计原则：
(1) 用户应当感觉系统的运行始终在自己的控制之下，保持用户与人机界面间的双向交流; (2) 当系统发生错误或程序运行时间较长时，用户界面应该为用户提供有意义的反馈信息; (3) 应该忍受用户在使用过程中发生的各种操作错误，并能够方便地恢复过来，保证系统不受或少受影响;
(4) 应该遵循一定的标准和常规;
(5) 采取灵活多样的数据输入方式，尽量减少用户数据输入负担;
2、 人机界面设计最好采用原形迭代法：
(1) 初步设计
(2) 用户界面细节设计; (3) 原形设计与改进;
第8章 关系数据库操作语言SQL
8.1 SQL支持的数据类型
8.1.1 数值型
1、 准确型
2、 近似型 8.1.2 字符串型
1、 普通编码字符串类型;
2、 统一编码字符串类型—Unicode编码;
3、 二进制字符串类型; 8.1.3 日期时间类型 8.1.4 货币类型
8.2 定义和维护关系表
8.2.1 关系表的定义与删除
1、定义表
CREATE TABLE <表名> (<列名><数据类型>[列级完整性约束定义]{, <列名><数据类型>[列级完整性约束定义]„}[,表级完整性约束定义])
1、 列级完整性约束：
(1) NOT NULL：取值非空;
(2) DEFAULT：指定列的默认值，形式：DEFAULT 常量; (3) UNIQUE：列取值不重复;
(4) CHECK：列的取值范围，形式：CHECK(约束表达式); (5) PRIMARY KEY：指定本列为主码;
(6) FOREIGN KEY：定义本列为引用其他表的外码;
2、 删除表 DROP TABLE <表名>
8.2.2 修改表结构 ALTER TABLE <表名>
8.3 数据操作语言
8.3.1 数据查询
1、查询语句的基本结构：
SELECT <目标列名序列> FROM <数据源> {WHERE , GROUP BY , HAVING , ORGER BY} (1) 比较：SELECT A，B，C FROM TABLE_A WHERE A>30; (2) 确定范围：WHERE A (NOT)BETWEEN 初始值 AND 结束值; (3) 确定集合：WHERE A (NOT)IN (‘A1’，‘A2’„.‘A3’); (4) 字符串匹配：WHERE A LIKE <匹配符>; (5) 四种<匹配符>：
(A)_(下划线)：匹配任意一个字符; (B)%(百分号)：匹配0个或多个字符; (C)[ ]：匹配[ ]中的任意一个字符; (D)[^]：不匹配[ ]中的任意一个字符;
(6) 涉及空值的查询：WHERE A IS (NOT)NULL;
(7) 多重条件查询：AND(条件必须全部为TRUE，结果才为TRUE)，OR(任一条件为TRUE，结果即为TRUE);
(8) 对查询结果进行排序：ORDER BY A [ASC(顺序) | DESC(逆序)]; (9) 列别名：列名 AS 新列名;
(10) 消除取值相同的行：SELECT DISTINCT A FROM TABLE_A; (11) 使用聚合函数统计数据：SQL的聚合函数：
(A) COUNT(*)：统计表中元组的个数;
(B) COUNT([ALL (全部)| DISTINCT(无重复)] <列名>)：统计本列非空列值的个数;
(C) SUM(列名)：计算列值的总和(必须是数值型列); (D) AVG(列名)：计算列值平均值(必须是数值型列); (E) MAX(列名)：求列最大值; (F) MIN(列名)：求列最小值; (12) 对查询结果进行分组计算：
(A) 使用GROUP BY; (B) 使用HAVING子句;
3、 连接查询
(1) 内连接：FROM 表1 JOIN 表2 ON (连接条件);
(2) 自连接：一种特殊的内连接，相互连接的表在物理上是同一张表，但通过为表取别名的方法，在逻辑上分为两张表;
(3) 外连接：输出不满足连接条件的元组，格式：
FROM 表1 LEFT|RIGHT OUTER JOIN 表2 ON (连接条件)
4、 查询语句的扩展：
(1) 合并多个结果集：SELECT 语句1 UNION SELECT 语句2„„，使用UNION的两个基本规则：
(A) 所有查询语句中列的个数和列的顺序必须相同; (B) 所有查询语句中对应的数据类型必须兼容; (2) 将查询结果保存到新表中：SELECT 查询列表序列 INTO 新表名 FROM 数据源; (3) 使用TOP限制结果集行数：TOP n [percent] [WITH TIES] (A) TOP n ：表示取查询结果的前n行; (B) TOP n percent：表示取查询结果的前n%行; (C) WITH TIES：表示包括并列的结果; (4) 使用CASE表达式：
(A) 简单CASE表达式： (B) 搜索CASE表达式;
5、子查询：如果一个SELECT语句是嵌套在一个SELECT、INSERT、UPDATE或DELETE语句中，则称为子查询或内层查询，包含子查询的语句称为主查询或外层查询;
(1) 使用子查询进行基于集合的测试，形式：WHERE 表达式 [NOT] IN (子查询); (2) 使用子查询进行比较测试，形式：WHERE 表达式 比较运算符 (子查询); (3) 使用子查询进行存在性测试，形式：WHERE [NOT] EXISTS (子查询); 8.3.2 数据修改
1、 添加数据：INSERT [INTO] 表名 VALUE 值列表;使用插入单行语句时要注意：
(1) 值列表中的值与列名表中的列按位置顺序对应，要求它们的数据类型必须一致; (2) 如果[表名]后边没有指明列名，则值列表中的值的顺序必须与表中列的顺序一致，且每一列均有值;
2、 更新数据：形式 UPDATE 表名 SET [列名=表达式] [WHERE 更新条件];
3、 删除数据：：形式DELETE [FROM] 表名 [WHERE 删除条件];
8.4 索引
1、 创建索引：CREATE [UNIQUE] [CLUSTERED | NONCLUSTERED] INDEX 索引名 ON 表名
(1) UNIQUE：表示要创建的索引是唯一索引; (2) CLUSTERED：表示要创建的索引是聚集索引; (3) NONCLUSTERED：表示要创建的索引是非聚集索引;
2、 删除索引：DROP INDEX 索引名;
8.5 视图
8.5.1 定义视图
1、 语法格式：CREATE VIEW 视图名 AS SELECT 语句 [WITH CHECK OPTION]
2、 需要注意下列几点： (1) 在定义视图时要么指定全部视图列，要么全部省略不写。如果省略了视图列名，则视图的列名与查询语句的列名相同。但如下情况则要明确指出组成视图的所有列名： A、 某个目标列不是单纯的属性名，而是计算函数或列的表达式; B、 多表连接时选出了几个同名列作为视图的字段; C、 需要在视图中为某个列选用新的更合适的列名。
(2) WITH CHECK OPTION选项表示通过视图对数据进行增加、删除和更改操作时要保证对数据的操作结果要满足定义视图时指定的WHERE子句条件;
3、 视图通常用于查询数据，也可修改基本表中的数据，但不是所有的视力都可以这样。
4、 定义单源表视图—视图数据可只取自一个基本表的部分行、列，这样的视图行列与基本表行列对应，这样定义的视图一般可以进行查询和更改数据操作
5、 定义多源表视图—视图数据可以来自多个表中，这样定义的视图一般只用于查询，不用于修改数据。
6、 在已有视图上定义新视图—可以在视图上再建立视图，这时作为数据源的视图必须是已经建立好的。
7、 定义带表达式的视图—在定义基本表时，为减少数据库中的冗余数据，表中只存放基本数据，由基本数据经过各种计算派生出的数据一般是不存储的。所以定义视图时可以根据需要设置一些派生属性列，在这些派生属性列中保存经过计算的值。这些派生属性由于在基本表中并不实际存在，因此，也称它们为虚拟列。包含虚拟列的视图也称为带表达式的视图。
8、 含分组统计信息的视图—指定义视图的查询语句中含有GROUP BY 子句，这样的视图只能用于查询，不能修改数据。 8.5.2 删除视图
1、 格式为：DROP VIEW <视图名> 8.5.3 视图的作用
1、 简化数据查询语句;
2、 使用户能从多角度看到同一数据;
3、 提高了数据的安全性;
4、 提供了一定程度的逻辑独立性
第9章 事务调度与并发控制
9.1事务与事务调度
9.1.1 事务的概念
1、 事务是构成数据库应用中一个独立逻辑工作单元的操作的集合，也是访问并可能更新数据库中各种数据项的一个程序执行单元。数据库系统通过执行各种事务实现对数据库数据的操作，管理和执行事务是DBMS的基本功能。 9.1.2 事务的特性(ACID特性)
1、原子性(Atomicity)
一个事务对数据库的所有操作是一个不可分割的工作单元，这些操作要么全部执行，要么一个也不执行。
2、 一致性(Consistency)
当一个事务独立执行时，其执行结果应维护数据库的一致性，即数据库不会因事务执行而受到破坏。数据库满足全部完整性约束，处于正确的状态;
3、 隔离性(Isolation)
当多个事务并发执行时，系统应保证一个事务的执行结果不受其他事务的干扰，事务并发执行结果与这些事务串行执行时的结果是一样的;
4、 持久性(Durability)
一个事务一旦成功完成全部操作，则它对数据库的所有更新就永久地反映在数据库中，即使以后数据库发生了故障; 9.1.3 事务调度
1、 一个事务中各操作的执行顺序和执行时机一方面取决于事务自身内部逻辑，另一方面也受DBMS中事务调度机制的控制。当多个事务并发执行时，DBMS必须采用合适的并发调度机制合理安排各个事务执行顺序，以保证事务的ACID特性。
2、 调度分为串行调度和并发调度，串行调度的特点是一个事务的所有操作都执行完后才开始执行另一事务，不存在事务操作的交叉执行;不同事务操作的交叉执行称为并发调度，DBMS交叉执行来自多个事务的各个操作，以提高数据库系统的性能。 9.1.4 可串行化调度
1、 事务的串行调度能够产生正确的结果，但执行效率低，如果并发调度S等价于某一定义在TS上的串行调度，那么S称为可串行化调度;
2、 给定两个定义在事务集TS上的的调度S和S’，如果可以通过交换S中一系列非冲突操作的执行顺序将S转换为S’，则称S与S’是冲突等价。
3、 如果定义在事务TS上的并发调度S冲突等价于事务集TS上的某个串行调度S’，则称S是冲突可串行的。
4、 在引入冲突可串行概念后，判断一个并发调度是否正确可以归结为判断该调度是否冲突可串行的。
9.2 基于锁的并发控制技术
9.2.1 锁的概念
1、 对数据库系统中每个可能被多个事务并发访问的数据项设置锁，锁代表了对该数据项的访问权限。即事务T在访问数据项Q前须向DBMS申请获得设置在Q上的锁，如成功，则T获得对Q的访问权，T对Q操作完成后，释放所占用的锁，允许其他事务获得该锁并访问Q，在T释放设置在Q上的锁前，其他事务不能访问Q。
2、 锁的类型有两种：
(1) 互斥锁(X锁)：若T获得Q上的X锁，则T可以对Q读写，其他事务不能再对Q进行任何操作，直到T释放Q上的锁;
(2) 共享锁(S锁)：若T获得Q上的S锁，则T可以对Q进行读取操作，但不可以修改，同时，允许其他事务再申请获得Q上的S锁，与T并行读取Q，但在T释放Q上的S锁前，其他事务不能对Q做任何修改;
9.2.2 加锁协议
1、 保证数据一致性的三级加锁协议：
(1) 1级加锁协议要求事务T在修改数据项Q之前必须先对Q加X锁，直到事务结束才释放，事务结束包括正常结束和非正常结束，但事务如果只对Q读而不写，则不需对Q加锁;
(2) 2级加锁协议是在1级加锁协议基础上，要求T在读取Q前必须先对其加S锁，读完后立即释放S锁;
(3) 3级加锁协议是在1级加锁协议基础上，要求在读取Q前必须先对其加S锁，但需等到事务结束后才释放S锁。
9.2.3 两阶段锁协议
1、 两阶段锁(2PL)基本原理如下：
(1) 每个事务的执行过程划分为两个阶段，加锁阶段和解锁阶段;
(2) 在加锁阶段，事务可以申请获得任何数据项上的任何类型的锁，但是不允许释放任何锁; (3) 在解锁阶段，事务可以释放任何数据上的任何类型的锁，但是不能再申请任何的锁; (4) 每个事务开始执行后就进入加锁阶段，当第一次释放锁后，即进入解锁阶段。 9.2.4 锁粒度
1、 施加X锁和S锁的数据项大小称为锁粒度。
2、 锁粒度越大，系统中可以被锁的数据项就越少，事务的并发执行度也越低，但同时系统的开销也小，相反，当锁粒度越小时，事务的并发度高，但系统开销也较大;
9.3 死锁处理
9.3.1 死锁预防
1、 一次加锁法
该方法要求每个事务在开始时必须将需要访问的数据项全部加锁，否则不能执行下去，也就是要求事务必须一次性地获得对需要访问的全部数据项的访问权; 该方法的缺点是：
(1) 多个数据项会被一个事务长期锁定独占，导致其他事务无法及时访问这些数据项，降低了系统的并发程度;
(2) 由于很难事先精确知道每个事务在执行过程中需要加锁的全部数据项，只能扩大加锁范围，将事务执行时可能访问的所有数据项全部加锁，进一步降低了系统的并发程度;
2、 顺序加锁法
该方法对数据库中事务访问的所有数据项规定一个加锁顺序，每个事务在执行过程中必须按此顺序对所需数据加锁; 该方法的缺点：
(1) 数据库中需要加锁的数据项非常多，并且不断变化，维护这些数据项的加锁顺序很困难，代价非常大;
(2) 事务访问的数据项有时无法事先完全确定，有时很难要求事务按照固定的顺序对这些数据项进行加锁;
9.3.2 死锁检测与恢复
1、 死锁检测
(1) 可以利用事务等待图进行死锁检测，数据库系统出现死锁当且仅当事务等待图中包含回路，而且回路中的所有事务就是处于死锁的事务;
(2) 数据库并发控制子系统动态地构造和维护事务等待图，并周期地检测等待图，如图中有回路，则说明系统中出现了死锁;
2、死锁恢复
(1) 当发现死锁存在时，系统可以通过死锁恢复机制将系统从死锁中解救出来，通常是选取一个或几个死锁事务，撤消这些事务，释放其所有的锁，消除事务等待图中的回路，从而解决了系统死锁问题;
(2) 如果决定撤消哪个事务或哪些事务，有两个原则：
A、 选择处于最多条回路交点处的事务; B、 选择具有最少撤消代价的事务。
9.4 活锁处理
1、如果一个事务在系统不存在死锁的情况下，长期得不到DBMS的获批，处于长时间等待中的情况叫活锁，为了避免活锁，DBMS可采用先来先服务的原则解决。
第10章 数据库的实施、运行和维护
10.1数据库的实施
10.1.1 定义数据库结构
1、 为了实现数据库的逻辑结构设计和物理结构设计结果，必须建立实际的数据库，即在确定了数据库的逻辑结构和物理结构后，开发人员使用具体的DBMS提供的数据定义语言(DDL)来严格描述数据库结构。 10.1.2 数据装载
1、 完成了数据库定义后，还须装入各种实际数据;
2、 由于数据的来源不同，其组织方式、结构、格式会不同，可能出现源数据与新数据库结构不相容;
3、 我们可以先将源数据提取出来，存入计算机，然后分类转换，成为符合新数据库结构的数据，再存入数据库，具体步骤如下：
(1) 筛选数据;(2)转换数据格式;(3)输入数据;(4)校验数据;
4、 为完成初始数据的录入，通常需要设计一些数据录入子系统，由计算机辅助完成入库工作，对某些纸质数据或数据量少的数据，可由人工一条条进行录入;而对于数据量大的数据，可考虑采用批量数据装载程序来实现。 10.1.3 编写与调试应用程序
1、 只有当数据库的结构建立好后，才能开始应用程序的编写和调试;
2、 可使用模拟数据进行程序的调试。 10.1.4 数据库的试运行
1、 应用程序调试完成并已有一小部分数据入库，就可以开始数据库的试运行，也称联合调试;
2、 试运行十分重要，因为：
(1) 检测应用程序在接近真实的环境中运行是否符合设计要求; (2) 检测系统设计的性能和评价。
3、 试运行的工作主要有两个：
(1) 功能测试：运行数据库应用程序，执行各种操作，测试程序是否满足设计要求，找出不足，改进现有程序直到符合设计要求;
(2) 性能测试：测量系统的性能指标，分析是否符合设计目标。
10.2 数据库的运行和维护
1、 数据库设计并试运行后，如试运行结果符合设计目标，数据库就可以真正投入运行了，同时也标志着开发任务的基本结束和维护工作的开始;
2、 维护工作包括：
(1) 数据库的转储与恢复; (2) 数据库安全性和完整性控制; (3) 数据库性能的检测与改善; (4) 数据库的重组和重构。
10.3 监控分析
1、 数据库的监控分析：指管理员借助相应工具在数据库运行过程中监测数据库系统的运行情况，掌握数据库当前或以往的负荷、配置、应用和其他相应信息，并对监测数据进行分析，分析数据库的性能参数和环境信息，评估系统的整体运行状态，为系统的安全运行和性能调优提供依据，并提出相应的改善措施，帮助管理人员尽早清除数据库的性能隐患;
2、 监控分析的目的：保证数据库系统安全、稳定地运行，以便在发现不正常的情况时，及时对系统进行维护;
3、 根据实现的方法不同，监控的机制分为：
(1) 自动监控机制; (2) 手动监控机制。
4、根据监控的对象不同，监控分为：
(1) 对数据库架构体系的的监控; (2) 对数据库性能的监控。
10. 4 空间管理
1、 在数据库运行过程中，对数据库空间使用情况，特别是空间的增长情况进行监控，并采取相应的措施对空间进行管理非常重要;
2、 空间管理主要包括：创建数据库空间，更改空间大小，删除空间，修改空间状态，新建、移动、关联数据文件等;
10. 5 参数调整
1、外部调整： (1) CPU：当数据库操作对CPU的要求超过数据库服务器的CPU性能时，数据库性能就受到CPU的限制，使数据库操作变慢;如业务高峰时，CPU的使用量仍然很低，说明服务器CPU资源充足;
(2) 网络：大量的SQL数据在网络上传输会导致网速变慢，调整网络设备，也可以一定程度上提高数据库的性能;
2、 调整内存分配
3、 调整磁盘I/O
4、 调整竞争：
(1) 修改参数以控制连接到数据库的最大进程数; (2) 减少调试进程的竞争; (3) 减少多线程服务进程的竞争; (4) 减少重做日志缓冲区竞争; (5) 减少回滚段竞争。
10. 6 查询优化
1、 合理使用索引：索引是数据库中重要的数据结构，根本目的就是为了提高查询效率，使用原则如下 ：
(1) 经常在索引中作为条件被使用的列，应为其建立索引;
(2) 频繁进行排序或分组(即进行group by或order by操作)的列，应为其建立索引; (3) 一个列的值域很大时，应为其建立索引;
(4) 如果待排列的列有多个，应在这些列上建立复合索引; (5) 可以使用系统工具来检查索引的完整性，必要时进行修复。
2、 避免或简化排序：因为磁盘排序的开销很大，当能够利用索引自动以适当的次序产生输出时，优化器就可以避免不必要的排序步骤，以下是一些影响因素：
(1) 由于现有的索引不足，导致排序时索引中不包括一个或几个等待排序的列; (2) group by或order by子句中列的次序与索引的次序不一样; (3) 排序的列来自不同的表。
为了避免不必要的排序，就要正确地增建索引，合理地合并数据库表。如排序不可避免，那么应试图简化它。
3、 消除对大型表行数据的顺序存取：在嵌套查询中，对表的顺序存取对查询效率可能产生致命的影响，解决方法就是对连接的列进行索引。还可以使用并集来避免顺序存取。
4、 避免相关子查询：查询嵌套层次越多，效率越低，应尽量避免子查询，如不可避免，那么要在子查询中过滤尽量多的行;
5、 避免困难的正规表达式：避免含MATCHES和LINK关键字的正规表达式;
6、 使用临时表加速查询：把表的一个子集进行排序并创建临时表，有时能加速查询;
7、 用排序来取代非顺序磁盘存取;
8、 不充分的连接条件;
9、 存储过程;
10、
11、 不要随意使用游标; 事务处理。
第11章 故障管理
11.1 事务
1、事务是数据库的逻辑控制单位，是操作数据的一个程序执行单元。
2、为了保证数据的完整性，要求数据库系统维护事务具有如下性质：
(1) 原子性：事务是一个不可分割的工作单位，事务中的操作要么都做，要么都不做; (2) 一致性：事务执行的结果必须使数据库从一个一致的状态变到另一个一致的状态; (3) 隔离性：一个事务内部的操作及使用的数据对于其他并发事务是隔离的;
(4) 持续性：一个事务提交后，它对数据库中数据的改变是永久性的，即使系统可能出现故障，也不会对其它执行的结果有任何影响。
11.2 故障的种类及解决方法
11.2.1 事务内部故障
1、预期的事务内部故障：
通过事务程序本身发现的事物内部故障，可以通过将事务回滚，撤销其对数据库的修改，从而使数据库回到一致性的状态;
2、非预期的事务内部故障：
(1)由于事务内部故障大部分属于此类，所以事务故障仅限指此类故障;
(2)事务故障表明事务没有提交或撤销就结束了，因此数据库可能处于不正确的状态，因此，恢复事务必须强行回滚事务，在保证该事务对其他事务没有影响的条件下，利用日志文件撤销其对数据库的修改，使数据库恢复到该事务运行之前的效果; (3)事务故障恢复是由系统自动完成的，对用户是透明的。 11.2.2 系统故障(软故障)
1、指数据库在运行过程中，由于硬件故障、数据库软件及操作系统的漏洞、突然停电等情况，导致系统停止运转，所有正在运行的事务以非正常方式终止，需要系统重新启动的一类故障;
2、系统故障导致内存中的内容丢失，而在硬盘上的内容仍然完好;从而导致数据库的数据可以处于不正确的状态;
3、要消除这些事务对数据库的影响，保证数据库中数据的一致性，办法就是在计算机系统重新启动后，对于未完成的事务可能已经写入数据库的内容，回滚所有未完成的事务写的结果，以保证数据库中数据的一致性;对于已完成的事务可能部分或全部留在缓存区的结果，需要重做所有已提交的事务，以将数据库真正恢复到一致状态。
4、一句话，当数据库发生系统故障时，容错对策是在重新启动系统后，撤销(UNDO)所有未提交的事务，重做(REDO)所有已提交的事务。 11.2.3 介质故障(硬故障)
1、指数据库在运行过程中，由于磁盘损坏、天灾人祸等情况，使用数据库中的数据部分或全部丢失的一类故障;
2、介质故障的容错对策采用两种方式： (1)软件容错：
是使用数据库备份及事务日志文件，通过恢复技术，恢复数据库到备份结束时的状态; (2)硬件容错：
目前常用的方法是采用双物理存储设备，最完全的方式是设计两套相同的数据库系统同时工作，数据的变化也同步，空间有一定距离，这样当发生损坏性的自然现象时，由于两套数据库系统具有空间距离，因此同时发生破坏的概率几乎为零，达到数据库的完全安全。
11.2.4 计算机病毒故障
1、计算机病毒是一种恶意的计算机程序，在对计算机系统造成破坏的同时也可对数据库系统造成破坏(主要破坏数据库文件);
2、可以通过设立防火墙预防，杀毒软件查杀已感染的文件和数据库备份来解决;
11.3 数据库恢复技术概述
1、 恢复机制涉及两个关键问题：
(1) 如何建立冗余数据;
(2) 如何利用这些冗余数据实施数据库恢复。
2、 最常用的建立冗余数据技术是数据备份和登录日志文件，他们通常是结合起来使用的。
11.4 数据转储
1、 数据转储—指数据库管理员(DBA)定期拷贝数据库，并将拷贝得到的数据库放到其他介质中的过程。
2、 DBA可在数据库系统发生故障后，利用这些副本恢复数据库，但此时恢复的数据库只能回到转储时的状态，要想恢复到故障前的状态，需要参考日志文件，重新运行转储后到故障前的所有事务才可以;
3、 静态转储和动态转储
(1) 静态转储：在静态转储过程中系统不能运行其他事务，不允许在转储期间对数据库的任何存取、修改活动。
(2) 动态转储：允许转储操作和用户事务并发执行;
(3) 静态转储虽然保证了数据的有效性，但却是以降低数据库的可用性为代价;而动态转储虽然提高了数据库的可用性，但数据库的有效性却得不到保证。
(4) 为了能保证数据的有效性，而又不降低可用性，就需要引入日志文件，用它记录转储期间各事务对数据库的修改活动，然后使用动态转储的备份副本加上日志文件就可将数据库恢复到某一时刻的正确状态。
3、 几种数据转储机制
(1) 完全转储：对所有数据库进行备份，需占用较多时间和空间，可作为系统失败时恢复数据库的基础;
(2) 增量转储：只复制上次备份后变化的文件;
(3) 差量转储：对最近一次数据库完全备份以来发生的数据变化进行备份，优点是速度快，占用较少的时间和空间。
4、 多种转储方法结合使用
(1) 仅采用完全转储; (2) 完全转储加增量转储; (3) 完全转储加差量转储
11.5 登记日志文件
11.5.1 日志文件的格式和内容
日志文件是记录每个事务对数据库更新操作的文件，数据库系统在运行过程中，DBMS负责将所有事务的更新操作登记到日志文件中，也就是说日志文件是系统自动维护的。
1、以记录为单位的日志文件：其内容包括每个事务的开始标记、结束标记和所有更新操作;每个日志记录的内容包括：事务标识、操作类型、操作对象、更新前数据的旧值，和更新后数据的新值;
2、数据块为单位的日志文件：将更新前的整个数据块和更新后的整个数据块全部放在了日志文件中; 11.5.2 日志文件的作用
1、事务故障恢复和系统故障恢复必须使用日志文件 (1)故障恢复的两个基本操作：UNDO和REDO (A) UNDO的作用是撤销事务，具体步骤：
(a) 反向扫描日志文件，找到需要撤销的事务的更新操作; (b) 对事务的更新操作执行逆操作;
(c) 继续反向查找该事务的其他更新操作，并执行相应的逆操作; (d) 重复执行步骤(C)，直至遇到该事务开始记录。 (B) REDO的作用是重做事务，具体步骤：
(a) 正向扫描日志文件，找到需要重做的事务的更新操作;
(b) 对事务重新执行日志文件登记的操作，即将日志文件中“更新后的值”写入数据库; (c) 继续正向查找该事务的其他更新操作，并重新执行，将日志文件中“更新后的值”写入数据库;
(d) 重复执行步骤(C)，直至遇到该事务的提交记录。 (3) 事务故障恢复：只需把相应的事务作撤销UNDO即可; (4) 系统故障恢复：
(A) 正向扫描日志文件，找到系统故障前发生的所有事务，如果该事务没有完成，将其事务标记加入撤销队列，如果该事务已经完成，则将其事务标记加入重做队列;
(B) 对撤销队列中的所有事务作撤销操作UNDO; (C) 对重做队列中的所有事务作重做操作REDO。
2、在动态转储方式中必须建立日志文件
3、 在静态转储方式中，也可以建立日志文件 11.5.3 登记日志文件的原则
1、 登记的次序严格按并行事务执行的时间次序;
2、 必须先写日志文件，后写数据库
11.6 具有检查点的恢复技术
11.6.1 检查点的作用
检查点最大限度地减少数据库完全恢复时所必须执行的日志部分; 11.6.2 检查点的引入
1、在日志文件中增加一类新的记录—检查点记录，增加一个“重新开始文件”，并让恢复子系统在登录日志文件期间动态地维护日志
2、检查点记录的内容：
(1) 建立检查点时刻所有正在执行的事务清单; (2) 这些事务最近一个日志记录的地址。
第五篇：数据库期末复习教案[定稿]
15计科本《数据库系统原理与应用》期末复习纲要
一、 题型与分值分布
1、
2、
3、
4、 单项选择20题，计20分 填空题，每空1分，计10分 简答题4小题，计20分 综合应用题2题，计50分
(1)概念模型(ER图)，转化成相关的关系模型并写出主码与外码，并建立相关的关系表(20分) (2)T—SQL语名的作用，6小题，计30分
二、 具体知识要点及课后习题
具体知识点： 第一章
1、 数据库中的数据具有哪些基本特点。(永久存储、有组织、可共享)
2、 数据库系统具有哪些基本特点。(数据共享、数据完整性、数据独立性及较小的冗余度)
3、
4、 数据库系统与数据库、数据库管理系统之间的关系? 数据库中的数据独立性分为物理独立性和逻辑独立性，分别指的是什么?P11-12
5、
6、 模式
7、 数据库管理系统的功能结构为P16 数据库系统的三级数据模式结构：逻辑模式、外模式、内数据库系统的二级映象技术是指外模式与模式之间的映象，它不仅在三级数据模式之间建立了联系，同时也保证了数据的独立性。
8、数据的正确、有效和相容称之为数据的完整性 第二章
1、信息的三种世界是指现实世界、信息世界和计算机世界(数据世界)。
2、数据库系统的核心是数据模型，、概念模型是现实世界的第一层抽象，这一类模型中最著名的模型是实体-关系模型。
3、数据模型的三要素是：数据结构、数据操作和完整性约束条件。如“实体完整性”约束规则，要求关系中的“主码”不允许取空值
4、数据库系统中常见的数据模型有：层次模型、网状模型和关系模型
5、概念模型的特点是：对现实世界的第一层抽象;与软、硬件无关;从用户观点对数据建模。逻辑模型的特点是：对现实世界的第二层抽象;与硬件无关，与软件有关;从计算机实现观点对数据建模。 第三章
1、数据库的概念结构设计(E-R图)P55-58: E-R模型是对现实世界的一种抽象，E-R图的主要成分是实体、联系和属性;各分E-R图之间的冲突主要有属性冲突、命名冲突和结构冲突三类。
2、概念模型向关系模型的转换(逻辑结构设计)P62
3、概念数据模型不依赖于任何数据库管理系统。实体-关系模型是概念模型中最著名的一种。 第四章
1、数据库中关系的类型有基本表、视图表和查询表三种，它们各有何不同P91
2、关系中的基本名词：元组、属性、候选码和主码、全码、主属性和非主属性P91 一个关系只有一个主码
3、数据库中基本关系的性质P92
4、关系的完整性 P95
5、关系操作语言的种类：关系代数语言、关系演算语言、基于映象的语言(如SQL是一种映象，是非过程化的)。SQL包含数据定义、数据操作和数据控制三种功能
5、关系模型的完整性约束有三类：实体完整性、参照完整性和用户定义的完整性 P96 主要掌握主码、外码等
6、专门的关系运算：选择、投影、连接
7、关系代数运算中，传统的集合运算有笛卡尔积、并、交和差
8、数据库数据具有永久存储、有组织、可共享三个基本特点。 重点掌握4.2.3用关系代数表示检索的实例 第五章
1、SQL语句分类，按功能分为数据定义语句、数据操纵语句、数据控制语句
2、SQL的数据定义包括基本表、索引、视图和数据库(重点掌握视图的建立和用SQL语句写出查询程序)，如在关系数据库系统中，为了简化用户的查询操作，而又不增加数据的存储空间，常用的方法是创建视图
学会同时用SQL语言和关系代数实现下列相关操作
P119 例5-
1、5-
2、5-3
3、SQL的数据更新语句有插入(INSERT)、修改(UPDATE)与删除(DELTE)三种
4、数据控制是系统通过对数据用户的使用权限加以限制而保证数据安全的重要措施。SQL的数据控制语句包括授权(Grant)、收权(Revoke)和拒绝访问(Deny)三种。用户权限包含数据对象和操作类型两个要素;而数据库角色是被命名的一组与数据库操作相关的权限，角色是权限的集合
5、利用游标进行查询需要4种语句，分别是说明游标、打开游标、推进游标、关闭游标
第六章
1、数据库对象包含哪些?P156 SQL Server2008的数据库对象有很多，例如：表、视图、角色、索引(或存储过程、默认值、数据类型、触发器、约束)
2、数据库类别P157
3、数据库对象是数据库的逻辑文件。SQL Server2008的数据库对象包括表、视图、角色、索引、数据类型、默认值、存储过程、触发器和约束等。了解各自的含义。
4、SQL Server2008的数据库中有3种物理文件：基本数据文件、辅助数据和日志文件
5、掌握视图的创建和维护方法。视图是根据子模式建立的虚拟表。视图的有哪些优点呢?
如：视图能够简化用户的操作;视图使用户能以多种角度看待同一数据;视图对重构数据库提供了一定程度的逻辑独立性;视图能够对机密数据提供安全保护 P247
6、掌握存储过程和触发器的创建和维护.P179
7、Trantsact-SQL语言：重点放在数据操纵语言P192 第七章
1、关系模式应满足的基本要求P214
2、已知关系模式R及其上的相关函数依赖集合，会求出该关系模式对应的候选码。
例1：已知关系模式R(A，B，C，D，E)及其上的函数依赖集合F={A→D，B→C ，E→A }，该关系模式 的候选码是(BE)
例2：学生表(id，name，sex，age，depart_id，depart_name)，存在的函数依赖是id→{name，sex，age，depart_id}; dept_id→dept_name，其满足2NF
3、重点掌握课本习题P239 3 P240 15(1) 第八章
1、数据库安全性是指什么?P244
2、数据库安全性控制的一般方法有哪些?P244
3、数据库完整性是指数据的正确性和相容性。P259 (1)数据完整性约束分为表级约束、元组约束和属性约束
(2)SQL server使用约束、默认、规则和触发器4种方法定义和实施数据库完整性功能
4、数据库并发控制。数据库的并发控制就是控制数据库，防止多用户并发使用数据库时造成数据错误和程序运行错误，保证数据的完整性。解决事务并发操作带来的数据不一致性，常用封锁机制。
5、事务的概念和特征P265 并发操作带来的数据不一致性包括3类：丢失修改、不可重复读和读“脏”数据。
6、封锁：封锁机制作为并发控制的重要手段，利用封锁的特性和封锁协议，它在并发操作保证事务的隔离性，用正确的方式调度并发操作，使一个用户事务的执行不受其他事务的干扰，从而避免造成数据的不一致。
(1)锁的类型：排他锁(X锁)和共享锁(S锁)，它们各自的特点是什么。P268 (2)封锁协议：一级封锁协议、二级封锁协议(如1：事务T对要修改数据必须先加X锁，直到事务结束才释放X锁;对要读取数据必须先加S锁;如2：若事务T对数据对象A加上X锁，则只允许T读取和修改A，其他任何事务都不能再对A加任何类型的锁)、三级封锁协议;
封锁出现的问题及解决的方法。举例说明何谓活锁，如何解决活锁?P270
7、数据库恢复技术
恢复机制涉及的两个关键问题是：第一，如何建立备份数据;第二，如何利用这些备份数据实施数据恢复。建立备份数据最常用的技术是数据转储和登录日志文件。
数据库的备份方法通常有完整备份、差异备份、事务日志备份
8、何谓两段锁协议 P271
9、何谓“并发调度可串行化” P270;何谓“可串行化调度” P271
10、用户权限是由两个要素组成的，分别是数据对象和操作类型
11、数据库角色是被命名的一组与数据库操作相关的权限，角色是权限的集合。
课后习题
1、
2、
3、 第1章P19：
一、4;5;10
二、全部 第2章P42：
二、全部
第3章P85:
一、
19、
22、23
二、全部
4、第4章P111：
一、
14、
15、16
二、
8、9
11、
21、
22、
24、
25、
32、33
5、第5章 P127 4
6、
7、
8、 第6章P176：
一、
2、3
二、
1、
4、
6、
7、
8、
9、
10、
11、12 第7章P205:
二、
1、
6、
7、
8、9 第8章P252：
一、
1、3 、
12、
13、
15、26
二、
8、
12、
13、
15、
16、18