数据库引论:5、关系数据库设计理论

2024-04-18 21:13

本文主要是介绍数据库引论:5、关系数据库设计理论,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

5.1 好的关系设计的特点

​ 没有冗余,例如 i n _ d e p in\_dep in_dep模式:
i n _ d e p ( I D , n a m e , s a l a r y , d e p t _ n a m e , b u i l d i n g , b u d g e t ) in\_dep(ID,name,salary,dept\_name,building,budget) in_dep(ID,name,salary,dept_name,building,budget)
​ 表示 i n s t r u c t o r instructor instructor d e p a r t m e n t department department的关系上进行自然连接的结果,但实际上存在许多冗余,对于同一个院系的老师(例如 C o m p . S c i . Comp.Sci. Comp.Sci.),每一个元组都在 b u i l d i n g building building属性上冗余了。

​ 此外,如果想要创建一个新的院系,是一件比较麻烦的事情,或许可以通过插入空值来实现,但这样可能会导致不可预料的错误。

​ 那么这个模式就不是一个好的关系

5.1.1 分解

​ 避免模式中信息重复的唯一方式是将其分解为两个模式,单并非所有的模式分解都是有益的,例如:
e m p l o y e e ( I D , n a m e , s t r e e t , c i t y , s a l a r y ) employee(ID,name,street,city,salary) employee(ID,name,street,city,salary)
​ 分解为以下两个模式:
KaTeX parse error: Expected 'EOF', got '&' at position 2: &̲employee1(ID,na…
​ 存在如下缺陷:如果存在同名的两个员工,我们将其自然连接后,无法分辨到底是谁,反而多了很多无意义的元组。实际上,分解后得到了更多的元组,但却获得了更少的信息,这是因为我们丢失了正确连接的信息。

​ 我们将这样的分解称为有损分解,而将那些没有信息丢失的称为无损分解

图1 不好的分解导致信息丢失

5.1.2 无损分解

​ 令 R R R为关系模式,并令 R 1 R_1 R1 R 2 R_2 R2构成 R R R的分解,即 R = R 1 ∪ R 2 R=R_1\cup R_2 R=R1R2,如果对于所有合法的数据库实例,关系 r r r都包含与下述SQL查询的结果相同的元组集,我们称该分解是无损的:

	select *from (select R1 from r)natural join(select R2 from r)

​ 或用关系代数表示为: Π R 1 ( r ) ⋈ Π R 2 ( r ) = r \Pi_{R_1}(r)\Join \Pi_{R_2}(r)=r ΠR1(r)ΠR2(r)=r

​ 类似的,如果 r r r是真子集,即$r\sub\Pi_{R_1}®\Join \Pi_{R_2} $,那么分解是有损的

5.2 使用函数依赖进行分解

​ 在真实世界中的数据上通常存在各种约束(规则)。例如,在一个大学数据库中期望满足的一些约束有:

  1. 学生和教师通过他们的ID来唯一识别
  2. 每位学生和教师只有一个名字
  3. 每位教师和学生只(主要)关联一个系
  4. 每个系只有一个预算值,并且只有一栋关联的办公楼

​ 一个关系的满足所有这种真实世界约束的实例被称为该关系的合法实例(legal instance)

5.2.2 码和函数依赖

​ 在之前,我们将超码定义为:能够一起来唯一标识出关系中一个元组的一个或多个属性的集合。在这里,重新定义如下:

​ 给定 r ( R ) r(R) r(R) R R R的一个子集 K K K r ( R ) r(R) r(R)超码的条件是:

​ 在 r ( R ) r(R) r(R)的任意合法实例中,对于 r r r的实例中的所有元组对 t 1 t_1 t1 t 2 t_2 t2总满足:若 t 1 ≠ t 2 t_1\ne t_2 t1=t2 t 1 [ K ] ≠ t 2 [ K ] t_1[K]\neq t_2[K] t1[K]=t2[K],也就是在关系 r ( R ) r(R) r(R)的任意合法实例中,不存在两个元组在属性值 K K K上具有相同的值。

​ 考虑一个关系模式 r ( R ) r(R) r(R),并且令 α ⊆ R \alpha \subseteq R αR β ⊆ R \beta \subseteq R βR

  • 给定 r ( R ) r(R) r(R)的一个实例,如果对于该实例中的所有元组对 t 1 t_1 t1 t 2 t_2 t2,使得若 t 1 [ α ] = t 2 [ α ] t_1[\alpha]=t_2[\alpha] t1[α]=t2[α],则 t 1 [ β ] = t 2 [ β ] t_1[\beta]=t_2[\beta] t1[β]=t2[β]也成立,那么我们称该实例满足函数依赖 α → β \alpha \rightarrow \beta αβ
  • 如果 r ( R ) r(R) r(R)的每个合法实例都满足函数依赖 α → β \alpha\rightarrow \beta αβ,则我们称该函数依赖在模式 r ( R ) r(R) r(R)成立(hold)

​ 利用函数依赖的表达方式,我们可以对超码和候选码进行重新定义

K K K是关系表 R R R的一个超码,如果 K → R K\rightarrow R KR

K K K是关系表 R R R的一个候选码,如果 K → R a n d n o a ⊂ K , a → R K\rightarrow R \ and\ no \ a\subset K,a\rightarrow R KR and no aK,aR

​ 考虑之前提过的模式:
i n _ d e p ( I D , n a m e , s a l a r y , d e p t _ n a m e , b u i l d i n g , b u d g e t ) in\_dep(ID,name,salary,dept\_name,building,budget) in_dep(ID,name,salary,dept_name,building,budget)
​ 对于一个系,他的预算是唯一的,那么函数依赖 d e p t _ n a m e → b u d g e t dept\_name\rightarrow budget dept_namebudget成立,此外,属性对 ( I D , d e p t _ n a m e ) (ID,dept\_name) (ID,dept_name)构成 i n _ d e p in\_dep in_dep的一个超码,可写作:
I D , d e p t _ n a m e → n a m e , s a l a r y , b u i l d i n g , b u d g e t ID,dept\_name \rightarrow name,salary,building,budget IDdept_namename,salary,building,budget
​ 我们可以发现,函数依赖是否成立,取决于现实世界的一些约束,比如一个学生只能有一个院系,那么 s t u d e n t _ I D → d e p t _ n a m e student\_ID\rightarrow dept\_name student_IDdept_name是成立的,而相反,尽管表中的每一个实例都满足某一个依赖,也不能断定函数依赖成立。

​ 有些函数依赖被称为是平凡的(trival),因为它们被所有关系满足,例如 A → A , A B → A A\rightarrow A,AB\rightarrow A AA,ABA,一般地,如果 β ⊆ α \beta \subseteq \alpha βα,则形如 α → β \alpha\rightarrow \beta αβ地函数依赖是平凡的。

​ 一个关系的实例可能满足的某些函数依赖并不需要在关系的模式上成立。

闭包:包含集合 F F F中的所有函数依赖。使用符号 F + F^+ F+来表示,即为能够从给定的集合 F F F推导出的所有函数依赖的集合。

Armstrong’s Axiom

  1. 自反律:如果 β ⊆ α \beta \subseteq \alpha βα,则 α → β \alpha \rightarrow \beta αβ
  2. 增广律:如果 α → β \alpha\rightarrow \beta αβ,则 γ α → γ β \gamma\alpha\rightarrow \gamma\beta γαγβ
  3. 传递律:如果 α → β , β → γ \alpha\rightarrow\beta,\beta\rightarrow\gamma αβ,βγ,则 α → γ \alpha\rightarrow\gamma αγ

这个公理是正确且完备的

通过公理可推导出:

  1. 合并规则:如果 α → β , α → γ \alpha\rightarrow\beta,\alpha\rightarrow\gamma αβ,αγ,则 α → β γ \alpha\rightarrow\beta\gamma αβγ
  2. 分解规则:如果 α → β γ \alpha\rightarrow\beta\gamma αβγ,则 α → β , α → γ \alpha\rightarrow\beta,\alpha\rightarrow\gamma αβ,αγ
  3. 伪传递规则:如果 α → β , γ β → δ \alpha\rightarrow\beta,\gamma\beta\rightarrow\delta αβ,γβδ,则 α γ → δ \alpha\gamma\rightarrow\delta αγδ

例子:
R = ( A , B , C , G , H , I ) F = { A → B , A → C , C G → H , C G → I , B → H } R=(A,B,C,G,H,I)\ F=\{A\rightarrow B,A\rightarrow C,CG\rightarrow H,CG\rightarrow I,B\rightarrow H\} R=(A,B,C,G,H,I) F={AB,AC,CGH,CGI,BH}

A → H , A G → I , C G → H I , ⋯ ∈ F + A\rightarrow H,AG\rightarrow I,CG\rightarrow HI,\cdots \in F^+ AH,AGI,CGHI,F+

属性集闭包(Closure of attributes sets)

​ 给定一组属性 α \alpha α,定义属性 α \alpha α F F F下的闭包为: α → β ∈ F + ⟺ β ⊆ α + \alpha\rightarrow\beta \in F^+ \Longleftrightarrow \beta \subseteq \alpha^+ αβF+βα+

​ 计算 α + \alpha^+ α+的算法:
KaTeX parse error: Expected 'EOF', got '&' at position 2: &̲result:=\alpha;…
例子:

R = ( A , B , C , G , H , I ) , F = { A → B , A → C , C G → H , C G → I , B → H } R=(A,B,C,G,H,I),F=\{A\rightarrow B,A\rightarrow C,CG\rightarrow H,CG\rightarrow I,B\rightarrow H\} R=(A,B,C,G,H,I),F={AB,AC,CGH,CGI,BH}

计算 ( A G ) + (AG)^+ (AG)+

​ result = AG

​ result = ABCG( A → C , A → B A\rightarrow C ,A\rightarrow B AC,AB)

​ resullt = ABCGH ( C G → H CG\rightarrow H CGH)

​ result = ABCGHI=R ( C G → I CG\rightarrow I CGI)

A G AG AG是超键吗?

​ 是否有 A G → R AG\rightarrow R AGR? 显然 R ⊆ ( A G ) + R\subseteq (AG)^+ R(AG)+

A G AG AG是候选码吗?

​ 是否有 A → R A\rightarrow R AR?计算可得 ( A ) + = A B C H (A)^+=ABCH (A)+=ABCH,

​ 是否有 G → R G\rightarrow R GR?计算可得 ( G ) + = G (G)^+=G (G)+=G

最小覆盖(Canonical cover)

例如:

  • 在右边: { A → B , B → C , A → C D } \{A\rightarrow B,B\rightarrow C,A\rightarrow CD\} {AB,BC,ACD}可被简化为 { A → B , B → C , A → D } \{A\rightarrow B,B\rightarrow C,A\rightarrow D\} {AB,BC,AD} (缩小的过程)
  • 在左边: { A → B , B → C , A C → D } \{A\rightarrow B,B\rightarrow C,AC\rightarrow D\} {AB,BC,ACD}可被简化为 { A → B , B → C , A → D } \{A\rightarrow B,B\rightarrow C,A \rightarrow D\} {AB,BC,AD} (放大的过程)

最小覆盖:最简形式的 F F F

无关属性:考虑 F F F中的一个依赖 α → β \alpha\rightarrow \beta αβ

  • 属性A在左侧是无关的:如果 A ∈ α A\in \alpha Aα并且 F F F满足, ( F − { α → β } ) ∪ { ( α − A ) → β } (F-\{\alpha\rightarrow \beta\})\cup\{(\alpha-A)\rightarrow\beta\} (F{αβ}){(αA)β}
  • 属性A在右侧是无关的:如果 A ∈ β A\in\beta Aβ并且 F F F满足, ( F − { α → β } ) ∪ { ( α → ( β − A ) ) } (F-\{\alpha\rightarrow\beta\})\cup\{(\alpha\rightarrow(\beta-A))\} (F{αβ}){(α(βA))}
检测某一属性是否多余

​ 考虑 α ∈ β \alpha\in\beta αβ

  • 为了检测左侧的属性 A A A是否多余:
    • 利用 F F F中的依赖,计算 ( { α } − A ) + (\{\alpha\}-A)^+ ({α}A)+
    • 检查这个闭包,如果包含 β \beta β,那么A是多余的
  • 为了检测右侧的属性 B B B是否多余:
    • 利用 F ′ = ( F − { α → β } ∪ { α → ( β − A ) } ) F'=(F-\{\alpha\rightarrow\beta\}\cup\{\alpha\rightarrow(\beta-A)\}) F=(F{αβ}{α(βA)})中的依赖关系,计算闭包 α + \alpha ^+ α+
    • 如果闭包包含A,那么确实多余。

最小覆盖的严格定义

F F F的最小覆盖是依赖的一个集合 F c F_c Fc,满足:

  • F F F可以推导出 F c F_c Fc中的所有关系,反之亦然
  • F c F_c Fc中的所有依赖没有多余的属性
  • F c F_c Fc中的所有依赖,他们的左边都是唯一的,例如,没有这样两个依赖: α 1 → β 1 , α 2 → β 2 \alpha_1\rightarrow\beta_1,\alpha_2\rightarrow\beta_2 α1β1,α2β2,有 α 1 = α 2 \alpha_1=\alpha_2 α1=α2

计算最小覆盖的算法

伪代码:

repeat

​ 用集合的并来替换 F F F中形如 α 1 → β 1 a n d α 2 → β 2 \alpha_1\rightarrow\beta_1\ and\ \alpha_2\rightarrow\beta_2 α1β1 and α2β2 α 1 → β 1 β 2 \alpha_1\rightarrow\beta_1\beta_2 α1β1β2

​ 找多余的属性,并删除

until F不再变化

找候选码

​ 对于 R ( A 1 , A 2 , ⋯ , A n ) R(A_1,A_2,\cdots,A_n) R(A1,A2,,An)以及 F F F中的依赖关系,所有属性都可以被分类为4类:

  1. L L L:属性只出现在左侧
  2. R R R:属性只出现在右侧
  3. N N N:属性在两侧均未出现
  4. L R LR LR:属性出现在两侧

算法伪代码:

  1. 对所有属性分类: x x x代表 L L L N N N类, y y y代表 L R LR LR
  2. 计算 x + x^+ x+,如果 x x x包含 R R R中的所有属性,那么 x x x就是唯一的候选码,结束算法
  3. y y y中取属性 A A A,计算 ( x A ) + (xA)^+ (xA)+,如果 ( x A ) + (xA)^+ (xA)+包含 R R R中的所有属性,那么 x A xA xA R R R的一个候选码。继续选取,知道 y y y中属性的所有组合都被选过
  4. 结束,输出结果

无损链接分解

即无损分解,对于 R R R表中的所有属性,必须出现在分解 ( R 1 , R 2 ) (R_1,R_2) (R1,R2)中,即 R = R 1 ∪ R 2 R=R_1\cup R_2 R=R1R2,对于 R R R上所有可能的关系 r r r,有 r = Π R 1 ( r ) ⋈ Π R 2 ( r ) r=\Pi_{R_1}(r)\Join \Pi_{R_2}(r) r=ΠR1(r)ΠR2(r)

无损分解的判断

​ 对于 ( R ) = ( R 1 , R 2 ) (R)=(R_1,R_2) (R)=(R1,R2),它是一个无损分解,当且仅当

  • R 1 ∩ R 2 → R 1 R_1 \cap R_2 \rightarrow R_1 R1R2R1
  • R 1 ∩ R 2 → R 2 R_1\cap R_2 \rightarrow R_2 R1R2R2

​ 至少满足一个。

例如:给定 R < U , F > R<U,F> R<U,F>, U = { A , B , C , D , E } , F = { A B → C , C → D , D → E } U=\{A,B,C,D,E\},F=\{AB\rightarrow C,C\rightarrow D,D\rightarrow E\} U={A,B,C,D,E},F={ABC,CD,DE} R R R上的一个分解为: R 1 ( A , B , C ) , R 2 ( C , D ) , R 3 ( D , E ) R1(A,B,C),R2(C,D),R3(D,E) R1(A,B,C),R2(C,D),R3(D,E),判断是否为无损分解

P r o o f : Proof: Proof:
R 1 ∩ R 2 = C C → A B C ? 没有这个依赖关系 C → C D √ R 2 ∩ R 3 = D D → C D ? 没有这个依赖关系 D → D E √ R1\cap R2=C\\ C\rightarrow ABC \ ? 没有这个依赖关系\\ C\rightarrow CD \ √ \\ R2 \cap R3= D \\ D\rightarrow CD \ ? 没有这个依赖关系\\ D\rightarrow DE \ √ R1R2=CCABC ?没有这个依赖关系CCD R2R3=DDCD ?没有这个依赖关系DDE 
所以是无损分解。

这篇关于数据库引论:5、关系数据库设计理论的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/915849

相关文章

SQL server数据库如何下载和安装

《SQLserver数据库如何下载和安装》本文指导如何下载安装SQLServer2022评估版及SSMS工具,涵盖安装配置、连接字符串设置、C#连接数据库方法和安全注意事项,如混合验证、参数化查... 目录第一步:打开官网下载对应文件第二步:程序安装配置第三部:安装工具SQL Server Manageme

C#连接SQL server数据库命令的基本步骤

《C#连接SQLserver数据库命令的基本步骤》文章讲解了连接SQLServer数据库的步骤,包括引入命名空间、构建连接字符串、使用SqlConnection和SqlCommand执行SQL操作,... 目录建议配合使用:如何下载和安装SQL server数据库-CSDN博客1. 引入必要的命名空间2.

Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式

《Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式》本文详细介绍如何使用Java通过JDBC连接MySQL数据库,包括下载驱动、配置Eclipse环境、检测数据库连接等关键步骤,... 目录一、下载驱动包二、放jar包三、检测数据库连接JavaJava 如何使用 JDBC 连接 mys

MySQL数据库中ENUM的用法是什么详解

《MySQL数据库中ENUM的用法是什么详解》ENUM是一个字符串对象,用于指定一组预定义的值,并可在创建表时使用,下面:本文主要介绍MySQL数据库中ENUM的用法是什么的相关资料,文中通过代码... 目录mysql 中 ENUM 的用法一、ENUM 的定义与语法二、ENUM 的特点三、ENUM 的用法1

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

Go语言数据库编程GORM 的基本使用详解

《Go语言数据库编程GORM的基本使用详解》GORM是Go语言流行的ORM框架,封装database/sql,支持自动迁移、关联、事务等,提供CRUD、条件查询、钩子函数、日志等功能,简化数据库操作... 目录一、安装与初始化1. 安装 GORM 及数据库驱动2. 建立数据库连接二、定义模型结构体三、自动迁

嵌入式数据库SQLite 3配置使用讲解

《嵌入式数据库SQLite3配置使用讲解》本文强调嵌入式项目中SQLite3数据库的重要性,因其零配置、轻量级、跨平台及事务处理特性,可保障数据溯源与责任明确,详细讲解安装配置、基础语法及SQLit... 目录0、惨痛教训1、SQLite3环境配置(1)、下载安装SQLite库(2)、解压下载的文件(3)、

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

MySQL追踪数据库表更新操作来源的全面指南

《MySQL追踪数据库表更新操作来源的全面指南》本文将以一个具体问题为例,如何监测哪个IP来源对数据库表statistics_test进行了UPDATE操作,文内探讨了多种方法,并提供了详细的代码... 目录引言1. 为什么需要监控数据库更新操作2. 方法1:启用数据库审计日志(1)mysql/mariad

postgresql数据库基本操作及命令详解

《postgresql数据库基本操作及命令详解》本文介绍了PostgreSQL数据库的基础操作,包括连接、创建、查看数据库,表的增删改查、索引管理、备份恢复及退出命令,适用于数据库管理和开发实践,感兴... 目录1. 连接 PostgreSQL 数据库2. 创建数据库3. 查看当前数据库4. 查看所有数据库