0%

关系数据库设计

一个难题

其实本节的内容,主要围绕着一个问题展开:

  • 是把导师和部门放在一个表inst_dept中,还是放在分开放在两个表instructor,department中呢?

让我们分别看看两种方案吧


方案一:放在一个表中

ID name salary dept_name building budget
22222 Einstein 95000 Physics Waston 70000
12121 Wu 90000 Finance Painter 120000
45565 Katz 75000 Comp.Sci Taylor 10000
10101 Srinivasan 65000 Comp.Sci Taylor 10000
83821 Brandt 92000 Comp.Sci Taylor 10000
inst_dept

一眼看去,表非常的直观,能清楚地了解每个老师的所有信息。而且,在查询时不需要使用join语句,对程序员也十分友好。这种方案看似非常不错,但却有两个非常严重的缺点。

1.先有老师再有系

如果大连理工大学创建了一个干饭系,但是由于这个系没有前景,所以迟迟没有老师愿意加入。我们没办法把干饭系加入到表中,因为每个记录在表中的系,都是有老师的。没有老师,就不能录入表格,在数据库中,要避免使用空值,所以把老师那里录入空值也不太好。

2.有很多废信息

假如大连理工大学有10000名教职工,却只有30个系,现在我们正在看有10000名教职工信息的表格

ID name salary dept_name building budget
1 小陈 95000 软国 信息楼 62000
2 小王 90000 软国 信息楼 62000
3 小夏 75000 软国 信息楼 62000
4 小薛 65000 软国 信息楼 62000
5 小张 92000 软国 信息楼 62000
…… …… …… 软国 信息楼 62000
inst_dept

当我们看完软国的所有老师后,我们一定会想,为什么不单独把软国的办公地点预算列出来呢,在每个老师后面都重复一遍是不是没啥必要😅

实际上,把所有老师后面都加上每个系的办公地点和预算,是对内存空间的浪费。特别是有10000名教职工的时候,每一排的浪费,在✖️10000之后,都会被无限放大。


方案二:放在两个表中

ID name dept_name salary
22222 Einstein Physics 95000
12121 Wu Finance 90000
45565 Katz Comp.Sci 75000
10101 Srinivasan Comp.Sci 65000
83821 Brandt Comp.Sci 92000
instructor
dept_name building budget
Physics Watson 70000
Finance Painter 120000
Comp.Sci Taylor 10000
department

方案二就好很多了,即使录入10000条数据,也不会浪费空间,需要查询老师院系的办公地点时,只需要将两个表连接后再查询就行了。

所以我们得出结论

  • 分开记录比合起来记录要好!❌

这个结论是不严谨的,因为没有考虑分解有损的情况


有损分解

故名思义,有损分解就是把大表分解成小表之后,会损失原始数据的分解

让我们来看一个例子,下面的是原表

ID name street city salary
57766 Kim Main Perryridge 75000
98776 Kim North Hampton 67000
employee

我们把原表分解之后,两个Kim会出现混淆的现象

ID name
57766 Kim
98776 Kim

。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

name street city salary
Kim Main Perryridge 75000
Kim North Hampton 67000

如果现在要把两个表格合在一起,会无法分辨表一中的ID对应表二中的哪个Kim

无损分解

如果分解之后再合成,能够得到跟原来一样的表(没有损失信息),就叫做无损分解

关系代数来表示,就是:


使用函数依赖进行分解

表示方法

关系模式是一个属性集,为了稍作区分,我们用三种不同的方法表示属性集

  • α :表示属性集,但是不知道属性集是不是关系模式
  • r(R):表示属性集,这里的属性集特指关系模式,r代表关系的名字,不在意名字的话,可以省掉r,只写R

超码是一个或多个属性的集合,可以在表中区分不同的实体,某集合只要包含了超码,也会变成超码,所以说超码的超集也是超码

  • K:表示属性集,这里的属性集特指超码

函数依赖

给定r(R)上的一个实例,我们判断这个实例满足函数依赖X→Y的条件是:对实例中所有的元组对t1和t2,若t1[X] = t2[X],有t1[X] = t2[X],则t1[Y] = t2[Y]

通俗来讲就是:

设X,Y是关系R的两个属性集合,当任何时刻R中的任意两个元组中的X属性值相同时,则它们的Y属性值也相同,则称X函数决定Y,或Y函数依赖于X。

  • 例1:A→C在下表中是否成立?C→A呢?
A B C
a1 b1 c1
a1 b2 c1
a2 b2 c2
a2 b3 c2
a3 b3 c2

写这种题要记住一句关键的话,一个X仅有一个Y对应,跟判段是否为函数十分相似

可以看到,a1对应c1,a2对应c2,a3也对应c3,A中的每一个值都仅有唯一的C值对应,所以A→C成立

但是在C中,c2对应a2和a3,所以C→A不成立

  • 例2:在关系模式R中,K→R是否成立?

根据超码的定义,如果两个元组在超码上的值相同,那么这两个元组一定是同一个,所以,K→R成立


平凡函数依赖和非平凡函数依赖

若X→Y且X不包含Y,则称X→Y为非平凡函数依赖;否则若X包含Y,则必有X→Y,称此X→Y为平凡函数依赖.

常见的平凡函数依赖有

  • A→A
  • AB→A

Armstrong公理

自反律:若X为一属性集且Y⊆X,则X→Y成立

增补律:若X→Y成立且Z为一属性集,则ZX→ZY成立

传递率:若X→Y和Y→Z成立,则X→成立

公理推论:

合并律:若X→Y和X→Z成立,则X→YZ成立

分解律:若X→ZY成立,则X→Y和X→Z成立

伪传递律:若X→Y和ZY→M成立,XZ→M成立

让我们通过公理来证明一下推论

  • 合并律:

因X→Y ,所以X→XY (增广律 XX→XY即X→XY)

因X→Z ,所以XY→YZ (增广律)

因X→XY,XY→YZ(增广律)

故X→YZ (传递律)

  • 分解律:

因Y⊆ZY,所以ZY→Y(增广律)

因X→ZY,所以X→Y(传递律)

因Z⊆ZY,所以ZY→Z(增广律)

因X→ZY,所以Z→Y(传递律)

  • 伪传递律:

因X→Y ,所以WX→WY (增广律)

因WY→Z ,所以XW→Z (传递律)


依赖函数集F及其闭包

用通俗的话来讲,F就是给出的依赖关系集,但是给出的依赖集一般给的很简单,往往可以进一步推导出别的依赖关系,把所有推导出来的依赖关系加上原来给出的依赖关系合在一起,就可以得到F的闭包F+

我们不妨来看一道例题

  • 已知关系模式R(ABC),F={A→C,B→C},求F+

这题的关键是,用{A→C,B→C}推导出所有可以推导出的依赖关系

这个过程一般很庞大,我们就只推一部分,主要是为了更好的理解F+

现在已知A→C,我们就可以推出AC→C(增广律),我们把AC→C加入F+中

A→A在F中也没有,也可以加入到F+中

当然,F+远不止这些,因为还有很多依赖关系没有被推导出来,全推出来后合上F,就能得到F+了


范式

第一范式与原子域

  • 原子域:具有原子性的域。
  • 第一范式:在关系模型中,所有的域都应该是原子性的,即数据库表的每一列都是不可分割的原子数据项,而不能是集合,数组,记录等非原子数据项。

例如三围这个属性,是胸围,腰围,臀围的集合,如果一个表中包含了三围这个属性,必须要拆分成胸围,腰围,臀围后才能满足第一范式。

简单来说,满足第一范式是关系模型的基本要求,要是不满足第一范式,就不能被称作是关系模型。后面的BC范式和第三范式都是建立在第一范式的基础上的


BC范式(BCNF)

对F+中的形如X→Y的函数依赖,必须满足下面的两点之一

1.X→Y是平凡的函数依赖

2.X是超码

通过BC范式,我们能够轻松的区分一个表需不需要拆分,只要不满足BC范式,就需要拆分


依据BC范式进行拆分

经过检查,我们发现X→Y不满足BC范式,我们需要把表拆成两个部分

  • (X ∩ Y)
  • (R - (Y - X))

如果套用本文最开头大学的例子,X = dept_name,Y = {building, budget}

  • (X ∩ Y) = (dept_name, building, budget)
  • (R - (Y - X)) = (ID, name, dept_name, salary)

刚好是我们拆分后的两个表!


BC范式的局限

在设计数据库时,我们有的时候需要一些依赖关系如X → Y,这个依赖关系并不满足BC范式的要求,但是我们就是要保留这个依赖关系,这时BC范式就会暴露出要求过严的局限性

让我们看一个例子:

我们有一个大学的E-R图,包含以下要求:

  • 一个教师只能在一个系中
  • 一个学生可以有多个导师
  • 一个学生在一个系中最多有一个导师

根据以上条件和E-R图,我们可以得到两条函数依赖,需要在dept_name中成立

  • i_ID → dept_name
  • s_ID, dept_name → i_ID

如果按照BC范式的要求,i_ID并不是dept_name的超码(因为一个学生可以有多个导师),我们需要对dept_advisor进行拆分

拆分为

  • (s_ID, i_ID)
  • (i_ID, dept_name)

但是拆分后,s_ID, dept_name → i_ID不再成立,与我们的实际要求相违背

所以用BC范式约束dept_advisor是不合理的


第三范式(3NF)

第三范式可以看作是BC范式的宽松版,BC范式可以看作第三范式的特殊形式

第三范式在BC范式两条要求的基础上,加上了第三个条件

对F+中的形如X→Y的函数依赖,必须满足下面的三点之一:

1.X→Y是平凡的函数依赖

2.X是超码

3.Y - X中的每个属性A都包含于R的一个候选码中

如果我们用第三范式的要求来解上面那个例子,会是什么结果呢?

有下面两个函数依赖需要成立

  • i_ID → dept_name
  • s_ID, dept_name → i_ID

我们主要看i_ID → dept_name

很明显,不满足前两条,那满不满足第三条呢?

我们先用dept_name - i_ID = dept_name

接下来,只需要证明dept_name包含于候选码中,就可以满足第三个条件了

由于s_ID, dept_name → i_ID,那么(s_ID, dept_name)至少是一个超码

不存在(s_ID,dept_name)的子集也为超码,所以(s_ID, dept_name)是候选码

所以dept_name包含于(s_ID, dept_name)候选码中,i_ID → dept_name满足第三个条件,不需要进行拆分!


属性集的闭包

函数确定

X是属性集,Y是属性,如果X → Y,则称Y被X函数确定

用函数确定判断超码

我们不妨再回顾一下超码的知识

要证明X是超码,我们需要证明X→R,R是表中所有的属性的集合,所以我们需要证明X可以函数确定所有的属性

首先我们需要计算出F+,也就是所有的依赖关系,然后我们可能会得到诸如X→Z,X→M等依赖关系

当Y,Z,M等合起来能组成R时,就说明X是超码

但是这个做法有一个缺点,就是需要计算F+,很明显F+的计算是非常麻烦的,我们要尽量去避免


属性集闭包

令X为一个属性集,我们将函数依赖集F下被X函数确定的所有属性的集合称为F下X的闭包,记作X+

  • 有关系模式R<U,F>,其中U={A,B,C,D,E},F={AB→C,B→D,C→E,EC→B,AC→B},求(AB)+

首先,我们要从AB开始求,所以令X(0) = AB

第一步,求X(1)。我们要先列出X(0)的非空子集,即AB的非空子集,很显然为{A,B,AB}。然后扫描F集合,寻找包含有{A,B,AB}的函数依赖,就可以得到:AB→C,B→D。我们就可以把C,D合入X(0)中得到X(1),就可以求得X(1)=X(0)∪C∪D=ABCD。如果X(0)等于X(1)就说明继续进行下一步也会得到相同的结果,与离散数学中的传递闭包相似,于是我们可以结束步骤,所求即为答案,如果X(0)不等于X(1)就继续计算。

第二步,求X(2)。同第一步求X(1)的非空真子集,然后在F中一次寻找函数依赖,可以得到:AB→C,B→D,C→E,AC→B。所以X(2)=X(1)∪C∪D∪E∪B=ABCDE。这时候发现X(2)已经等于全部属性集U了,不可能再计算出新的结果,我们就结束计算,得出**(AB)+ =ABCDE。**

让我们来看一下C++实现求解属性集闭包的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
//首先输入F中的函数依赖对数 
//其次输入具体的函数依赖
//输入要求解的属性集X
//输出:X关于F的闭包:X+

/*输入示例:
比如F={A→C,B→C} 求A+
第一步: 2
第二步: A C
B C
第三步: A
输出: {AC}
*/
#include <iostream>
#include <string>
using namespace std;

struct FunctionDependence
{
string X;
string Y;
};
void Init (FunctionDependence FD[],int n)
{
//函数依赖关系初始化
int i;
string x,y;
cout<<"请输入F中的函数依赖(决定因素在左,被决定因素在右)"<<endl;
//输入函数依赖集合F
for (i=0;i<n;i++)
{
cin>>x>>y;
FD[i].X=x;
FD[i].Y=y;
}
cout<<"函数依赖集合F:";
cout<<"F={" ;
for (i=0;i<n;i++)
{
//显示已知的函数依赖集合F

cout<<FD[i].X<<"->"<<FD[i].Y;
if (i<n-1)cout<<", ";
}
cout<<"}"<<endl;
}

bool IsIn(string f,string zz)
{
bool flag1=false;
int len1=f.length();
int len2=zz.length();
int k=0,t=0,count1=0;
for (k=0;k<len1;k++)
{
for (t=0;t<len2;t++)
{
if (f[k]==zz[t])
{
//flag1=true;break;
count1++;
}
}
}
if (count1==len1)
{
flag1=true;
}
else flag1=false;
return flag1;
}
string CutAndSort(string mm)
{

int size=mm.length();
int kk=0,ii=0;;
string closure;
int a[200]={0};//用来记录各个命题出现的次数
for(kk=0;kk<size;kk++)
{
a[(int)mm[kk]]++;//强制转换类型,储存各个因素的次数
}

for (ii=0;ii<200;ii++)
{
if (a[ii]>=1)//cout<<(char)ii;
closure+=(char)ii;
}
return closure;
}

string X_Fn(FunctionDependence FD[],int n,string &xx)
{
string yy=xx;
for (int i=0;i<n;i++)
{
if (IsIn(FD[i].X,yy)==true)
{
xx+=FD[i].Y;
}
}
yy=CutAndSort(yy);
xx=CutAndSort(xx);
if (xx!=yy)
{
X_Fn(FD,n,xx);//递归
}
return xx;
}

void FD(FunctionDependence FD[],int n)
{
//输入 X
string xx;
int i;

cout<<"\n请输入属性集X:";
cin>> xx;
cout<<"\n"<<xx<<"关于F的闭包:{";
//求X关于F的闭包
cout<<X_Fn(FD,n,xx);

cout<<"}\n";
}

int main()
{
int N;
cout<<"请输入F中函数依赖的组数:";
cin>>N;

FunctionDependence fd[N];
Init(fd,N);
FD(fd,N);
FD(fd,N);
FD(fd,N);
return 0;
}

属性集闭包用途

  • 判断X是否为超码,如果X+包含了R中的所有属性,就说明X是超码
  • 用来判断X→Y,如果Y属于X+,则X→Y成立
  • 计算F+,我们通过计算所有属性的闭包,然后根据闭包得到函数依赖,把所有得到的函数依赖合在一起,就是F+

例题:R{A,B,C,D},D→A,C→A,C→D,B→C
请问候选码是?是否属于BC范式?

(1)首先我们求解A+,B+,C+,D+

使用上面的C++代码会很方便,这里我直接给出结果

A+ = {A},B+ = {ABCD},C+ = {ACD},D+ = {AD}

很明显,B是最小超码,即为候选码

(2)D→A既不满足D是超码,也不满足D包含A,所以R不满足BCNF


结语

本文主要参照《数据库系统概念》这本书,文中很多例子都出自此书,借着写博客的机会,把这本书的第八章又看了一遍。写完文章,看着电脑里面4个G的无声录屏,真是太尴尬了🌝,哈哈哈哈哈哈哈。

-------------本文结束感谢您的阅读-------------