基于相关性分析的不完整数据函数依赖挖掘方法

尹诗宁 张安珍 夏秀峰

摘 要：函数依赖（FD）挖掘方法通常专注于发现所有满足函数依赖语法特征的结果，在数据不完整的情况下常导致大量成立但无意义的FD。针对挖掘无效FD的问题，提出基于相关性分析的不完整数据FD挖掘方法。利用概率图模型构建具有缺失值属性的概率分布，通过相关性分析捕捉属性之间的关联关系，避免枚举所有可能性，以挖掘具有统计学意义的FD。实验结果表明，该方法可以更准确地定位到有意义的FD，与最先进的FD发现方法相比，F1分数平均提高1.5倍。

关键词：函数依赖；相关性分析；不完整数据

中图分类号：TP301   文献标志码：A    文章编号：1001-3695（2024）05-013-1368-06

doi： 10.19734/j.issn.1001-3695.2023.09.0451

Correlation analysis for discovering functional dependencies in incomplete data

Abstract：Function dependency （FD） discovery methods typically focus on identifying all results that satisfy the syntax features of function dependencies. In the case of incomplete data， it often results in a significant number of established but meaningless FD. In response to the issue of discovering invalid FD， this paper proposed a method for incomplete data FD discovery based on correlation analysis. It constructed a probability distribution with attributes containing missing values using a probability graph model， captured the relationships between attributes through correlation analysis， avoided enumerating all possibili-ties， to discover FD with statistical significance. The experimental results show that the proposed method can more accurately pinpoint meaningful FD， more accurately， with an average F1-score improvement of 1.5 times compared to state-of-the-art FD discovery methods.

Key words：functional dependency; correlation analysis; incomplete data

0 引言

函数依赖（functional dependency，FD）是数据库管理系统中的一个关键概念，用于描述数据库表中字段之间的关系，在许多领域有着广泛应用，如数据库设计、数据清洗、特征选择等。近年来，研究人员围绕FD挖掘展开了大量研究工作，这些研究工作通常假设数据是完整的。然而，真实应用中的数据通常存在大量的缺失值，如何在不完整数据中挖掘出正确的FD是一个亟待解决的问题。

不难发现，不完整数据上的FD挖掘比完整数据上的FD挖掘更具挑战性。一方面，若直接使用现有的完整数据上的FD挖掘方法在不完整数据上进行挖掘，将导致结果中出现大量过拟合的FD规则。这是由于现有的FD挖掘方法通常根据FD的语法特征进行挖掘，导致所有满足左部取值相同时右部取值也相同的规则出现在结果集中。例如，在只有几十个属性的数据集上，会找出成百上千条FD［1］，这些FD中大部分没有任何统计学意义。另一方面，现有的不完整数据上，FD挖掘方法［2］通常将所有满足近似度阈值的FD规则挖掘出来，然后再根据缺失值的概率分布验证每个FD规则的真伪。然而，为了保证在不完整数据上所有真实FD规则都被挖掘出来，需要设置一个很大的近似度阈值，最坏情况下，阈值等于缺失的元组数量，此时，结果中将出现大量假的FD规则。

为此，本文提出基于相关性分析的不完整数据FD挖掘方法，利用FD的语义特征指导挖掘过程，在处理缺失值的同时，挖掘出具有统计学意义的函数依赖。具体过程如下：首先，采用概率图模型建立各个属性的概率分布，给出缺失值填充方案正确性概率的计算模型。其次，利用相关性分析捕捉每对属性之间的关联关系，保留具有强关联性的属性，并组合中度关联的属性形成新的候选FD集合。最后，对候选FD进行细化，通过检查互补的、未经验证的依赖候选项，直到找到所有最小FD。

综上所述，本文的主要贡献如下：

a）提出了一种基于相關性分析的近似函数依赖挖掘方法，利用统计学概念快速定位具有相关性的属性，使得发现的FD结果可解释性更好。

b）建立了一种针对缺失值的概率模型，计算缺失值的取值概率，从而避免了缺失值解释的单一性可能引发的误差。

c）通过对候选FD细化，检查互补的、未经验证的依赖候选项，直到找到所有最小FD，确保输出的结果是最小且有意义的。

1 相关工作

常见的完整性约束包括函数依赖规则［3～5］、包含依赖规则［6］、顺序依赖关系［7］等，其中最常用的是函数依赖规则，得到了学术界的广泛研究。它有许多应用，如维护数据质量［8］、模式标准化［9］、修复数据不一致［10，11］等。

以TANE［12］为代表的行高效算法，使用分层搜索策略将FD的搜索空间建模为属性格。晶格从较小的属性集到较大的属性集逐级遍历，并使用剪枝技术缩减搜索空间，以发现精确和近似的FD。后续算法Fun［13］、FD-mine［14］、DFD［15］引入了不同的剪枝和格遍历策略。该类方法对数据量有良好的扩展性。

列高效算法FDep［16］、DepMiner［17］和FastFDs［18］，通过计算元组的不一致集确定FD的属性组合，以便生成两组不同的属性子集，从这些属性子集派生候选FD。这类方法对属性数量有良好扩展，但复杂度是数据量的平方。

混合算法［19，20］在行高效算法和列高效算法之间切换，结合前两种算法的优点，具体地说，采样后利用列高效算法得到非函数依赖，使用行高效部分进行验证，在元组和属性数量都增加的情况下有更好的伸缩性，但它不适用于近似函数依赖关系。

CORDS考虑相关性以获得软FD［21］，只研究LHS上具有单一属性的FD，提出了一种基于示例的方法，该方法使用系统编目检索列中不同值的数量。然而，CORDS中考虑的共现度量发现了边际依赖，而不是对应于真正FD的条件独立。

上述方法都是基于共现频率的，当左部属性多时容易出现过拟合的情况。为此提出了结构学习方法FDX［22］，依赖于稀疏回归，对样本进行結构学习，通过从原始数据获取采样的元组对的值差异。假设属性之间有一个全局优先级，通过逆协方差矩阵得到FD。

当数据中有缺失值时，现有FD挖掘方法通常采用以下三种策略。第一种策略是忽略不完整的元组［23］，直接在完整元组集合上挖掘FD规则。然而，这种方法存在一个严重问题，结果中可能包含大量虚假的FD规则。这些虚假规则在完整元组集合上成立，但在对应的不完整元组集合上不成立。第二种策略是根据给定的缺失值语义来挖掘FD规则［24］。常见的缺失值语义有两种：缺失值取值都相同（NULL-EQ）和缺失值取值都不同（NULL-NOT-EQ）。然而，真实的缺失值取值通常更加复杂，可能部分相同、部分不同，这导致在采用NULL-EQ语义时可能会挖掘出大量虚假的FD规则，而采用NULL-NOT-EQ语义时可能会错过真正的FD规则。第三种策略是首先填充缺失值，然后在填充后的完整数据上进行FD挖掘。然而，这种方法的准确性严重依赖于缺失值填充方法的准确性，不准确的填充可能导致错误的FD规则。

为了应对这些问题，Berti-quille等人［2］提出了一种方法，利用现有的近似FD挖掘方法在不完整数据上找出所有可能的近似FD规则，然后计算每个规则的概率，只保留概率较高的FD规则。然而，这种方法需要挖掘出所有近似度的FD规则才能保证真实FD规则不会被遗漏，而且后续的概率验证阶段代价非常大。之前关于FD发现的工作并没有试图分析缺失值数据上有意义的函数依赖，找出大量近似成立但无效的FD。

现有的解决方案没有充分利用属性之间的关联关系，而是系统地枚举有可能的FD规则并逐一验证，导致候选FD挖掘结果效率低且没有找到有意义的依赖关系。本文引入了相关性分析的方法提高函数依赖挖掘的准确性，大大减少候选FD的规模，有效避免了属性数量过多导致的过拟合现象。通过对缺失值建立概率模型，规避了仅考虑缺失值解释的单一性可能带来的误差问题。

2 预备知识及问题定义

定义1 函数依赖（functional dependency，FD）。给定属性集D上的关系模式R。R上的一个FD表示为X→Y，其中XR，Y∈R，表示X中的所有元组唯一地决定Y中的值。更正式地说，设ti［Y］是属性Y中的元组ti的值；t，t′∈r，t［X］=t′［X］t［Y］=t′［Y］，称X为FD的左部（LHS），Y为FD的右部（RHS）。

例1 以表1为例，表1为部分美国医院信息，主要包括医院编号、名称所在地、代码等，假设有FD：ProviderNumber→HospitalName，表示数据集中所有ProviderNumber取值相同的元组，对应属性HospitalName的取值一定相同。如果不相等，则该数据违反函数依赖规则。

定义2 空语义。将数据集中的缺失值表示为NULL值，用⊥表示。如前所述，在处理NULL值时，传统上提出了两种语义：第一种解释，NULL-EQ，表示为（⊥=⊥），认为所有缺失值都是相同的；第二种语义，NULL-NOT-EQ，表示（⊥≠⊥），认为每个缺失值都是不同的。这两种语义有不同的动机，并导致发现不同的FD集合。

定义3 卡方检验。卡方检验是一种用于检验两个分类变量之间是否存在显著关联性的统计方法，基于观察值与期望值之间的差异来判断两个变量是否独立。卡方检验的原假设是两个变量是独立的，备择假设是两个变量之间存在关联。

定义4 Cramers V系数。Cramers V是用于衡量两个分类变量之间关联性强度的指标。它是从卡方统计量中派生出来的，用于标准化卡方统计量，以便在不同的表格尺寸和自由度下进行比较。Cramers V的取值在0～1，值越接近1，表示两个变量之间的关联性越强。Cramers V的计算公式为

其中：χ2是卡方统计量；n是样本总数；k是第一个分类变量的类别数；r是第二个分类变量的类别数。卡方检验用于检验分类变量之间的关联性是否显著，而Cramers V则是一种衡量分类变量关联性强度的标准化指标。

3 不完整数据上近似函数依赖挖掘方法

针对不完整数据的函数依赖挖掘问题，本文提出基于相关性分析的近似函数依赖挖掘框架，旨在提高不完整近似函数依赖挖掘的效率和可解释性，缓解过拟合问题。

3.1 不完整数据上近似函数依赖挖掘框架

本文提出的不完整数据上近似函数依赖挖掘方法包括建立概率模型、相关性分析和候选FD规则验证与细化三个步骤，如图1所示。输入为带有缺失值的数据集D和错误阈值，输出为最小且非平凡的函数依赖集合。

a）建立概率模型：首先，在给定的不完整数据集上训练贝叶斯网，学习属性之间的相关关系以及条件概率分布；其次，建模缺失值填充方案正确性概率为P（A|E），即给定完整部分属性取值时，有缺失值属性取值的概率；最后，利用贝叶斯推理预测不完整数据的所有取值概率。

b）相关性分析：利用上一步输出对属性之间进行相关性分析，对相互独立的属性进行剪枝，减小候选FD的规模，剩下的属性进行逐层搜索，从底层单个节点开始，快速定位候选的FD。

c）候选FD规则验证与细化：如果LHS和RHS之间有强相关性，则认为这样的节点是最小的决定集。对于其他的节点进行组合，进一步验证相关性。如果不满足阈值，就继续添加属性细化，直到满足阈值或者无法继续添加属性，得到完整的FD集合。

3.2 统计学习与推理

本节给出了缺失值概率模型和概率推理方法，目的是根据缺失值取值的概率分布分析属性之间的相关性。

为了推断缺失值的概率，使用了一个广泛使用的概率图模型——贝叶斯网络，它提供了一种简洁地描述属性的概率分布方法。根据贝叶斯网络中的局部马尔可夫性质，每个变量在其父变量的条件下都与非子变量无关。因此，影响一个变量取值分布的变量都在马尔可夫毯中，通过观察有缺失值的属性A的马尔可夫毯上的属性，可以推断出属性A的可能取值范围，其他属性对属性A的取值不会产生直接影響。将有缺失值的属性A作为查询属性，其他属性E=attr（R）＼A为证据属性集，通过证据属性集预测查询属性各个取值的概率。

对于有缺失值属性A的元组t，有t［E］=t［E1，E2，…，EL］和t［A］。设SE=DOM（E1）×DOM（E2）×…×DOM（EL）表示t的证据属性的空间，SA=DOM（A）表示t的查询属性的空间。假设根据SA×SE上的概率分布P（A，E）随机生成元组。将t的缺失值概率建模为给定证据属性值的查询属性值的条件概率，即P（A=t［A］|E=t［E］）（简称P（t［A］|t［E］）），根据贝叶斯定理可得

给定总体上的贝叶斯网络，网络中所有变量的联合分布都可以因式分解为以其父变量为条件的单个密度函数的乘积。式（2）中的分子P（t［A］，t［E］），可以用式（3）来近似：

其中：父节点（Ej）表示Ej的父节点集。注意，由于所有属性的值都是已知的，所以P（t［A］|parent（A））和P（t［Ej］|parent（Ej））是贝叶斯网络中条件概率表（CPT）中的常量。当涉及式（2）中的分母P（t［E］）时，推理变得有点复杂。注意，P（t［E］）是证据属性的边际分布，可以通过边际化查询属性上的联合分布来计算，如式（4）所示。

P（t［E］）=P（A，t［E］）（4）

当同一元组t上存在多个缺失值的情况，每个查询属性Ai的分布通常不独立于其他属性。事实上，Ai的分布取决于其马尔可夫毯中属性的联合分布。因此，提出在Ai的马尔可夫毯的基础上对Ai的域进行剪枝。具体地说，使用MB（A）表示A的马尔可夫毯，且MB（A）=MB（A1）∪MB（A2）∪…∪MB（Ak）是所有查询变量的马尔可夫毯的交集。然后使用MB（A）中的证据属性对A的域剪枝，即考虑与E∪MB（A）的值在数据集中同时出现的查询属性值。

算法1 不完整数据概率推理算法

在算法1中，输入为关系模式R上的不完整数据集D，输出为带有概率的完整数据集D′。首先在不完整数据集D上训练贝叶斯网络，得到属性之间的关系和概率表，并初始化查询属性集合Q、证据属性集合E以及带概率的完整数据集D′（第1、2行），判断t［Ai］是否为空，并将空值属性添加到查询属性Q中（第4、5行），其次查找Q中所有属性的马尔可夫毯属性使其相交，得到共同马尔可夫毯属性MB（Q），并筛选出t［Ai］的所有可能填充的值V（第6～9行），然后将t［E∩MB（Q）］在D中至少出现一次的查询属性值添加到q_set，并利用式（3）计算P（t［E］）（第10～14行），遍历V中属性值利用式（2）计算P（t［Q］，t［E］）（第15～17行），最后计算P［ti］，将其和ti添加到D′中（第18、19行）。

3.3 相关性分析

本节介绍了一种基于卡方分布和Cramers V的方法，用于量化属性之间的相关性，卡方统计量衡量了观察值与期望值之间的偏离程度，当两个属性相互独立时，卡方值接近于零。Cramers V是一种用于衡量两个分类变量之间关联性强度的标准化指标，派生自卡方统计量，其目的是使不同表格尺寸和自由度下的卡方统计量可进行比较。Cramers V值为0～1，数值越接近1，说明两个变量之间的关联性越强。卡方检验用于验证分类变量之间的关联性是否具有显著性，而Cramers V则进一步提供了这种关联性的强度度量。

定理1 在干净数据集中，X→Y是一个FD，则Cramers V值为1。

当X和Y的频数分布集中在一个单元时，会导致偏离程度较大。定理1解释了随机变量之间的相关性可以用Cramers V来表示，因此求解属性之间的函数依赖关系等同于求解Cramers V的值，而这可以从观察到的数据样本中获取。FD发现，问题可以看作是在属性之间寻找强相关的属性，当属性之间存在强相关性时，则称它们是一个函数依赖。通过计算属性之间的关联关系，而不是直接遍历整个搜索空间，可以将函数依赖的发现问题简化为寻找属性之间的相关性。随后，进行逐层搜索，从底层开始，即单个属性节点，计算给定右部属性与其他属性的Cramers V值，并选取了大于给定阈值的属性对作为候选的函数依赖项。为了提高挖掘效率，采取了剪枝策略，即排除相互独立的属性；当Cramers V值超过给定阈值时，将这两个属性视为强相关属性，从而减小了候选函数依赖项的数量。

例2 图2表示美国医院数据集所有属性之间的相关性分析热图，当ProviderNumber和HospitalName完全独立时，总体上的分布和某个取值上的分布情况应该是相同的，当ProviderNumber和HospitalName完全相关时，也就是说， ProviderNumber的值就可以唯一地确定一个HospitalName，这就是Cramers V可能出现的最高值，也就是函数依赖关系。

3.4 候选FD规则验证与细化

本节将详细介绍对候选FD规则验证与细化的过程，其目的是找到所有最小的函数依赖集合。当左部是多个属性时，可以进行细化操作而不會引入额外的误差。为实现这一目标，该过程执行以下步骤：首先，对于关系模式R的每个属性A，寻找以A为RHS的最小AFDs。其次，计算属性A与attr（R）＼A的每个属性的Cramers V值。如果属性A与某个属性之间存在强相关性，确定该属性为FD并报告它。如果属性之间是中度相关关系，则将它们存入候选项中进行组合，直到无法从候选集中添加属性。在此过程中，不断剪枝相互独立的属性，并组合中度关联的属性，以确保找到的属性集合都具有相关性。

在分析关系模式R时，每个候选RHS属性A都需要被过滤，以确定是否有关联关系。该过滤需要计算Cramers V值，以确定每个候选左部属性是否适合作为FD的左部候选项。如果某个候选左部属性被中度关联的属性作为细化候选，则可以使用算法2来执行细化，用于生成给定关系数据集D′的下一层级的FD。逐步增加属性组合的规模，继续计算它们之间的相关性，直到满足阈值或不能继续添加属性。

算法2 候选FD规则验证与细化算法

算法2接受一个带有概率的完整数据集D′作为输入，并输出一组形式为X→Y的FD。在算法的开始，初始化一个用于存储候选依赖项的新字典结构M以及一个空集合FD，用于存储最终的FD集合（第1行）。接下来，算法遍历关系模式R中的每个属性，并针对每个属性A遍历attr（R）＼A中的属性X（第2行）。通过调用函数计算X和A属性之间的Cramers V（第6行），与上限阈值Vupper比较确保是一个FD，并将它储存在集合FD中（第7、8行），例如图2中的属性B为依赖项，因此可以将B的超集剪枝。如果计算得到的Cramers V在上限阈值Vupper和下限阈值Vlower之间，则将属性X添加到候选依赖项M中，就像图2中的属性{A，C，D}，只需要对中度关联的属性进行细化，这是潜在的最小依赖项，如果递归产生最小的函数依赖项，则会立即报告它。

对于候选依赖项进入细化部分，从候选依赖项M中选择一个没有被修剪的候选组合，向它添加M中单个属性，组成一个没有被修剪过的新候选项（第11行），在图3中细化访问的ACD是一个函数依赖项，并将它储存在集合FD中（第14～16行）。如果错误地假设ACD是一个依赖项，将ACD添加到候选项M中，并继续对ACD进行细化（第18行），直到无法从候选项中添加属性，返回最终函数依赖项FD。与遍历所有搜索空间相比，从单一属性开始，对相互独立的属性剪枝，并对于中度关联的属性进行组合，大大减少了候选FD的规模。

例3 对于表1，当Stateavg作为右部属性时，与State和 MeasureCode存在相关关系，且并非强相关性，将它们存入候选项中进行组合。通过验证，确认{State，MeasureCode}与Stateavg为强相关关系，因此State，MeasureCode→Stateavg是一个FD。继续验证所有候选项，直到满足预设阈值或无法继续添加属性。

4 实验分析

本章通过实验，评估了在不完整数据上挖掘近似函数依赖的方法，并展示了在合成数据集上的性能实验结果。具体而言，本章将深入分析算法的准确率（P）、召回率（R）以及F1分数。

4.1 实验设置

实验采用Java实现了优化方法的编写，命名为SFD，并与最先进的挖掘语义FD的方法FDX进行对比。

a）对比方法：FDX［20］是最先进的查询有意义的函数依赖，从统计学角度出发，将FD发现转换为线性结构化方程模型上的结构学习问题，在处理噪声数据集时更具有鲁棒性。参数保留其默认设置。

b）数据集：实验数据使用合成数据集，给定一个具有r属性的关系模式。考虑类别型和数值型两种常见模式的函数依赖。对于类别型的FD，首先为LHS中的每个属性分配一个域dom（X），并将RHS的域分配为dom（Y）。然后，对于每个值x∈dom（X）随机选择一个值y∈dom（Y）作为其对应的RHS值。如果LHS中有多个属性，则将它们视为一个整体，并遵循与上述相同的流程。生成的样本数量由分配给元组数量的参数t的值决定；对于数值型的FD，首先为LHS属性分别分配一个域，dom（X1）和dom（X2）。属性Y是FD的右部，使得X1+X2=Y。由于数值型函数依赖的可逆性质，X1+X2→Y、Y－X1→X2、Y－X2→X1也成立。

c）缺失值：使用Uniform和Pareto两种模式，注入从5%到30%的缺失值百分比。在Uniform模式下，将随机注入的缺失值均匀分布在属性集上；对于Pareto模式，在80%的属性中随机注入20%的缺失值，在其余20%的属性中随机注入80%的缺失值。

d）实验评价：为了评估算法对数据集检测的准确性，实验使用准确率（P）定义在所有识别的FD中正确检测到的真实FD的百分比，召回率（R）定义在所有实际FD中正确发现的真实FD的百分比；而F1分数计算为2PR/（P+R），同时考虑了准确率和召回率。F1分数可以看作是模型准确率和召回率的调和平均值，最大值为1，最小值为0。

4.2 实验分析

在本章实验中，通过改变输入数据的不同关键因素，评估了提出的不完整数据上的近似函数依赖挖掘方法和其他方法在合成数据集中挖掘FD的性能。

4.2.1 评估FD挖掘方法对元组数量的拓展性

实验评估了元组数量对方法的扩展性，生成了一组合成数据集，并比较了不同元组数量下的性能。为了确定算法在行数上的可扩展性，使用了一个包含17列，缺失率为10%的合成数据集，在具有{1000、2000、5000、10000、20000、50000、100000}不同元组数量的数据集上进行了实验，并在图4中描述了结果。SFD在处理更多元组时展现出可扩展性，随着元组数量的增加，在准确率、召回率和F1分数上呈现出更好的表现。同时，两种缺失值语义和跳过缺失元组的变化相对稳定，相比之下，FDX无法识别具有环形结构的依赖，即同一属性既出现在一个规则的左部，又出现在另一个规则的右部，导致准确率和召回率较低。

4.2.2 评估FD挖掘方法对缺失率的鲁棒性

在Uniform模式下，实验评估了缺失值的百分比对方法的影响。使用了一个包含17列，10 000行合成数据集，并随机将与参与真实函数依赖的属性对应的单元格翻转为空值，以模拟高缺失率环境。通过控制“缺失率”设置来调整翻转单元格百分比，并测量在{0.01，0.05，0.1，0.15，0.2，0.25，0.3}不同缺失率下各方法的性能表现。对比了两种缺失值语义（⊥=⊥）和（⊥≠⊥），跳过缺失值所在的行与FDX方法，实验结果如图5所示，在高缺失率的情况下，所有方法都受到影响而性能恶化。SFD始终保持相对稳定且F1分数优于其他方法；对于两种缺失值语义和跳过缺失元组，会挖掘出大量虚假的FD规则或错过真正的FD规则，导致准确率、召回率和F1分数偏低。FDX总体上仍有非常低的准确率和召回率。

4.2.3 评估FD挖掘方法对缺失值分布的影响

现实世界中缺失值的分布通常是不均匀的，使用Pareto模式注入缺失值以模拟真实世界上的缺失值分布，如图6所示。通过比较实验结果发现，与Uniform模式相同，当缺失率过高时，所有方法的准确率、召回率和F1分数都会明显降低。但提出的方法在F1分数上优于其他方法，并且在保持高召回率方面表现出色。由于FDX的列排序限制了属性之间的优先级，无法挖掘具有环形结构的FD，可能会错过一些依赖关系，导致无法完整挖掘到所有存在的函数依赖，使得准确率和召回率偏低。SFD通过基于相关性分析和概率模型的思想，更加灵活地捕捉属性之间的关联关系。

所提算法存在一些限制，其中最主要的限制是它无法发现数值型的FD。该算法专注于识别LHS和RHS之间的相关性，并且它不能进行逆向推导，找到数值型的函数依赖。然而，在实际应用中，用于数据清洗的函数依赖大多具有语义关系。未来的研究可以进一步完善算法，以更好地满足实际数据清洗的需求。

5 结束语

本文提出了一种语义FD发现方法，探讨了现有的函数依赖挖掘方法在面對缺失值和语义关系时的局限性。为了克服这些问题，本文提出了一种基于统计学的FD挖掘方法，考虑属性之间的关联性，并利用概率图模型对不完整数据进行建模，可以在不完整数据上挖掘出有意义的函数依赖规则。利用属性之间的关联关系而不是遍历所有的搜索空间来提高FD发现的准确率和召回率。测试表明，提出的方法在合成数据集上得到了高准确率和召回率。但当数据集中的缺失率较高时，存在大量缺失信息，使得通过概率建模难以准确捕捉属性之间的真实语义关系。在处理大规模真实数据集时，算法的计算开销较大。未来的研究可以致力于应对这些挑战，优化算法以适应高缺失率情况，并寻找更有效的方法来处理大规模真实数据集。

参考文献：

［1］Kruse S，Naumann F. Efficient discovery of approximate dependencies ［J］. Proceedings of the VLDB Endowment，2018，11（7）： 759-772.

［2］Berti-quille L，Harmouch H，Naumann F，et al. Discovery of genuine functional dependencies from relational data with missing values ［J］. Proceedings of the VLDB Endowment，2018，11（8）： 880-892.

［3］张安珍，司佳宇，梁天宇，等. 规则与概率相结合的不一致数据子集修复方法 ［J/OL］. 软件学报，2023. https：//doi. org/10. 13328/j.cnki.jos.006972. （Zhang Anzhen，Si Jiayu，Liang Tianyu，et al. Subset repair method combining rules and probabilities for inconsistent data ［J/OL］. Journal of Software，2023. https：//doi. org/10. 13328/j. cnki. jos. 006972.）

［4］Zheng Zheng，Zheng Longtao，Alipourlangouri M，et al. Contextual data cleaning with ontology functional dependencies ［J］. ACM Journal of Data and Information Quality，2022，14（3）： 1-26.

［5］Song Shaoxu，Gao Fei，Huang Ruihong，et al. Data dependencies extended for variety and veracity： a family tree ［J］. IEEE Trans on Knowledge and Data Engineering，2020，34（10）： 4717-4736.

［6］Kaminsky Y，Pena E H M，Naumann F. Discovering similarity inclusion dependencies ［J］. Proceedings of the ACM on Management of Data，2023，1（1）： 1-24.

［7］Schmidl S，Papenbrock T. Efficient distributed discovery of bidirectional order dependencies ［J］. The VLDB Journal，2022，31（1）： 49-74.

［8］Fan Wenfei，Geerts F. Uniform dependency language for improving data quality ［J］. IEEE Data Engineering Bulletin，2011，34（3）： 34-42.

［9］Papenbrock T，Naumann F. Data-driven schema normalization ［C］//Proc of the 20th International Conference on Extending Database Technology. 2017： 342-353.

［10］夏秀峰，劉朝辉，张安珍. 基于马尔可夫毯的近似函数依赖挖掘算法 ［J］. 沈阳航空航天大学学报，2023，40（4）： 8-18. （Xia Xiufeng，Liu Zhaohui，Zhang Anzhen. Approximate functional depen-dence discovering algorithm based on Markov blanket ［J］. Journal of Shenyang Aerospace University，2023，40（4）： 8-18.）

［11］Beskales G，Ilyas I F，Golab L. Sampling the repairs of functional dependency violations under hard constraints ［J］. Proceedings of the VLDB Endowment，2010，3（1-2）： 197-207.

［12］Huhtala Y，Krkkinen J，Porkka P，et al. TANE： an efficient algorithm for discovering functional and approximate dependencies ［J］. The Computer Journal，1999，42（2）： 100-111.

［13］Novelli N，Cicchetti R. Functional and embedded dependency infe-rence： a data mining point of view ［J］. Information Systems，2001，26（7）： 477-506.

［14］Hong Yao，Hamilton H，Butz C. FD-Mine： discovering functional dependencies in a database using equivalences ［C］// Proc of IEEE International Conference on Data Mining. Piscataway，NJ： IEEE Press，2002： 729-732.

［15］Abedjan Z，Schulze P，Naumann F.DFD： efficient functional depen-dency discovery ［C］// Proc of the 23rd ACM International Confe-rence on Information and Knowledge Management. New York： ACM Press，2014： 949-958.

［16］Flach P A，Savnik I. Database dependency discovery： a machine learning approach ［J］. AI Communications，1999，12（3）： 139-160.

［17］Lopes S，Petit J M，Lakhal L. Efficient discovery of functional depen-dencies and Armstrong relations ［C］// Proc of International Confe-rence on Extending Database Technology. Berlin： Springer，2000： 350-364.

［18］Wyss C，Giannella C，Robertson E. FastFDs： a heuristic-driven，depth-first algorithm for mining functional dependencies from relation instances extended abstract ［C］// Proc of International Conference on Data Warehousing and Knowledge Discovery. Berlin：Springer，2001： 101-110.

［19］Papenbrock T，Naumann F. A hybrid approach to functional depen-dency discovery ［C］// Proc of International Conference on Management of Data. New York： ACM Press，2016： 821-833.

［20］Wei Ziheng，Link S. Discovery and ranking of functional dependencies ［C］// Proc of the 35th IEEE International Conference on Data Engineering. Piscataway，NJ： IEEE Press，2019： 1526-153.

［21］Ilyas I F，Markl V，Haas P，et al. CORDS： automatic discovery of correlations and soft functional dependencies ［C］// Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press，2004： 647-658.

［22］Zhang Yunjia，Guo Zhihan，Rekatsinas T. A statistical perspective on discovering functional dependencies in noisy data ［C］// Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press，2020： 861-876.

［23］Badia A，Lemire D. Functional dependencies with null markers ［J］. The Computer Journal，2015，58（5）： 1160-1168.

［24］Badia A，Lemire D. On desirable semantics of functional dependencies over databases with incomplete information ［J］. Fundamenta Informaticae，2018，158（4）： 327-352.