关系数据库中的属性约简.pdfVIP

计算机科学2002V01．29No．8 关系数据库中的属性约简 Attribute ReductioninRelationalDatadase 李晓瑞刘刚张小平张红云马垣 (鞍山钢铁学院计算机科学与工程学院 鞍山114002) This Abstract extendsthe of{unction and thatitisrelation paper concept dependencyproves with in some KDD．Wehave avalid aboutattribute important concepts complete gotten algorithm in reductionKDD it． by using Attribute Keywords reduction，Relationaldatabase，KDD 从E．F．Codd的一系列论文开始，关系数据库 计算属性约简目前已有许多方法，例如， 的理论研究已有三十多年的历史了。虽然近年来备 Pawlak教授本人给出的逐个将属性删除，逐个进行 受人们关注的从数据库发现知识(KDD)的很多课测试的计算方法cu，利用差别矩阵的计算方法Cz]，利 题都是从关系数据库中发现知识的，但由于两者的 用信息熵以及互信息的计算方法[6J]，增量式算 出发点不完全相同，所以关系数据库的许多经典理 法【8]，二进制可辨矩阵的变换算法Do]，利用属性频 论，例如函数依赖、多值依赖、连接依赖、元组产生依 率函数的算法[1¨，以及一些不完备的多项式算 赖、等值产生依赖、q无回路、B无回路等，用于知识 法[3’4]。其中文[1]中的算法是最原始的算法，由于要 发现课题的还不太多。显然将关系数据库的经典理 逐个删除属性或属性集合，逐个进行测试，工作量太 论加以推广，使之能更有效地应用于知识发现领域， 大，所以目前已不为人们所用。文[2]中的方法已证 将是十分有意义的。这样既能给知识发现领域增加 明不是多项式的[93，而文[3，4，6～8，10，11]中的算 新的思路与方法，又能丰富关系数据库理论自身。本 法都是不完备的，正如文[11]中所说：“如何给出最 文想对函数依赖进行推广并将其用于知识约简，得 小约的完备算法仍是一个未解决的问题”。本文将借 到一个既是有效完备的又是多项式次数的全新算 助将关系数据库中的函数依赖概念的推广这个有力 法。 武器，来最终彻底解决这个问题。 1．知识约简及其现状 2。函数依赖的推广 知识约简是从数据库发现知识领域中的重要工 为了使关系数据库的理论能更好地用于知识发 作。可用Rough集理论逐步定义如下n](采用关系 现领域，我们将函数依赖做如下的推广 数据库的术语)： 定义1 设R是一个关系模式，r是R上的关 定义0 设尺是一个关系模式，，-是R上的关 系，X，y量尺，记号口：X—y表示一个函数依赖，其 系，x垡尺，对r中的每个元组“，令■]x一{DI口∈r^ 中仃为其名称，x—y为其实体。用口(r)表示该函数 秽[x]=“X]}，令r／X={[“]xI铭∈r}，显然r／x是依赖对关系