保持无损连接的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

目录
相关文章
|
24天前
|
并行计算 算法 计算机视觉
【MATLAB 】 EMD信号分解+模糊熵(近似熵)算法
【MATLAB 】 EMD信号分解+模糊熵(近似熵)算法
51 0
|
24天前
|
并行计算 算法 计算机视觉
【MATLAB 】 EEMD 信号分解+模糊熵(近似熵)算法
【MATLAB 】 EEMD 信号分解+模糊熵(近似熵)算法
60 0
|
9天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于DCT变换和位平面分解的数字水印嵌入提取算法matlab仿真
这是一个关于数字水印算法的摘要:使用MATLAB2022a实现,结合DCT和位平面分解技术。算法先通过DCT变换将图像转至频域,随后利用位平面分解嵌入水印,确保在图像处理后仍能提取。核心程序包括水印嵌入和提取,以及性能分析部分,通过PSNR和NC指标评估水印在不同噪声条件下的鲁棒性。
|
24天前
|
算法 Java vr&ar
保持无损连接和函数依赖的3NF合成算法(详细简介)期末必备
保持无损连接和函数依赖的3NF合成算法(详细简介)期末必备
20 0
|
24天前
|
人工智能 算法 BI
【图论】【 割边】【C++算法】1192. 查找集群内的关键连接
【图论】【 割边】【C++算法】1192. 查找集群内的关键连接
|
24天前
|
编解码 算法 jenkins
【MATLAB 】 小波分解-ARIMA联合时序预测算法,科研创新优选算法
【MATLAB 】 小波分解-ARIMA联合时序预测算法,科研创新优选算法
61 0
|
24天前
|
算法 数据安全/隐私保护 计算机视觉
基于二维CS-SCHT变换和LABS方法的水印嵌入和提取算法matlab仿真
该内容包括一个算法的运行展示和详细步骤,使用了MATLAB2022a。算法涉及水印嵌入和提取,利用LAB色彩空间可能用于隐藏水印。水印通过二维CS-SCHT变换、低频系数处理和特定解码策略来提取。代码段展示了水印置乱、图像处理(如噪声、旋转、剪切等攻击)以及水印的逆置乱和提取过程。最后,计算并保存了比特率,用于评估水印的稳健性。
|
1天前
|
算法
m基于PSO粒子群优化的LDPC码NMS译码算法最优归一化参数计算和误码率matlab仿真
MATLAB2022a仿真实现了基于遗传优化的NMS LDPC译码算法,优化归一化参数以提升纠错性能。NMS算法通过迭代处理低密度校验码,而PSO算法用于寻找最佳归一化因子。程序包含粒子群优化的迭代过程,根据误码率评估性能并更新解码参数。最终,展示了迭代次数与优化过程的关系,并绘制了SNR与误码率曲线。
9 2
|
2天前
|
算法 决策智能
基于GA-PSO遗传粒子群混合优化算法的CDVRP问题求解matlab仿真
该文介绍了车辆路径问题(Vehicle Routing Problem, VRP)中的组合优化问题CDVRP,旨在找寻满足客户需求的最优车辆路径。在MATLAB2022a中运行测试,结果显示了算法过程。核心程序运用了GA-PSO混合算法,包括粒子更新、交叉、距离计算及变异等步骤。算法原理部分详细阐述了遗传算法(GA)的编码、适应度函数、选择、交叉和变异操作,以及粒子群优化算法(PSO)的粒子表示、速度和位置更新。最后,GA-PSO混合算法结合两者的优点,通过迭代优化求解CDVRP问题。
|
10天前
|
算法 数据安全/隐私保护 C++
基于二维CS-SCHT变换和扩频方法的彩色图像水印嵌入和提取算法matlab仿真
该内容是关于一个图像水印算法的描述。在MATLAB2022a中运行,算法包括水印的嵌入和提取。首先,RGB图像转换为YUV格式,然后水印通过特定规则嵌入到Y分量中,并经过Arnold置乱增强安全性。水印提取时,经过逆过程恢复,使用了二维CS-SCHT变换和噪声对比度(NC)计算来评估水印的鲁棒性。代码中展示了从RGB到YUV的转换、水印嵌入、JPEG压缩攻击模拟以及水印提取的步骤。