求闭包_牛客博客

上周刚考完数据库，当时就想着要把计算题题型整理一下，当时复习花了两天的时间，把题目按照题型归了一下类，看看别人的解析，加上自己的思考，整理了一套自己的做题方法，趁着还有记忆，整理一下，以便以后要用到。

先讲闭包。这个是求其他的前提。

例：关系模式R（U，F），其中U={A，B，C，D，E，I}，F={A→D，AB→E，BI→E，CD→I，E→C}，计算（AE）⁺。

解：

第一步：令X={AE}，X^（0）=AE。

第二步：求X^（¹^）。逐一扫描F集合中各个函数依赖，在F中找出左边是AE子集的函数依赖，其结果是：A→D，E→C。这是，F中这两个函数依赖要打上标记(我通常是打上√，表示已经用过，后面不能用了)。于是X^（¹^）=AE∪DC=ACDE；

第三步：判断X^（¹^）是否等于 X^（⁰^）以及 X^（¹^）是否等于 U。

在这里，X^（¹^）≠ X^（⁰^），且X^（¹^）≠ U，所以在F中继续找出左边是ACDE子集的函数依赖，其结果是：CD→I。同样打上标记。于是X^（²^）=ACDE∪I=ACDEI。(这里有一个注意点，∪右边的元素只写左边没有的)

继续判断，虽然X^（²^）≠ X^（¹^），但在F中未用过的函数依赖的左边属性已没有X^（²^）的子集，所以不必再计算下去，即（AE）⁺=ACDEI。

这里总结一下解题套路：

第一步：X^（0）=X。

第二步：求X^（¹^）。就是在F中找，左边是X（0）的元素子集的函数依赖，打上标记√。

第三步：判断X^（¹^）是否等于 X^（⁰^）以及 X^（¹^）是否等于 U。

这里有四种情况：

第一种：X^（ⁱ^）= X^（^i-1^），说明已经找到闭包。

第二种：X^（ⁱ^）≠ X^（^i-1^）但是X^（ⁱ^）= U，说明已经找到闭包。

第三种：都不相等，但是在F中未用过的函数依赖的左边属性已没有X^（ⁱ^）的子集，所以不必再计算下去，已经找到闭包。

第四种：都不相等，在F中未用过的函数依赖的左边属性还有X^（ⁱ^）的子集，重复执行。