数据库引论: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

相关文章

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

MySQL数据库宕机,启动不起来,教你一招搞定!

作者介绍:老苏,10余年DBA工作运维经验,擅长Oracle、MySQL、PG、Mongodb数据库运维(如安装迁移,性能优化、故障应急处理等)公众号:老苏畅谈运维欢迎关注本人公众号,更多精彩与您分享。 MySQL数据库宕机,数据页损坏问题,启动不起来,该如何排查和解决,本文将为你说明具体的排查过程。 查看MySQL error日志 查看 MySQL error日志,排查哪个表(表空间

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

怎么让1台电脑共享给7人同时流畅设计

在当今的创意设计与数字内容生产领域,图形工作站以其强大的计算能力、专业的图形处理能力和稳定的系统性能,成为了众多设计师、动画师、视频编辑师等创意工作者的必备工具。 设计团队面临资源有限,比如只有一台高性能电脑时,如何高效地让七人同时流畅地进行设计工作,便成为了一个亟待解决的问题。 一、硬件升级与配置 1.高性能处理器(CPU):选择多核、高线程的处理器,例如Intel的至强系列或AMD的Ry

基于51单片机的自动转向修复系统的设计与实现

文章目录 前言资料获取设计介绍功能介绍设计清单具体实现截图参考文献设计获取 前言 💗博主介绍:✌全网粉丝10W+,CSDN特邀作者、博客专家、CSDN新星计划导师,一名热衷于单片机技术探索与分享的博主、专注于 精通51/STM32/MSP430/AVR等单片机设计 主要对象是咱们电子相关专业的大学生,希望您们都共创辉煌!✌💗 👇🏻 精彩专栏 推荐订阅👇🏻 单片机

深入理解数据库的 4NF:多值依赖与消除数据异常

在数据库设计中, "范式" 是一个常常被提到的重要概念。许多初学者在学习数据库设计时,经常听到第一范式(1NF)、第二范式(2NF)、第三范式(3NF)以及 BCNF(Boyce-Codd范式)。这些范式都旨在通过消除数据冗余和异常来优化数据库结构。然而,当我们谈到 4NF(第四范式)时,事情变得更加复杂。本文将带你深入了解 多值依赖 和 4NF,帮助你在数据库设计中消除更高级别的异常。 什么是

SprinBoot+Vue网络商城海鲜市场的设计与实现

目录 1 项目介绍2 项目截图3 核心代码3.1 Controller3.2 Service3.3 Dao3.4 application.yml3.5 SpringbootApplication3.5 Vue 4 数据库表设计5 文档参考6 计算机毕设选题推荐7 源码获取 1 项目介绍 博主个人介绍:CSDN认证博客专家,CSDN平台Java领域优质创作者,全网30w+

DM8数据库安装后配置

1 前言 在上篇文章中,我们已经成功将库装好。在安装完成后,为了能够更好地满足应用需求和保障系统的安全稳定运行,通常需要进行一些基本的配置。下面是一些常见的配置项: 数据库服务注册:默认包含14个功能模块,将这些模块注册成服务后,可以更好的启动和管理这些功能;基本的实例参数配置:契合应用场景和发挥系统的最大性能;备份:有备无患;… 2 注册实例服务 注册了实例服务后,可以使用系统服务管理,