数据库系统标准设计期末考总结.docx

数据库系统设计期末考总结
Ø 什么是数据库？
数据库是被一个系统所使用全部数据集合
数据库管理员(Database Administrator)
Ø 什么是数据库管理系统？（DBMS）
数据库管理系统就是帮助存放，管理和使用数据库程序集合，对数据库进行统一管理和控制，以确保数据库安全性和完整性
Ø DBMS（database management system）数据库管理系统环境组成
硬件，软件，数据，程序（procedures），人
Ø 数据库系统开发生命周期(database system development lifecycle)

Ø 数据库设计三个关键步骤:
概念设计
逻辑设计
物理设计

Ø C/S vs B/S
C/S
即Client/Server (用户机/服务器) 结构，经过将任务合理分配到Client端和Server端，降低了系统通讯开销，需要安装用户端才可进行管理操作。
用户端和服务器端程序不一样，用户程序关键在用户端，服务器端关键提供数据管理、数据共享、数据及系统维护和并发控制等，用户端程序关键完成用户具体业务。
开发比较轻易，操作简便，但应用程序升级和用户端程序维护较为困难。
三层C/S构架
在三层架构中，用户端接收用户请求，用户端向应用服务提出请求，应用服务从数据库服务中取得数据，应用服务将数据进行计算并将结果提交给用户端，用户端将结果展现给用户。

Ø 两层和三层区分？
两层架构
Client side presented two problems preventing true scalability:
¡ ‘Fat’ client, requiring considerable resources on client’s computer to run effectively.
¡ Significant client side administration overhead.
¡ By 1995, three layers proposed, each potentially running on a different platform.
用户端提出两个问题阻止真正可伸缩性:
脂肪”用户端,需要相当大用户端电脑上资源有效地运行。
重大用户端管理开销。
三层架构
Advantages:
¡ ‘Thin’ client, requiring less expensive hardware.
¡ Application maintenance centralized.
¡ Easier to modify or replace one tier without affecting others.
¡ Separating business logic from database functions makes it easier to implement load balancing.
¡ Maps quite naturally to Web environment.
优点:
瘦”用户机,需要更少昂贵硬件。
应用程序维护集中。
轻易修改或替换一个层而不影响其它。
将业务逻辑和数据库函数分开使其轻易实现负载平衡。
很自然地映射到Web环境。

Three main types of transactions（三种关键类型事务）:

retrieval transactions检索事务
update transactions更新交易处理
mixed transactions混合事项

B/S
即Browser/Server (浏览器/服务器) 结构,用户界面完全经过WWW浏览器实现。
用户端基础上没有专门应用程序，应用程序基础上全部在服务器端。因为用户端没有程序，应用程序升级和维护全部能够在服务器端完成，升级维护方便。因为用户端使用浏览器，使得用户界面“丰富多彩”，但数据打印输出等功效受到了限制。

Ø SQL
SQL分类： 
 DDL—数据定义语言(CREATE，ALTER，DROP，DECLARE)   
 DML—数据操纵语言(SELECT，DELETE，UPDATEINSERT)  
  DCL—数据控制语言(GRANT，REVOKE，COMMIT
n Query（查询）
n Security(安全)
n Index（索引）
n View（视图）

Ø ERD
A five-step process for ERD construction :
ERD构建五个步骤过程:
n Step1: Represent Entities as Tables（将实体转换成表）
n Step2: Determine Relationships（确定关系）
¡ In most cases, a record in one table will correspond to multiple records in another table.
在大多数情况下,一个表统计将对应于另一个表中多条统计。
¡ For many-to-many relationships, a new associative table must be created between two tables. 多对多关系,必需创建一个新关联表两个表之间关系。
n Step3:List Fields（确定表属性）
n Step4: Identify Keys（确定键，主键和外键）
n Step5: Determining Data Types确定数据类型
¡ Primary and foreign keys must match in data type and size. 主键和外键必需匹配数据类型和大小。
2.主键
A primary key uniquely identifies each record in a table.
主键唯一标示表中每一条统计。
n Unique
n Minimal
n Not Null
n Nonupdateable
3.外键
假如公共关键字在一个关系中是主关键字，那么这个公共关键字被称为另一个关系外键。
4.完整性
实体完整性：每个表一定要有一个正当主键。（主键值唯一）
参考完整性规则（Referential Integrity）：若属性组F是关系模式R1主键，同时F也是关系模式R2外键，则在R2关系中，F取值只许可两种可能：空值或等于R1关系中某个主键值。（外键，值在主键中没有出现）
5.范式
第一范式：（1NF）强调是列原子性，即列不能够再分成其它几列。 Definition: A table in which all fields contain a single value.
第二范式：（2NF）属性完全依靠于主键Definition: A table in which each non-key field is determined by the whole primary key and not part of the primary key by itself.
没有包含在主键中列必需完全依靠于主键，而不能只依靠于主键一部分。
第三范式：（3NF）属性不依靠于其它非主属性
首先是 2NF，另外非主键列必需直接依靠于主键，不能存在传输依靠。即不能存在：非主键列 A 依靠于非主键列 B，非主键列 B 依靠于主键情况。
6.Normalization规范化
没有进行规范化数据存在插入（表没有分开，插入数据是产生异常），更新（数据冗余，更新时产生异常），删除异常（表没有分开，数据间存在依靠关系）同一张表本身设计不合理造成异常
规范化优缺点
优点:
• 消除更新异常
• 降低数据冗余
• 处理了数据完整性问题
• 节省存放空间
缺点:
• 包含多表子查询和表之间联接，需要更复杂SQL语句
• DBMS额外工作使应用程序变慢

7.关系型数据库优点
n 依靠逻辑,而不是物理、相关统计之间联络　　
n 使用第四代语言(4 gl) 　
n 备抵高度数据独立性

n Weak Entity（弱实体）
一个实体对于另一个实体含有很强依靠关系，而且该实体主键一部分或全部全部是从其它强实体中取得，则称该实体为弱实体
n Derived attribute（派生属性）
Attribute that represents a value that is derivable from value of a related attribute, or set of attributes, not necessarily in the same entity.
属性代表了一个值从一个相关属性中派生出来,或一组属性值引出，,不一定在同一个实体。

n recursive relationship（递归关系）
添加一个外键，使得有一对多关系，多对多关系

n complex relationship(复杂关系)
Multiplicity is the number (or range) of possible occurrences of an entity type in an n-ary relationship when other (n-1) values are fixed.

n problems in an ER model
Often due to a misinterpretation of the meaning of certain relationships.
通常因为特定意义关系误解。
connection traps. (连接陷阱)
俩个关键连接陷进：扇形陷进和深坑陷进
扇形陷进：两个实体有一个一对多关系，从而扇出第三个实体，两个实体键本该有一个直接关系提供必需信息
深坑陷进：一个模型显示实体之间存在关系,但一些实体出现之间路径不存在。
n Supertype/Subtype Hierarchies（超类和子类）
某个实体类型中全部实体同时也是另一个实体类型实体.此时,我们称前一实体类型是后一实体类型子类(Subtype),后一实体类型称为超类(Supertype).
不过子类有一个很关键性质:继承性。子类继承其超类上定义全部属性,其本身还能够包含其它另外属性.
第九章：
磁盘性能指标：磁盘容量，存取时间，数据传输速度，可靠性
磁盘总容量
统计盘面数*每统计盘面磁道数*每磁道扇区数*每扇区字节数
扇区：扇区是磁盘寻址最小单位，其大小通常是512字节
数据在磁盘上定位信息：柱面号，磁头号，扇区号
编址方法：柱面从外向内编址（如：0~199），磁道按柱面编号（如：0号柱面从上向下编号0~19，再给1号柱面磁道编号），盘块号（假设每个磁道有17个扇区，0号柱面0号磁道0号扇区盘块号为0,0号柱面1号磁道0号扇区盘块号为17）

Access time (存取时间)– the time it takes from when a read or write request is issued to when data transfer begins. (一个读或写请求发出到数据开始传输时间) Consists of:
Seek time （寻道时间）– time it takes to reposition the arm over the correct track.
4 将磁头移到柱面时间：约2~30ms
Rotational latency （旋转等候时间）– time it takes for the sector to be accessed to appear under the head.
4 约10~20ms
l 总时间：10~40ms

Data-transfer rate – the rate at which data can be retrieved from or stored to the disk. （从磁盘上读取数据或存放数据到磁盘时间）

Mean time to failure (MTTF) （平均失效时间）– the average time the disk is expected to run continuously without any failure.（磁盘无故障连续运行时间Typically 3 to 5 years）

Block – a contiguous sequence of sectors from a single track
data is transferred between disk and main memory in blocks
sizes range from 512 bytes to several kilobytes
内存和外存一次数据交换称为一次I/O操作，每次交换数据量是一个Block
内存中开辟缓冲区大小最少要等于一个block
Block大小通常由DBMS厂商决定
廉价磁盘冗余阵列（RAID） Redundant Arrays of Independent Disks
经过冗余提升可靠性
是一个利用大量廉价磁盘进行磁盘组织技术
价格上，大量廉价磁盘比少许昂贵大磁盘合算得多
性能上，使用大量磁盘能够提升数据并行存取
可靠性上，冗余数据能够存放在多个磁盘上，所以一个磁盘故障不会造成数据丢失
冗余（Redundancy）
存放额外信息，方便当磁盘故障时能从中重建
磁盘还是内存？
l 5-minute rule：假如一个被随机访问页面使用频率超出每5分钟一次，那么它应该被驻留在内存
l minute rule：假如被次序访问页面使用频率超出每1分钟一次，那么它应该被驻留在内存

文件存放：
The database is stored as a collection of files. Each file is a sequence of records. A record is a sequence of fields
数据库是存放为文件集合。每个文件全部是一个序列统计。字段统计是一个序列。

第十章：
Basic Steps in Query Processing（查询处理基础步骤）：
1. Parsing and translation解析和翻译
2. Optimization最优化
3. Evaluation评定

RDBMS查询处理阶段 ：
1. 查询分析
2. 查询检验
3. 查询优化
4. 查询实施

选择操作经典实现方法：
1. 简单全表扫描方法
Ø 对查询基础表次序扫描，逐一检验每个元组是否满足选择条件，把满足条件元组作为结果输出
Ø 适合小表，不适合大表
2. 索引(或散列)扫描方法
Ø 适合选择条件中属性上有索引(比如B+树索引或Hash索引)
Ø 经过索引先找到满足条件元组主码或元组指针，再经过元组指针直接在查询基础表中找到元组

排序
n 原因
n SQL查询能够指定对输出进行排序
n 关系运算一些操作，如连接运算，排序后实现高效
n 对于可放进内存关系，使用如快排序之类技术。对不能放进内存关系，使用外排序

n 内排序
n 当数据集小于可用内存时，采取快速排序算法
n 快速排序思想起源于分治策略。将数据块划分为两个序列，第一个序列值小于第二个序列，在两个序列中根据递归排序思想再次进行上述划分，这么直到没有措施划分为止
n 外排序
n 创建有序段＋N路归并
n 全部输入数据最初分成很多有序归并段文件，然后不停归并成很多更大归并段文件，直到剩下一个文件为止
§ Join Operation
多个不一样连接算法
Nested-loop join（嵌套循环连接）
Block nested-loop join（块嵌套循环连接）
Indexed nested-loop join（索引嵌套循环连接）
Merge-join（合并连接）
Hash-join（哈希或散列连接）
Choice based on cost estimate（依据成本估算选择连接方法）
关系型数据库优点
§ 依靠逻辑,而不是物理、相关统计之间联络　　
§ 使用第四代语言(4 gl) 　
§ 备抵高度数据独立性

Ø 关系数据库系统查询优化
v 查询优化优点不仅在于用户无须考虑怎样最好地表示查询以取得很好效率，而且在于系统能够比用户程序“优化”做得愈加好
(1) 优化器能够从数据字典中获取很多统计信息，而用户程序则难以取得这些信息
(2)假如数据库物理统计信息改变了，系统能够自动对查询重新优化以选择相适应实施计划。在非关系系统中必需重写程序，而重写程序在实际应用中往往是不太可能
(3)优化器能够考虑数百种不一样实施计划，程序员通常只能考虑有限多个可能性。
(4)优化器中包含了很多复杂优化技术，这些优化技术往往只有最好程序员才能掌握。系统自动优化相当于使得全部些人全部拥有这些优化技术

v RDBMS关系型数据库管理系统（Relational Database Management System）经过某种等价模型计算出多种查询实施策略实施代价，然后选替换价最小实施方案
§ 集中式数据库
Ø 实施开销关键包含：
– 磁盘存取块数(I/O代价)
– 处理机时间(CPU代价)
– 查询内存开销
Ø I/O代价是最关键
§ 分布式数据库
Ø 总代价=I/O代价+CPU代价+内存代价＋通信代价
v 查询优化总目标：
§ 选择有效策略
§ 求得给定关系表示式值
§ 使得查询代价最小(实际上是较小)
Ø 实际系统查询优化步骤：
1. 将查询转换成某种内部表示，通常是语法树
2. 依据一定等价变换规则把语法树转换成标准（优化）形式
3. 选择低层操作算法
对于语法树中每一个操作
• 计算多种实施算法实施代价
• 选择代价小实施算法
4. 生成查询计划(查询实施方案) 查询计划是由一系列内部操作组成。
2 代 数 优 化
v 代数优化策略：经过对关系代数表示式等价变换来提升查询效率
v 关系代数表示式等价：指用相同关系替换两个表示式中对应关系所得到结果是相同
v 两个关系表示式E1和E2是等价，可记为E1≡E2
具体方法 笛卡尔积

v 查询树启发式优化
v 经典启发式规则：
1. 选择运算应尽可能先做。在优化策略中这是最关键、最基础一条
2. 把投影运算和选择运算同时进行
如有若干投影和选择运算，而且它们全部对同一个关系操作，则能够在扫描此关系同时完成全部这些运算以避免反复扫描关系
3. 把投影同其前或其后双目运算结合起来
4. 把一些选择同在它前面要实施笛卡尔积结合起来成为一个连接运算
5. 找出公共子表示式
假如这种反复出现子表示式结果不是很大关系而且从外存中读入这个关系比计算该子表示式时间少得多，则先计算一次公共子表示式并把结果写入中间文件是合算
当查询是视图时，定义视图表示式就是公共子表示式情况
6. 在实施连接操作前对关系合适进行预处理
§ 按连接属性排序
§ 在连接属性上建立索引 
v 索引：
v Search Key（检索关键字） - attribute to set of attributes used to look up records in a file.（设置属性用于查找在一个文件中统计）
An index file consists of records (called index entries) of the form（一个索引文件包含统计表格即索引项表）

Index files are typically much smaller than the original file (索引文件比源文件小很多)
v Two basic kinds of indices（两种基础索引）:
Ordered indices（指令索引）: search keys are stored in sorted order（根据次序搜索密钥存放）
Hash indices（哈希索引）: search keys are distributed uniformly across “buckets” using a “hash function”.检索关键字均匀分布哈希函数桶中）
v clustering index聚簇索引：
Primary index: in a sequentially ordered file, the index whose search key specifies the sequential order of the file.初级索引:在一个次序文件、索引搜索键指定文件次序。
Also called clustering index聚簇索引
The search key of a primary index is usually but not necessarily the primary key.主索引检索关键字通常但不一定是主键。
v non-clustering index.非聚簇索引
Secondary index: an index whose search key specifies an order different from the sequential order of the file. 索引检索关键字指定一个次序不一样于文件中次序。 Also called
non-clustering index.非聚簇索引
v Dense Index Files（密集索引文件）指向行
Index record appears for every searchkey value in the file. 索引统计对应每个检索关键字值（一一对应）
v Sparse Index Files（稀疏索引文件）指向页
contains index records for only some search-key values. 只包含部分search-key值索引统计。
Applicable when records are sequentially ordered on search-key适适用于统计次序统计检索关键字
v Multilevel Index

v 冲突可串行化
n 冲突指令
当两条指令是不一样事务在相同数据项上操作，而且其中最少有一个是write指令时，则称这两条指令是冲突
如在②、③、④情况下，Ii和Ij 是冲突
非冲突指令交换次序不会影响调度最终止果
n 冲突等价
假如调度S能够经过一系列非冲突指令交换转换成调度S'，则称调度S和S'是冲突等价

v B+-tree
B+-tree indices are an alternative to indexed-sequential files（B+ 树索引是连续索引文件替换）
v Disadvantage of indexed-sequential files（次序索引文件缺点）
• performance degrades as file grows, since many overflow blocks get created. （伴随文件增多，性能会有所下降，因为创建了很多溢出块）
• Periodic reorganization of entire file is required.（必需定时重组整个文件）
v Advantage of B+-tree index files（B+-tree优点）:
• automatically reorganizes itself with small, local, changes, in the face of insertions and deletions.（在进行插入和删除时候，能自动对备份和更改善行整理）
• Reorganization of entire file is not required to maintain performance.（对于性能维护，不需要对整个文件进行重组）
v (Minor) disadvantage of B+-trees（缺点）:
extra insertion and deletion overhead, space overhead.
（额外插入和删除开销,空间开销。）

Advantages of B+-trees outweigh disadvantages，B+-trees are used extensively（B+-trees优点大于缺点，被广泛使用）

v A B+-tree is a rooted tree satisfying the following properties（B+-tree含有以下属性）:
All paths from root to leaf are of the same length（全部树枝从根到叶长度相同）
Each node that is not a root or a leaf has between én/2ù and n children.（每个不是根节点也不是叶子节点节点有n/2到n个孩子节点）
A leaf node has between é(n–1)/2ù and n–1 values
特殊情况: 　　假如根不是一片叶子,它最少有两个孩子。　　假如根是叶(即没有其它节点树),它能够有0到(n - 1)之间值。
B+-Tree Node Structure（节点结构）

P1是指针，指向子节点（非叶子结点）或指向统计内容（叶子结点）
Ki are the search-key values
K1是关键字检索值
B+-Tree中叶子结点

Ø ACID properties of a Transaction（事务ACID属性）
n 原子性（Atomicity）：一个事务中全部操作要么全部成功，要么全部失败。原子性由恢复机制实现。
n 一致性（Consistency）：事务完成后，全部数据处于应有状态，全部内部结构正确，能够正确反应事务所作工作。基于隔离性实现。
n 隔离性（Isolation）：一个事务不会干扰另一个事务进程，事务交叉调度实施结果和串行调度实施结果是一致。隔离性由并发控制机制实现。
n 持久性（Durability）：事务提交后，对数据库影响是持久，即不会因为系统故障影响事务持久性。持久性由恢复机制实现。
Ø 事务调度：
p 事务实施次序称为一个调度，表示事务指令在系统中实施时间次序
p 一组事务调度必需确保
n 包含了全部事务操作指令
n 一个事务中指令次序必需保持不变
p 串行调度
n 在串行调度中，属于同一事务指令紧挨在一起
n 对于有n个事务事务组，能够有n！个有效调度
p 并行调度
n 在并行调度中，来自不一样事务指令能够交叉实施
n 当并行调度等价于某个串行调度时，则称它是正确

Ø 锁
v 锁作用
n 一个事务对某个数据对象加锁，取得对它一定控制，限制其它事务对该数据对象使用，由此提供事务需要隔离性，确保各个事务不会相互干扰，一个事务不会读取或修改另一个事务正在使用数据。
n 另外，锁提供隔离性还确保事务一致性。
n 为了使系统性能良好，应使事务尽可能简短和不受干扰。
n 要访问一个数据项R，事务Ti必需先申请对R封锁，假如R已经被事务Tj加了不相容锁，则Ti需要等候，直至Tj释放它封锁

v 锁模式关键有六种：共享锁、更新锁、排她锁、结构锁、意向锁和块更新锁。

p 共享锁（S锁，Share lock）
n 事务T对数据对象R加上S锁，则其它事务对RX锁请求不能成功，而对RS锁请求能够成功；又称读锁
n 申请对R共享锁： lock-S(R)
n 用于只读数据操作，它允很多个并发事务读取（Select）锁定资源，但严禁其它事务对锁定资源进行修改。通常读取数据后就释放共享锁，除非要将锁升级。
p 排它锁（X锁，eXclusive lock）
n 事务T对数据对象R加上X锁，则其它事务对R任何封锁请求全部不能成功，直至T释放R上X锁；又称写锁
n 申请对R排它锁：lock-X(R)
n 通常来说，SQL Server在事务结束时释放排她锁。
Two-Phase Locking Protocol
p 两阶段封锁协议内容
n 增加阶段(Growing Phase)
p 事务能够取得锁，但不能释放锁
n 缩减阶段(Shrinking Phase)
事务能够释放锁，但不能取得锁
p 封锁点：事务取得其最终封锁时间
p 事务调度等价于和它们封锁点次序一致串行调度
死锁：
两个事务全部封锁了部分数据对象，并相互等候对方释放另部分数据对象方便对其封锁，结果两个事务全部不能结束，则发生死锁

v 死锁发生条件
①互斥条件：事务请求对资源独占控制
②占有等候条件：事务已持有一定资源，又去申请并等候其它资源
③非抢占条件：直到资源被持有它事务释放之前，不可能将该资源强制从持有它事务夺去
④循环等候条件：存在事务相互等候等候圈

v 预防死锁
n 预先占据所需全部资源，要么一次全部封锁要么全不封锁
缺点：难于预知需要封锁哪些数据而且数据使用率低
n 全部资源预先排序，事务按要求次序封锁数据
n 使用抢占和事务回滚
• wait-die：假如T1等候T2，仅当T1时间戳小于T2时，许可T1等候，不然回滚T1。
• wound-wait：假如T1等候T2，仅当T1时间戳大于T2时，许可T1等候，不然回滚T2
n 死锁检测和恢复
n 超时法
假如等候封锁时间超出限时，则撤消该事务
n 等候图法