函数依赖总结

关系模式的外延和内涵

一个关系模式包含外延和内涵。

外延就是通常所说的关系、表或当前值。由于用户经常进行增删改查,所以外延是与时间有关的。

内涵是与时间独立的,是对数据的定义以及数据完整性约束的定义。对数据的定义包括关系、属性、域的定义和说明。

对数据完整性约束主要包括两个方面:

  • 静态约束:涉及数据之间的联系(函数依赖)、主键和值域的设计。
  • 动态约束:定义各种操作(增删改)对关系值的影响。

一般就把内涵称为关系模式。

关系模式的冗余和异常

数据冗余是指同一个数据在系统中多次出现。

由于数据的冗余,在对数据进行操作时会引发各种异常:如修改异常、插入异常、删除异常。根本原因是数据冗余可能造成操作后数据不一致现象。

“分解”是解决冗余的主要方法,也是规范化的一条原则“关系模式有冗余问题,就分解它”。

关系模式的非形式化设计准则

  • 关系模式的设计应尽可能 只包含有直接联系的属性,不要包含有间接联系的属性。
  • 关系模式的设计应尽可能 使相应关系中不出现插入、修改、删除等操作异常现象。
  • 关系模式的设计应尽可能 使得相应关系中避免放置经常为空值的属性。
  • 关系模式的设计应尽可能 使得关系的等值连接在主键和外键的属性上进行,并且保证链接后不会生成额外的元组。

函数依赖(FD)

FD的定义:

课本上使用数学集合论定义,其实函数依赖就是某个属性集决定另一个属性集时,称另一属性集依赖于该属性集。

在数据库中,FD是对关系模式R的一切可能的关系r定义的。对于当前关系r的任意两个元组,如果X值相同,则要求Y值也相同。这种依赖称为函数依赖。记为X->Y, 读作“X决定Y”,或“Y依赖与X”。

如果X->Y 和Y->X同时成立,则可记为X<-->Y,也就是在关系中,X和Y具有一一对应关系。

FD的逻辑蕴涵:

逻辑蕴含问题:比如A->B和B->C在关系模式上成立,那么A->C是否成立?这个问题就是逻辑蕴含问题。

设F是关系模式R上的一个函数依赖集合,X->Y是R上的一个函数依赖。如果对于R上的每个满足F的关系r也满足X->Y,那么称F逻辑蕴含X->Y。记为 F |= X->Y。

被F逻辑蕴含的函数依赖全体构成的集合,称为函数依赖集F的闭包,记为F+。

FD的推理规则:

从已知的一些FD,可以推导出另外一些FD,这需要一系列规则。这些规则常被称为“Armstrong"公理。

设U是关系模式R的属性集,F是R上成立的函数依赖集。FD的推广规则如下:

  1. 自反性:若X1⊆X⊆U,则X->X1在R上成立。(X与自己的子集自反)
  2. 增广性:若X->Y在R上成立,且Z⊆U,则XZ->YZ在R上成立。
  3. 传递性:若X->Y和Y->Z在R上成立,则X->Z在R上成立。
  4. 合并性:{X->Y, X->Z}  |= X->YZ
  5. 分解性:{X->Y, Z⊆Y} |= X->Z
  6. 伪传递性:{X->Y, WY->Z} |= WX->Z
  7. 复合性:{X->Y, W->Z}  |= XW->YZ
  8. 通用一致性原理:{X->Y, W->Z}  |= X∪(W-Y) ->YZ

FD和关键码的关系

有了FD的概念,可以把关键码和FD联系起来:

设关系模式R的属性集为U,X是U的一个子集,如果X->U在R上成立,那么称X是R的一个超键。如果X->U在R上成立,但X的任一真子集X1->U在R上不成立,则称X是是R的一个候选键。

一般键都是指候选键。

属性集闭包

求解函数依赖集闭包(F+)是NP完全问题,所以当需要判断是否能从已知FD集F中推导出FD X->Y,先求出F+再判断X->Y是否在F+中是很耗时间的事情。下面引入属性集闭包。

属性集闭包:F是属性集U上的FD集,X是U的子集,那么相对于F的属性集X的闭包X+可以定义为:它是一个从F集使用FD推理规则推出的所有满足X->A的属性A的集合。

求解属性集闭包的算法可以参考:属性集闭包算法

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏take time, save time

你所能用到的无损压缩编码(二)

     上个月项目荷兰大佬要检查,搞的我想写的东西不断推迟,现在检查完了,我决定继续把我想写的这整个一个系列写完,上一次写的是最简单的无损编码行程编码,这一次...

37490
来自专栏代码永生,思想不朽

utf8中文字符串的多模式匹配算法的优化

上个月接触到了我组的一个关于在海量文本中匹配字符串业务。读源代码时发现一些问题,并针对这些问题做了优化工作,效果非常明显。

50830
来自专栏小樱的经验随笔

零基础学并查集算法

并查集是我暑假从高手那里学到的一招,觉得真是太精妙的设计了。以前我无法解决的一类问题竟然可以用如此简单高效的方法搞定。不分享出来真是对不起party了。(pa...

56380
来自专栏c#开发者

设计模式之策略模式(Strategy)

策略模式: 策略模式属于对象行为模式[GOF95]。其用意是针对一组算法,将每一个算法封装到具体共同缄口的独立的类中,从来是的他们可以相互替换。策略模式使得算法...

374140
来自专栏智能算法

ZIP压缩算法详细分析及解压实例解释(上)

来源:esingchan - 博客园 链接:www.cnblogs.com/esingchan/p/3958962.html(点击尾部阅读原文前往) 最近自己实...

68090
来自专栏数说工作室

【SAS Says】基础篇:6. 开发数据(二)

如果你管着一份10000条的客户数据,有一天,老板拿着一个500人的表告诉你,这表上的500位客户的信息发生了变动,而且变动的变量很不规律,如客户102是收入发...

40730
来自专栏杨建荣的学习笔记

Python之Numpy初识

今天翻了下计划,要学习Numpy了,所以得调动脑细胞的积极性,看看能有什么收获。 首先得了解下什么是Numpy,从我的印象中,一般提到这个工具都会和机器学习关...

363110
来自专栏算法channel

玩转Pandas,让数据处理更easy系列6

玩转Pandas系列已经连续推送5篇,尽量贴近Pandas的本质原理,结合工作实践,按照使用Pandas的逻辑步骤,系统地并结合实例推送Pandas的主要常用功...

10020
来自专栏java一日一条

Java 8:HashMap的性能提升

HashMap是一个高效通用的数据结构,它在每一个Java程序中都随处可见。先来介绍些基础知识。你可能也知道,HashMap使用key的hashCode()和e...

8620
来自专栏机器学习算法与Python学习

机器学习(31)之频繁集挖掘FP Tree详解

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第一 【Python】:排名第三 【算法】:排名第四 明早7:22推送第2期免费送书活动 ...

43260

扫码关注云+社区

领取腾讯云代金券