数据库系统概念
2020-06-02 11:35:46 7 举报AI智能生成
数据库系统概念知识点
作者其他创作
大纲/内容
Chapter1. INTRO
文件系统缺点
数据冗余和不一致
访问数据困难
数据隔离，多个文件和格式
完整性问题
更新的原子性
多用户并发访问不行
安全问题
数据库访问的优点
数据共享
减少冗余
避免不一致
提供事务支持
完整性
安全性
三层架构
视图层
应用程序隐藏数据类型的细节，并能够处于安全目的隐藏一些信息
逻辑层
描述存储在数据库中的数据以及数据间的关系
物理层
描述记录是如何存储的
Mapping 映象
The Physical(internal)/Logical(conceptual) mapping
The View(external)/Logical(conceptual) mapping
Instances and Schemas
Schema 模式
数据库中数据结构的描述
Instance 实例
某个特定时刻数据库的实际内容
数据库语言
数据定义语言DDL
数据操作语言DML
数据库结构
存储管理
事务管理
DBMS 的功能
数据定义和存储管理
数据操作和访问
数据安全和完整性
事务管理，数据恢复和并发
数据字典
Chapter2 Relational Model
关系型数据结构
超键
任意两条记录没有相同的值
候选键
最小的超键
一般选一个作为主键
外键
另一个表的主键
完整性约束
实体完整性约束
参照完整性约束
基础级关系代数
Select 选择
Project 投影
Union 并
set difference 差
Cartesian product 笛卡尔积
Rename 更名
加强级关系代数
Set intersection 交
（Natural）join(自然)连接
Division 除法
Assignment 赋值
拓展级关系代数
Generalized Projection
Outer Join
Aggregate Functions
Null值
与空值的比较返回总是 unknown
对于unknown在选择的时候总是false
想要判别是否为空 用not exist
聚集函数总是简单的忽略空值
在消除重复和组合时，null被看做任何一种值，两个null可以当做一样
数据库修改
Chapter7 ER Model
Design Process
从用户角度将数据特征化
将数据模型转化成概念模式
子主题
Modeling
Constraints
E-R Diagram
Design Issues
Weak Entity Sets
Extended E-R Features
Design of the Bank Database
Reduction to Relation Schemas
Database Design
UML
Chapter8 Normal Form
Pitfalls in Relational Database Design
Bad design may lead to
Redundancy
Waste
Inconsistency
Incompleteness
Functional Dependencies
如果两条记录能根据某个属性的值确定另一个属性的值，则这个属性和那个属性函数依赖
平凡依赖
传递依赖
部分依赖
逻辑蕴含
函数依赖集闭包
Armstrong's Axioms
自反律reflexivity
增广律augmentation
传递律transitivity
附加规则
union
decomposition
pseudotransitivity
属性集闭包
作用
测试超键
测试函数依赖
计算F闭包
最小覆盖、正则覆盖
最小覆盖、正则覆盖
无关属性
F <=> (F-{α->β}）∪ {（α-A）->β}
判断是否是无关属性的方法
左边的
判断 (a-A)+（F）包含β吗
右边的
判断 a+(F-{a-β}）∪{a->(β-A)} 包含A吗
没有无关属性
函数依赖的左边都是不一样的
Normal Forms
Decomposition
Overall Database Design Process
Chapter10 Storage and File Structure
Storage Access
blocks are units of both storage allocation and data transfer
Buffer
内存中能够存储块的部分
Buffer manager
主存中负责分配buffer的子系统
Buffer-Replacement Policies
LRU
Pinned block钉住的块
forced output强制写出
Toss-immediate立即丢弃
只要那个块的最后一条记录被处理了就立即清空空间
MRU
File Organization
Fixed-Length Records
从n*(i-1)开始存第i个记录，n是一个记录的大小
删除策略
后面的记录前移
最后一条记录放到空位
将空闲空间连起来
保存第一个删掉的记录的地址
用这个地址来存第二个删除的记录的地址
Variable-Length Records
Slotted Page Structure
header
记录入口的数量
块中空闲空间的末端
每个记录的位置和大小
Organization of Records in Files
Heap堆
记录可以放在文件中的任意空位置
Sequential顺序
根据记录的search key的值按顺序存储
Hashing哈希
用哈希函数计算某些属性的值，这个值就指定了这条记录保存的文件在那个块
Clustering聚集
几个不同的关系可以存储在一个文件中
Data-Dictionary Storage
Data dictionary
保存关于数据的数据
关系的信息
关系名
每个关系的属性名称和类型
视图的定义和名称
完整性限制
用户和账户信息，包含密码
统计和描述数据
每个关系中的元组数
物理文件组织信息
关系是如何存储的
关系的物理位置
索引的信息
Chapter11 Indexing and Hashing
Basic Concepts
Search Key
用来查找记录的一个或集合属性
index file
search-key|pointer
两种索引类型
Ordered indices
Hash indices
Ordered Indices
Primary index
clustering index聚集索引
search key通常是主键
Index-sequential file
带有主索引的有序文件
Secondary index
和文件顺序无关
index entry按照search key的值排序存储
Dense Indices 稠密索引
每一个search key都包含了
Sparse Indices稀疏索引
只有部分的search key
Multilevel Index 多级索引
outer index
主索引的稀疏索引
inner index
主索引文件
Index Update : Deletion
Single-level
Dense indices
删除指针
更新指针
Sparse indices
不做事
用下一个search-key代替
更新指针
Multilevel
Index Update: Insertion
Single-level
Dense
insert index/add pointer/update pointer
Sparse
no change/insert index/update pointer
Multilevel
主索引和辅助索引
辅助索引必须dense
使用主索引进行顺序扫描很有效，但是使用辅助索引代价高
B+Tree Index
Hash Indices
Static Hashing
bucket
包含一个或多个记录的存储单元（通常是一个块）
hash function
uniform
random
Handling of Bucket Overflows
Hash indices
a hash index organizes the search keys, with their associated record pointers, into a hash file structure
通常是辅助索引
Deficiencies
static hashing
哈希函数将search key映射到一个固定的bucket地址集合
数据库随时间增长，如果bucket初始数量太少，性能将因为overflow而下降
如果文件大小在未来某时刻提前满了，而buckets的数量分配了，就会造成大量空间浪费
如果数据库缩小了，空间也会被浪费
一个选择就是周期性的用新的哈希函数重组文件
Index Definition in SQL
create index <index-name> or <relation-name> <attribute-list>
Chapter12 Query Processing
Basic Steps in Query Processing
Parsing and translation
optimization
evaluation
Measures of Query Cost
磁盘访问是主要代价
访问次数
读取块数量
写入块的数量
简化
传输一个块的数量
查找的数量
b*t_T+S*t_S
Selection Operation
File scan
A1算法（线性搜索）
b_r*t_T+t_S
b_r为包含关系r中记录的块的数量
如果找到就停止
b_r/2*t_T+t_S
A2算法（二分搜索）
文件有序，块连续
ceiling(log2(b_r))*(t_T+t_S)
Index scan
A3算法（等值查询，在候选键上的主索引），获取单条记录
(h_i+1)*(t_T+t_S)
A4算法（等值查询，非主键的主索引），获取多条记录
h_i*(t_T+t_S)+t_S+t_T*b
A5算法（等值查询，辅助索引上的search key）
单条记录，search key是候选键
（h_i+1）*(t_T+t_S)
多条记录，不是候选键
（h_i+n）*(t_T+t_S)
A6算法（比较查询，主索引）
A>=V
利用index找到第一个元组>=v，然后顺序扫描
A<=V
从开始顺序扫描，知道找到第一个>v
A7算法（比较查询，辅助索引）
A>=V
利用index找到第一个元组>=v，然后顺序扫描
A<=V
值扫描index的叶子页来找记录的指针，直到找到第一个>v的
Conjunction
A8（使用单索引的交选择）
子主题
A9（使用多键索引的交选择）
A10（利用差值identifiers进行交选择）
Disjunction
A11（利用identifiers的联合来进行并选择）
Negation
Chapter13 Query Optimization
Why Optimization
Cost-based optimization
Heuristic optimization
尽早执行选择
尽早执行投影
在其他相似操作之前，执行最限制的选择和交曹组
等价规则
选择串接律
选择交换律
投影串接律
子主题
步骤
分解选择操作
下移选择操作
下移投影操作
将选择+笛卡尔乘积变成连接操作
Chapter14 Transactions
Transaction
a collection of operations that form a single logical unit of work
a unit of program execution that accesses and possibly updates various data items
ACID
Atomicity
Consistency
Isolation
Durability
State
Active
Partially committed
Failed
Aborted
restart the transaction
kill
Committed
Implementation of Atomicity and Durability
recovery management实现atomicity and durability
shadow-database scheme
Concurrent Executions
increased processor and disk utilization
reduced average response time
Schedules
serial schedule串行调度
concurrent schedule并发调度
Serializability
conflict serializability
S is conflict serializable if it is conflict equivalent to a serial schedule
一个调度是冲突可串行化的当且仅当过程图没有环路
view serializability
Recoverability
Recoverable schedule可恢复调度
Tj在Ti写入之后读，Ti比Tj提交的早
Cascading rollback级联回滚
单个事务的失败造成多个事务的回滚
Cascadeless schedules无级联调度
不会发生级联回滚
Tj在Ti写入之后读取数据，Ti在Tj读取之前提交
无级联调度都是可恢复地哦啊哦度
Implementation of Isolation
Transaction Definition in SQL
Testing for Serializability
Chapter15 Concurrency Control
Concurrency Control Protocol
Lock-Based Protocols
Locks
exclusive mode
shared mode
缺陷
限制了可能的调度
The two-phase locking protocol
phase 1: growing phase
phase 2: shrinking phase
assures confilct serializability
不能保证无死锁
可能有级联回滚
strict two-phase locking
直到提交或中断才放开X锁
rigorous two-phase locking
所有锁必须提交或中断才放弃
Timestamp-Based Protocols
老的事务的时间戳比新的事务时间戳小
对于数据Q
W-timestamp（Q）
R-timestamp（Q)
能保证冲突可串行化
能保证不会死锁
但是不能保证无级联、甚至可能不能恢复
Multiple Granularity
fine granularity(lower in tree): high concurrency, high locking overhead
coarse granularity(higher in tree) :low locking overhead, low concurrency
Intention Lock Modes
intention-shared IS 共享意向锁
intention-exclusive IX 互斥意向锁
shared and intention-exclusive SIX 共享互斥意向锁
Deadlock Handling
Deadlock prevention
要求事务在开始执行前把它的数据项都上锁
对部分数据项排序，要求按照顺序上锁
基于时间耗尽的策略
超时等待则回滚
wait-die scheme
时间戳小则等待，大则回滚重启
老的会等小的释放，小的不会等老的，而是回滚
非抢占
wound-wait scheme
时间戳大则等待，小则回滚重启上锁的那个
老的会伤害（回滚）小的，而小的会等老的
相比较少回滚
抢占式
Deadlock Detection
wait-for graph
有环路就有死锁可能
Deadlock Recovery
选择损失最少的事务回滚
Chapter16 Recovery System
Failure Classification
Transaction failure
Logical errors
System errors
System crash
Fail-stop assumption
Disk failure
Recovery Algorithms
采取措施保证足够信息存在以恢复
在错误发生后采取措施恢复数据内容
Storage Structure
Volatile storage（易失）
Nonvolatile storage
Stable storage
Data Access
Physical blocks
Buffer blocks
Recovery and Atomicity
Log-Based Recovery
Deferred Database Modification
前提是start commit都在log文件中
redo
Immediate Database Modification
commit前失败则undo
commit后partial commited状态则redo
Checkpoints
checkpoint之前的start到之后的commit全部redo，没commit的全部undo
Recovery with Concurrent Transactions
所有事务共享一个磁盘缓冲和一个日志
一个缓冲块可以被一个或多个事务更新
假设并发控制使用strict two-phase locking
Checkpoint
将undo-list和redo-list设为空
从后往前扫描log，找到checkpoint L就停止
如果<Ti commit>，就将Ti放入redo-list
如果<Ti start>而且Ti不在redo-list，则加入undo-list
对于L中的每个Ti，如果Ti不在redo-list，就加入undo-list
恢复过程
从最近的记录开始从后向前扫描，遇到undo-list中的每个Ti的start语句时停止
在这个过程中，对undo-list中的事务执行undo
定位到最近的checkpoint L
从checkpoint开始向后扫描到log末尾
在这个过程中，对redo-list中的事务进行redo
Log Record Buffering
0 条评论
下一页
