数据库原理-数据库练习题

计算机基础

数据库原理

发布日期: 2022-12-09

第一套题

Person(driver_id, name, address);

Car(license_plate, model, year);

Accident(report_no, year, location);

Owns(driver_id, license_plate);

Participated(report_no, license_plate, driver_id, damage_amount);

(1) Find the license plates of cars owned by the driver named “Smith” (in relational algebra and SQL 6 points)

题目大意:找到司机名字是Smith的所有license plates

思路,先通过person找到smith对应的driver_id,然后过滤owns中所有driver_id即可

注意题目这里plates带了个s,意思可能是有重名的。

首先写出关系代数式如下

$$\Pi_{license_{}plate}(\sigma_{name=”smith”}(Person)\Join Owns)$$

SQL如下,这里用的是子查询,感觉分步骤好些

#先查出simth对应的dirver_id
select driver_id
from Person
where name="Smith"

然后用in作为条件连起来

select license_plate
from Owns
where driver_id in (select driver_id
					from Person
					where name="Smith");

(2) Find names and driver id(s) for these persons who never had any accidents in 2021. (in relational algebra and SQL 6 points )

题目大意:找到那些在2021年从来没有发生过事故的司机的id和名字

首先确认要找哪几个表:Accident、Person、Participated

然后如何来组织查询?

第一步,首先从year=2021入手,从Accident找出那些2021年发生的所有事故(report_no)

第二步,从Participated过滤出那些发生过事故的车主id,report_no in...

第三步,用投影后的Person表减去第二步查询出来的那个集合即可

具体实现,首先先实现关系代数式:

第一步的关系代数式,$$\sigma_{year=2021}(Accident)$$

第二步做过滤,用自然连接,使得那些dirver_id相同的记录连在一起,注意由于要做投影多一个name的字段,因此还要和Person做一个自然连接,使得有name这个字段,$$\Pi_{dirver_{}id}(\sigma_{year=2021}(Accident)\Join Participated)$$

第三步,用总的表减去那个集合,$$\Pi_{dirver_{}id,name}(Person)-\Pi_{dirver_{}id,name}(\sigma_{year=2021}(Accident)\Join Participated \Join Person)$$

然后我们实现SQL,SQL的实现如下

#找出发生事故的编号
select report_no
from Accident
where year = 2021
#过滤出发生过事故的车主
select driver_id
from Participated
where driver_id in (第一个子查询...)
#过滤出没有发生过事故的车主
select driver_id,name
from Person
where driver_id not in (第二个子查询)

完整SQL如下:

select driver_id,name
from Person
where driver_id not in (select driver_id
						from Participated
						where driver_id in (select report_no
											from Accident
											where year = 2021));

(3) Find the location with the most of accidents in 2021**.(in SQL 3 points)**

题目大意:找出那些发生最多事故的地点(2021)

select location
from Accident as S
where year = 2021 
group by location
having count(report_no) >= all (select count(report_no)
                                from Accident
                                group by location);

(4) Find the driver id and person names that had at least two accidents in 2021.(in SQL 3 points)

题目大意:找到那些至少发生过两起事故的司机(2021)

首先分析要哪些表,因为需要name和driver_id,所以肯定需要Person,然后要统计发生的事故,又要和事故有关,又要和司机有关,那么就要Participated

然后分析如何执行查询

题目中一个很关键的信息就是至少发生过两起事故,这个可以联想到一个关键字unique,unique的特性是:对于null和1都是输出true,而对于2以上的都是输出false,也可以使用count()计数,这里的话我采用第一种。

首先就是统计每一个driver_id所对应的事故次数,这里的话可以做一个自然连接,让Accident和Participated用driver_id连起来,然后unique一下,就可以得到一个关于这个司机是否有两起以上的事故的一个where条件了

然后执行查询即可

select driver_id,name
from Person as S
where unique(select report_no
             from Accident natural join Participated as T
             where Accident.year = 2021 and S.driver_id = T.driver_id);

(5) Increase the damage amount by 10% for the car with license plate “SCAU888” in the accident(s) located at “Wushan” in 2021.(in SQL 3 points)

题目大意:提高10%的费用,对于那些牌照是SCAU888,然后在2021年在Wushan发生事故的事故

可以确定题目肯定是要编写一个update语句,然后要利用上面的条件来做限定

update Participated
set damage_amount = damage_amount*1.10
where license_plate="SCAU888" and report_no in
(select report_no
 from Accident
 where year = 2021 and location="Wushan");

dependencies F ={AB→CD, D→C, DEF→AB, DE→B, AC→DC } holds on R.

(1) List all candidate keys of relation R. (3 points)

题目大意,请你列出这个关系的所有的候选码

首先从函数依赖出发,找左部是否能够构成候选码

(AB)+={AB}={ABCD},如果要形成候选码,那么必须闭包中包含R中的所有的元素,还缺少E和F,而E和F之间没有的依赖函数依赖可以推导,因此只需要将E和F加上去即可,所以第一个候选码是ABEF

(D)+={D}={CD},由DEF->AB,因此(DEF)+={DEF}={ABDEF},在D的基础上加上EF即可形成候选码

(DEF)+已经计算过了

(AC)+={AC}={ACD},还缺少BEF,由DE->B,因此只需要加上EF即可

综上所述,候选码为ABEF、DEF、ACEF

(2) Does the functional dependency AC→B holds on R, Explain why. (2 points)

这道题问你AC->B这个函数依赖在关系R上是否成立,验证的办法就是求(AC)+

(AC)+={AC}={ACD},没有包含B,因此这个函数依赖是不成立的

(3) Give a decomposition of R with only one time of BCNF decomposition. (3 points)

这道题要求我们只需要执行一次BCNF的分解即可

首先要找到一个非平凡的函数依赖,这个函数依赖的左部不是候选码,于是我们选中AB->CD

于是,我们将AB看作a,将CD看作b

r1={a∪b}={ABCD},r2={r-b}={ABEF}

分解完成

(4) Give a 3NF decomposition of R, and list the main procedure for calculating your canonical cover. (3 points)

这道题要求我们写出分解为第三范式的结果

分解为第三范式,必须先求出正则覆盖,F ={AB→CD, D→C, DEF→AB, DE→B, AC→DC }

第一步,先根据分解律得到一个新的函数依赖集

F={AB->C,AB->D,D->C,DEF->A,DEF->B,DE->B,AC->D,AC->C}

然后挨个验证函数依赖是否是必要的,

对于AB->C,计算(AB)+={AB}={ABD}={ABCD},包含有C,所以这个函数依赖是多余的

对于AB->D,计算(AB)+={AB},不包含D,因此保留此函数依赖

对于D->C,计算(D)+={D},不包含C,保留函数依赖

此时的函数依赖集为F={AB->D,D->C,DEF->A,DEF->B,DE->B,AC->D,AC->C}

对于DEF->A,参考函数F={AB->D,D->C,DEF->B,DE->B,AC->D,AC->C},计算(DEF)+={DEF}={BDEF}={BDEF}不包含A,因此保留此函数依赖

对于DEF->B,参考函数F={AB->D,D->C,DEF->A,DE->B,AC->D,AC->C},计算(DEF)+={DEF}={ADEF}={ABDEF}={ABCDEF},包含了B,因此不保留此函数依赖

此时的函数依赖集为F={AB->D,D->C,DEF->A,DE->B,AC->D,AC->C}

对于DE->B,参考函数依赖F={AB->D,D->C,DEF->A,AC->D,AC->C},计算(DE)+={DE},不包含B,因此保留

对于AC->D,参考函数依赖F={AB->D,D->C,DEF->A,DE->B,AC->C},计算(AC)+={AC},不包含D,因此保留

对于AC->C,参考函数依赖F={AB->D,D->C,DEF->A,DE->B,AC->D},计算(AC)+={AC}={ACD},包含了C,因此不保留

此时函数依赖集为F={AB->D,D->C,DEF->A,DE->B,AC->D}

然后计算左部的冗余元素

对于AB->D

如果我们删除A,那么计算(B)+={B},没有包含D,因此A不是冗余的
如果我们删除B,那么计算(A)+={A},没有包含D,因此B不是冗余的

对于DEF->A

如果删除D,那么计算(EF)+={EF},因此D不是冗余的
如果删除E,那么计算(DF)+={DCF},因此E不是冗余的
如果删除F,那么计算(DE)+={DCE},因此F不是冗余的

对于DE->B

如果删除D,那么计算(E)+={E},不包含B,因此不是冗余的
如果删除E,那么计算(D)+={D}={DC},不包含B,因此不是冗余的

如果AC->D

如果删除A,那么计算(C)+={C},因此不是冗余的
如果删除C,那么计算(A)+={A},因此不是冗余的

综上所述,一个正则覆盖Fc={AB->D,D->C,DEF->A,DE->B,AC->D}

基于此,分解为3NF:

第一步,直接合并函数依赖的左部和右部

R={ABD,CD,ADEF,BDE,ACD}

第二步,去除被包含的关系模式

R={ABD,ADEF,BDE,ACD}

第三步,检查是否包含候选码ABEF、DEF、ACEF

观察到含有DEF

说明一下:并不需要放所有的候选码,如果有多个放一个候选码就可以了

然后这道题就解完了

事务操作题

T0	T1	T2	T3
Read(A);	Read(B);	Read(C)	Read(D)
Read(B);	Read(C);	C:=C-100;	D:=D+100;
A:=A-50;	B:=B-500;	Write(C);	Write(D)
B:=B+50;	C:=C+500;
Write(A);	Write(B);
Write(B).	Write(C)

Let A=1000, B=2000, C=700, D=300 as the initial values.

(1) Explain the distinction between the terms serial schedule and serializable schedule. (2 points)

请你解释一下可串行化调度和串行调度的区别是什么?

串行调度是由来自各个事务的指令序列组成的,其中属于同一个事务的指令必须挨在一起,不能分割

可串行化调度:在并发执行中,通过保证所执行的任何调度的效果等价与一个串行调度,这种调度称为可串行化

区别:可串行化调度

(2) Give a concurrent execution of T0, T1, T2, and T3 that produces a serializable schedule such that the order in which the transaction commit is different from the serializable order. Then show its serializability order. (4 points)

题目大意,就是说,你要给出一个调度的指令序列,要满足下面两点

事务的开始执行顺序和提交顺序不同,比如说开始执行的顺序是T1 T3 T2 T0,那么提交的顺序就要是T0 T3 T2 T1,只要保证这两个序列不一样就可以

这个指令序列要满足可串行化

思路:我们观察事务的指令序列,特点是这样的T0和T1有指令可能导致冲突,T1和T0、T2可能导致冲突,T2和T1可能冲突,T3不于其他事务冲突,因此,我们的思路就是让T3在前三位开始,最后一位提交,这样可以满足第一个条件,然后编排T0 T1 T2的顺序使之满足可串行化即可

编排如下

T0	T1	T2	T3(第二个开始,最后提交)
Read(A)
Read(B)
A:= A-50
B:= B+50
			Read(D)
		Read(C)
		C:= C-100
		Write(C)
Write(A)
Write(B)
	Read(B)
	Read(C)
	B:= B-500
	C:= C+500
	Write(B)
	Write(C)
commit
		commit
	commit
			D:= D+100
			Write(D)
			Commit

注意,这里很容易忽略的一点就是关于可恢复调度的问题,如果要求这个调度同时是可恢复的

对于事务Ti和Tj而言,如果Tj读取了Ti所写的数据项,那么Ti应该要先提交而Tj后提交

对应到我们的题目就是T1读取了T0的数据,那么应该T0先提交

(3) Explain the checkpoint technology. (2 points)

请你简述一下什么是检查点

将当前位于主存的所有日志都输出到稳定存储器

将所有修改的缓冲块输出到磁盘

将一个日志记录checkPoint<L>输出到稳定存储器,其中L是执行检查点时正活跃的事务列表

<checkpoint {T1, T2}>
<T3, start>
<T2, commit>
<T3, D, 300, 400>
<T1, B, 2050>
<T1, abort>

(4) Describe the change of Undo List In the Redo Pass. (3 points)

请你描述一下撤销列表是如何变化的,注意,这个从前往后的过程会redo

首先我们找到checkpint<{T1,T2}>

因此初始化undo-list={T1,T2}

然后从前向后扫描,发现T3开始,undo-list={T1,T2,T3}

T2 commit,删除T2,undo-list={T1,T3}

T1 abort 删除T1,undo-list={T3},开始撤销3

(5) Show the log records which should be added during recovery. (2 points)

在T3重做的时候,会留下那个read-only的日志,格式为<T,数据项,值>
<T3, start>
<T2, commit>
<T3, D, 300, 400>#300是旧值,400是新值
<T3,D,300>
<T3,abort>

(6) List the final value of B, C and D after completing recovery. (2 points)

B=2050, C=600, D=300

列出BCD在恢复之后的值

完整的事务操作

Beginning of log
<To, start>
<To, A, 1000, 950>
<To, B, 2000, 2050>
<T1, start>
<T0, commit>
<T1, B, 2050, 1550>
<T2, start>
<T2, C, 700, 600>
<checkpoint {T1, T2}>#在这个点A:950 B:1550 C:600
<T3, start>
<T2, commit>
<T3, D, 300, 400># D:400
<T1, B, 2050>#B:2050
<T1, abort>
<T3,D,300>#D:300
<T3,abort>