avatar

Ryan-Hong's Tech Blog

Stay Humble

  • 首页
  • 分类
  • 技术栈
  • 知识库
Home 数据库系统---关系数据理论
文章

数据库系统---关系数据理论

Posted 2025-06-10 Updated 2025-06- 11
By Administrator
50~64 min read

问题的提出

表设计的好不好?

数据冗余+增删改异常

为什么有问题?

数据依赖关系 y=f(x)

eg:sname=f(sno)

eg:Student(Sno,Sdept,Mname,Cno,Grade)

合适的函数依赖关系

(Sno,Cno)---Grade SC(Sno,Cno,Grade)

Grade与Sno,Cno有关

有不合适的函数依赖关系

(Sno,Cno)---Sdept---Mname

Sdept和Mname只与Sno有关

数据依赖关系有哪些?

(函数依赖 FD y=f(x) vs 多值依赖x=f(y) MVD(不合适))

函数依赖关系

(完全依赖 vs 部分依赖(不合适))

(传递依赖(不合适))

Sno->Sdept->Mname

(平凡依赖(不合适) vs 非平凡依赖)

范式理论

函数依赖

定义 设R(U)是一个属性集U上的关系模式,X和Y是U的子集。若对于R(U)的任意一个可能的关系r,r 中不可能存在两个元组在X上的属性值相等, 而在Y上的属性值不等, 则称“X函数确定Y”或“Y函数依赖于X”,记作X→Y。

eg:Student(Sno,Sdept,Mname,Cno,Grade)

假设不允许重名:

Sno → Ssex, Sno → Sage

Sno → Sdept, Sno ←→ Sname

Sname → Ssex, Sname → Sage

Sname → Sdept


平凡函数依赖与非平凡函数依赖

X→Y,但Y⊈X则称X→Y是非平凡的函数依赖。

X决定Y,Y与X一点关系也没有

X→Y,但Y⊆X 则称X→Y是平凡的函数依赖。

X决定Y,Y属于X

对于任一关系模式,平凡函数依赖都是必然成立的,它不反映新的语义。

若不特别声明, 我们总是讨论非平凡函数依赖。


完全函数依赖与部分函数依赖

定义 在R(U)中,如果X→Y,并且对于X的任何一个真子集X’, 都有 X’ ↛ Y, 则称Y对X完全函数依赖,记作X →F Y。

若X→Y,但Y不完全函数依赖于X,则称Y对X部分函数依赖,记作X →P Y


传递函数依赖


范式

范式是符合某一种级别的关系模式的集合。

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

范式的种类:

各种范式之间存在联系:

某一关系模式R为第n范式,可简记为R∈nNF。

一个低一级范式的关系模式,通过模式分解(schema decomposition)可以转换为若干个高一级范式的关系模式的集合,这种过程就叫规范化(normalization)。

BCNF之后的4NF与5NF是多值依赖

1NF

定义:关系中每一分量不可再分。即不能以集合、序列等作为属性。(也就是不能表中套表,要保证数据的原子性。)

不满足1NF,因为{C1,C2,C3}和{C1,C4}是集合。

2NF

定义:每一个非主属性都完全函数依赖于任何一个候选码(消除非主属性对键的部分依赖)

eg:[例] S-L-C(Sno,Sdept,Sloc,Cno,Grade), Sloc为学生的住处,并且每个系的学生住在同一个地方。S-L-C的码为(Sno,Cno)。

函数依赖有

(Sno,Cno)→(F)Grade

Sno→Sdept, (Sno,Cno)→(P)Sdept

Sno→Sloc, (Sno,Cno)→(P)Sloc

Sdept→Sloc

  • 非主属性Sdept、Sloc并不完全依赖于码

关系模式S-L-C不属于2NF

消除非主属性对候选码的部份依赖

怎么进行模式分解?

S-L-C(Sno,Sdept,Sloc,Cno,Grade):(拆表:谁对你好,复制自己,把它带走)

  • SC(Sno,Cno,Grade)

  • S-L(Sno,Sdept,Sloc)

当主码只有一个,不存在完整部分的关系

3NF

定义:消除非主属性对键的传递依赖

eg:

  • SC(Sno,Cno,Grade)

  • S-L(Sno,Sdept,Sloc)(拆表:谁对你好,复制自己,把它带走)

    • S-D(Sno,Sdept)∈ 3NF

    • D-L(Sdept,Sloc)∈ 3NF

BCNF

定义:消除主属性对码的部分和传递函数依赖

判断方式:

1.将所有的依赖关系列出来,如果左边都是候选码,则满足BCNF

2.主属性内部没有对码的部分和传递函数依赖

eg:[例6.8] 关系模式STJ(S,T,J)中,S表示学生,T表示教师,J表示课程。每一教师只教一门课。每门课有若干教师,某一学生选定某门课,就对应一个固定的教师。

  • 由语义可得到函数依赖:(S,J)→T;(S,T)→J;T→J

  • 因为没有任何非主属性对码传递依赖或部分依赖,STJ ∈ 3NF。

  • 因为T是决定因素,而T不包含码,所以STJ ∈(/) BCNF关系。

4NF

5NF

数据依赖的公理系统

逻辑蕴涵

定义: 对于满足一组函数依赖F的关系模式 R <U,F>,其任何一个关系r,若函数依赖X→Y都成立,则称F逻辑蕴涵X →Y(即r中任意两元组t、s,若t[X]=s[X],则 t[Y]=s[Y])

eg:Student(Sno,Sname,Gender,Sage,Sdept)

R为Student关系,U为Sno,Sname,Gender,Sage,Sdept的集合,F为函数依赖关系的集合

F逻辑蕴涵X →Y

在表中含义:在Student关系中,Sno->Sname成立,则Student逻辑蕴涵Sno->Sname

闭包

定义:在关系模式R<U,F>中为F所逻辑蕴涵的函数依赖的全体叫作F的闭包,记为F+。

定义:设F为属性集U上的一组函数依赖,X、Y属于U, XF+={ A|X→A能由F根据Armstrong公理导出},XF+称为属性集X关于函数依赖集F的闭包

eg:U={ABCDE},F={A-B,B-C,D-E}

F+=写了的+没写的

在例中:写了的:A-B,B-C,D-E

没写的:A-C......还有很多

AF+=把A写在左边,所有可以推出来的:(写了的+没写的)

写了的:A-B

没写的:A-C

Armstrong公理系统

一套推理规则,是模式分解算法的理论基础

用途:

  • 求给定关系模式的码

  • 从一组函数依赖求得蕴涵的函数依赖

设U为属性集总体,F是U上的一组函数依赖, 于是有关系模式R <U,F >。

对R <U,F> 来说有以下的推理规则:

A1 自反律(reflexivity rule):若Y属于X属于U,则X →Y 为F所蕴涵

eg:U=(sno,cno,grade)X=sno,cno Y=sno

A2 增广律(augmentation rule):若X→Y为F所蕴涵,且Z  U,则XZ→YZ 为F所蕴涵

eg:U=(sno,cno,grade)X=sno,cno+grade Y=sno+grade

成立

A3 传递律(transitivity rule):若X→Y及Y→Z为F所蕴涵,则X→Z 为F所蕴涵

根据A1,A2,A3这三条推理规则可以得到下面三条推理规则:

合并规则(union rule):由X→Y,X→Z,有X→YZ

伪传递规则(pseudo transitivity rule):由X→Y,WY→Z,有XW→Z

分解规则(decomposition rule):由X→Y及Z属于Y,有X→Z

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

引理6.1 X→A1 A2…Ak成立的充分必要条件是X→Ai成立(i=1,2,…,k)

引理6.2 设F为属性集U上的一组函数依赖,X、Y属于U,X→Y能由F根据Armstrong公理导出的充分必要条件是Y属于XF+

求闭包的算法

算法6.1 求属性集X(X属于U)关于U上的函数依赖集F的闭包XF+

输入:X,F

输出:XF+

步骤:

[例6.11] 已知关系模式R<U, F>,其中

U={A, B, C, D, E};

F={AB→C, B→D, C→E, EC→B, AC→B}。

求(AB)F+ 。

X0=AB

X1=X0(AB)+CD=ABCD

X2=X1(ABCD)+CDEB=ABCDE

Stop

Con:AB->ABCDE=U

(AB)F+=U

函数依赖集等价

定义:如果G+=F+,就说函数依赖集F覆盖G(F是G的覆盖,或G是F的覆盖),或F与G等价

两个函数依赖集等价是指它们的闭包等价

最小函数依赖集等价

定义:如果函数依赖集F满足下列条件,则称F为一个极小函数依赖集,亦称为最小依赖集(Fmin)或最小覆盖

(1)A-BC->A-B,A-C

F vs Fmin vs F+

F与F+相等,因为闭包相等

F与Fmin相等,因为闭包相等

F--凝缩-->Fmin

F--扩充-->F+

知识库
DataBase
License:  CC BY 4.0
Share

Further Reading

Jun 13, 2025

数据库系统---关系代数

关系代数是一种抽象的查询语言,它用对关系的运算来表达查询 传统的集合运算 并(Union) R: S:

Jun 13, 2025

数据库系统---数据模型

层次模型 层次模型是数据库系统中最早出现的数据模型 层次模型用树形结构来表示各类实体以及实体间的联系 满足下面两个条件的基本层次联系的集合为层次模型 1. 有且只有一个结点没有双亲结点,这个结点称为根结点 2. 根以外的其它结点有且只有一个双亲结点 层次模型的特点: 结点

Jun 13, 2025

数据库系统---视图

定义视图 建立视图 CREATE VIEW <视图名> [(<列名> [,<列名>]…)] AS <子查询>

OLDER

数据库系统---数据库设计

NEWER

数据库系统---数据库恢复技术

Recently Updated

  • For zsh修改 PATH 环境变量
  • 数据库系统---关系代数
  • 数据库系统---数据模型
  • 数据库系统---视图
  • 数据库系统---未掌握

Trending Tags

thesis 色彩 NLP Typora Java Linux 数据分析 pandas MacOS DataBase

Contents

©2025 Ryan-Hong's Tech Blog. Some rights reserved.

Using the Halo theme Chirpy