数据库复习——模式分解

模式分解这边主要包括无损分解保持函数依赖的分解两种形式,简单整理一下。

无损分解

  把一个 R R R 分成 ρ = { R 1 , R 2 , ⋯ , R k } \rho =\{R_1,R_2,\cdots,R_k\} ρ={R1,R2,,Rk},然后通过自然连接 R 1 ⋈ R 2 ⋈ ⋯ ⋈ R k R_1\bowtie R_2\bowtie \cdots\bowtie R_k R1R2Rk,如果连回来了就是无损分解,如果多出了一些冗余元组就是有损分解。

这个定义很难直接用来判定,下面介绍一个判定算法。

判定算法

术语描述

   ρ = { R 1 < U 1 , F 1 > , ⋯ , R k < U k , F k > } \rho = \{R_1<U_1,F_1>,\cdots,R_k<U_k,F_k>\} ρ={R1<U1,F1>,,Rk<Uk,Fk>} R < U , F > R<U,F> R<U,F> 的一个分解, U = { A 1 , ⋯ , A n } U=\{A_1,\cdots,A_n\} U={A1,,An} F = { F D 1 , ⋯ , F D ρ } F=\{\mathrm{FD_1,\cdots,FD}_\rho\} F={FD1,,FDρ}(必须是极小依赖集),其中 F D i : = X i → A l i \mathrm{FD}_i:=X_i\rightarrow A_{li} FDi:=XiAli。算法的过程:
( 1 ) (1) (1) 建立 k × n k\times n k×n C = [ c i j ] k × n \boldsymbol C=[c_{ij}]_{k\times n} C=[cij]k×n,每列对应属性 A j ( j = 1 , ⋯ , n ) A_j(j=1,\cdots,n) Aj(j=1,,n),每行对应一个分解的 U i U_i Ui c i j = { a j , A j ∈ U i , b i j , A j ∉ U i c_{ij}=\displaystyle\begin{cases}a_j,&A_j\in U_i,\\b_{ij},&A_j\notin U_i\end{cases} cij={aj,bij,AjUi,Aj/Ui
( 2 ) (2) (2) 遍历 F D i \mathrm{FD}_i FDi,截取 C \boldsymbol C C 中对应 X i X_i Xi 的列,看看哪些行的内容是相同的。这些行在 l i li li 列若存在一个 a l i a_{li} ali,那么这些行在 l i li li 列的值全部改为 a l i a_{li} ali;否则全部改为 b m l i b_{mli} bmli,其中 m m m 为这些行的行号最小值。

一个符号被更改,表中其它所有相同的符号都应作相同的更改。

( 3 ) (3) (3) 重复 ( 2 ) (2) (2) 的操作,如果有一行全 a a a 说明 ρ \rho ρ 是无损连接分解,停止算法;否则表 C \boldsymbol C C 总会在某个时刻不再更新,停止算法并下结论 ρ \rho ρ 是有损连接分解。

案例描述(直接上图)

设有关系模式 R ( A , B , C , D , E ) R(A,B,C,D,E) R(A,B,C,D,E) R R R 的最小函数依赖集是 F = A → D , E → D , D → B , B C → D , D C → A \mathit{F={A→D,E →D,D →B,BC →D,DC →A}} F=AD,ED,DB,BCD,DCA。判断 ρ = { A B , A E , E C , D B C , A C } \mathit{ρ=\{AB,AE,EC,DBC,AC\ \}} ρ={AB,AE,EC,DBC,AC } 是否为无损连接分解。

判定定理(分解为 2 个关系)

  定理描述:对于 R < U , F > R<U,F> R<U,F> 的一个分解 ρ = { R 1 < U 1 , F 1 > , R 2 < U 2 , F 2 > } \rho = \{R_1<U_1,F_1>,R_2<U_2,F_2>\} ρ={R1<U1,F1>,R2<U2,F2>},如果 U 1 ∩ U 2 → U 1 − U 2 ∈ F + U_1\cap U_2\rightarrow U_1-U_2\in F^+ U1U2U1U2F+ U 1 ∩ U 2 → U 2 − U 1 ∈ F + U_1\cap U_2\rightarrow U_2-U_1\in F^+ U1U2U2U1F+,则 ρ \rho ρ 具有无损连接性。
  这个定理可以从上面的算法得出,具体证明看下图就知道了。

保持函数依赖的分解

  把一个 R R R 分成 ρ = { R 1 , R 2 , ⋯ , R k } \rho =\{R_1,R_2,\cdots,R_k\} ρ={R1,R2,,Rk},然后看看是否有 F 1 + ∪ F 2 + ∪ ⋯ ∪ F k + = F + F_1^+\cup F_2^+\cup\cdots\cup F_k^+=F^+ F1+F2+Fk+=F+,如果相等就是保持函数依赖的分解,否则不是。

这个定义可以直接用来判定。

模式分解算法

保持函数依赖的 3NF 分解

描述

( 1 ) (1) (1) R < U , F > R<U,F> R<U,F>中的 F F F进行极小化处理。处理后的函数依赖集仍用 F F F 表示。
( 2 ) (2) (2) 找出不在 F F F 中出现的属性,把这样的属性构成一个关系模式,并把这些属性从 U U U 中去掉。
( 3 ) (3) (3) 如果 F F F 中有一个函数依赖涉及 R R R 的全部属性,则 R R R 不能再分解。
( 4 ) (4) (4) 如果F中含有 X → A X→A XA,则分解应包含模式 X A XA XA,如果 X → A 1 , X → A 2 , ⋯ , X → A n X→A_1,X→A_2,\cdots,X→A_n XA1,XA2,,XAn 均属于 F F F,则分解应包含模式 X A 1 A 2 ⋯ A n \mathit{XA}_1A_2\cdots A_n XA1A2An

例子

  设关系模式 R < U , F > R<U,F> R<U,F> U = { C , T , H , R , S , G , X , Y , Z } U=\{C,T,H,R,S,G,X,Y, Z\} U={C,T,H,R,S,G,X,Y,Z} F = { C → T , C S → G , H R → C , H S → R , T H → R , C → X } F=\mathit{\{C→T,CS→G,HR→C,HS→R,TH→R,C→X\}} F={CT,CSG,HRC,HSR,THR,CX},将 R R R 分解为 3 N F \rm3NF 3NF,且保持函数依赖。

:设该函数依赖集已经是最小化的,先对 F F F 中左边相同的进行合并 ( C → T + C → X = C → T X ) (C→T +C→X=C\rightarrow\mathit{TX}) (CT+CX=CTX) F = { C → T X , C S → G , H R → C , H S → R , T H → R } F=\mathit{\{C→TX,CS→G,HR→C,HS→R,TH→R\}} F={CTX,CSG,HRC,HSR,THR}
因此 ρ = { Y Z , C T X , C S G , H R C , H S R , T H R } \mathit{\rho=\{YZ,CTX,CSG,HRC,HSR,THR\}} ρ={YZ,CTX,CSG,HRC,HSR,THR}

Y Z \mathit{YZ} YZ F F F 中没有出现的属性,单独拿出来。

保持函数依赖的无损 3NF 分解

  在保持函数依赖的 3NF 分解基础上,尝试在 ρ \rho ρ 中加入 R R R 所有的码得 τ \tau τ。加入后可能会存在包含关系,保大去小。举个例子说明。
  有关系模式 R < U , F > R<U,F> R<U,F> U = { C , T , H , R , S , G } U=\{C,T,H,R,S,G\} U={C,T,H,R,S,G} F = { C → T , C S → G , H R → C , H S → R , T H → R } \mathit{F=\{C→T,CS→G, HR→C,HS→R,TH→R\}} F={CT,CSG,HRC,HSR,THR},将 R R R 分解为 3 N F \rm3NF 3NF,且既具有无损连接性又能保持函数依赖。

:求得关系模式 R R R 的码为 H S \mathit{HS} HS,它的一个保持函数依赖的 3 N F \rm3NF 3NF为: ρ = { C T , C S G , H R C , H S R , T H R } \mathit{\rho=\{CT,CSG,HRC,HSR,THR\}} ρ={CT,CSG,HRC,HSR,THR}
因为码 H S ⊂ H S R \mathit{HS\subset HSR} HSHSR,所以去掉 H S \mathit{HS} HS,保留 H S R \mathit{HSR} HSR。所以 τ = ρ = { C T , C S G , H R C , H S R , T H R } \mathit{\tau=\rho=\{CT,CSG,HRC,HSR,THR\}} τ=ρ={CT,CSG,HRC,HSR,THR}为满足要求的分解。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/355217.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

git的远程管理与标签管理

✨前言✨ &#x1f4d8; 博客主页&#xff1a;to Keep博客主页 &#x1f646;欢迎关注&#xff0c;&#x1f44d;点赞&#xff0c;&#x1f4dd;留言评论 ⏳首发时间&#xff1a;2024年6月20日 &#x1f4e8; 博主码云地址&#xff1a;博主码云地址 &#x1f4d5;参考书籍&…

swift使用swift-protobuf协议通讯,使用指北

什么是Protobuf Protobuf&#xff08;Protocol Buffers&#xff09;协议&#x1f609; Protobuf 是一种由 Google 开发的二进制序列化格式和相关的技术&#xff0c;它用于高效地序列化和反序列化结构化数据&#xff0c;通常用于网络通信、数据存储等场景。 为什么要使用Proto…

【python】Sklearn—Cluster

参考学习来自 10种聚类算法的完整python操作示例 文章目录 聚类数据集亲和力传播——AffinityPropagation聚合聚类——AgglomerationClusteringBIRCH——Birch&#xff08;✔&#xff09;DBSCAN——DBSCANK均值——KMeansMini-Batch K-均值——MiniBatchKMeans均值漂移聚类——…

MySQL之复制(七)

复制 定制的复制方案 分离功能 许多应用都混合了在线事务处理(OLTP)和在线数据分析(OLAP)的查询。OLTP查询比较短并且是事务型的。OLAP查询则通常很大&#xff0c;也很慢&#xff0c;并且不要求绝对最新的数据。这两种查询给服务器带来的负担完全不同&#xff0c;因此它们需…

Linux系统部署Samba服务,共享文件夹给Windows

Samba服务是在Linux和UNIX系统上实现SMB协议的一个免费软件&#xff0c;由服务器及客户端程序构成。 Samba服务是连接Linux与Windows的桥梁&#xff0c;它通过实现SMB&#xff08;Server Message Block&#xff09;协议来允许跨平台的文件和打印机共享。该服务不仅支持Linux和…

用React编写一个密码组件表单

theme: condensed-night-purple highlight: atelier-cave-light 背景介绍 我们在使用网站或者应用程序的登录界面或创建帐户界面时&#xff0c;往往避免不了需要用户输入密码这一步骤&#xff0c;而用户是否可以选择看见他们输入的密码是十分重要的一项功能。尤其是在当输入的…

20240620每日后端---------Spring Boot中的 5 大设计模式最佳实践和示例 这些是我经常使用的设计模式并且非常喜欢

在本文中&#xff0c;我们将深入探讨五种基本设计模式&#xff0c;并探讨在 Spring Boot 项目中有效应用它们的最佳实践。每个模式都将附有一个实际示例来演示其实现。 单例模式 Singleton 模式确保一个类只有一个实例&#xff0c;并提供对它的全局访问点。这对于管理资源&am…

【车载开发系列】CAN通信总线再理解(中篇)

【车载开发系列】CAN通信总线再理解&#xff08;中篇&#xff09; 九. CAN总线标准十. CAN物理层十一. CAN数据链路层1&#xff09;CAN的通信帧类型2&#xff09;CAN的标准帧格式1. CAN ID2. 数据场 3&#xff09;CAN总线仲裁 十二. CAN应用层1&#xff09;CANopen2&#xff09…

linux如何部署前端项目和安装nginx

要在Linux上部署前端项目并安装Nginx&#xff0c;你可以按照以下步骤操作&#xff1a; 安装Nginx: sudo apt update sudo apt install nginx 启动Nginx服务: sudo systemctl start nginx 确保Nginx服务开机自启: sudo systemctl enable nginx 部署前端项目&#xff0c;假设前…

Ruby on Rails Post项目设置网站初始界面

在构建了Ruby的Web服务器后&#xff0c;第三步就可以去掉框架的官方页面&#xff0c;设置自己的网页初始页了。 Linux系统安装Ruby语言-CSDN博客 、在Ubuntu中创建Ruby on Rails项目并搭建数据库-CSDN博客、 Ruby语言建立Web服务器-CSDN博客 了解Ruby onRails项目中的主要文件…

Srouce Insight 4出现乱码

今天用SI4打开一个工程文件&#xff0c;一打开发现注释全是乱码。中文全部看不出来&#xff0c;英文和数字可以看得出来。 那是因为中文的编码格式不算特别兼容。所以需要调整编码格式。 于是我在这里调整了编码格式&#xff1a; 找到菜单的Options-Preferences里面的Files 调…

《计算机英语》Unit1 计算机概述

期末试卷组成 1、选择20道 2、判断20道 3、词汇翻译&#xff08;单词词组&#xff0c;参照课后习题&#xff09; 4、翻译2道&#xff08;一道原题&#xff0c;参照作业&#xff09; Unit One Computer Overview 单元1 计算机概述 algorithm n. 算法 operate …

k8s之kubelet证书时间过期升级

1.查看当前证书时间 # kubeadm alpha certs renew kubelet Kubeadm experimental sub-commands kubeadm是一个用于引导Kubernetes集群的工具&#xff0c;它提供了许多命令和子命令来管理集群的一生周期。过去&#xff0c;某些功能被标记为实验性的&#xff0c;并通过kubeadm a…

CVPR 2024揭幕,清华大学论文接收量霸榜,轻松碾压斯坦福、麻省理工

CVPR2024 会议之眼 快讯 会议介绍 2024 年 CVPR &#xff08;Computer Vision and Pattern Recogntion Conference) 即国际计算机视觉与模式识别会议&#xff0c;于6月17日至21日正在美国西雅图召开。CVPR是计算机视觉和模式识别领域的顶级会议之一。与ICCV和ECCV并称为计算…

Java基础 - 练习(四)打印九九乘法表

Java基础练习 打印九九乘法表&#xff0c;先上代码&#xff1a; public static void multiplicationTable() {for (int i 1; i < 9; i) {for (int j 1; j < i; j) {// \t 跳到下一个TAB位置System.out.print(j "" i "" i * j "\t"…

【全网最全最详细】RabbitMQ面试题

一、说下RabbitMQ的架构大致是什么样的&#xff1f; RabbitMQ是一个开源的消息中间件&#xff0c;用于在应用程序之间传递消息。它实现了AMQP&#xff08;高级消息队列协议&#xff09;并支持其它消息传递协议&#xff0c;例如STOMP&#xff08;简单文本定向消息协议&#xff…

【QT5】<重点> QT多线程

文章目录 前言 一、QThread创建多线程 二、QMutex基于互斥量的同步 三、QReadWriteLock线程同步 四、QWaitCondition线程同步 五、QSemaphore基于信号量的同步 前言 本篇记录学习QT多线程的知识&#xff0c;参考视频13.1QThread创建多线程程序_哔哩哔哩。若涉及版权问题…

LeetCode 338.比特位计数

各位朋友们&#xff0c;大家好啊&#xff0c;今天此题我用的方法比较好理解&#xff0c;但时间复杂度比较高如果大家觉得可以的话&#xff0c;不妨给个免费的赞吧&#xff0c;谢谢了^ _ ^ 1.题目要求如图所示: 2.做题步骤: 1.先计算总共多少个数: int count 0;int number 0;…

基于C#开发web网页管理系统模板流程-主界面密码维护功能完善

点击返回目录-> 基于C#开发web网页管理系统模板流程-总集篇-CSDN博客 前言 紧接上篇->基于C#开发web网页管理系统模板流程-主界面统计功能完善-CSDN博客 一个合格的管理系统&#xff0c;至少一定存在一个功能——用户能够自己修改密码&#xff0c;理论上来说密码只能有用…

嵌入式实验---实验四 DMA传输实验

一、实验目的 1、掌握STM32F103DMA传输程序设计流程&#xff1b; 2、熟悉STM32固件库的基本使用。 二、实验原理 1、利用外部按键KEY1来控制DMA的传送&#xff0c;每按一次KEY1&#xff0c;DMA就传送一次数据到USART1&#xff08;串口1&#xff09;&#xff1b; 2、该串口…