数据库最小依赖集题解

朴灿烈づ我的快乐病毒、 2023-10-06 21:27 10阅读 0赞

## 数据库例题 ##

### 一、最小依赖、候选键 ###

> 1.  考虑关系模式R(A, B, C, D, E, F)，其函数依赖集为F=\{AC→EF, B→CE, C→B, AB→D, E→F\} (1) 求R的最小函数依赖集。 (2)列举R的全部候选键。 (3)将R分解为一组关系模式，要求每个关系模式均满足BCNF。

（1）求解第一问最小函数集依赖  
思路：根据传递率，求出并删掉重复的  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16]

> F=\{AC→EF, B→CE, C→B, AB→D, E→F\}  
> ∴F=\{AC→E, AC→F, B→C,B→E,C→B,AB→D,E→F\}  
> ∵AC→E, E→F, ∴AC→F  
> ∴F=\{AC→E, B→C,B→E,C→B,AB→D,E→F\}  
> ∵C→B，B→E∴C→E  
> ∴F=\{ B→C,B→E,C→B,AB→D,E→F\}  
> 经检查Fmin=\{ B→C,B→E,C→B,AB→D,E→F\}为最小函数依赖集

（2）求解全部候选键  
思路：根据

> 1、L类：全部出现在函数依赖的左半部  
> 2、R：全部出现在函数依赖的右半部  
> 3、LR：出现在函数依赖的左右两边  
> 4、N：不出现在函数依赖中  
> 可能成为候选键的有L类,LR类和N类  
> 对于L类,求出它的闭包,若包含所有属性,则说明其为候选键,且为唯一候选键.  
> 对于LR类,求出其闭包,若包含所有属性,则为候选键,若不包含,在找出其中一个属性结合.  
> 对于N类,直接加至候选键即可.

### 二、利用可扩展hash方法对以下记录进行hash存储：3, 5, 7, 13, 20, 25 ###

> 设hash函数h(x)= x mod 7，其中散列函数h(k)是一个b(足够大)位二进制序列，序列的前d位用作索引，来区分每个元素属于哪个桶。  
> 现要求每个桶至多包含2个元素，以上元素按从左往右的顺序依次添加。开始时只使用序列的前1位作索引（即d=1），当桶满时进行分裂，d相应增大。请画出添加完以上所有元素后，最终的索引结构。

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16 1]

### 三、冲突串行化调度 ###

> 1.考虑如下的三个事务的调度。这是否是一个冲突串行化调度？请解释一下你的判据。如果是，将它转换成串行调度。

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
解：根据下表对应看是否发生冲突  
![请添加图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16 3]

**用优先图判断**![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
转换后优先图  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16 5]

### 四、优化查询 ###

**考虑下面的关系模式**

> Student=\{ SID, Name, Degree, College, Address, Phone\}  
> Course=\{CourseNo, College, Semester\} Enrol=\{SID, CourseNo, Semester,  
> Unit, Status\}, 外键约束有Enrol.\{CourseNo,Semester\} 关联Course.\{CourseNo,  
> Semester\} 及Enrol.SID 关联Student.SID.

> 考虑下面的SQL查询  
> πSID,Address,Phone(σCourseNo=‘COMP 2400’ ((Course ⋈ Enrol) ⋈ Enrol.SID=Student.SID Student))  
> 画出它的查询计划树，然后对初始查询计划树进行查询优化，并画出经过查询优化之后的查询计划树。

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16 6]  
**结果：**  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16 7]

### 五、E-R图 ###

> 1．为一个银行设计一个数据库，包括顾客和顾客的账户的相关信息。  
> (1) 顾客的信息包括姓名、地址、电话和社会安全号码。  
> (2) 顾客可以有多个地址（地址是由所在州、城市、街道组成的三元组），每个地址可以有多个电话。  
> (3) 账户的信息包括号码、类型（支票账户或者储蓄账户）和收支情况，也应记录它的所有者。  
> (4) 一个账户只能有一个所有者。  
> 请根据以上信息：画出对应的 E-R 图；指出每个关系中的主键、外键和完整性约束；把 E-R 图转化为对应的关系模式。

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16 8]

### 六、B+树生成器 ###

[B+树生成器][B]

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/ee090e20a4994fa9bab5bf220a558746.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Y-r5oiR6ICB5Lyv,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: https://img-blog.csdnimg.cn/72b39b342fce431b9420c3d1365f4af5.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Y-r5oiR6ICB5Lyv,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/cb5b91faeb1e4702aad09987d12ae226.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Y-r5oiR6ICB5Lyv,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/f2fcd626721d4629ae96161aa3bd8bf2.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Y-r5oiR6ICB5Lyv,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/7430d7f61e3c43bab89d523d405879e3.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Y-r5oiR6ICB5Lyv,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16 4]: https://img-blog.csdnimg.cn/669be066098145a19695ab81ea371b6b.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Y-r5oiR6ICB5Lyv,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16 5]: https://img-blog.csdnimg.cn/dcba638545b9411d964a553797a658ed.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Y-r5oiR6ICB5Lyv,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16 6]: https://img-blog.csdnimg.cn/ecc493f7bd3a4c16925d6d2c0b2c6b46.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Y-r5oiR6ICB5Lyv,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16 7]: https://img-blog.csdnimg.cn/2b9b6e97e5bb468fa27482188824a41e.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Y-r5oiR6ICB5Lyv,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16 8]: https://img-blog.csdnimg.cn/55680362449e4692bb65b44e88bd56f6.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Y-r5oiR6ICB5Lyv,size_20,color_FFFFFF,t_70,g_se,x_16
[B]: https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html