Journal of so/ fare软件学报Vol27,No.7,Juy2016 D满足条件函数依赖集合∑则满足,从而降低了求解判定问题的难度 其次研究了数据一致性判定问题的计算复杂性和近似性证明数据一致性判定问题是NP完全的;不 存在多项式时间(2-近似算法,除非 unique game猜想为真;问题是1.3606不可多项式时间近似的,除 非P=NP,规则为3且属性为4时,问题是1.0625不可近似的; ·最后给出了一种近似比最优化的O( nlogn)时间的2近似算法,并给出了一种O(log(n)时间的(2+)-随 机近似算法 文献[43]研究了使用条件函数依赖评价数据一致性的关键问题—一最小元组删除集的计算问题证明了该 问题是NP完全的给出了基于冲突图的近似求解算法,算法的近似比为2-(1/2)2,其中,是给定的条件函数依 赖集 (2)数据时效性判定的理论和算法 数据时效性判定方法可以分为两类即,基于时间戳的时效性判定和独立于时间戳的时效性判定 基于时间戳的时效性判定要求数据集合中每个数据值具有时间戳文献145-50把数据从上一次更新到本 保质期7给定一个数据文献5把F的时效性定义为概么时效性文献15481假设数据有一个确定的 次使用的时间间隔定义为数据年龄Age,从不同角度定义了数搪 4ge()-7()>0而文献[48]则在T)PAge(V) 的条件下把数据的Age()定义为V的时效性文献[46,47]假设数据时效性随时间流逝的减弱程度可以用时效 性衰减函数/来刻画,定义数据V的时效性为ep)×g.文献[49]把数据年龄定义为数据的时效性文献[50提出 了一种基于模糊逻辑来推断时效性衰减函数的时效性判定方法 针对实际应用中时间戳常常不存在的情况,文献133研究了独立于时间戳的数据时效性判定方法 首先在数据时效性表达机制的基础上提出了数据时效性的数学模型; 然后证明了时效性判定问题是P问题,且其时间复杂性下界为2(n2) 最后给出了两种基于时效图的数据时效性判定算法:一种是针对一般时效图的On1ogn)时间算法,另 种是针对无环时效图的O(m2)时间最优化算法 文献[51]研究了相对于査询的数据时效性判定问题,建立了数据相对时效性的数学模型.针对最新值査询 和时效序列查询这两类查询,提出了查询结果的时效性判定方法,并将每类查询作为一个整体给出了数据集合 相对于每类查询的平均时效性判定方法 (3)数据完整性判定的理论和算法 文献[52]研究了数据完整性判定问题 首先给出了一种数据完整性模型,这种数据模型避免了假阳性错误,即,避免能够由函数依赖可导出的 值被误判为缺失值; ·然后,确定了数据完整性判定问题的计算复杂性证明了该问题是P问题,且其时间复杂度下界是 ·最后给出了时间复杂度为On2)的最优化判定算法并给出了一种适用于大数据的(E,-近似算法,其 时间和空间复杂性均为O(Eln(2) 文献[53]进一步扩展了这项研究结果. 文献[54]综述了早期的数据完整判定的研究工作,介绍了不同种类的数据完整度的定义和计算方法 文献[55]提出了判定地理数据完整性的计算方法文献[56给出了时间序列数据完整性判定方法文献[57, 58]给出了其他特定数据集合的数据完整性判定方法 (4)数据精确性判定的理论和算法 对于数据集合中的不精确值,其精确值难以预知于是,数据精确性判定问题是一个非常困难的问题.文献 [5960]提出了一种多模态数据集的精确性判定方法,使用均方误差这一参数衡量数据的精确性该方法把数据 集合中的数据分为3类,即可量度型、可比性型、分类型针对每类数据的特点建立了不同的精确性数学模型, 并组合这些数学模型,最终建立了数据精确性的数学模型针对精确值可知与不可知两种情况,该方法提供了不 中国科学院软件研究所htp:/ww.jos.org.cn
1610 Journal of Software 软件学报 Vol.27, No.7, July 2016 D′满足条件函数依赖集合 Σ,则满足 Σ* ,从而降低了求解判定问题的难度; • 其次,研究了数据一致性判定问题的计算复杂性和近似性,证明:数据一致性判定问题是 NP-完全的;不 存在多项式时间(2−ε)-近似算法,除非 unique game 猜想为真;问题是 1.3606 不可多项式时间近似的,除 非 P=NP;规则为 3 且属性为 4 时,问题是 1.0625 不可近似的; • 最后,给出了一种近似比最优化的 O(nlogn)时间的 2-近似算法,并给出了一种 O(log(n))时间的(2+ε)-随 机近似算法. 文献[43]研究了使用条件函数依赖评价数据一致性的关键问题——最小元组删除集的计算问题,证明了该 问题是 NP-完全的,给出了基于冲突图的近似求解算法,算法的近似比为 2−(1/2)|Σ| ,其中,Σ是给定的条件函数依 赖集. (2) 数据时效性判定的理论和算法 数据时效性判定方法可以分为两类,即,基于时间戳的时效性判定和独立于时间戳的时效性判定. 基于时间戳的时效性判定要求数据集合中每个数据值具有时间戳.文献[45−50]把数据从上一次更新到本 次使用的时间间隔定义为数据年龄 Age,从不同角度定义了数据的时效性.文献[45,48]假设数据有一个确定的 保质期 T.给定一个数据 V,文献[45]把 V 的时效性定义为概率 Pr[Age(V)−T(V)>0],而文献[48]则在 T(V)>Age(V) 的条件下把数据的 Age(V)定义为 V 的时效性.文献[46,47]假设数据时效性随时间流逝的减弱程度可以用时效 性衰减函数 f 来刻画,定义数据 V 的时效性为 e−f(V)×Age(V) .文献[49]把数据年龄定义为数据的时效性.文献[50]提出 了一种基于模糊逻辑来推断时效性衰减函数的时效性判定方法. 针对实际应用中时间戳常常不存在的情况,文献[33]研究了独立于时间戳的数据时效性判定方法. • 首先,在数据时效性表达机制的基础上提出了数据时效性的数学模型; • 然后,证明了时效性判定问题是 P 问题,且其时间复杂性下界为Ω(n2 ); • 最后,给出了两种基于时效图的数据时效性判定算法:一种是针对一般时效图的 O(n2 logn)时间算法,另 一种是针对无环时效图的 O(n2 )时间最优化算法. 文献[51]研究了相对于查询的数据时效性判定问题,建立了数据相对时效性的数学模型.针对最新值查询 和时效序列查询这两类查询,提出了查询结果的时效性判定方法,并将每类查询作为一个整体,给出了数据集合 相对于每类查询的平均时效性判定方法. (3) 数据完整性判定的理论和算法 文献[52]研究了数据完整性判定问题. • 首先,给出了一种数据完整性模型,这种数据模型避免了假阳性错误,即,避免能够由函数依赖可导出的 值被误判为缺失值; • 然后,确定了数据完整性判定问题的计算复杂性,证明了该问题是 P 问题,且其时间复杂度下界是 Ω(n2 ); • 最后,给出了时间复杂度为 O(n2 )的最优化判定算法,并给出了一种适用于大数据的(ε,δ)-近似算法,其 时间和空间复杂性均为 O(ε −2 ln(δ −1 )). 文献[53]进一步扩展了这项研究结果. 文献[54]综述了早期的数据完整判定的研究工作,介绍了不同种类的数据完整度的定义和计算方法. 文献[55]提出了判定地理数据完整性的计算方法.文献[56]给出了时间序列数据完整性判定方法.文献[57, 58]给出了其他特定数据集合的数据完整性判定方法. (4) 数据精确性判定的理论和算法 对于数据集合中的不精确值,其精确值难以预知.于是,数据精确性判定问题是一个非常困难的问题.文献 [59,60]提出了一种多模态数据集的精确性判定方法,使用均方误差这一参数衡量数据的精确性.该方法把数据 集合中的数据分为 3 类,即可量度型、可比性型、分类型.针对每类数据的特点,建立了不同的精确性数学模型, 并组合这些数学模型,最终建立了数据精确性的数学模型.针对精确值可知与不可知两种情况,该方法提供了不
李建中等:大数据可用性的研究进展 同的数据精确性判定算法在精确值可知的情况下,直接用均方误差来判定数据的精确性;在精确值缺失的情况 下,针对不同的数据类型,分别提出了二次规划算法、迭代算法和EM算法,以求解各类数据精确性的判定问题 最后确定整个数据集合的精确性. (5)实体同一性判定的理论和算法 文献[61]提出了一种基于实体识别结果的实体同一性判定方法 首先,定义了元组之间的距离用以描述任意两个元组在所有属性上的值的不一致的程度,并基于元组 的距离进一步定义了实体同一性的数学模型 其次,研究了实体同一性判定的计算复杂性证明了实体同一性判定问题是NP难的 最后分别给出了求解实体同一性判定问题的4个子问题的 O(nlogn)时间2-近似算法和 O(nlogn)时间 n近似算法,并最终给出了O( nlogn)时间的n-近似算法 2.3数据错误检测与修复研究进 数据可用性具有数据一致性、完整性、精确性、时效性和实体同一性这5个维度.数据错误检测和修复方 面的研究主要围绕一致性、完整性、时效性和实体同一性这5个方面开展研究,在考虑了多维度错误的同时检 测与修复问题本节介绍这些研究结果 (1)数据一致性错误的检测与修复 基于条件函数依赖,人们提出了很多数据一致性错误的检测与修复方法文献[6,63]针对集中存储的关系 数据库,使用SQL语言设计了自动检测算法,用于查找违反条件函数依赖和条件包含依赖的元组文献[64]研究 了在分布式环境下检测数据一致性错误的问题,目标是最小化数据通信量文献[65]给出了一种增量式的分布 式数据库中数据一致性错误的检测方法 文献[66铪给出了基于主数据的数据一致性修复问题给定数据集合D、条件函数依赖集∑和主数据Dm修 复D中的数据一致性错误 首先证明了该问题是NP完全的、不存在多项式时间的 O(ogn)近似算法除非NP=P, 然后,提出了与主数据相关的修复规则证明修复规则的一致性问题和覆盖问题是coNP-完全的; ·最后,基于主数据和修复规则,提出了启发式数据一致性错误修复算法」 文献[6研究了基于用户反馈的数据一致性错误修复问题,证明了对于多类查询该问题分别是NP完全 的、∑-完全的或 PSPACE完全的而对于选择投影查询该问题是P问题针对选择-投影查询给出了时间复 杂性为O(n)的精确的问题求解算法 文献[68]研究了数据一致性修复问题中,数据集合的一致性表达规则可能不正确的问题,提出了相对信任 的概念,用以判定是数据可信还是一致性表达规则可信,从而确定是修改数据还是修改一致性表达规则,并提 出了相应算法 文献69]设计了一个数据不一致性修复框架提出了不同的一致性约束条件类型和选择最优值的方法,用 以解决数据一致性错误修复问题,提出了新的修复规则语义和一种计算最优修复方案的算法 文献[70]提出了基于 Hadoop并行平台的不一致数据检测与修复算法 (2)数据时效性错误的检测与修复 文献[76]合并时效函数依赖与近似函数依赖提出了时效近似函数依赖并给出其基本定义和一些相关的 数据挖掘技术 文献[7提出了一种模型,通过部分时间顺序和时间约束来指定数据时效性并通过不变的条件函数依赖 来强化数据时效性 文献[78]针对网络数据的时效性提出了时效规则发现问题给出了基于关联规则和离群点识别的机器学习 算法,从而实现了数据的时效性检测与修复 文献[79提出一类新的时效性修复规则CRR,将规则和统计的方法结合起来修复过时数据该规则一方面 能够通过规则模式表达领域知识,另一方面还能够使用其特有的分布表来描述数据随时间变化的统计信息. 中国科学院软件研究所htp:/ww.jos.org.cn
李建中 等:大数据可用性的研究进展 1611 同的数据精确性判定算法.在精确值可知的情况下,直接用均方误差来判定数据的精确性;在精确值缺失的情况 下,针对不同的数据类型,分别提出了二次规划算法、迭代算法和 EM 算法,以求解各类数据精确性的判定问题, 最后确定整个数据集合的精确性. (5) 实体同一性判定的理论和算法 文献[61]提出了一种基于实体识别结果的实体同一性判定方法. • 首先,定义了元组之间的距离,用以描述任意两个元组在所有属性上的值的不一致的程度,并基于元组 的距离进一步定义了实体同一性的数学模型; • 其次,研究了实体同一性判定的计算复杂性,证明了实体同一性判定问题是 NP-难的; • 最后,分别给出了求解实体同一性判定问题的 4 个子问题的 O(nlogn)时间 2-近似算法和 O(nlogn)时间 n-近似算法,并最终给出了 O(nlogn)时间的 n-近似算法. 2.3 数据错误检测与修复研究进展 数据可用性具有数据一致性、完整性、精确性、时效性和实体同一性这 5 个维度.数据错误检测和修复方 面的研究主要围绕一致性、完整性、时效性和实体同一性这 5 个方面开展研究,在考虑了多维度错误的同时检 测与修复问题.本节介绍这些研究结果. (1) 数据一致性错误的检测与修复 基于条件函数依赖,人们提出了很多数据一致性错误的检测与修复方法.文献[62,63]针对集中存储的关系 数据库,使用 SQL 语言设计了自动检测算法,用于查找违反条件函数依赖和条件包含依赖的元组.文献[64]研究 了在分布式环境下检测数据一致性错误的问题,目标是最小化数据通信量.文献[65]给出了一种增量式的分布 式数据库中数据一致性错误的检测方法. 文献[66]给出了基于主数据的数据一致性修复问题:给定数据集合 D、条件函数依赖集 Σ 和主数据 Dm,修 复 D 中的数据一致性错误. • 首先,证明了该问题是 NP-完全的、不存在多项式时间的 O(logn)-近似算法,除非 NP=P; • 然后,提出了与主数据相关的修复规则,证明修复规则的一致性问题和覆盖问题是 coNP-完全的; • 最后,基于主数据和修复规则,提出了启发式数据一致性错误修复算法. 文献[67]研究了基于用户反馈的数据一致性错误修复问题,证明了对于多类查询,该问题分别是 NP-完全 的、 2 P Σ -完全的或 PSPACE-完全的;而对于选择-投影查询,该问题是 P 问题.针对选择-投影查询,给出了时间复 杂性为 O(n2 )的精确的问题求解算法. 文献[68]研究了数据一致性修复问题中,数据集合的一致性表达规则可能不正确的问题,提出了相对信任 的概念,用以判定是数据可信,还是一致性表达规则可信,从而确定是修改数据还是修改一致性表达规则,并提 出了相应算法. 文献[69]设计了一个数据不一致性修复框架,提出了不同的一致性约束条件类型和选择最优值的方法,用 以解决数据一致性错误修复问题,提出了新的修复规则语义和一种计算最优修复方案的算法. 文献[70]提出了基于 Hadoop 并行平台的不一致数据检测与修复算法. (2) 数据时效性错误的检测与修复 文献[76]合并时效函数依赖与近似函数依赖,提出了时效近似函数依赖,并给出其基本定义和一些相关的 数据挖掘技术. 文献[77]提出了一种模型,通过部分时间顺序和时间约束来指定数据时效性,并通过不变的条件函数依赖 来强化数据时效性. 文献[78]针对网络数据的时效性提出了时效规则发现问题,给出了基于关联规则和离群点识别的机器学习 算法,从而实现了数据的时效性检测与修复. 文献[79]提出一类新的时效性修复规则 CRR,将规则和统计的方法结合起来修复过时数据.该规则一方面 能够通过规则模式表达领域知识,另一方面还能够使用其特有的分布表来描述数据随时间变化的统计信息.由