数据库的课堂笔记罢了。

# 关系模型与关系代数

# 基本概念

关系数据库 (relational database) 是一些表的集合。我们称一个表为一个关系 (relation), 表中的每一行称为一个元组 (tuple), 表中的每一列称为一个属性 (attribute).

# 数据库与映射

数据库的实质是多重集上的映射。对于一个关系上的任一属性，我们称其的所有取值组成的集合为一个域 (domain). 如果域中的元素是不可再分的，则称该域是原子的 (atomic).

建立一个数据库，一个重要的要求是采用关系中的不同属性区分各个元组。这事实上是建立了数个属性值到单一元组的映射。

# 码

超码 (super key) 是一个或多个属性的集合，这些属性的组合可以使我们在一个关系中唯一地标识一个元组。若集合 $K$ 是一个超码，且 $K$ 的任一真子集都不是超码，那么称这样的最小超码为候选码 (candidate key).

# 关系代数

关系代数中的几个基本运算及符号表达如下：

select A1,A2, ..., An

from r1, r2, ..., rm

where P

# 关系演算

关系演算 (relation calculus) 是关系数据库的数学基础。包括元组关系演算和域关系演算两部分。关系演算不同于关系代数。

# 元组关系演算

检索出年龄不是最小的所有同学：

$$\{t|t \in Student \wedge \exists (u \in Student)(t[Sage]>u[Sage])\}$$

检索出小于年龄 20 岁，并且是男同学的所有学生：

$$\{t|t \in Student \wedge t[Sage]<20 \wedge t[Sex]='\text{男}'\}$$

检索出年龄小于 20 岁，或者 03 系的所有男学生：

$$\{t|t \in Student \wedge (t[Sage]<20 \vee t[D\#]=03) \wedge t[Sex]='\text{男}'\}$$

检索不是 03 系的所有学生：

$$\{t|t \in Student \wedge (\neg t[D\#]=03 )\}$$

检索不是 (小于 20 岁的男同学) 的所有同学：

$$\{t|t \in Student \wedge \neg(t[Sage]<20 \wedge t[Sex]='\text{男}')\}$$

检索计算机系的所有同学：

$$\Big\{t|t \in Student \wedge \big(\exists d\in\{d|d\in Dept \wedge d[Dname]='\text{计算机}'\} \, t[D\#]=d[D\#] \big)\Big\}$$

$$\Big\{t|t \in Student \wedge \big(\exists d\in Dept \, (t[D\#]=d[D\#] \wedge d[Dname]='\text{计算机}') \big)\Big\}$$

第二种更加像人类思维一些。

检索比 (任一) 张三年龄小的所有同学：

$$\Big\{t|t \in Student \wedge \big(\exists s \in \{s|s\in Student \wedge s[Sname]='\text{张三}'\} \,t[Sage]<s[Sage]\big)\Big\}$$

检索比所有张三年龄都小的同学：

$$\Big\{t|t \in Student \wedge \big(\forall s \in \{s|s\in Student \wedge s[Sname]='\text{张三}'\} \,t[Sage]<s[Sage]\big)\Big\}$$

或者

$$\Big\{t|t \in Student \wedge \neg \exists s \in Student (s[Sname]='\text{张三}'\wedge \,t[Sage]<s[Sage])\Big\}$$

或者

$$\Big\{t|t \in Student \wedge \forall s \in Student (s[Sname]='\text{张三}' \Rightarrow \,t[Sage]<s[Sage])\Big\}$$

检索学过所有课程的同学

$$\Big\{t|t \in Student \wedge \forall \left(u \in Course \big(\exists (s \in SC) (s[S\#] = t[S\#] \wedge u[C\#] = s[C\#])\big)\right)\Big\}$$

检索不是 03 系的所有学生

$$\{t|t \in Student \wedge t[D\#]!=03\}$$

检索不是（小于 20 岁的男同学）的所有同学的姓名

$$\Big\{n\Big|\exists t \in Student \big( \neg (t[Ssex]='\text{男}'\wedge t[Sage]<20) \wedge t[Sname]=n\big) \Big\}$$

检索所有同学所有课程全部及格的系

$$\Big\{d|d \in Dept \wedge \forall s \in Students \,\big(s[D\#]=d[D\#] \Rightarrow (\forall u \in SC (u[S\#] = s[S\#] \Rightarrow u[Score]>=60))\big)\Big\}$$

$$a \Rightarrow b \Leftrightarrow \neg a \vee b$$

# Reference

• relational calculus
• Tuple relational calculus

# SQL 语言

这部分主要是 SQL 具体怎么写。从初级的写法到一直到部分比较高级的写法。

# SQL 语言的组成

SQL 语言包括以下几部分：

• 数据定义语言 (Data Definition Language, DDL): 提供定义和修改关系模式，删除关系等命令。
  • 完整性 (integrity)
  • 视图定义 (view definition)
  • 授权 (authorization): 访问权限的规定。
• 数据操纵语言 (Data Manipulation Language, DML): 提供一个关系中元组的查询、插入、删除和修改等命令。
• 嵌入式 SQL (embedded SQL) 和动态 SQL (dynamic SQL): 定义 SQL 嵌入到通用编程语言的方式。

# SQL 基本语法特点

• 大小写：SQL 对大小写不敏感
• 空白符：SQL 对空格和换行符的处理与 C 语言相同，即多个空格 / 换行视作单一的分隔符处理。在不破坏单词完整性的情况下，可以在任意位置添加空行。
• 注释：SQL 中单行注释采用 -- 插入，多行注释采用 /* ... */ 插入。

# 基本数据类型

SQL 中的基本数据类型包括：

• char(n) : 固定长度的字符串，用户指定长度 $n$. 也可以使用全称 character .
• varchar(n) : 可变长度的字符串，用户指定最大长度 $n$, 等价于全称 character varying .
• int : 整数类型 (和机器相关的整数的有限子集)，等价于全称 integer .
• smallint : 小整数类型 (和机器相关的整数类型的子集)。
• numeric(p,d) : 定点数，精度由用户指定。这个数有 $p$ 位数字 (加上一个符号位)，其中$d$ 位数字在小数点右边。所以在一个这种类型的字段上， numeric(3,1) 可以精确储存 $44.5$, 但不能精确存储 $444.5$ 或 $0.32$ 这样的数。
• real , double precision : 浮点数与双精度浮点数，精度与机器相关。
• float(n) : 精度至少为 $n$ 位的浮点数。

此外，SQL 中还有时间等特殊的数据类型。

# SQL 中关系的创建

在 SQL 中，采用 create table 命令创建一个关系，其通用形式为

create table r ( 

  A1, D1,

  A2, D2, 

  ...,

  An, Dn,

  ⟨integrity-constraint_1⟩, 

  ...,

  ⟨integrity-constraint_k⟩

);

其中，完整性约束 (integrity constraint) 包括 (但不限于) 以下几种：

• primary key(A_j1, A_j2, ..., A_jm) : 主码约束
• foreign key(A_k1, A_k2, ..., A_kn) : 外码约束
• not null : 非空约束

一个关系创建的示例如下：

create table department (

  dept_name varchar(20), 

  building varchar(15), 

  budget numeric(12, 2), 

  primary key (dept_name)

);

# SQL 中关系的删除

要删除一个关系 department , 只需要执行

drop table department

# SQL 中数据的插入

在 SQL 中，采用 insert 命令将数据加载到关系中。例如下面的 SQL 语句：

insert into test1_student_course values(

    '201800020101',

    '300001',

    91.5,

    '200101',

    to_date('2009-07-15 09:09:09', 'yyyy-mm-dd hh24-mi-ss')

);

# SQL 查询

# 基本的 SQL 查询

SQL 查询语句的基本结构为

select ...  -- some attributes

from ...    -- some tables

where ...   -- some judgments

其中， select 后接一个或多个属性， from 后接一个或多个关系， where 后接一个或多个谓词。

# distinct & all

distinct 关键词用于 SQL 中的查询去重，该关键词一般置于属性名前，用来筛选出属性不同的各元组。下面是一个例子：

select distinct dept_name from instructor

该例子用来筛选所有不同的院系名称。

相对应地，还定义了关键词 all 用来显示表示不去重。但 SQL 是默认不去重的，因此 all 的使用较少。下面是一个例子：

select all dept_name from instructor

该例子用来筛选所有教师对应的院系名称 (有重复)。

下面是一些例子：

选取工资小于 1500 或工资大于 2000, 且编号为 03 的教师姓名：

select TName from Teacher 

where (Salary<1500 or Salary>2000) and D#='03';

需要注意 and 的优先级高于 or , 因此需要加括号。

求既学过 001 号课程，又学过 002 号课程的所有学生的学号

select S1.S# from SC as S1, SC as S2

where S1.S# = S2.S# and S1.C# = '001' and S2.C# = '002';

求 001 号课程比 002 号课程高的所有学生的学号

select S1.S# from SC as S1, SC as S2

where S1.S# = S2.S# and S1.C# = '001' and S2.C# = '002' and S1.Score > S2.Score;

查询 SQL 中的非空项，采用 not null 实现。如果希望查询不为空字符串的项，则采用 <> '' 实现。

# 聚集函数

聚集函数是以某个集合为输入，输出为某个值的函数。换句话说，聚集函数计算的是集合中的某个统计量。常见的聚集函数包括

• avg() 返回平均值
• min() 返回最小值
• max() 返回最大值
• sum() 求和
• count() 计数
  聚集函数可以用在 select 后，作为返回的属性。

# 基本应用举例

求计算机系教师的平均工资的 SQL 语句可以表示为：

select avg(salary) from instructor

where dept_name = 'Comp. Sci.';

# group by & having

求不及格课程超过两门的同学的学号

select S# from SC

where Score < 60

group by S#

having count(*) > 2;

没有学过李明老师讲授课程的所有学生的姓名

select Sname 

from Student natural join Course natural join SC natural join Teacher 

where (Tname <> '李明')

group by S#

having count(*) = 0;

select Sname from Student

where S# not in (Select S# from SC, Course as C, Teacher as T and T.T#=C.T#)

求两门以上不及格课程的同学的学号及其平均成绩：

select S#, avg(Score)

from SC

where Score < 60

group by S#

having count(*)>2;

是不对的，这样的 avg(score) 是不及格课程的平均成绩，不是全部的平均成绩。

正确的方法是

select S#, avg(Score) from SC

where S# in (

  select S# from SC

  where Score < 60

  group by S# having count(*)>2

)

group by S#;

# 集合的比较

找出工资最低的教师姓名：

select TName from Teacher

where Salary <= all (select Salary from Teacher)

找出 001 号课成绩不是最高的所有学生的学号

select S# from SC

where (

  C# = '001'

  and Score < some(

    select Score from SC

    where C# = '001'

  )

)

用分组的方式可以写为

select S# from SC

group by S#

所有课程都不及格的学生姓名

select SName 

from Student natural join SC

group by S#

having max(Score)<60

这样写有问题，因为不能默认 SName 和 S# 是一一对应的。

select SName from Student 

where 60 > all(

  select score from SC

  where S#=Student.S#

)

此处 Student.S# 是该行对应的一个固定值。

SELECT SName 

FROM Student S JOIN (

  SELECT Sid, COUNT (*) FailCount 

  FROM SC 

  WHERE Score < 60 

  GROUP BY 

  Sid

  ) F

  ON S.Sid = F.Sid JOIN ( SELECT Cid FROM Course ) AS C ON F.FailCount = C.Cid;

找出平均工资最高的系

select dept_name from instructor

group by dept_name

having avg(salary) >= all(

  select avg(salary) from instructor

  group by dept_name

)

列出选修了赵三老师主讲课程的所有学生的姓名

select SName 

from Student natural join SC

where C# in (

  select C# 

  from Course natural join Teacher

  where TName='赵三'

)

# exists 语句

exists 语句

没学过李明老师讲授的任何一门课程的所有学生姓名

select SName 

from Student natural join SC

where not exists (

  select C# from Course natural join Teacher

  where TName='李明' and C#=SC.C#

);

找出工资总额最大系的工资总额

select max(total_salary) from (

  select dept_name, sum(salary) 

  from instructor

  group by dept_name as dept_total(dept_name, total_salary)

)

找出平均工资最高的系

select dept_name from instructor

group by

# with

用来定义临时的关系

# 举例

找出预算最高的院系

with max_budget(value) as (

  select max(budget) from department

)

select department.name

from department, max_budget

where department.name = max_budget.value

或

select department.name

from department

where budget>=all(select budget from department)

找总工资高于平均总工资的院系

with dept_total(dept_name, value) as (

  select dept_name, sum(salary) 

  from instructor

  group by dept_name

), 

dept_total_avg(value) as (

  select avg(value) from dept_total

)

select dept_name 

from dept_total, dept_total_avg

where dept_total.value > dept_total_avg.value

删除有四门课程不及格的同学

with fail_id(S#) as (

  select * from SC

  group by S#

  having count(Score < 60) >= 4

)

delete from Student

where (

  Student.S# = fail_id.S#

)

标准答案

delete from Student where S# in (

  select S# from SC where Score < 60

  group by S#

  having count(*)>=4

)

# SQL 修改

当某学生 001 号课程成绩低于平均成绩时，将该学生的该成绩提高 $5\%$.

update SC

  set Score = Score*1.05

  where Score < (

    select avg(Score) from SC

    where C# = '001'

  ) and C# = '001'

# 中级 SQL

# SQL 连接

SQL 连接运算可以指定谓词，称为连接谓词 (join predicate), 使得结果可以包含被自然连接排除在外的元组。SQL 连接的基本表达式为

R1 join R2 on R1.id = R2.id

对其余连接运算，可以将 join 以其余连接关键词替换，如 outer join 等。

例如，求所有老师的任课情况，要求没有任课的老师也要在表中

select * from Teacher left outer join course on Teacher.T# = Course.T#

# 视图

视图没有物理上出现，而是一个存在于逻辑上的表。

定义视图 StudStat , 描述学生的学号、姓名、平均成绩、最高成绩，最低成绩、选课数目。

create view StudStat as (

  select S#, Sname, avg(Score) avgScore, max(Score) maxScore, min(Score) minScore, count(distinct C#) numCourse

  from Student left outer join SC on Student.S# = SC.S#

  group by Student.S#, Student.Sname

)

# 关系数据库设计

# 函数依赖

# 定义

函数依赖是关系模式中属性间的关系。对于一个关系模式 $r(R)$ 及其两个属性 $\alpha, \beta \subseteq R$, 若对于 $r(R)$ 的一个实例，其中的任意两元组 $t_1, t_2$ 都有

$$t_1[\alpha] = t_2[\alpha] \Rightarrow t_1[\beta] = t_2[\beta]$$

那么称该实例满足函数依赖 (satisfies the functional dependency) $\alpha \to \beta$. 进一步地，如果对于 $r(R)$ 的每个合法实例，都满足函数依赖 $\alpha \to \beta$, 那么称函数依赖 $\alpha \to \beta$ 在模式 $r(R)$ 上成立 (hold).

# 平凡的函数依赖

若 $\beta \subseteq \alpha$, 那么称函数依赖 $\alpha \to \beta$ 是平凡的 (trivial).

# Armstrong 公理及推论

• Armstrong 公理
  • 自反律 (reflexivity rule): $\beta \subseteq \alpha \Rightarrow \alpha \to \beta$.
  • 增补律 (augmentation rule): $\alpha \to \beta \Rightarrow \gamma\alpha \to \gamma\beta$.
  • 传递律 (transitivity rule): $\alpha \to \beta, \beta \to \gamma \Rightarrow \alpha \to \gamma$.
• 推论
  • $\alpha \beta \to \alpha$.
  • $\alpha \to \beta \wedge \gamma \to \delta \Rightarrow \alpha\gamma \to \beta\delta$.
  • 合并律 (union rule): $\alpha \to \beta, \alpha \to \gamma \Rightarrow \alpha \to \beta\gamma$.
  • 分解律 (decomposition rule): $\alpha \to \beta\gamma \Rightarrow \alpha \to \beta, \alpha \to \gamma$.
  • 伪传递律 (pseudo-transitivity rule): $\alpha \to \beta, \gamma\beta \to \delta \Rightarrow \alpha\gamma \to \delta$.
• 另外一些显然的性质
  • $\alpha\beta = \beta\alpha$. (基于定义)

下面是一个例子：

$F = \{AB \to E, BE \to I, E \to G, GI \to H\}$, 求证 $AB \to GH$.

证明如下：

$$\begin{aligned} & GI \to H, GI \to G && \Rightarrow && GI \to GH && (1) \\ & BE \to E, E \to G && \Rightarrow && BE \to G && (2) \\ & BE \to I, BE \to G\;(2) && \Rightarrow && BE \to GI && (3) \\ & AB \to E, AB \to B && \Rightarrow && AB \to BE && (4) \\ & (4), (3), (1) && \Rightarrow && AB \to GH \end{aligned}$$

# 函数依赖闭包

给定关系 $r(R)$ 上的函数依赖集 $F$, 其可以导出的所有函数依赖称为它的闭包 (closure), 记作 $F^+$.

函数依赖闭包的求解方式与其它领域求解闭包的方式是类似的，例如编译原理中 LR (0) 方法求解项目集闭包。采用的方式都是遍历生成，直到无新增时终止。可以用如下算法描述：

/*

 * input: attribute set a

 */

set<struct attr> result = a;

set<struct sttr> result_old;

while (result != result_old) {

  result_old = result;

  for (struct dep_rel d : F) {

    auto iter1 = find(result.begin(), result.end(), d.father);

    auto iter2 = find(result.begin(), result.end(), d.sun);

    if (iter1 != result.end() && iter2 == result.end()) { // 父亲在，儿子不在，就把儿子加入进去

      result.insert(*iter2);

    }

  }

}

# 无关属性和正则覆盖

# BCNF 和 3NF

# 数据库的存储和文件结构

# 文件组织

# 有序文件组织

一般按某个属性字段进行排序，该属性字段称为排序字段 (ordering field). 排序字段通常是关系中的主码。

特点：

• 查询效率高
• 更新效率低

# 聚簇文件组织

聚簇文件 (clustering file) 组织

# 多表聚簇