大三暑期计划

已拿到nju offer，预推免开摆

第一阶段

目标很简单：恢复正常的作息与生活

确定很简单吗？

第二阶段

查缺补漏，重点整理

引用

这里先只谈左值引用。引用和被引用变量是一回事，个人认为实质上是二者所代表的变量地址相同。

函数返回值是引用

例如：

1
2
3
4
5
6
7
8

#include<iostream>
int n;
int &fuck(){return n;}
int main(){
    fuck() = 2;
    std::cout << n; // 2
    return 0;
}

可以将函数调用作为赋值对象。

常引用

指的是 const int &，不能通过常引用去修改其引用的变量。

不能将常引用初始化给非常引用：

1
2
3

const int &p = n;
int &q = p;
// compile error

函数重载

这里重载的定义是：函数名相同，函数参数个数或参数类型不同。

因此，函数参数列表相同但返回值类型不同，是不允许重载的。

如果在类里，还可以通过分别定义非常量成员函数和常量成员函数（函数定义后面加 const ）来重载。

例：

1
2
3

int fuck(int n){return n;}
long long fuck(int m){return 1ll * m * m;}
// 1.cpp:4:11: error: ambiguating new declaration of 'long long int fuck(int)'

函数缺省参数

指的是可以给函数参数列表后面几个连续的参数默认值。

1

int fuck(int n, int m = 0){return n + m;}

这里主要理解缺省参数存在的意义，它主要是为了优化程序的可扩充性。在初步进行需求开发时，可能对于一个接口的功能并没有完善的规划。到后期有了更完善的需求，可能会在同一个接口上扩充功能。这时可以在该接口（这里指函数）后面添加缺省参数，通过这个缺省参数来在扩充功能的同时，保证原程序中无需扩充功能的函数调用不需要修改调用形式（即一个一个在函数尾部添加参数）。

然后提醒一下，对于重载+缺省产生的二义性：

1
2

int fuck(int n = 1){return n * 2;}
int fuck(){return 1;}

当使用 fuck() 调用时，产生的二义性会让编译器产生错误。

类

私有成员

这里主要提醒一件事情，就是对于 private 修饰的成员，只能在成员函数内部访问。但是成员函数内部可以访问自己以及其它相同类的私有成员：

1
2
3
4
5
6
7
8

class fuck{
    private:
    int shit;
    void printshit(fuck *a){
        std::cout << shit + a->shit << std::endl;
    }
};
// ok

复制构造函数

指的是形如 T (T &) 或 T (const T &) 这样的用另一个对象的引用来初始化该对象的构造函数。如果不自己定义，会自动生成一个默认的复制构造函数。

新增tip：对于封闭类，编译器为其生成默认的复制构造函数时，会按照先调用其成员对象的复制构造函数的规则生成，而不是无参构造函数。

复制构造函数在三种情况下起作用：

• 用一个对象去初始化另一个对象：Complex c2(c1);，Complex c2 = c1; //初始化，不是赋值
• 一个函数中有一个参数是类A的对象，调用该函数时，类A的复制构造函数会被调用。
• 函数的返回值是类A的对象，则函数返回时会被调用，将返回值赋值给临时对象（注意）。

当然，像g++这种编译器可能会进行优化，可能不会生成临时对象，就少了中间的临时对象的复制构造函数和析构函数的调用（不愧是g++，主打一个激进）。而msvc这种就会按照C++的规定来编译。

类型转换构造函数

之前没听说过

指的是只有一个参数的构造函数。

这样无论是使用 = 进行赋值还是初始化，可以进行自动类型转换。具体看例子吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include<iostream>
class Complex{
public:
    double real, imag;
    Complex(int i){ // 类型转换构造函数
        std::cout << "IntConstructor called" << std::endl;
        real = i; imag = 0;
    }    
    Complex(double r, double i){
        real = r;
        imag = i;
        std::cout << "CommonConstructor called" << std::endl;
    }
};
int main(){
    Complex c1(7, 8);
    Complex c2 = 12;
    c1 = 9; // 9被转换成一个临时Complex对象，然后赋值给c1，在前面转换的过程中会调用类型转换构造函数
    std::cout << c1.real << "," << c1.imag << std::endl;
    return 0;
}

静态成员

对于类的静态变量，需要在定义类的文件中对其进行一次说明或初始化，否则会发生链接错误：

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

#include<iostream>
class Complex{
public:
    double real, imag;
    static int total_number;
    Complex(int i){ // 类型转换构造函数
        std::cout << "IntConstructor called" << std::endl;
        real = i; imag = 0;
    }    
    Complex(double r, double i){
        real = r;
        imag = i;
        std::cout << "CommonConstructor called" << std::endl;
    }
    ~Complex(){
        std::cout << "Destructor called" << std::endl;
    }
};
Complex fun(Complex tmp){
    return tmp;
}
int Complex::total_number = 0; // 初始化
int main(){
    std::cout << Complex::total_number;
    return 0;
}

思考：如何维护这个total_number呢？应该在怎么样的构造函数和析构函数来实时维护该变量？

封闭类构造函数/析构函数

封闭类：含有成员对象的类

封闭类对象生成时，先执行所有对象成员的构造函数（按照类中的说明次序，与初始化列表顺序无关），然后执行封闭类的构造函数。

封闭类对象消亡时，先执行封闭类对象的析构函数，再执行成员对象的析构函数（按照构造函数调用的反序）。

重载自增自减运算符

Tip：C++约定俗成的规则，就是前置形式的 ++c 返回的是对象 c 的引用，c++ 返回的是新的对象。

因此可以这么写 (++c)=1 。重载的时候注意返回值类型。

可以注意到前置的自增自减运算符效率更高，因为后置的情况会导致对象的拷贝。这也是为什么我喜欢在acm中写for循环喜欢写 for(int i = 0; i < n; ++i) ，当然对于内置整形变量其实无所谓了，更看个人风格。

protected

派生类可以访问的是当前对象的基类对象的protected成员，而不能访问非当前对象的protected成员。

多态

主要有两种表现方式：基类指针指向派生类对象、基类引用派生类对象

Tip：在类的成员函数（非构造、非析构）中调用虚函数，等价于 this 指针调用虚函数，表现为多态。而如果是构造函数和析构函数就不是多态（想想也是嘛，多态函数得等对象初始化完才能用）。

Tip2：派生类中和基类的虚函数同名同参数表的函数可以不加 virtual 。

保研记录

本人情况：

• 本科院校：江苏某top4！
• 本科专业：AI
• 排名：1/87
• 四级：595，六级：538
• 竞赛：ICPC银若干，CCPC铜若干，JSCPC金银，CSP440，cf两紫名号（？）
• 科研：无
• 项目：水项目
• 国奖，CCF优大（这俩感觉基本没用）
• 偏就业向，未来偏向于做引擎开发。因此梦校是软微、南软和人大信专。

总结为A批，而且又菜又爱玩，不仅没拿到金牌，还因为这沟槽的网瘾，没有深入参与过含金量高的项目。不过好在大三因为一个队友去和大一的两位noi✌组队，另一个队友退出了，然后我也选择了退役，转去卷课内，得以保住rk。但就夏令营的情况来看，保rk弃acm是我做的一个非常正确的选择。

夏令营之前：

虽然我是AI专业，但是我对AI提不起一点兴趣，尤其是CV、NLP这些（别问我为什么没转专业）。大二ICPC赛季结束的时候被一个学长忽悠去做AI相关的科研，后面还进了某CV组，体会了一下开组会读paper做pre的氛围，也是感到十分不快。

后面大三上的时候考虑做过sys，虽然谈不上非常喜欢，但至少不反感。不过从大三开始入门sys说实话感觉有点晚了，而且AI的培养计划并不注重对计算机系统能力的培养，导致我甚至连CPU指令流水线这种基本概念都不清楚，加上保rk要学讨厌的课程，我没办法分配出太多精力出来，因此学术梦碎。

为什么选择就业向呢？首先我本身是一名ACM选手，非常喜欢coding。其次我也是个造轮子爱好者兼游戏爱好者，对工程较感兴趣，也开发过一些小型3D游戏。不过由于大学期间大部分时间在卷ACM和课内（基本在码python，pytorch那些，当调包侠），没有多少实践的机会（面南大的时候老师也指出了我这个问题，哈哈），因此也希望读研期间能精进自己的engineering能力。

总结来看，作为一名ACM败犬，我在选择读研方向上也是经历了一波三折的过程。期间经历了无数次痛苦，包括误入歧途、自我怀疑、被学长yygq。尤其是大三选择ACM退役的那段时间，感觉自己大学中唯一一件有意义的事情与我断绝了，只剩下一堆不喜欢的AI课程要卷，也不知道自己接下来的路该怎么走，每一步所做出的选择是否是正确的。不过好在就保研而言的结果还是能让我满意的。

夏令营情况：

可以看到，多亏了大三上学期选择放弃ACM，得以保住rk1，让我在没有任何科研项目的情况下入了很多营。但是实际上我只完整参加了两个，主要是今年和往年相比，夏令营的时间冲突的太多了，属于是大型车祸现场。特别是六月初得知ruc信院和南软冲突的时候，我真的有点破防。最后由于华五情节与优营率的考虑，选择了南软，鸽了ruc。

1. njucs

今年南计开的非常早，好像四月份就开了，然后五月初就截止报名。当时我根本没有做好准备，内心也是非常慌。

由于我夏令营的目标是南软，所以一开始是不想去南计的，因为按往年情况来看，南大cs，se，ai这三个夏令营只能去一个（njusz那里我不太清楚）。但是看绿裙说南大cs线上测不考虑冲突因素，可以放心参加，我就参加了（怎么说也是梦校）。

南计的线上笔试也算是著名的难，往年原题可以参考绿裙的github仓库（虽然很少）。范围大概是408+算法+编译原理+linux+其余杂项，题型是单选+多选，多选漏选超选错选皆不得分。我记得今年的题偏向于编译原理和数据结构。因为我本科AI的，很多课程没学过，因此大多数题都是蒙的，除去几个ACM中接触到的几个算法和数据结构（kmp，背包）。

结果比较出乎意料，过了：

然鹅后续放弃了。

2. tongji cs

本来是没想报同济的，但是绿裙里有个同济的宣传大使，说这个学校就业非常好什么的，再加上夏令营时间也比较好，没和其它学校冲突，我就报了。（不是）

然而没想到的是今年同济cs夏令营的bar非常高，整个学院只入了我一个人。最后只能孤身一人前往上海。

同济的考核非常硬核，机考+笔试408+英语笔试+英语口试+面试，五脏俱全。是计分制，满分350.

机考的话非常简单，第一题是给定一个字符串，然后对串的每个字母在其对应的位置（例如a对应第1列，z对应26列）一行一行输出。第二题是找给定数独九宫格的冲突位置。第三题是输出数字三角形。我大概花了十几分钟就做完了，但是后面静查的时候发现了第二题的一个bug，及时改正。

笔试408+英语，非常难，时间也特别赶。我记得大题后两题我都直接空着（分别是计组画什么数据通路，以及计网给定一个802帧分析其内容，ip地址，协议什么的）。英语是一道阅读理解，一篇论文。

可以参考：https://zhuanlan.zhihu.com/p/658346474

面试，有九个老师围着你坐，轮流提问。一开始是让我英语自我介绍两分钟，然后是让我英语说transformer的原理。后面就提问了一些项目和专业课的知识，我记得问了我系统调用和普通函数调用的区别。最后一个问题出乎我意料，一个老师问了我高数题（我记得是分部积分啥的），这我咋会？感觉我这个组比较压力面，然而另一个哥们的组感觉非常友好，问了很多生活问题，还有思政题。

结果没想到是优营，分数还挺高，满分350拿了二百八十几分，应该是稳offer了。

面试那天雨非常大，emmm

3. njuse

南软是我夏令营的最高目标，毕竟华五+两年制+放实习，太适合我这种就业鼠鼠了。

南软的bar也是很神奇，隔壁江苏top3的rk2+ACM银没入营，我校只入了软工的rk1和我（套磁了一个导师，可能捞了我进去），同院计科的rk1也没入。但是南软同时放了若干双非非rk1的金牌✌入营。现在想想，当初ICPC没拿金的我选择保住rk1，真是太明智了。

南软安排又紧又松。紧是因为我一天半就走完了夏令营流程，松是因为南软通知事项的方式很随意，就建个群，然后有通知了就@全体成员发消息，公告都不带发的，也没有流程pdf，感觉就非常敷衍。

南软考核也比较全，笔试+机试+面试。

笔试的内容有五项，顺序依次为离散数学（群论+图论的证明题）、软件工程（画状态图，软件测试）、操作系统（页式内存，PV操作）、计算机网络（DNS，ALOHA协议，求极限（啊？））和数据库系统（B+树索引，递归查询sql语句，事务undo+redo），各占20分。开卷，但是考的很偏，我很多都没做出来。

机试的话，今年是四道算法题，没有了往年的面向对象题。今年南软的机试题普遍反映非常难，和隔壁南计的机试题（没有算法题）形成鲜明对比，我记得第一题是给定已有的面额值 ，要求你求出最少的需要补充的额外面额值的个数，在每个面额值的使用次数小于等于一个给定值 的情况下，能够相加组合得到范围 内的所有数。第二题是要你用两个平行于坐标轴的不相交矩形来包围给定的二维点集，要求两个矩形的面积和最小。第三题是给定一个坐标轴，坐标轴的第二象限有 头牛，每头牛占据一个单位长度，左开右闭，并按照 的速度（这里的速度是每 秒瞬移一个单位，注意）朝着 +x 方向移动。然后你在原点朝着 +y 方向观察，问给定每头牛的坐标，及其速度，问最多有多少头牛经过你的视线。第四题是给定一个二维平面，平面上有字母，空白以及障碍，要求除去障碍，每一个行或每一个列内部的连续块（连续的字母与空，障碍隔开）形成的序列是一个回文串。求你能够确定的最多的空白对应的字母的坐标数量，并给出最终局面。

由于我是ACMer，AK了，全场快300人中有10个AK的。没有签到题，感觉对一般人比较不友好。四道题的难度大概在div1a, b这种。解法分别为数学+贪心，排序+枚举切割的横/纵坐标，离散化+线段树，BFS。

我记得笔试交卷的时候，大家动静很大。然后有个监考老师露出了诡异的笑容，说：“诶，你们先别叫，下午再叫，下午才是正菜（早上笔试下午机试），现在只是给你们开开胃。欸，下午你们叫也叫不出来，哈哈哈，那个才叫酸爽。”当时给我们都整懵逼了。

面试的话，虽然拿同济练过手，但是作为i人的我，还是很紧张。不过惊喜的是在面试前半个小时，我收到了同济优营的消息。拿到第一个offer的喜悦瞬间冲刷了我所有的焦虑，后续面试也不再紧张了。

具体面试内容也比较轻松，让你介绍你的项目经历，不问专业课。由于我的项目比较水，老师转而让我陈述大学期间做过的有意义的事情，我直接把我的ACM经历全炸出来，感觉老师也是比较感兴趣。期间问了我最喜欢的算法，我说树状数组，然后老师们似乎并不太清楚这个东西，我就大致介绍了一下它的功能和原理。后面稍微批评了我项目实践能力较为缺乏。最后一个老师问了一些关于实验室横向的问题，也是畅所欲言。

当然面试内容具体情况分组考虑，有的组会压力面，比如作英语自我介绍，翻译英语，问软工那些模型（瀑布、螺旋、敏捷开发）什么的，因此建议充分准备。

最后也因为机试AK，没有悬念地优营了。说实话当初面完南软就觉得自己稳了，以至于过于自信，后续的sjtu软就没去（当然也有懒得读论文的原因）。但说实话不建议大家这么干，有点冒险（

预推免情况：

估计不会报名预推免了，主要是除了ruc信院，感觉没有比南软更适合我的去处了。可惜ruc不开预推免，呜呜呜呜。

顺带一提，今年软微保研似乎改革，变成纯科研向了，鼠鼠top2梦碎。

数据库完整性

实体完整性

create table中用primary key定义

例：创建学生表Student，将Sno属性定义为主码：

1
2
3
4
5
6
7
8

create table student(
	sno char(8),
	sname char(20) unique,
	ssex char(6),
	sbirthdate date,
	smajor varchar(40),
	primary key(sno)
);

插入或对主码列进行更新操作时，关系数据库管理系统按照实体完整性规则自动进行检查。

• 检查主码值是否唯一
• 检查主码的各个属性是否为空

这种检查操作需要 遍历每一条记录，十分耗时。因此关系数据库管理系统一般都在主码上自动建立一个索引。例如B+树索引。

参照完整性

在create table中用foreign key短语定义哪些列为外码。

用references短语指明这些外码参照哪些表的主码。

例：关系SC中（Sno, Cno）是主码，Sno、Cno分别参照Student表的主码和Course表的主码。

1
2
3
4
5
6
7
8
9
10

create table sc(
	sno char(8),
	cno char(5),
	grade smallint,
	semester char(5),
	teachingclass char(8),
	primary key (sno, cno),
	foreign key (sno) references student(sno),
	foreign key (cno) references course(cno)
);

一个参照完整性将两个表中的相应元组联系起来。对被参照表和参照表进行增删改查操作时可能会破坏参照完整性，必须进行检查。

例：

• 向SC表中增加一个元组，该元组的Sno属性值在表Student中找不到一个元组，其Sno属性值与之相等。
• 修改SC表中的一个元组，情况如上
• 从Student表中删除一个元组，造成SC表中某些元组的Sno属性值在Student中找不到一个元组对应
• 修改Student表中的一个元组，情况如上

参照完整性违约处理：

• 拒绝执行：一般为默认策略
• 级联操作：当删除或修改被参照表的一个元组导致与参照表的不一致，则删除或修改参照表中的所有导致不一致的元组
• 设置为空值：当删除或修改被参照表的一个元组导致不一致，则将参照表中所有造成不一致的元组的对应属性设置为空值

用户定义的完整性

针对某一具体应用的数据必须满足的语义要求。

属性上的约束

create table中定义属性约束

• 列值非空 (not null)
• 列值唯一 (unique)
• 检查列值是否满足一个条件表达式 (check短语)

元组上的约束

在create table语句中可以用check短语定义元组间不同属性需满足的限制

完整性约束命名子句

constraint <完整性约束名> <完整性约束>

修改表中的完整性限制

使用alter table语句

例：

1
2

alter table student
add constraint c1 check(sno between '114514' and '1919810');

触发器

挖坑

作业

假设有下面两个关系模式

职工（职工号，姓名，出生日期，职务，工资，部门号），其中职工号为主码

部门（部门号，名称，经理姓名，电话），其中部门号为主码

用SQL定义这两个关系模式，要去在模式中完成以下完整性约束的定义：

1. 定义每个模式的主码
2. 定义参照完整性约束
3. 定义职工年龄不超过65岁

oracle不支持constraint带有变量，这里需要使用触发器

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

drop table 职工;
drop table 部门;

create table 部门(
    部门号 char(8) primary key,
    名称 varchar(20),
    经理姓名 varchar(20),
    电话 varchar(20)
);

create table 职工(
    职工号 char(8) primary key,
    姓名 varchar(20),
    出生日期 date not null,
    职务 varchar(20),
    工资 decimal(10, 2),
    部门号 char(8),
    constraint fk_部门 foreign key(部门号) references 部门(部门号)
);

create or replace trigger ck_age
before insert or update on 职工
for each row
begin
	if(extract(year from current_date) - extract(year from :new.出生日期) > 65) then
		raise_application_error(-114514, '职工年龄不应超过65岁');
	end if;
end;
/

测试：

1
2
3
4
5

insert into 部门 values('88488848', 'test1', 'name1', '114514');
insert into 职工 values('66666666', 'name2', TO_DATE('1980-01-15', 'YYYY-MM-DD'), 'job1', '1145.14', '88488848');
insert into 职工 values('66666666', 'name2', TO_DATE('1980-01-15', 'YYYY-MM-DD'), 'job1', '1145.14', '88488849');
insert into 职工 values('66666667', 'name2', TO_DATE('1980-01-15', 'YYYY-MM-DD'), 'job1', '1145.14', '88488849');
insert into 职工 values('66666667', 'name2', TO_DATE('1880-01-15', 'YYYY-MM-DD'), 'job1', '1145.14', '88488848');

前两行正确，后三行应出现错误：

摘自《数据库系统概论》第六章

关系数据理论

1. 问题

针对一个具体问题，如何构造一个适合它的数据模式

即应该构造几个关系，每个关系由哪些属性组成等。

不好的关系模式：

• 数据冗余度太大，浪费存储空间
• 更新异常
• 插入异常
• 删除异常

数据依赖

属性值间的相互关联。是数据内在的性质，是语义的体现

主要介绍函数依赖。

不合适的数据依赖，容易造成上述的4个问题。

2. 规范化

2.1 函数依赖

给定关系模式R(U, F)（本章忽略D域，DOM属性到域的映射），X和Y是U的子集。若对于R(U, F)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称“X函数确定Y”或“Y函数依赖于X”，记作 。

X称为这个函数依赖的决定属性组，也称为决定因素。

函数依赖是语义范畴的概念，只能根据数据的语义来确定函数依赖。例如“姓名->年龄”这个函数依赖只有在学生不重名的情况下成立。数据库设计者可以对现实世界作强制的规定。

函数依赖是指关系模式R在任何时刻的关系实例均要满足的约束条件。

非平凡函数依赖：

只讨论非平凡函数依赖。平凡函数依赖没有意义。

完全函数依赖：若 ，但对于X的任何一个真子集X‘，都有 ，则称Y对X完全函数依赖，记作 。否则称为部分函数依赖，记作

传递函数依赖：在R(U, F)中，如果 ，则称Z对X传递函数依赖。记作 。

注意这里不能存在 ，否则X与Y是等价的，Z直接依赖于X。

2.2 码

设K为关系模式R(U, F)中的属性或属性组合。若 ，则称K为R的一个候选码。

若，则K称为超码。

若关系模式R有多个候选码，则选定其中的一个作为主码。

主属性：包含在任何一个候选码的属性。

全码：整个属性组U是码。

外码：关系模式R的属性（组）X并非R的码，但X是另一个关系模式的码，则称X是R的外码。

主码与外码一起提供了表示关系间联系的手段。

2.3 范式 （不允许表中有表）

关系数据库的关系必须满足一定的要求。满足不同程度要求的为不同范式。

一个低一级范式的关系模式，通过模式分解，可以转换为若干个高一级范式的关系集合。这种过程叫做规范化。

1NF：

如果一个关系模式R的所有属性都是不可分的数据项，则 。

不允许表中有表。

2.4 2NF （非主属性不允许部分依赖）

若 ，且每一个非主属性完全函数依赖于任何一个候选码，则 。

采用投影分解法可将一个1NF关系分解为多个2NF关系，可一定程度上减轻原1NF关系存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。但并不能完全消除。

不是很懂这里非主属性的意义所在。

2.5 3NF （非主属性不允许传递依赖）

设关系模式 ，若R中不存在这样的码X、属性组Y及非主属性Z ，使得 成立，，则称 。

不是很懂这里Z是非主属性的意义所在。

不允许传递依赖，自然就不允许部分依赖。

2.6 BCNF（不依赖于非码）

设关系模式 ，若 且 时X必含有码，则 。

BC范式首先解决了3NF中主属性存在的部分依赖问题，例如3NF中可能某候选码中的一个子集可以—>另一个主属性，但是BCNF要求必须是码或码的超集才可以->。其次解决了3NF中主属性存在的传递依赖问题，这个也是类似的情况。

2.7 多值依赖

给定关系模式R(U,F)，X,Y,Z是U的子集，且Z=U-X-Y。关系模式R中多值依赖 成立当且仅当对R的任意关系r给定的一对(x,z)值，有一组Y的值，这组值仅仅决定于x值而与z值无关。

等价定义

非平凡多值依赖：X->->Y，且Z不为空。若Z为空则为平凡多值依赖。

多值依赖的性质：

• 对称性：若X->->Y，则X->->Z。（可以画个二分图？？？）
• 传递性：若XYZ=U，X->->Y，Y->->Z，则X->->Z-Y
• 函数依赖是多值依赖的特殊情况
• 懒得写了

2.8 4NF

关系模式 ，如果对于R的每个非平凡多值依赖 ，X都含有码，则 。

4NF允许的非平凡多值依赖实际上是函数依赖。

3. 数据依赖的公理系统

模式分解算法的理论基础。函数依赖有一个有效且完备的公理系统——Armstrong公理系统

用途：

• 求给定关系模式的码
• 从一组函数依赖求得蕴含的函数依赖

逻辑蕴含：给定关系模式R(U, F)，其任何一个关系r，若函数依赖X->Y都成立，则称F逻辑蕴含X->Y。

3.1 Armstrong公理系统

对关系模式 R(U, F) 有以下推理规则：

• 自反律：若 ，则 为F所蕴含。
• 增广律：若 为F所蕴含，且 ，则 为F所蕴含。
• 传递律：若 和 为F所蕴含，则 为F所蕴含。

3.2 导出规则

可通过以上三条推理规则推出以下三条推理规则：

• 合并规则：由 得 。
• 伪传递规则：由 得 。
• 分解规则：由 得 。

根据合并和分解规则，可得引理

成立的充分必要条件是 成立。

3.3 函数依赖闭包

闭包：在关系模式R(U, F)中为F所逻辑蕴含的函数依赖的全体叫做F的闭包，记为 。

属性集闭包：。

判定 即判定 。

3.5 函数依赖集等价

如果 ，就说函数依赖集F覆盖G，或者F与G等价。

引理：F与G等价的充要条件是 。

3.6 最小依赖集

如果函数依赖集F满足：

• F中任一函数依赖的右部仅含有一个属性。
• F中不存在这样的函数依赖X->A，使得F与F-{X->A}等价。（即F中的函数依赖均不能由F中其他函数依赖导出）
• F中不存在这样的函数依赖X->A，X有真子集Z使得F-{X->A}U{Z->A}与F等价。（F中各函数依赖左部为最小属性集）

则F为极小函数依赖集。

定理：每一个函数依赖集F均等价于一个极小函数依赖集，此 为F的最小依赖集。

F的最小依赖集不一定是唯一的

求最小依赖集步骤：

• 将F中的所有依赖右边化为单一元素
• 去掉F中的所有依赖左边的冗余元素
• 去掉F中的所有冗余关系

4. 保持函数依赖的模式分解

关系模式 的一个分解是指 ，（其中 ，并且没有 ），即 。

若满足 ，那么该分解是一个保持函数依赖的分解。（可以用上面3.5节中的引理来证明一个分解是否保持函数依赖）

4.1 转换为3NF

1、极小化处理

2、按照相同左部进行分组

可以证明得到的一定是一系列3NF，具体证明在书P190-191

作业

1、设有关系模式 ，其中 ，。

(1). 计算 和 。

解：设 。

计算 ，逐一扫描 中的各个函数依赖，得 。因此 。

计算 ，逐一扫描 中的各个函数依赖，发现无额外元素，即 。

因此 。

设 。

计算 ，逐一扫描 中的各个函数依赖，得 。因此 。

计算 ，逐一扫描 中的各个函数依赖，发现无额外元素，即 。

因此 。

(2). 求 的所有候选码，并说明理由。

解：求出单个属性所对应的属性闭包：

由于只有 包含 ，因此候选码内部必有 。

可得 且 。

且 。

通过额外枚举，可以发现只有上述 满足候选码性质。

(3). 最高满足第几范式？为什么？

解：由于 ，因此 部分依赖于候选码 ，不满足第二范式条件。

因此 最高满足第一范式。

2、设有关系模式 ，其中：，求 的最小依赖集。

解：

首先将所有函数依赖的右边转换为单一属性：

然后去除所有函数依赖的左边的冗余属性：

考虑函数依赖 ，由于 ，因此 为冗余属性。故进一步简化：

考虑 是否冗余：不冗余

考虑 是否冗余：不冗余

考虑 是否冗余：可从 与Armstrong推出，故冗余

此时

考虑 是否冗余：不冗余

考虑 是否冗余：可从 得出，故冗余

此时

考虑 是否冗余：不冗余

考虑 是否冗余：不冗余

故得到 的最小依赖集：

3、设有关系模式 ，其中：，试问 是否成立，若成立请给出证明过程。

解：成立。证明如下：

令 。

计算 ，逐一扫描 中的各个函数依赖，得 ，故

计算 ，逐一扫描 中的各个函数依赖，得 。因此可知 ，根据Armstrong公理的性质，可得出 。

4、试用Armstrong公理系统推导出下面的推理规则：若 ，则有 。

解：首先根据增广率，可由 知 。

再根据传递率，可由 知 。

5、已知学生关系模式 。其中： 学号、 姓名、 系名、 系主任名、 课程、 成绩。

（1）写出关系模式 的基本函数依赖和主码。

解：，，，。

主码：。

（2）原关系模式 为第几范式？为什么？分解成高一级范式，并说明为什么？

解：为第一范式。首先对于关系模式 ，其所有属性都是不可分的属性，满足第一范式定义。

其次在该关系模式中，非主属性 部分函数依赖于主码 ，不满足第二范式定义。故 为1NF。

可以进行模式分解：。对于新关系模式 ，其主码为 ，故不存在部分函数依赖（但是存在传递依赖 ，），故为第二范式。对于新关系模式 ，其主码为 ，不存在部分函数依赖，也为第二范式。

（3）将关系分解成第三范式，并说明为什么？

解：在（2）的基础上进一步分解：。

对于 ，其只存在函数依赖 和 ，不存在传递依赖，故为第三范式。

对于 ，其只存在函数依赖 ，不存在传递依赖，故为第三范式。

对于 ，其只存在函数依赖 ，不存在传递依赖，故为第三范式。

6、设有关系模式 ，其中6个属性分别为学生的学号、姓名、年龄、教师的姓名、课程名及课程成绩。假设学生有重名，课程名也可能有重名。又假设教师无重名，且每个教师只教一门课，但一门课可有几个教师同时开设。当某个学生选定某门课后，其上课教师就固定了。

（1）试给出R的所有函数依赖（平凡函数依赖和部分函数依赖可不写）

解：，，，，。

（2） 试给出R的所有候选码。

解：

不存在除 外的属性组被 依赖，故候选码必然包含 。也因此可推出候选码不包含 。

求出单个属性所对应的属性闭包：

。

可知 ，且 。

同样 ，且 。

除此之外，无其余候选码。

7、试证明任何一个二目关系模式 都属于 。

证明：

分以下三种情况讨论：

• 关系模式 主码为 ，即全码，此时显然为 。
• 主码为 ，此时必有 ，，且 包含在码中，故满足 的定义。
• 主码为 ，理由同上

证毕。

8、若 ，试证明 。

证明：利用反证法。

假设关系 中存在码 ，属性组 和非主属性 ，满足 ，即不满足 的定义。

由于 ，故 和 必包含码。

由于 包含码，故 能够决定其余属性组，包括 ，即 。这与假设中的 矛盾，故假设不成立。（本质上是通过让 和 等价来消除传递依赖。）

因此 。

9、设属性 两两不相交，且 。已知：元组 在数据库中，请给出哪些元组也必然在数据库中。

解：根据 ，可得出新的两个元组：,

根据 ， 可得出新的四个元组：。

10、给定关系 如下：

试给出至少2个非对称多值依赖。注：仅写结果不分析不得分。

解：首先有多值依赖 ，这是因为 相对于 有两个取值 ，且对于这两个取值，属性 都有对应属性值 ，即 取值只与 有关。

其次有多值依赖 ，这是因为 相对于 有四个取值 ，且对于这四个取值，属性 都有对应属性值 ，即 取值只与 有关。