《关系数据中函数依赖检测方法》由会员分享，可在线阅读，更多相关《关系数据中函数依赖检测方法（20页珍藏版）》请在金锄头文库上搜索。
1、关系数据中函数依赖检测方法 钟评 李战怀 陈群 西北工业大学计算机学院 摘 要： 在数据质量研究中函数依赖被广泛用于关系数据不一致性的修复.然而, 不一致修复问题面临的一个主要挑战是如何从包含有错误的关系数据中自动发现有效的函数依赖 (Functional Dependence, FD) .目前基于统计度量置信度的 FD 自动发现方法经常找出大量近似成立但无效的 FD.如果直接利用这些 FD 修复数据, 会产生更多错误.针对该问题, 文中提出了一种基于数据语义分析的函数依赖检测方法.该方法通过条件概率来分析属性值和元组的数据置信度, 进而计算函数依赖成立的置信度.文中同时提出了利用关系数据构建
2、马尔科夫毯贝叶斯网络用以计算数据置信度的方法.最后文中通过实验在模拟数据和真实数据上验证了基于数据语义的置信度计算方法在自动检测中的精确度优于基于统计的计算方法, 并且在交互式检测应用场景中数据语义的置信度所需用户工作量少于基于统计的方法.关键词： 数据质量; 函数依赖; 数据置信度; 条件概率; 作者简介：钟评, 男, 1985 年生, 博士研究生, 中国计算机学会 (CCF) 会员, 主要研究方向为数据管理.E-mail:.作者简介：李战怀, 男, 1961 年生, 博士, 教授, 主要研究领域为数据库理论与技术.作者简介：陈群, 男, 1976 年生, 博士, 教授, 主要研究领域为云计
3、算, 图数据管理.收稿日期：2015-11-20基金：国家“九七三”重点基础研究发展规划项目基金 (2012CB316203) A Functional Dependencies Checking Method in Relational DataZHONG Ping LI Zhan-Huai CHEN Qun Department of Computer Science, Northwestern Polytechnical University; Abstract： In data quality research, Functional Dependencies (FDs) have b
4、een widely used to repair inconsistent relational data.However, the main challenge of repairing inconsistent data is how to discover valid functional dependencies from errorous relational data.The existing FD discovery methods, which are based on statistical confidence measurement, usually find many
5、 approximately correct but actually invalid FDs.Directly applying these discovered FDs to repair inconsistent relational data may introduce more data errors.To address this issue, we propose a novel approach for FD confidence measurement based on data semantics analysis.It first uses conditional pro
6、babilities to measure confidence of an attribute value, and then aggregate them for estimating the confidence level of a given FD.We also provide an efficient method to construct Markov blanket Bayesian networks for every relational data attribute, and then use Markov blanket Bayesian networks to co
7、mpute conditional probabilities.Our experimental study on both synthetic and real-world data shows that the proposed approach achieves considerably higher accuracy than the statistics-based approach.Furthermore, we designed an interactive application scenario that each iteration consults user on ver
8、ifying the FDs with highest confidence.Our experiment results also show our approach requires fewer manual works than statistics-based approach in interactive application scenario.Keyword： data quality; functional dependency; data confidence; conditional probability; Received： 2015-11-201 引言当前数据不一致是
9、关系数据中普遍存在的问题1.从关系数据中发现函数依赖 (Functional Dependence, FD) , 再通过删除或修改不一致数据使其满足给定函数依赖, 是当前不一致性修复的常用方法.然而, 在当前不一致性修复中, FD 自动发现算法得到的近似成立 FD 不一定是真实成立的.在给定数据和 FD 集都含有错误的情况下, 如果数据违反了 FD, 则有两种可能原因: (1) FD 成立, 数据违反函数依赖需要修复; (2) FD 本身不成立, 数据不需要修复.本文主要研究在数据含有错误的情况下 FD 的检测问题.以表 1 为例, 假设表 1 中存在两个近似成立 FD, 记为 1与 2, 分
10、别有其中数据元组 t1不满足函数依赖 1, 但是通过实际验证可以发现, t 1虽然City (城市名) , County (郡名) 属性与 t3, t4, t5, t6取值相同, 但是实际中却是同名的不同城市, 因此该 FD 在实际语义中不成立.与 1相比, 对违反 2的元组 t9验证可知, t 9中 County 属性值现实中确实是错误应当修改, 2成立.由此可见, FD 检测通常需要涉及到关系数据在现实世界中的语义.虽然现实世界中的语义信息无法完全和精确获取, 但本文通过在给定的关系数据中寻找能够反映现实世界语义的信息, 即数据语义作为解决当前问题依据.目前, 仅有部分不一致性修复研究考虑
11、了 FD 不成立的情况2-4, 针对关系数据的 FD 自动挖掘仍主要采用基于统计的置信度5计算方法.该方法假定数据中错误仅占很小一部分, 因此 FD 中不一致数据越少, 其成立的可能性越大.然而, 由于该方法没有考虑数据语义, 除包含真实成立的 FD 以外, 检测结果通常也会包含很多无效的 FD, 因此总体的检测精确度仍有可能很低.如第 6 节图 4 (e) (h) 实验所示, 在真实数据 hospital 的精确度实验中置信度前 20%的近似 FD中真实成立的 FD 不到 30%.本文贡献如下: (1) 针对关系数据提出了一种基于数据语义分析的 FD 检测方法.该方法通过条件概率定义属性值和
12、元组的数据置信度, 提出相应的 FD 置信度计算方法; (2) 提出了构建并使用马尔科夫毯贝叶斯网络来计算数据置信度的方法; (3) 通过在模拟数据和真实数据集上的实验, 验证了基于数据语义的置信度计算方法在自动检测中精确度高于统计置信度方法, 并且在交互式检测应用场景中数据语义的置信度所需用户工作量少于基于统计的方法.本文第 2 节为相关工作;第 3 节概述 FD 概念以及 FD 检测问题;第 4 节介绍数据置信度和 FD 数据语义分析置信度的定义;第 5 节介绍使用数据构建马尔科夫毯贝叶斯网络用以计算数据置信度的方法;第 6 节通过实验验证该方法对函数依赖的检测效果;第 7 节为结论.2
13、相关工作目前, 关系数据中不一致性的修复主要通过函数依赖实现.文献对不一致性修复进行了综述性介绍.文献首先提出了直接修复数据值的代价修复模型.该模型通过寻找一个满足给定FD 集并且修复代价最小的修复方案来修复数据.文献对 FD 在语义上扩展提出了条件函数依赖 (Conditional Functional Dependence, CFD) , CFD 可以看做是一种局部的 FD, 文献提出了基于代价修复模型使用 FD 和 CFD 共同修复数据的方法.文献对代价模型修复算法进行优化, 提出了近似最优修复的方法.文献提出使用采样的方法对海量数据进行修复.此外, 文献分别提出了不同于 FD 和CFD
14、 的其他数据修复方法.关系数据不一致性修复首先需要自动发现数据中的 FD.文献介绍了 FD 自动发现研究现状, 文献等分别提出了从数据中发现最小 FD 集的算法.文献提出的 TANE算法使用分层搜索策略, 将 FD 搜索空间按照 FD 中属性数分层并逐层搜索, 同时在搜索过程中对搜索空间剪枝.并证明该方法对数据量有良好扩展性.文献提出算法 FastFDs 通过计算各数据元组的不一致集来发现 FD 集, 该方法对数据中属性数量有良好扩展, 但复杂度是数据量的平方.文献将 FD 自动发现算法扩展到 CFD, 提出了分别基于 TANE 算法和 FastFDs 算法的 CFD 发现算法 CTANE 和
15、CFDMiner.文献提出一种深度优先的发现算法, 该方法能够用于数据量较大条件下的发现.文献实验评估了当前多种发现算法的效率.当前数据修复流程主要是首先通过上述文献17-19中函数依赖发现算法发现数据中成立或近似成立的 FD 或 CFD 等规则.再使用文献方法对不满足规则的数据进行修复.但这样的方法面临一个问题是 FD 或 CFD 发现方法得到的规则不是语义上成立的, 无法直接应用于数据修复.当前衡量规则是否成立主要采用文献基于统计的置信度的方法, 置信度是近似函数依赖15 (Approximate Functional Dependence, AFD) 中使用的概念.该方法假定数据中错误仅
16、占很小一部分, 则 FD 中不一致数据越少, 其成立的可能性越大.该方法发现的近似成立 FD 中通常含有大量无效的 FD, 需要进一步的人工判定.文献分析了 FD, CFD与关联规则 (Association Rale, AR) 之间的层级关系, 并指出 AR 发现算法可适用于所有依赖发现问题.由于近似成立的 FD 不一定在语义上真实成立, 直接应用其对数据修复会引入更多错误.文献2-3研究了给定 FD 集不完全成立条件下的修复方法, 同时考虑FD 和数据的修复代价, 但研究局限于修复代价的优化问题上.文献提出的增量式修复方法通过人为定义 FD 的统计特征作为分类特征, 通过人工标注的函数依赖作为训练集进行增量式的有监督学习和修复, 再检测其他 FD 是否成立并进行数据修复.该方法特征选取有主观性, 忽略了不同 FD 可能包含的不同语义.而且, 该方式是有监督学习方法, 需要人工进行样本标注.本文针对上述检测 FD 是否成立的问题进行了研究, 提出了一种自动检测 F
