软件学报ISSN1000-9825, CODEN RUXUEW Journal of so/nare,201627(7):1605-1625|doi:10.13328/ cnki. jos.005038] ◎中国科学院软件研究所版权所有 +86-10-62562563 大数据可用性的研究进展 李建中,王宏志,高宏 (哈尔滨工业大学计算机科学与技术学院黑龙江哈尔滨150001) 通讯作者:李建中,E-mai:lijzh@hit.edu.cn 摘要:信息技术的迅速发展,催生了大数据时代的到来大数据已经成为信息社会的重要财富,为人们更深入地 感知、认识和控制物理世界提供了前所未有的丰富信息然而随着数据规模的扩大,劣质数据也随之而来,导致大数 据质量低劣,极大地降低了大数据的可用性,严重困扰着信息社会近年来,数据可用性问题引起了学术界和工业界 的共同关注,展开了深入的研究,取得了一系列研究成果介绍了数据可用性的基本概念,讨论数据可用性的挑战与 研究问题综述了数据可用性方面的研究成果,探索了大数据可用性的未来研究方向 关键词:大数据;数据可用性;数据质量;数据清洗;数据管理 中图法分类号:TP311 中文引用格式:李建中,王宏志高宏大数据可用性的研究进展软件学报2016,27(7):1605-1625.htp/www.jos.org.cn/1000 9825/5038hm 英文引用格式:LiJz, Wang HZ,GaoH. State-of-the-Art of research on big data usability. Ruan jian Xue Bao/Journal of Software2016,27(7):1605-1625(inChinese).http://www.jos.orgcn/1000-9825/5038.htm State-of-the-Art of Research on Big Data Usability LI Jian-Zhong, WANG Hong-Zhi, GAO Hong ( School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China) Abstract: The rapid development of information technology gives rise to the big data era. Big data has become an important wealth of formation society, and has provided unprece world. However, withthe growth in data scale, dirty datacomes along. Dirty data leads to the low qualityand usability of big data, and seriously harms the information society. In recent years, the data usability problems have drawn the attentions of both the academia and dustry. In-Depth studies have been conducted, and a series of research results have been obtained. This paper introduces the concept of data usability, discusses the challenges and research issues, reviews the research results and explories future research directions in this Key words: big data, data usability; data quality; data cleaning; data management 信息技术的迅速发展特别是数据获取技术的突飞猛进催生了大数据时代的到来包括我国在内的世界很 多国家都在很多领域积累了PB(1015字节)级以上规模的大数据这些大数据对于国民经济发展、社会进步、社 会安全和稳定、科学研究模式变革等人类社会的各个方面都具有重大价值,为人类更深入地感知、认识和控制 物理世界提供了前所未有的丰富信息大数据已经开始造福于人类,成为信息社会的重要财富,引起了学术界 工业界和各国政府的高度重视研究工作风起云涌 基金项目:国家重点基础研究发展计划(973)(2012CB316200,国家自然科学基金(U1509216,61472099) Foundation item: National Basic Research Program of China(973)(2012CB3 16200 ); National Natural Science Foundation of China 收稿时间:2016-05-12;采用时间:2016-05-17;jos在线出版时间:201605-19 CNKI网络优先出版:2016-05-1816:45:38,htp/ww. cnki. net/kcms/deta12560.TP.20160518.1645.001html ◎中国科学院软件研究所htp:/w.jos.org.cn
软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn Journal of Software,2016,27(7):1605−1625 [doi: 10.13328/j.cnki.jos.005038] http://www.jos.org.cn ©中国科学院软件研究所版权所有. Tel: +86-10-62562563 大数据可用性的研究进展∗ 李建中, 王宏志, 高 宏 (哈尔滨工业大学 计算机科学与技术学院,黑龙江 哈尔滨 150001) 通讯作者: 李建中, E-mail: lijzh@hit.edu.cn 摘 要: 信息技术的迅速发展,催生了大数据时代的到来.大数据已经成为信息社会的重要财富,为人们更深入地 感知、认识和控制物理世界提供了前所未有的丰富信息.然而随着数据规模的扩大,劣质数据也随之而来,导致大数 据质量低劣,极大地降低了大数据的可用性,严重困扰着信息社会.近年来,数据可用性问题引起了学术界和工业界 的共同关注,展开了深入的研究,取得了一系列研究成果.介绍了数据可用性的基本概念,讨论数据可用性的挑战与 研究问题,综述了数据可用性方面的研究成果,探索了大数据可用性的未来研究方向. 关键词: 大数据;数据可用性;数据质量;数据清洗;数据管理 中图法分类号: TP311 中文引用格式: 李建中,王宏志,高宏.大数据可用性的研究进展.软件学报,2016,27(7):1605−1625. http://www.jos.org.cn/1000- 9825/5038.htm 英文引用格式: Li JZ, Wang HZ, Gao H. State-of-the-Art of research on big data usability. Ruan Jian Xue Bao/Journal of Software, 2016, 27(7):1605−1625 (in Chinese). http://www.jos.org.cn/1000-9825/5038.htm State-of-the-Art of Research on Big Data Usability LI Jian-Zhong, WANG Hong-Zhi, GAO Hong (School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China) Abstract: The rapid development of information technology gives rise to the big data era. Big data has become an important wealth of information society, and has provided unprecedented rich information for people to further perceive, understand and control the physical world. However, withthe growth in data scale, dirty datacomes along. Dirty data leads to the low qualityand usability of big data, and seriously harms the information society. In recent years, the data usability problems have drawn the attentions of both the academia and industry. In-Depth studies have been conducted, and a series of research results have been obtained. This paper introduces the concept of data usability, discusses the challenges and research issues, reviews the research results and explories future research directions in this area. Key words: big data; data usability; data quality; data cleaning; data management 信息技术的迅速发展,特别是数据获取技术的突飞猛进,催生了大数据时代的到来,包括我国在内的世界很 多国家都在很多领域积累了 PB(1015 字节)级以上规模的大数据.这些大数据对于国民经济发展、社会进步、社 会安全和稳定、科学研究模式变革等人类社会的各个方面都具有重大价值,为人类更深入地感知、认识和控制 物理世界提供了前所未有的丰富信息.大数据已经开始造福于人类,成为信息社会的重要财富,引起了学术界、 工业界和各国政府的高度重视,研究工作风起云涌. ∗ 基金项目: 国家重点基础研究发展计划(973)(2012CB316200); 国家自然科学基金(U1509216, 61472099) Foundation item: National Basic Research Program of China (973) (2012CB316200); National Natural Science Foundation of China (U1509216, 61472099) 收稿时间: 2016-05-12; 采用时间: 2016-05-17; jos 在线出版时间: 2016-05-19 CNKI 网络优先出版：2016-05-18 16:45:38, http://www.cnki.net/kcms/detail/11.2560.TP.20160518.1645.001.html
Journal of so/ fare软件学报Vol27,No.7,Juy2016 然而,随着大数据的爆炸性增长,劣质数据也随之而来,导致数据质量低劣,极大地降低了数据的可用性国 外权威机构的统计表明美国的企业信息系统中,1%30%的数据存在各种错误和误差,美国的医疗信息系统 中,13.6%-81%的关键数据不完整或陈旧国际著名的科技咨询机构 Gartner的调查结果显示全球财富1000 强企业中,超过25%的企业信息系统中存在数据错误时 数据可用性问题及其所导致的知识和决策错误已经在全球范围内造成了恶劣的后果严重困扰着信息社 会例如在医疗方面美国由于数据错误引发的医疗事故每年导致的患者死亡人数高达98000名以上向在工业 方面错误和陈旧的数据每年给美国的工业企业造成约6110亿美元的损失在商业方面美国的零售业中每 年仅错误标价这一种数据可用性问题的诱因,就导致了25亿美元的损失在金融方面仅在2006年在美国的 银行业中,由于数据不一致而导致的信用卡欺诈失察就造成48亿美元的损失,在数据仓库开发过程中,30% 80%的开发时间和开发预算花费在清理数据错误方面,数据可用性问题给每个企业增加的平均成本是产值的 0%-20%明因而大数据的广泛应用对数据可用性的保障提出了迫切需求 数据可用性问题是信息化社会的固有问题不仅西方发达国家存在我国也存在例如我们通过对我国某 个大型医药企业信息中心的大规模数据进行抽 6以上的数据存在错误 综上所述确保数据可用性是关系到信息社会存亡的重大任务,是有效发掘和利用大数据价值的前提深入 开展数据可用性研究,具有重要的战略意义最近几年,数据可用性的研究引起了全球的关注中国国家重大基 础研究发展计划(973计划012年启动了为期5年的“海量数据可用性基础理论与关键技术研究”项目.目前,大 数据可用性的研究蓬勃开展,成为大数据研究的一个重要方面,取得了很多研究成果本文旨在介绍大数据可用 性的基本概念分析大数据可用性的研究问题介绍大数据可用性的研究进展探索未来的研究方向 1大数据可用性概念、挑战与研究问题 11数据可用性的基本概念 数据可用性具有很多度量指标文献[0列出了20个数据可用性指标,文献[1]归纳了40个数据可用性指 标我们针对大数据的实际应用,对大数据的可用性度量指标进行了全面而系统的分析抽象出如下5个实际可 亍的度量指标12 数据一致性 数据集合中每个信息都不包含语义错误或相互矛盾的数据例如,数据(公司=“先导”,国码=“86”,区号= “10”,城市=“上海”)含有一致性错误,因为10是北京区号而非上海区号 数据精确性 数据集合中每个数据都能准确表述现实世界中的实体例如某城市人口数量为4130465,而数据库中记 载为400万宏观来看,该信息是合理的,但不精确 ·数据完整性 数据集合中包含足够的数据来回答各种查询,并支持各种计算例如某医疗数据库中的数据一致且精确 但遗失某些患者的既往病史,从而存在不完整性,可能导致不正确的诊断甚至严重医疗事故 数据时效性 信息集合中,每个信息都与时俱进不过时例如,某数据库中的用户地址在2010年是正确的但在2011年未 必正确,即数据过时 ·实体同一性 同一实体的标识在所有数据集合中必须相同而且数据必须一致例如企业的市场、销售和服务部门可能 维护各自的数据库,如果这些数据库中的同一个实体没有相同的标识或数据不一致将存在大量具有差异的重 复数据,导致实体表达混乱 设集合D的数据一致性、精确性、完整性、时效性和实体同一性分别为Q1,Q2Q3Q4和Q3,则数据可用性 可以定义为 中国科学院软件研究所htp:/ww.jos.org.cn
1606 Journal of Software 软件学报 Vol.27, No.7, July 2016 然而,随着大数据的爆炸性增长,劣质数据也随之而来,导致数据质量低劣,极大地降低了数据的可用性.国 外权威机构的统计表明:美国的企业信息系统中,1%~30%的数据存在各种错误和误差[1];美国的医疗信息系统 中,13.6%~81%的关键数据不完整或陈旧[2].国际著名的科技咨询机构 Gartner 的调查结果显示:全球财富 1 000 强企业中,超过 25%的企业信息系统中存在数据错误[3]. 数据可用性问题及其所导致的知识和决策错误已经在全球范围内造成了恶劣的后果,严重困扰着信息社 会.例如:在医疗方面,美国由于数据错误引发的医疗事故每年导致的患者死亡人数高达 98 000 名以上[4];在工业 方面,错误和陈旧的数据每年给美国的工业企业造成约 6 110 亿美元的损失[5];在商业方面,美国的零售业中,每 年仅错误标价这一种数据可用性问题的诱因,就导致了 25 亿美元的损失[6];在金融方面,仅在 2006 年,在美国的 银行业中,由于数据不一致而导致的信用卡欺诈失察就造成 48 亿美元的损失[7];在数据仓库开发过程中,30%~ 80%的开发时间和开发预算花费在清理数据错误方面[8];数据可用性问题给每个企业增加的平均成本是产值的 10%~20%[9].因而,大数据的广泛应用对数据可用性的保障提出了迫切需求. 数据可用性问题是信息化社会的固有问题,不仅西方发达国家存在,我国也存在.例如,我们通过对我国某 个大型医药企业信息中心的大规模数据进行抽样检验,发现 10%以上的数据存在错误. 综上所述,确保数据可用性是关系到信息社会存亡的重大任务,是有效发掘和利用大数据价值的前提.深入 开展数据可用性研究,具有重要的战略意义.最近几年,数据可用性的研究引起了全球的关注.中国国家重大基 础研究发展计划(973 计划)2012 年启动了为期 5 年的“海量数据可用性基础理论与关键技术研究”项目.目前,大 数据可用性的研究蓬勃开展,成为大数据研究的一个重要方面,取得了很多研究成果.本文旨在介绍大数据可用 性的基本概念,分析大数据可用性的研究问题,介绍大数据可用性的研究进展,探索未来的研究方向. 1 大数据可用性概念、挑战与研究问题 1.1 数据可用性的基本概念 数据可用性具有很多度量指标.文献[10]列出了 20 个数据可用性指标,文献[11]归纳了 40 个数据可用性指 标.我们针对大数据的实际应用,对大数据的可用性度量指标进行了全面而系统的分析,抽象出如下 5 个实际可 行的度量指标[12]. • 数据一致性 数据集合中,每个信息都不包含语义错误或相互矛盾的数据.例如,数据(公司=“先导”,国码=“86”,区号= “10”,城市=“上海”)含有一致性错误,因为 10 是北京区号而非上海区号. • 数据精确性 数据集合中,每个数据都能准确表述现实世界中的实体.例如,某城市人口数量为 4 130 465,而数据库中记 载为 400 万.宏观来看,该信息是合理的,但不精确. • 数据完整性 数据集合中包含足够的数据来回答各种查询,并支持各种计算.例如,某医疗数据库中的数据一致且精确, 但遗失某些患者的既往病史,从而存在不完整性,可能导致不正确的诊断甚至严重医疗事故. • 数据时效性 信息集合中,每个信息都与时俱进,不过时.例如,某数据库中的用户地址在 2010 年是正确的,但在 2011 年未 必正确,即数据过时. • 实体同一性 同一实体的标识在所有数据集合中必须相同而且数据必须一致.例如,企业的市场、销售和服务部门可能 维护各自的数据库,如果这些数据库中的同一个实体没有相同的标识或数据不一致,将存在大量具有差异的重 复数据,导致实体表达混乱. 设集合 D 的数据一致性、精确性、完整性、时效性和实体同一性分别为 Q1,Q2,Q3,Q4 和 Q5,则数据可用性 可以定义为
李建中等:大数据可用性的研究进展 1607 usability(D501+802+803+&04+8Os, 其中,δ,⑤,6,6和6是由用户根据实际需要确定的权值,且6+2+3+64+B=1 1.2大数据可用性的挑战和研究问题 大数据可用性向我们提出了如下3个挑战问题 (1)量质融合管理如何实现大数据的数量与质量的融合管理? 现有的大数据管理研究仅关注数据的规模、系统的处理能力和可扩展性,重在“量”的管理,忽视了数据 质℃(即质量)的管理我们面临的第一个挑战是确保大数据的质量,将大数据管理从“量”的管理拓展到“质”的管 理,最终实现“量”与“质”的融合管理为了彻底实现量质融合管理,我们必须研究量质融合管理问题提出完整的 理论体系解决关键技术问题 (2)劣质容忍原理:如何完成劣质数据上的精确或近似计算? 数据错误几乎无处不在已成为不争的事实“劣质容忍”是指在数据存在错误的情况下,如何完成精确或近 似计算为了实现劣质容忍,我们必须完成如下两个挑战性任务:第一,自动发现并修正大数据的错误将可校正 的劣质数据修复为完全正确的可用数据,支持正确的计算第二很多数据错误无法完全修复经过修复后,这些 数据成为部分正确的弱可用数据我们必须解决如何在弱可用大数据上完成高质量的近似计算 (3)深度演化机理:如何认知大数据演化的机理,追索数据错误根源? 数据不是一成不变的它会随着时间和物理世界的变化而发生演化现有的大数据研究忽略了按数据的演 化机理所进行的研究,使得数据错误的根源难以追索我们需要探索大数据的深度演化机理,即,以可用性为核 心的多源信息集合在时间、空间、形态、粒度等多个维度上正向协同的演化机理 为了应对上述挑战,我们需要以数据的一致性、精确性、完整性、时效性和实体同一性为核心,以保障信 息可用性为目标,研究以下7个问题,创建一套完整的确保海量信息可用性的理论、方法和技术 (1)大数据可用性的表达机理 首先探索数据的一致性、精确性、完整性、时效性、实体同一性的语义规则,建立大数据可用性语义表 达规则系统,判定规则系统可否公理化如果可公理化,则建立公理系统;然后,确定从大数据自动发现语义规则 问题的计算复杂性并设计求解算法;最后,确定大数据可用性自动推理问题的计算复杂性并设计求解算法 (2)大数据可用性的判定理论 首先,分别建立大数据的一致性、精确性、完整性、时效性、实体同一性的数学模型;然后,根据大数据研 究可用性这5项指标之间的相互影响,建立大数据可用性的综合数学模型最后,确定大数据可用性判定问题的 计算复杂性,设计求解算法 (3)大数据的演化原理 探索大数据的演化过程,建立大数据演化的世系模型及追踪技术,包括时空、多粒度、多路径和不确定的 大数据演化的理论,演化的可逆性判定与近似求解算法演化描述的复杂性理论和方法,以及网络化、多粒度 随机化的世系追踪和数据错误追踪技术 (4)大数据量质融合管理的理论和技术 首先,建立支持大数据量质融合管理的数据模型和相关理论,包括数据的逻辑结构、运算系统、数据的语 义约束模型;然后,解决数据质量管理模型和理论与传统数据管理模型和理论的融合问题,建立大数据量质融合 管理的模型和理论;最后,研究大数据量质融合管理关键问题的可计算性和计算复杂性,并设计求解算法 (5)高质量数据获取与整合的理论和技术 高质量数据的获取,是确保大数据可用性的重要环节大数据的来源多种多样类型千差万别,质量参差不 齐整合困难这些问题在当今突飞猛进的传感网和物联网背景下尤为严重我们需要解决如下具有挑战性的问 题:最优化逼近物理世界的高精度数据获取的理论和技术、最大化数据与问题求解相关性的高相关数据获取的 理论和技术、最小化无价值数据的高纯度数据获取的理论和技术 (6)数据错误自动检测与修复的理论和技术 中国科学院软件研究所htp:/ww.jos.org.cn
李建中 等:大数据可用性的研究进展 1607 usability(D)=δ1Q1+δ2Q2+δ3Q3+δ4Q4+δ5Q5, 其中,δ1,δ2,δ3,δ4 和δ5 是由用户根据实际需要确定的权值,且δ1+δ2+δ3+δ4+δ5=1. 1.2 大数据可用性的挑战和研究问题 大数据可用性向我们提出了如下 3 个挑战问题. (1) 量质融合管理:如何实现大数据的数量与质量的融合管理? 现有的大数据管理研究仅关注数据的规模、系统的处理能力和可扩展性,重在“量”的管理,忽视了数据 “质”(即质量)的管理.我们面临的第一个挑战是确保大数据的质量,将大数据管理从“量”的管理拓展到“质”的管 理,最终实现“量”与“质”的融合管理.为了彻底实现量质融合管理,我们必须研究量质融合管理问题,提出完整的 理论体系,解决关键技术问题. (2) 劣质容忍原理:如何完成劣质数据上的精确或近似计算? 数据错误几乎无处不在已成为不争的事实.“劣质容忍”是指在数据存在错误的情况下,如何完成精确或近 似计算.为了实现劣质容忍,我们必须完成如下两个挑战性任务:第一,自动发现并修正大数据的错误,将可校正 的劣质数据修复为完全正确的可用数据,支持正确的计算;第二,很多数据错误无法完全修复,经过修复后,这些 数据成为部分正确的弱可用数据.我们必须解决如何在弱可用大数据上完成高质量的近似计算. (3) 深度演化机理:如何认知大数据演化的机理,追索数据错误根源? 数据不是一成不变的,它会随着时间和物理世界的变化而发生演化.现有的大数据研究忽略了按数据的演 化机理所进行的研究,使得数据错误的根源难以追索.我们需要探索大数据的深度演化机理,即,以可用性为核 心的多源信息集合在时间、空间、形态、粒度等多个维度上正向协同的演化机理. 为了应对上述挑战,我们需要以数据的一致性、精确性、完整性、时效性和实体同一性为核心,以保障信 息可用性为目标,研究以下 7 个问题,创建一套完整的确保海量信息可用性的理论、方法和技术. (1) 大数据可用性的表达机理 首先,探索数据的一致性、精确性、完整性、时效性、实体同一性的语义规则,建立大数据可用性语义表 达规则系统,判定规则系统可否公理化,如果可公理化,则建立公理系统;然后,确定从大数据自动发现语义规则 问题的计算复杂性,并设计求解算法;最后,确定大数据可用性自动推理问题的计算复杂性,并设计求解算法. (2) 大数据可用性的判定理论 首先,分别建立大数据的一致性、精确性、完整性、时效性、实体同一性的数学模型;然后,根据大数据研 究可用性这 5 项指标之间的相互影响,建立大数据可用性的综合数学模型;最后,确定大数据可用性判定问题的 计算复杂性,设计求解算法. (3) 大数据的演化原理 探索大数据的演化过程,建立大数据演化的世系模型及追踪技术,包括时空、多粒度、多路径和不确定的 大数据演化的理论,演化的可逆性判定与近似求解算法,演化描述的复杂性理论和方法,以及网络化、多粒度、 随机化的世系追踪和数据错误追踪技术. (4) 大数据量质融合管理的理论和技术 首先,建立支持大数据量质融合管理的数据模型和相关理论,包括数据的逻辑结构、运算系统、数据的语 义约束模型;然后,解决数据质量管理模型和理论与传统数据管理模型和理论的融合问题,建立大数据量质融合 管理的模型和理论;最后,研究大数据量质融合管理关键问题的可计算性和计算复杂性,并设计求解算法. (5) 高质量数据获取与整合的理论和技术 高质量数据的获取,是确保大数据可用性的重要环节.大数据的来源多种多样,类型千差万别,质量参差不 齐,整合困难.这些问题在当今突飞猛进的传感网和物联网背景下尤为严重.我们需要解决如下具有挑战性的问 题:最优化逼近物理世界的高精度数据获取的理论和技术、最大化数据与问题求解相关性的高相关数据获取的 理论和技术、最小化无价值数据的高纯度数据获取的理论和技术. (6) 数据错误自动检测与修复的理论和技术
l608 Journal of so/ fare软件学报Vol27,No.7,Juy2016 数据错误的自动检测和修复是十分困难的问题我们需要在大数据可用性的表达机理、大数据可用性的判 定理论、大数据演化原理的基础上探索大数据错误自动检测和修复的理论和技术,主要包括数据错误自动检 测和修复问题的可计算性理论、计算复杂性理论、修复结果可信性理论、大数据错误自动检测与修复算法 (7)弱可用数据上的近似计算的理论和算法 当一个数据集合中的错误不能彻底修复时我们称其为弱可用数据于是,弱可用数据上近似计算(如查询 分析、挖掘等)的理论和算法成为重要的研究问题弱可用数据上的近似计算不同于传统意义下的近似计算,它 是在具有一致性错误、完整性错误、精确性错误、时效性错误或实体冋一性错误的数据上近似地求解满足给 定精度要求的问题的解现有的近似理论与算法无法支持弱可用数据上的近似计算,因此我们需要研究弱可用 数据近似计算的可行性理论、弱可用数据计算问题的计算复杂性理论和算法、弱可用数据近似计算结果的质 量评估理论 2大数据可用性的研究进展 近年来,人们开展了大量的研究工作,取得了很多研究成果,文献[12-14]是关于数据可用性早期研究工作 的 综述本节综述大数据可用性研究的新进展,包括数据可用性表达机理、数据可用性判定的理论和方法、数据 错误检测与修复的理论与方法、弱可用数据近似计算的理论和算法、高质量数据获取的理论和方法、大数 可用性管理系统 2.1数据可用性的表达机理的研究进展 数据可用性的表达机理主要解决如何表达一个数据集合的数据一致性、精确性、完整性、时效性和实体 同一性及其相关理论问题,为数据可用性的判定和数据错误的自动发现与修复奠定基础 (1)数据一致性的表达机理 文献[!5]对函数依赖理论进行了扩展,提出了基于条件函数依赖的数据一致性表达机制,证明了存在有穷 推理规则集使该机制可有穷公理化,给出了具有4条推理规则的公理系统并证明了公理系统的有效性和完备 性文献[16]研究了如何从数据中有效地发现条件函数依赖的问题提出了4种有效发现条件函数依赖的算法 文献[17-19研究了条件函数依赖的推理问题、覆盖问题、检测问题、传递问题的计算复杂度及其求解算法 文献[44]研究了条件函数依赖的置信度评估问题,提出了基于抽样的条件函数依赖置信度评估算法,并证明了 该算法能够以1-。概率给出相对误差小于ε的估计结果,其中,∞0,0<1. 文献20]针对条件函数依赖无法描述“并”语义的问题,提出了表示支持“与”和“并”语义的扩展的条件函数 依赖文献[21]提出了微条件函数依赖文献[20,211分别证明了各自的扩展条件函数依赖规则系统是可公理化 的,建立了公理系统,证明了公理系统的有效性和完备性,并确定了自动推理问题的计算复杂性,提出了求解算 法文献[120,21]还分别确定了各自的扩展条件函数依赖的自动挖掘问题的计算复杂性,并提出挖掘算法文 [2]提出了概率数据库中随机条件函数依赖 文献[23]在有时间戳的数据上提出了序列依赖语义规则,用来描述随时间变化数据的一致性约束,试图解 决随时间变化数据的一致性错误的发现和修复问题 文献[24]针对异枃数据源中由数据格式不一致引发的一致性错误,利用属性值的相似性扩展了函数依赖, 用来描述异构数据的一致性发现和修复异构数据的一致性错误 文献[25]利用统计模型来描述数据的一致性,并通过求解和比较模型参数的方法来发现和修复数据不一致 性错误文献[26提出了基于统计知识的数据不一致性描述方法,并给出了基于超团的数据一致性提升算法 文献171-75]研究了数据一致性规则挖掘问题分别提出了在数据集合中挖掘各种数据一致性规则的算法 (2)数据完整性的表达机理 传统的数据完整性研究工作一般都建立在封闭世界或开放世界假设的基础上封闭世界假设表示数据库 包含了所有表述现实世界实体的元组,这些元组的某些属性值可能遗缺开放世界假设表示数据库中不仅属性 值可能遗失,描述实体的元组也可能完全遗缺然而,现实世界的数据库经常既不是完全封闭的,也不是完全开 中国科学院软件研究所htp:/ww.jos.org.cn
1608 Journal of Software 软件学报 Vol.27, No.7, July 2016 数据错误的自动检测和修复是十分困难的问题.我们需要在大数据可用性的表达机理、大数据可用性的判 定理论、大数据演化原理的基础上,探索大数据错误自动检测和修复的理论和技术,主要包括:数据错误自动检 测和修复问题的可计算性理论、计算复杂性理论、修复结果可信性理论、大数据错误自动检测与修复算法. (7) 弱可用数据上的近似计算的理论和算法 当一个数据集合中的错误不能彻底修复时,我们称其为弱可用数据.于是,弱可用数据上近似计算(如查询、 分析、挖掘等)的理论和算法成为重要的研究问题.弱可用数据上的近似计算不同于传统意义下的近似计算,它 是在具有一致性错误、完整性错误、精确性错误、时效性错误或实体同一性错误的数据上近似地求解满足给 定精度要求的问题的解.现有的近似理论与算法无法支持弱可用数据上的近似计算,因此,我们需要研究弱可用 数据近似计算的可行性理论、弱可用数据计算问题的计算复杂性理论和算法、弱可用数据近似计算结果的质 量评估理论. 2 大数据可用性的研究进展 近年来,人们开展了大量的研究工作,取得了很多研究成果,文献[12−14]是关于数据可用性早期研究工作的 综述.本节综述大数据可用性研究的新进展,包括数据可用性表达机理、数据可用性判定的理论和方法、数据 错误检测与修复的理论与方法、弱可用数据近似计算的理论和算法、高质量数据获取的理论和方法、大数据 可用性管理系统. 2.1 数据可用性的表达机理的研究进展 数据可用性的表达机理主要解决如何表达一个数据集合的数据一致性、精确性、完整性、时效性和实体 同一性及其相关理论问题,为数据可用性的判定和数据错误的自动发现与修复奠定基础. (1) 数据一致性的表达机理 文献[15]对函数依赖理论进行了扩展,提出了基于条件函数依赖的数据一致性表达机制,证明了存在有穷 推理规则集使该机制可有穷公理化,给出了具有 4 条推理规则的公理系统,并证明了公理系统的有效性和完备 性.文献[16]研究了如何从数据中有效地发现条件函数依赖的问题,提出了 4 种有效发现条件函数依赖的算法. 文献[17−19]研究了条件函数依赖的推理问题、覆盖问题、检测问题、传递问题的计算复杂度及其求解算法. 文献[44]研究了条件函数依赖的置信度评估问题,提出了基于抽样的条件函数依赖置信度评估算法,并证明了 该算法能够以 1−δ的概率给出相对误差小于ε的估计结果,其中,ε>0,0<δ<1. 文献[20]针对条件函数依赖无法描述“并”语义的问题,提出了表示支持“与”和“并”语义的扩展的条件函数 依赖.文献[21]提出了微条件函数依赖.文献[20,21]分别证明了各自的扩展条件函数依赖规则系统是可公理化 的,建立了公理系统,证明了公理系统的有效性和完备性,并确定了自动推理问题的计算复杂性,提出了求解算 法.文献[20,21]还分别确定了各自的扩展条件函数依赖的自动挖掘问题的计算复杂性,并提出挖掘算法.文献 [22]提出了概率数据库中随机条件函数依赖. 文献[23]在有时间戳的数据上提出了序列依赖语义规则,用来描述随时间变化数据的一致性约束,试图解 决随时间变化数据的一致性错误的发现和修复问题. 文献[24]针对异构数据源中由数据格式不一致引发的一致性错误,利用属性值的相似性扩展了函数依赖, 用来描述异构数据的一致性,发现和修复异构数据的一致性错误. 文献[25]利用统计模型来描述数据的一致性,并通过求解和比较模型参数的方法来发现和修复数据不一致 性错误.文献[26]提出了基于统计知识的数据不一致性描述方法,并给出了基于超团的数据一致性提升算法. 文献[71−75]研究了数据一致性规则挖掘问题,分别提出了在数据集合中挖掘各种数据一致性规则的算法. (2) 数据完整性的表达机理 传统的数据完整性研究工作一般都建立在封闭世界或开放世界假设的基础上.封闭世界假设表示数据库 包含了所有表述现实世界实体的元组,这些元组的某些属性值可能遗缺.开放世界假设表示数据库中不仅属性 值可能遗失,描述实体的元组也可能完全遗缺.然而,现实世界的数据库经常既不是完全封闭的,也不是完全开
李建中等:大数据可用性的研究进展 放的基于这个考虑,文献[27,28]扩展了包含依赖提出了一种表示数据完整性的包含依赖规则系统,定义了规则 的语法和语义,证明了规则系统是可公理化的,建立了公理系统证明了22个相关基础问题的不可计算性 coNP完全性、完全性、2-完全性或 EXPTIME-完全性文献[29扩展了文献[27,28]的研究结果 文献[30,31]将传统的完整性理论扩展到XML数据上研究了XML数据的问题完整性表达机制 (3)数据时效性的表达机理 文献[32]在同一个实体具有多个元组的假设下,提出了一种基于规则的数据时效性表示机制,定义了同 实体对应的不同元组的属性值的时序关系表示方法,提出了基于实体的最新值的时效性查询语义,并给出了应 用元组间的时序关系和拷贝关系推导实体最新信息的推理机制基于这种数据时效性表达机制和时效性查询 语义,文献[32]还给出了用户查询的计算复杂性,并研究了在实体最新值缺失的情况下如何扩展元组间拷贝关 系以找到实体的最新值但是,“同一个实体具有多个元组”的假设使得这种数据时效性表达机制具有很大的局 限性 为了突破文献[32]的数据时效性表达机制的局限性文献[33]提出了基于不确定规则的数据时效性表达机 制,定义了数据时效性规则的语法和语义,证明了规则系统是可有穷公理化的,建立了具有两条推理规则的公理 系统证明了公理系统的有效性和完备性,同时证明了数据时效性规则自动推理问题是P问题,确定了问题的时 复杂性下界,并给出求解推理问题的最优化算法文献[3]还证明了规则挖掘问题是NP-难的,并给出O(n)和 O(n2)时间近似挖掘算法,n是数据集合的大小 (4)实体同一性的表达机理 文献[34]提出了基于规则的实体同一性表达机制,定义了实体同一性规则的语法和语义,证明了对于任意 数据集合D都存在一个有效、一致、完整和独立的实体规则集合∑同时证明了可满足问题和语义蕴含问题皆 为P问题而且它们的时间复杂性下界都是),并给出了求解这两个问题的时间复杂性为)的最优化 算法文献[34]还研究了从数据集合D中挖掘实体同一性规则的问题,证明了该问题是P问题且其时间复杂性下 界为D)给出了时间复杂性为O(D)的最优化求解算法并且证明该算法能够从数据集合D中挖掘出满足 有效性、一致性、完整性和独立性的实体同一性规则集合,即,算法是正确的 文献[35]提出了实体同一性描述规则,系统地研究了规则的推理问题,提高了描述实体同一性的能力.文献 [36]进一步在动态语义下研究了实体同一性规则的相互作用及推理问题 文献[37提出用否定规则描述实体的同一性并研究了否定规则对实体同一性的影响.文献[38]提出了用聚 集约束来描述实体同一性的方法文献[39]结合EM算法和无监督学习方法提出了获取实体同一性描述规则的 方法 (5)数据精确性的表达机理 文献[40在“同一个实体具有多个元组”的假设下,提出了一种基于规则的数据精确性表示机制,定义了同 实体对应的不同元组的属性值之间的精确性偏序关系;在此基础上定义了数据精确性规则的语法和语义,确 定了规则系统的推理问题的计算复杂性,给出了求解问题的算法并提出了相应的精确性错误修复框架. 文献[4I]把不确定性视为精确度低的现象,提出了一种基于可能世界语义的数据精确性描述方法,并给出 了对应的精确性评估算法 22数据可用性判定的研究进展 数据可用性判定问题定义如下给定任意数据集合D,计算D的可用性 usability(D)数据可用性判定的关键 在于数据的一致性、精确性、完整性、时效性和实体同一性的判定.本节介绍数据一致性、精确性、完整性 时效性和实体同一性的研究进展 (1)数据一致性判定的理论和算法 文献[42]系统地研究了数据一致性判定问题 ·首先,基于数据一致性表达机制建立了数据一致性的数学模型给定数据集合D和D上的条件函数依 赖集∑D的一致性定义为 Consistency(D=|DD,其中,D是D中满足∑的最大子集,并证明了:如果 中国科学院软件研究所htp:/ww.jos.org.cn
李建中 等:大数据可用性的研究进展 1609 放的.基于这个考虑,文献[27,28]扩展了包含依赖,提出了一种表示数据完整性的包含依赖规则系统,定义了规则 的语法和语义,证明了规则系统是可公理化的,建立了公理系统,证明了 22 个相关基础问题的不可计算性、 coNP-完全性、 3 p Σ -完全性、 2 P Π -完全性或 EXPTIME-完全性.文献[29]扩展了文献[27,28]的研究结果. 文献[30,31]将传统的完整性理论扩展到 XML 数据上,研究了 XML 数据的问题完整性表达机制. (3) 数据时效性的表达机理 文献[32]在同一个实体具有多个元组的假设下,提出了一种基于规则的数据时效性表示机制,定义了同一 实体对应的不同元组的属性值的时序关系表示方法,提出了基于实体的最新值的时效性查询语义,并给出了应 用元组间的时序关系和拷贝关系推导实体最新信息的推理机制.基于这种数据时效性表达机制和时效性查询 语义,文献[32]还给出了用户查询的计算复杂性,并研究了在实体最新值缺失的情况下如何扩展元组间拷贝关 系以找到实体的最新值.但是,“同一个实体具有多个元组”的假设,使得这种数据时效性表达机制具有很大的局 限性. 为了突破文献[32]的数据时效性表达机制的局限性,文献[33]提出了基于不确定规则的数据时效性表达机 制,定义了数据时效性规则的语法和语义,证明了规则系统是可有穷公理化的,建立了具有两条推理规则的公理 系统,证明了公理系统的有效性和完备性,同时证明了数据时效性规则自动推理问题是 P 问题,确定了问题的时 间复杂性下界,并给出求解推理问题的最优化算法.文献[33]还证明了规则挖掘问题是 NP-难的,并给出 O(n)和 O(n2 )时间近似挖掘算法,n 是数据集合的大小. (4) 实体同一性的表达机理 文献[34]提出了基于规则的实体同一性表达机制,定义了实体同一性规则的语法和语义,证明了对于任意 数据集合 D 都存在一个有效、一致、完整和独立的实体规则集合 Σ,同时证明了可满足问题和语义蕴含问题皆 为 P 问题,而且它们的时间复杂性下界都是 Ω(|Σ| 2 ),并给出了求解这两个问题的时间复杂性为 Ω(|Σ| 2 )的最优化 算法.文献[34]还研究了从数据集合 D中挖掘实体同一性规则的问题,证明了该问题是 P问题且其时间复杂性下 界为 Ω(|D| 2 ),给出了时间复杂性为 O(|D| 2 )的最优化求解算法,并且证明该算法能够从数据集合 D 中挖掘出满足 有效性、一致性、完整性和独立性的实体同一性规则集合,即,算法是正确的. 文献[35]提出了实体同一性描述规则,系统地研究了规则的推理问题,提高了描述实体同一性的能力.文献 [36]进一步在动态语义下研究了实体同一性规则的相互作用及推理问题. 文献[37]提出用否定规则描述实体的同一性,并研究了否定规则对实体同一性的影响.文献[38]提出了用聚 集约束来描述实体同一性的方法.文献[39]结合 EM 算法和无监督学习方法,提出了获取实体同一性描述规则的 方法. (5) 数据精确性的表达机理 文献[40]在“同一个实体具有多个元组”的假设下,提出了一种基于规则的数据精确性表示机制,定义了同 一实体对应的不同元组的属性值之间的精确性偏序关系;在此基础上定义了数据精确性规则的语法和语义,确 定了规则系统的推理问题的计算复杂性,给出了求解问题的算法,并提出了相应的精确性错误修复框架. 文献[41]把不确定性视为精确度低的现象,提出了一种基于可能世界语义的数据精确性描述方法,并给出 了对应的精确性评估算法. 2.2 数据可用性判定的研究进展 数据可用性判定问题定义如下:给定任意数据集合 D,计算 D 的可用性 usability(D).数据可用性判定的关键 在于数据的一致性、精确性、完整性、时效性和实体同一性的判定.本节介绍数据一致性、精确性、完整性、 时效性和实体同一性的研究进展. (1) 数据一致性判定的理论和算法 文献[42]系统地研究了数据一致性判定问题. • 首先,基于数据一致性表达机制建立了数据一致性的数学模型.给定数据集合 D 和 D 上的条件函数依 赖集 Σ,D 的一致性定义为 Consistency(D)=|D′|/|D|,其中,D′是 D 中满足 Σ 的最大子集,并证明了:如果