Armstrong公理系统_若有x→y,x→z,则x→yz。-程序员宅基地

技术标签: 软考知识点记录  

Armstrong公理的推论

  • 合并规则:若X→Y,X→Z同时在R上成立,则X→YZ在R上也成立。
  • 分解规则:若X→W在R上成立,且属性集Z包含于W,则X→Z在R上也成立。
  • 伪传递规则:若X→Y在R上成立,且WY→Z,则XW→Z。

函数依赖的公理系统

一、Armstrong公理系统设关系模式R<U,F>,其中U为属性集,F是U上的一组函数依赖,那么有如下推理规则:

  1. A1自反律:若Y⊆X⊆U,则X→Y为F所蕴含;
  2. A2增广律:若X→Y为F所蕴含,且Z⊆U,则XZ→YZ为F所蕴含;
  3. A3传递律:若X→Y,Y→Z为F所蕴含,则X→Z为F所蕴含。

根据上面三条推理规则,又可推出下面三条推理规则:

  1. 合并规则:若X→Y,X→Z,则X→YZ为F所蕴含;
  2. 伪传递规则:若X→Y,WY→Z,则XW→Z为F所蕴含;
  3. 分解规则:若X→Y,Z⊆Y,则X→Z为F所蕴含。

引理:X→A1A2…Ak成立的充分必要条件是X→Ai成立(i=1,2,…,k)。

二、Armstrong公理系统的证明

  1. A1自反律:若Y X U,则X→Y为F所蕴含
    证明1
    设Y⊆X⊆U。
    对R<U,F>的任一关系r中的任意两个元组t,s:
    若t[X]=s[X],由于Y X,则有t[Y]=s[Y],所以X→Y成立,自反律得证。

  2. A2增广律:若X→Y为F所蕴含,且Z U,则XZ→YZ为F所蕴含
    证明2
    设X→Y为F所蕴含,且Z⊆U。
    对R<U,F>的任一关系r中的任意两个元组t,s:
    若t[XZ]=s[XZ],由于X ⊆XZ,Z⊆ XZ,根据自反律,则有t[X]=s[X]和t[Z]=s[Z];
    由于X→Y,于是t[Y]=s[Y],所以t[YZ]=s[YZ];所以XZ→YZ成立,增广律得证。

  3. A3传递律:若X→Y,Y→Z为F所蕴含,则X→Z为F所蕴含
    证明3
    设X→Y及Y→Z为F所蕴含。
    对R<U,F>的任一关系r中的任意两个元组t,s:
    若t[X]=s[X],由于X→Y,有t[Y]=s[Y];
    再由于Y→Z,有t[Z]=s[Z],所以X→Z为F所蕴含,传递律得证。

  4. 合并规则:若X→Y,X→Z,则X→YZ为F所蕴含
    证明4
    因X→Y ,所以X→XY (增广律 XX→XY即X→XY)
    因X→Z ,所以XY→YZ (增广律)
    因X→XY,XY→YZ
    故X→YZ (传递律)

  5. 伪传递规则:若X→Y,WY→Z,则XW→Z为F所蕴含
    证明5
    因X→Y ,所以WX→WY (增广律)
    因WY→Z ,所以XW→Z (传递律)

  6. 分解规则:若X→Y,Z∈Y,则X→Z为F所蕴含
    证明6
    因Z∈Y  所以Y→Z (自反律)
    因X→Y 所以X→Z (传递律)

闭包及其计算

  • 定义1:设F是关系模型R的一个函数依赖集,X,Y是R的属性子集,如果从F中的函数依赖能够推出X→Y,则称F[1]X→Y。
  • 定义2:被F逻辑蕴涵的函数依赖的全体构成的集合,称为F的闭包,记作F+。
  • 定义3:设F是属性集U上的一组函数依赖,则属性集X关于F的闭包X+F定义为X+F={A|A∈U且X→A可由F经Armstrong公理导出},即X+F={A|X→A∈F+}。
  • 定理1:设关系模型R(U),F为其函数依赖集,X,Y为U的真子集,则从F推出X→Y的充要条件是Y是X+F的真子集。
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/lishanleilixin/article/details/89961833

智能推荐

从本地或者网络读取图片,并转换为Bitmap图片_java 读取网页图像到bitmap-程序员宅基地

文章浏览阅读6.6k次。在做android项目时,我们经常需要从本地或者网络读取图片,并转换为Bitmap图片,以便使用,下面是读取本地图片并转换的方法:Java代码 /** * 得到本地或者网络上的bitmap url - 网络或者本地图片的绝对路径,比如: * * A.网络路径: url="http://blog.foreverlov_java 读取网页图像到bitmap

计算机组成原理|多功能ALU设计实验_设计一个具有8种运算功能的32位alu实验总结-程序员宅基地

文章浏览阅读9.8k次,点赞7次,收藏118次。多功能ALU设计实验一、实验目的与要求实验目的:(1)学习多功能ALU的工作原理,掌握运算器的设计方法(2)掌握运用Verilog HDL 进行行为描述与建模的技巧和方法实验要求:本实验要求设计一个具有8种运算功能的32位ALU,并能够产生运算结果的标志:结果为零标志ZF(Zero Flag)、溢出标志OF(Overflow Flag)。ALU通过3根控制线ALU_OP[2:0]..._设计一个具有8种运算功能的32位alu实验总结

iOS开发进阶之列表加载图片-程序员宅基地

文章浏览阅读484次,点赞10次,收藏5次。列表加载图片通常使用UITableView或UICollectionView,由于列表中内容数量不确定并且对于图片质量要求也不确定,所以对于图片加载的优化是很有必要的。

29、基于51单片机智能消防灭火小车 寻光自动红外壁障车设计_灭火小车设计方案-程序员宅基地

文章浏览阅读1k次,点赞2次,收藏16次。智能作为现代的新发明,是以后的发展方向,他可以按照预先设定的模式在一个环境里自动的运作,不需要人为的管理,可应用于科学勘探等等的用途。智能小车就是其中的一个体现,本次设计的多功能智能灭火避障小车,以STC89C52单片机作为微控制器,设计出一种可以寻找火源(火源以蜡烛模拟)和自动避开障碍物的小车。通过光敏晶体管传感器检测火源信号当检测到火源,小车自动调整姿态,对准火源。灭火电机启动将蜡烛吹灭实现模拟灭火。通过红外光电开关感应控制小车避障行驶。工作状态实时显示在1602液晶上。_灭火小车设计方案

Ubuntu虚拟机总是死机,然后重启就进不去打不开了怎么办_ubuntu卡死之后重启,打不开了-程序员宅基地

文章浏览阅读4.6k次。从网上搜到的方法都解决不了我的问题,分享一点我自己的实在的解决经验:养成保存快照的习惯,比什么方法都靠谱。 即打开VMWare->虚拟机->快照->拍摄快照,简单填写一下你现在做到的程度,然后点击拍摄快照,存一下,养成习惯,每做出些什么东西了,就存一个快照,哪天莫名其妙又死机了,开机又黑屏进不去了,直接用快照恢复到最近的进度继续做就好。..._ubuntu卡死之后重启,打不开了

随便推点

Snipaste的使用_snipaste使用-程序员宅基地

文章浏览阅读7.3k次,点赞5次,收藏11次。Snipaste的使用_snipaste使用

使用python下载加密的流媒体m3u8视频文件,获取电影资源-程序员宅基地

文章浏览阅读273次,点赞3次,收藏8次。Python崛起并且风靡,因为优点多、应用领域广、被大牛们认可。学习 Python 门槛很低,但它的晋级路线很多,通过它你能进入机器学习、数据挖掘、大数据,CS等更加高级的领域。Python可以做网络应用,可以做科学计算,数据分析,可以做网络爬虫,可以做机器学习、自然语言处理、可以写游戏、可以做桌面应用…Python可以做的很多,你需要学好基础,再选择明确的方向。这里给大家分享一份全套的 Python 学习资料,给那些想学习 Python 的小伙伴们一点帮助!

在Qt中使用CreateProcess打开命令行并执行命令_qt.createqprocess()-程序员宅基地

文章浏览阅读351次。在Qt应用程序中,执行命令行命令并获取输出结果可以使用QProcess类。现在,我们可以在Qt应用程序中调用这个函数来执行命令行命令并获取输出结果。现在,我们可以在Qt应用程序中调用这个函数来执行命令行命令并获取输出结果。在上面的示例中,我们将命令设置为"dir",这将列出当前目录的内容。在上面的示例中,我们将命令设置为"dir",这将列出当前目录的内容。这样,当我们点击按钮时,程序将执行命令并将输出结果显示在文本编辑器中。这样,当我们点击按钮时,程序将执行命令并将输出结果显示在文本编辑器中。_qt.createqprocess()

java logutil_Java日志组件1---Jdk自带Logger(java.util.logging.Logger)-程序员宅基地

文章浏览阅读216次。最近在看日志的一些东西,发现利用JDK自带的log也可以简单的实现日志的输出,将日志写入文件的过程记录如下:1、新建LogUtil.Java(里面写了几个静态方法,为log设置等级、添加log控制台handler、添加log文件输出handler)packagecn.darkranger.log.logger;importjava.io.IOException;importjava.text.S..._logutil.java

此时不应有 \scala\bin\..\lib\jline-2.14.5.jar_c:\users\dell>scala 此时不应有 \scala\bin\..\lib\jline--程序员宅基地

文章浏览阅读221次。scala安装时,此时不应有 \scala\bin…\lib\jline-2.14.5.jar那是因为安装Scala时,默认安装到Program Files (x86)或者Program Files下,但是这俩个文件夹命名存在空格,这是从新安装,选择没有空格存在的文件夹下面即可。谢谢..._c:\users\dell>scala 此时不应有 \scala\bin\..\lib\jline-2.14.5.jar

本地搭建docker仓库的详细步骤_本地安装docker-程序员宅基地

文章浏览阅读1.7k次。在本地创建一个用于存储Docker镜像的目录,比如 /data/docker-registry。如果需要加速拉取公共镜像,可以配置阿里云或DaoCloud等国内提供的Docker镜像加速器。如果需要在其他机器上访问该私有仓库,则需要配置证书。使用docker tag将本地构建好的镜像打标签,并推送到私有仓库中。在官网下载Docker安装包进行安装,具体操作方式可以参考官方文档。至此,本地Docker仓库搭建完成。配置客户端访问证书(可选)拉取Registry镜像。启动Registry容器。_本地安装docker