保持无损连接的BCNF分解算法

简介: 保持无损连接的BCNF分解算法

建议在看之前熟悉候选键的求法,不清楚的可以转到这里来:


http://t.csdn.cn/fW30Q


步骤:


INPUT:关系模式R以及在R上成立的函数依赖集F

1.初始化P={R}

2.若P中的所有关系模式S都是BCNF,则转步骤(4)

3.若P中有一个模式S不是BCNF,则S中必能找到一个函数依赖X->A,X不是S的候选码,且

A不属于x(如果CD->C,右侧元素属于左侧,则不需要分解)。设S1=XA,S2=S-A分解后的(S1S2}替代S转步骤(2)

4.算法结束,输出P


例:


R={A,B,C,D,E,F,G} F={A->B,A->C,C->D,C->E,E->FG},将R分解为BCNF范式


步骤一:初始化


p={A,B,C,D,E,F,G}    = {A->B,A->C,C->D,C->E,E->FG}


L:{A}


R:{B,D,F,G}


LR:{C,E}


N为空集


x=LUN=A,A的闭包={A,B,C,D,E,F,G},所以A是唯一候选键


步骤二:


 = {A->B,A->C,C->D,C->E,E->FG}


判断bcnf范式:看函数依赖的左侧是否全为候选键,如果是,就是BCNF范式


(1)很明显{C->D}不满足bcnf范式的要求:


则设R1=CD,R2=R-D={A,B,C,D,E,F,G}-{D}={A,B,C,E,F,G}


P={R1,R2}={R1{C,D},R2{A,B,C,E,F,G}}


F1={C->D}    F2={A->B,A->C,C->E,E->FG}


注:如果存在C->D,D->E类似的传递依赖虽然D没有在F2中,但是C->E要写在F2中


(2)求F2={A->B,A->C,C->E,E,->FG},与上面的算法同理,A是唯一候选键


注:每一次的候选码都是在变化的,只是这里恰巧是A,如果这里的候选码是B,那么就要看左侧是否全为B,来判断是否为BCNF范式


C->E不满足BCNF范式


R2=CE,   R3=R2-E={A,B,C,F,G}


P={R1{CD},R2{CE},R3{A,B,C,F,G}}


F2={C->E}     F3={A->B,A->C,C->FG}     //虽然R3中没有E,但是可以通过传递依赖推出C->FG


F4={A->B,A->C,C->FG}


(3)求F3的候选码:与上面的算法同理,A是唯一候选键


C->FG不满足BCNF范式,所以:


R4=CFG,R5=R3-FG={A,B,C}


P={R1{C,D},R2{C,E},R3{C,F,G},R4{A,B,C}}


在F4中函数依赖只有{A->B,A->C}


至此每一项都是BCNF范式


P={R1{C,D},R2{C,E},R3{C,F,G},R4{A,B,C}}  

💖💖💖这里还有💖💖💖

保持无损连接和函数依赖的3NF合成算法,一起看看吧!!!

http://t.csdn.cn/2K8w9

目录
相关文章
|
5月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
153 0
|
自然语言处理 算法 数据挖掘
【数据挖掘】十大算法之PageRank连接分析算法
文章介绍了PageRank算法的基本概念和数学模型,包括如何通过一阶马尔科夫链定义随机游走模型以及如何计算网页的重要性评分,并提供了PageRank迭代算法的具体步骤。
572 0
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
259 2
|
机器学习/深度学习 算法 搜索推荐
django调用矩阵分解推荐算法模型做推荐系统
django调用矩阵分解推荐算法模型做推荐系统
185 4
|
并行计算 算法 Python
Dantzig-Wolfe分解算法解释与Python代码示例
Dantzig-Wolfe分解算法解释与Python代码示例
|
弹性计算 负载均衡 监控
加权最小连接数算法介绍
加权最小连接数算法介绍
659 6
|
机器学习/深度学习 算法 数据安全/隐私保护
基于DCT变换和位平面分解的数字水印嵌入提取算法matlab仿真
这是一个关于数字水印算法的摘要:使用MATLAB2022a实现,结合DCT和位平面分解技术。算法先通过DCT变换将图像转至频域,随后利用位平面分解嵌入水印,确保在图像处理后仍能提取。核心程序包括水印嵌入和提取,以及性能分析部分,通过PSNR和NC指标评估水印在不同噪声条件下的鲁棒性。
|
算法 Java vr&ar
保持无损连接和函数依赖的3NF合成算法(详细简介)期末必备
保持无损连接和函数依赖的3NF合成算法(详细简介)期末必备
302 0
|
2月前
|
机器学习/深度学习 算法 机器人
【水下图像增强融合算法】基于融合的水下图像与视频增强研究(Matlab代码实现)
【水下图像增强融合算法】基于融合的水下图像与视频增强研究(Matlab代码实现)
214 0
|
2月前
|
数据采集 分布式计算 并行计算
mRMR算法实现特征选择-MATLAB
mRMR算法实现特征选择-MATLAB
169 2

热门文章

最新文章