数据库考点总结.doc

数据库考点总结
By penn pan
第一部分 考试题目类型
填空题 选择题 设计题
其中老师特别说明 鼓励大家用英文答题， 有c些题目 比如说填空题 即便是单词拼错了也没有关系，只要能让老师看懂意思，用中文答题可能评分可能打折，各位看中文版的同学注意了。
第二部分 重点考点总结
重点一
P25 F1.6 Database Architecture 仔细的看此图，可以将整本书的内容串起来

重点二 Data Model
E-R Model （chapter 6）

Relationship Data Model （chapter 7）

难点：（1） E-R 图在转化为关系数据模型时候时R部分的处理，（一对一情况 ； 一对多情况 ； 多对多情况）
（2） E-R 图中表示数量属性的方法 一是利用（箭头上标数字表示 特别留意与UML表示关系的上标中的区别） 二是利用箭头表示（表示一对多） 在实际数据库设计中 老师鼓励第二种方法。下面是例子
In the one-to-many relationship a loan is associated with at most one customer via borrower, a customer is associated with several (including 0) loans via borrower (如下图所示)

考点（1）E-R 同关系数据模型之间的转化 （尤其是E-R图转化为关系数据模型）
（2） 第三大题中的设计题部分
重点三 查询语言
（1） 关系代数表达式定义及其使用(chapter 2)
（2） 域关系表达式定义及其使用(chapter5)
（3） 元组关系表达式定义及其使用（其中老师强调过元组关系表达式的三个约束条件 分别为 (a)除输出变量外其他变量都要声明 (b)用同名变量连接相同元素（c）？）(chapter5)
（4） SQL定义及其使用(chapter3)
考点
（1） 给定条件写出相应的表达式（留意是否可以根据等价原则中的三条启发式规则优化）
Find the names of all customers who have a loan at the Perryridge branch.

Query2就做了优化
（2） 关系代数表达式与SQL 之间的相互转化

Chapter 3 课后作业 3.11(d)

至于后面为什么会有一个distinct 个人解释 因为关系代数是基于集合论，所以不允许重复 但奇怪的是老师的PPT上分明是
SQL duplicate semantics:
select A1,, A2, ..., An
from r1, r2, ..., rm
where P
is equivalent to the multiset version of the expression:

直接等价 坐等高人解释
（3） SQL 极函数以及使用 特别是avg ,count ,sum
select avg (balance)
from account
where branch_name = ‘Perryridge’
（4） SQL 分组查询 用一个例子说明
Find the names of all branches where the average account balance is more than $1,200.
select branch_name, avg (balance)
from account
group by branch_name
having avg (balance) > 1200
重点四 权限管理
(chapter 5 Advanced SQL chapter 8 application Design and development authorization in SQL)
（1） 权限的内容
Read update delete all privilege
（2） 权限的发放与回收
The grant statement is used to confer authorization
grant on to (with grant privilege )
The revoke statement is used to revoke authorization.
revoke on <relation name or view name> from
重点五 也是最重要的部分 BC 范式 和第三范式
（chapter 7 Relational Database Design）
重点：
（1） BC范式的定义

（2） 第三范式的定义

留意

其中，我个人认为难理解的不是这些范式的定义，而是大家并没有真正理解超键(super key) 候选键(candidate key) 主键(primary key)的定义 导致现在理解起来困难
(a)K is a superkey of R if values for K are sufficient to identify a unique tuple of each possible relation r(R)
(b)K is a candidate key if K is minimal super key
(c)Primary Key
所以根据定义可以得出 (c)属于(b)属于(a)
(3) 属性闭包的计算以及作用（Attribute Set Closure）
老师用一个例子阐明
R = (A, B, C, G, H, I)
F = {A → B
A → C
CG→ H
CG → I
B → H}
(AG)+→ (A, B, C, G, H, I)
所以AG为关系R的一个超键(super key) 同时也是 候选键(candidate key) 因为它已是最小集合。
属性闭包作用

(4) 分解的条件及判定（老师的PPT上在BC范式的转化方法上，个人认为应该前提，因为它能够帮我们很好的理解BC范式转化的公式）
分解必须满足
(a) 无损连接分解 （b）依赖保存
A decomposition of R into R1 and R2 is lossless join if and only if at least one of the following dependencies is in F+:
R1 ÇR2→ R1
R1 ÇR2 →R2
例子
R = (A, B, C) F = {A → B, B →C)
分解结果 R1 = (A, B), R2 = (A, C)
Lossless-join decomposition://满足无损分解
R1 Ç R2 = {A} and A →AB
Not dependency preserving //不满足依赖保存
(cannot checkB →C without computing R1 R2)
(5)BC范式以及第三范式的转化方法
BC范式

第三范式

简单的例子加强我们的理解
将关系分解为BC范式

第三范式分解的例子
R(A,B,C,D,E)
F={AB→C, C→B,A→D}

考点： BC范式的分解
重点六：优化
（1） chapter 13 Query processing
牢记几个个公式
Selection cost
A1(liner selection)
Cost estimate = br block transfers + 1 seek
br denotes number of blocks containing records from relation r
If selection is on a key attribute, can stop on finding record
cost = (br /2) block transfers + 1 seek
A2(binary research)
Cost estimate (number of disk blocks to be scanned):
cost of locating the first tuple by a binary search on the blocks
élog2(br)ù * (tT + tS)
A3 (primary index on candidate key, equality)Retrieve a single record that satisfies the corresponding equality condition
Cost = (hi + 1) * (tT + tS)
A4 (primary index on nonkey, equality) Retrieve multiple records.
Records will be on consecutive blocks
Let b = number of blocks containing matching records
Cost = hi * (tT + tS) + tS + tT * b
A5 (equality on search-key of secondary index).
Retrieve a single record if the search-key is a candidate key
Cost = (hi + 1) * (tT + tS)
Cost of Joint operation
(a)Nested Joint
In the worst case, (nr * bs + br)*block transfers+(nr + br)*seeks //留意那个位于循环外层
In the best case, (br + bs）* block transfers + 2 *seeks
(b)Block Nested-Loop Join
In the worst case, (br * bs + br)*block transfers+(nr + br)*seeks //留意那个位于循环外层
In the best case, (br + bs）* block transfers + 2 *seeks
(c)Indexed Nested-Loop Join
Cost of the join: br (tT + tS) + nr * c
Where c is the cost of traversing index and fetching all matching s tuples for one tuple or r
c can be estimated as cost of a single selection on s using the join condition.
(d)Merge-joint
the cost of merge join is:
( br + bs)* block transfers + （br / bb+ bs / bb）*seeks+ the cost of sorting if relations are unsorted.
bb is the number of buffer for the relations.
（2） Chapter 14 Query optimization
根据转化的等价规则，我们得出的三条启发式规则
(a)Perform selection early (reduces the number of tuples)
(b)Perform projection early (reduces the number of attributes)
(c)Perform most restrictive selection and join operations before other similar operations.
考点 （1） 根据名称和公式计算开销
（2） 关系代数表达式or SQL表达式的优化
重点七：琐碎的重要的考点
（1） 数据库事务的ACID原则 及其状态转化图 （chapter 15 transaction）
(a) (ACID) atomicity consistency isolation durability
(b)状态转化图

（2） 基于日志的恢复（log-based recovery）(chapter 17 recovery System)
(a) Deferred database modification

If log on stable storage at time of crash is as in case:
(a) No redo actions need to be taken
(b) redo(T0) must be performed since is present
(c) redo(T0) must be performed followed by redo(T1) since
and are present
(b) Immediate database modification
(c) checkpoint

T1 can be ignored (updates already output to disk due to checkpoint)
T2 and T3 redone.
T4 undone
考点：log-based recovery的判定
其他：不重要 优先级比较低的部分
（1） Chapter 11 storage and file structure Chapter 12 Hashing and indexing
（2） Chapter 10 XML XML 应用重要 但是考试的时候不会作为重点 至多考一下XML查询两种方法 （XPATH，XQUERY）
前面部分 包括XML 介绍 DTD XML schema 了解一下即可
需要掌握的内容
(a) subelement 与 attribute 区别
Same information can be represented in two ways
…. //attribute

A-101 …//subelement

(b) DTD 中提到的 IDREF
An element can have at most one attribute of type ID
The ID attribute value of each element in an XML document must be distinct
Thus the ID attribute value is an object identifier
An attribute of type IDREF must contain the ID value of an element in the same document
示例

//owners 即为IDREF
Downtown
500

Joe ustomer_name>
Monroe
Madison

Mary
Erin street>
Newark

在DTD中如此规定

所以XPATH, XQUERY也不会太难
XPATH
(a) 利用路径 /bank-2/customer/customer_name/text( ) 后面标记只取subelment 标签中的数值
(b) 利用中括号表示判断条件/bank-2/account[balance > 400]/@account_number 后面@标记表示为attribute
XQUERY 用一个例子表示

for $a in /bank/account, //SQL FROM
$c in /bank/customer,
$d in /bank/depositor
where $a/account_number = $d/account_number //SQL WHERE
and $c/customer_name = $d/customer_name
return { $c $a } //SQL SELECT
等价式
for $a in /bank/account,
$c in /bank/customer,
$d in /bank/depositor[
account_number = $a/account_number and
customer_name = $c/customer_name]
return { $c $a }

说明：（1）本考点总结是根据李东老师的PPT，同学们课后的提问加上自己根据笔记的一些理解整理而成，尽量减少了个人发挥，实属居家旅行必备之良品，备考防身之良药，当然错误和疏漏之处在所难免，贻笑大方，还请见谅。
开个玩笑 祝考试期间有个好心情(本来是想把上面文字改成下面这样)
“人在江湖飘，谁能不挨刀？白驼山壮骨粉，内用外服均有奇效。挨了刀涂一包，还想再挨第二刀，闪了腰吃一包，活到二百不显老。白驼山壮骨粉，青春的粉，友谊的粉，华山论剑指定营养品，本镇各大药铺医馆均有销售，购买时，请认准黑蛤蟆防伪标志，呱，呱……”
最后 祝同学们有个好成绩，希望自己任内消灭三班不必要挂科的目标达成。