论文部分内容阅读
摘要： 当前，随着大数据时代的来临，数据质量问题受到越来越多的关注。数据质量会随着时间的流逝迅速下降，因此在数据质量的各个维度中，数据时效性扮演的角色至关重要。判定一个给定的数据集合的时效性是确保数据时效性是第一步，但数据时效性的判定并非易事，其面临极大挑战。本文针对时效性判定问题面临的各个挑战，综述了当前该领域针对绝对时效性判定和相对时效性判定的关键理论和技术，分析了现有的各方法的优缺点，并对未来的研究方向给出了建议。
关键词：数据质量； 数据时效性； 时效性判定
中图分类号： TP391.41
文献标志码：A
文章编号： 2095-2163（2016）06-0072-04
0引言
随着大数据时代的到来，数据的“量”在飞速增长，但与此同时，数据的“质”的下降也成为了不可忽视的问题。多家机构的统计数据表明，当前各行各业中信息的可用性（即数据质量）问题亟待解决。在美国，企业中有1%～30%的数据存在各种质量问题[1]，医疗中有13.6%～81%的组成是不完整、或过时数据[2]。同时，根据国际著名科技咨询机构Gartner的调查结果，即使是在那些著名企业，如全球财富1 000强的企业中，也有超过25%的企业其信息系统中的关键信息不正确或不准确[3]。如果不能够及时有效地针对这些数据质量问题提供全面完整解决，就必将会对国民生活和企业决策形成不可预知的恶劣影响。事实上，已有多次调查结果陆续表明，如上的数据质量问题每年都会在全球范围内造成重大不良效应后果：数据质量问题在美国引发的医疗事故所导致的死亡人数高达98 000名，约等于总医疗事故致死人数的一半[4]；数据过时和错误将使得美国工业企业损失高达6 110亿美元，这一数值几乎可占美国GDP的6%[5]；标价错误还会导致美国零售业损失25亿美元[6]；数据中的不一致错误则会导致信用卡欺诈問题的深度隐藏，这在2006年曾造成48亿美元的财产损失[7]。由此，根据推算，劣质数据的处理需要花费30%～80%的开发时间和预算[8]，进而数据质量问题通常给企业增加获得同等产值约10%～20%的成本[9]。这也随即推动了数据质量工具市场的飞速增长，甚至远超IT行业的平均增长率[10]。劣质数据无时无刻都将通过网络在不同数据源之间传播，因此对数据可用性的研究已经成为数据管理领域中的首要问题内容之一。近几年来，数据库领域的顶级国际会议及期刊每年都会达成和开展多项关系着数据质量方面的相关议程和研究工作。
一般说来，要从下述5个维度来保证数据可用性[11]。现作如下论述：
1）时效性。保证数据与时俱进，不陈旧过时。例如，某数据库中的用户地址在2010年是正确的，但在2011年未必正确，即存在过时数据。
2） 一致性。保证数据不违背某些特定约束。例如，记录（邮编=“150000”，城市=“上海”）就违背了邮编和城市的对应关系，因为150000是哈尔滨的邮编、而非上海邮编。
3） 完整性。保证数据不存在缺失。例如，医疗数据库遗失某患者病史就会导致数据不完整，进而可能妨碍医生正确诊断病情。
4） 精确性。保证数据能够准确地描述对应实体。例如，哈尔滨全市总面积约为5.384万平方公里，但数据库中记录却为5万平方公里，这虽在宏观来看是合理的，但不精确。精确性和一致性并不相同，一致的信息也可能含有误差，即未必精确。
5） 实体同一性。保证描述同一实体的数据在不同数据源上是统一的。例如，可以通过对比个人信息来判断信用卡的使用者和持有者是否为同一人，从而防止欺诈。
在数据可用性的5个维度中，数据时效性的作用地位至关重要。据统计，在商业和医疗信息数据库中，约有2%的客户信息会在一个月内变得陈旧失效[5]，如果这些数据未获修复，那么在2年内，就将有近50%的记录会因为过时而使其可用性受到影响，而过时数据将会导致严重后果。在企业决策时，企业往往会因为使用了陈旧的数据而做出错误的决策，而在日常生活中，银行可能会将信用卡账单寄送到持有人搬家前的旧地址。同时，有相当一部分数据的不一致、不精确、不完整等都是由数据过时失效引起的。例如，银行未能及时更新客户的地址信息将会导致同一客户的住址和邮编难以匹配；随着人口的增长和流动，数据库中各城市的人口数会因为过时变得不再精确；新入学的学生的学籍信息未及时录入会导致记录学生信息的数据库无法趋于完整。因此，确保数据的时效性已成为热点与焦点。
判定一个给定的数据集合的时效性是确保数据时效性的第一步。只是数据时效性的判定却并非易事。同一记录的不同属性随时间变化的频率不同，使得同一记录的不同属性的新旧程度也会不同，这即使得数据时效性判定问题的研究面临严峻挑战。首先，数据库中通常没有完整、可用、精确的时间戳[12]，此时就需要建立一个不依赖于时间戳的数据时效性度量模型。使用该模型，可以对一个给定数据库，形式化地表示单个数据项、元组以及数据库整体的时效性（称为绝对时效性），并定量地判定其时效性。其次，数据库的绝对时效性可能无法直接判定，又或者判定结果不能有效地表达用户需求。为此，则需要针对该数据库上的常用查询或用户的特定需求，设计数据库的相对时效性度量模型。该模型能够度量数据库中较重要部分的时效性，如某些重要查询的提供结果的时效性，或者用户最常使用的数据集合的时效性。
基于如上的论证分析，本文将综述当前数据时效性判定的关键理论和技术，包括数据的绝对时效性和相对时效性判定模型，数据时效性修复算法及查询相关的数据时效性研究等。
[BT4]1绝对时效性判定
当前的时效性判定工作大致可以分为2类：基于时间戳的时效性判定和基于规则的时效性判定。其中，基于时间戳的时效性判定要求数据库中对每个待判定的值都存有完整、清洁、可用的时间戳，通常是事务时间，根据事务时间和数值有效性的衰减来判定当前值是否过时失效，即推断有效时间。该方法的优点是能够对于给定的时间点，判定数据在该时刻过时失效，但缺点却在于其需要大量的辅助信息，如每个值的事务时间和每个值的有效性衰减规律。由于各种属性的不同特性，这些辅助信息在真实应用中很难获得精炼提取，因此基于时间戳的时效性判定方法的适用范围随之受到一定限制。为了克服基于时间戳的方法的缺点与不足，基于规则的方法相应地据此而获提出。这类方法只需要根据少量的由领域知识得到的时效规则，就可以判断描述同一实体的不同属性值的时序关系，从而判定哪些值是过时失效的。这类方法所需的辅助信息大大减少，但其缺点却表现在当前的基于规则的方法仍不能判定某个值在给定的时间点是否过时失效。下面，即对这2类判定方法展开分析与讨论。 [BT5]1.1基于时间戳的绝对时效性判定
文献[13–18] 定义数据从上一次更新到本次使用的时间间隔为数据年龄（age（）），从不同角度定义了数据的时效性。文献[13]和文献[16]均假设数据有一个确定的保质期（ShelfLife（）），当数据的年龄大于保质期时认为数据过时失效。给定值A，文献[13]将其时效性定义为过期概率（ShelfLife（A）-age（A）>0），而文献[16]则直接使用age（A）作为数据的时效性，同时要求数据满足ShelfLife（A）-age（A）>0的约束。文献[14， 15]假设对于设定值A，A的时效性随时间流逝的减弱程度可以用时效性衰减函数decline（A）刻画，并进一步地定义A的时效性为exp（-decline（A）×age（A））。文献[17]与文献[16]类似，简单地使用数据年龄作为数据的时效性。并且，文献[18]又提出了一种基于模糊逻辑来推断时效性衰减函数的时效性判定方法，与前述工作相同，该方法也假定数据库有完整可用的时间戳来表示数据的存储时间。
文献[13–18] 提出的数据绝对时效性判定模型在数据库中有完整、清洁、可用的时间戳，且用户对数据的语义了解较为充分时可以有效地判定数据的时效性，但这些模型存在一定不足。具体阐析描述如下：
1）在实际应用中，数据库中不一定存在有效的时间戳，这就使得计算数据的年龄在多数情况下趋于困难。
2）上述工作均认为最近更新的数据就一定是最新的，这在实际应用中也不会一定成立，数据库管理人员可能只是用一个旧值替代了另一个旧值。
3）文献[13]和[16]均假设数据的保质期总是能被用户预先知晓，这在实际应用中也并不合理，而且文献[13]也没有确切给出该文献定义的数据时效性的计算方法。
4）文献[14， 15]要求数据的时效性减弱程度可以用decline（）刻画，却没有提出decline（）的获得方法，同时文献中也没有完整的理论分析来证实其时效性定义的合理性。文献[18]给出了decline（）的推断方法，却又需要额外的数据存储时间来辅助支持推断。
5）文献[16， 17]中仅用数据的年龄作为数据的时效性是远远不够的，不同数据表示的具体含义也各有不同，年齡长的数据其时效性也未必就会较差。
[BT5]1.2基于规则的绝对时效性判定
文献[19， 20]首次研究了在数据库中不存在时间戳时，如何使用规则来帮助判定数据的时效性。这些工作首次给出了不依赖于时间戳的数据时效性度量模型。该文献分3部分对数据的时效性来实现建模：时序关系（Currency Order）、时效约束（Currency Constraint）、不同数据源间的拷贝函数（Copy Function）。具体地，时序关系tiAtj表示元组ti在属性A上比元组tj旧。时效约束定义为一阶逻辑语句t1，…，tj： R（∧j∈[1，k]t1[EID]=tj[EID]∧φ→tuAtv），能够描述数据的语义信息。该约束表示如果一组元组t1，…，tj描述的实体相同（即EID相同），且满足特定条件φ，那么就有结论tuAtv。当数据来自于多个数据源时，拷贝函数R1[A→]←R2[B→]可以描述不同数据源间的依赖关系，如数据源R1的A→向量表示的属性可能就是拷贝自数据源R2的B→。
上述研究实现首次提出了时间戳不可用情况下的数据绝对时效性模型，其中虽然给出了较完整的数据时效性定义，但仍有许多问题没有解决：
1）没有给出定量地确定数据时效性的方法，仅能对给定的实体推测其属性值是否为最新。
2）没有给出任何能够判定数据库时效性的算法，而且上述工作定义的判定问题多为NP-完全或更难，这将给该模型进入实际工作带来相关困难，因此需要寻找快速的数据时效性判定算法。
3）提出的模型准确性依赖于时效约束，但是在实际应用中，用户很难给出完整正确的时效约束，该工作也没有讨论时效约束的获得方法。
4）提出的模型依赖于数据库中的冗余元组，当冗余元组不存在时，该模型就无法就直接使用。
5）文中提出的模型只能够针对不同属性值间的序关系进行建模，但是在实际应用中，数据时效性往往和具体的时间点有关，因此需要借助与时间点有关的数据语义来判定数据是否过时。
[BT5]1.3小结
综上可知，在数据绝对时效性的研究中，仍有如下关键问题亟待解决。首先应建立不依赖于时间戳和冗余元组的，能够定量度量数据绝对时效性的模型，该模型不仅要能够推断数据之间的时序关系，还要能够推断数据在给定时刻是否失效。而在此模型构建的基础上，还应给出多项式时间的数据时效性判定算法。
[BT4]2相对时效性判定
[BT5]2.1相对时效性判定方法研究
目前，相对时效性的研究工作非常有限，仅在分布式数据库环境下有类似的研究，即文献[21]。该工作研究数据分布式存储的环境下，查询结果的时效性度量，具体是将数据的更新建模为泊松过程，并计算当前查询能够用最新数据回答的概率，并以之作为数据的时效性。查询能够用最新数据回答的概率等于查询在数据过期之前发出的概率。文献[21]能够一定程度上解决相对时效性判定问题，但其不足却在于，只是考虑了数据分布式存储的情况，且假设2次更新的时间间隔长度的概率分布已知，而若数据的更新规律未知时则不可能知道更新时间间隔长度的概率分布，因此算法的使用也还未形成广泛拓展的新格局。
尽管相对时效性的研究工作迄今仍然限量可数，但是在数据可用性管理的其他领域，却也存在一些针对相对数据可用性的特征研究，这些进展成果对于相对时效性研究颇具启发意义。文献[22]是较早期的度量结果可信度的研究工作，通过将数据库构建为一个图，结点代表数据库中的元组，边表示元组间关系，边权值表示2个元组存在关系的概率。给定数据库以及特定关系R，查询要求返回那些有可能满足R的元组集合，而查询的结果可信度则定义为该结果满足R的概率。分析这一设计实现的不足可知，该文献本质上只是研究一个不确定数据库上的查询回答问题，并没有给出边权值的定义方法及来源，因此也未从本质上解决相对数据质量的判定问题。文献[23–25]研究不确定数据上查询结果的质量判定问题。文献[23， 24]均从结果二义性的角度出发，以信息熵的相反数为查询结果的质量度量指标，该指标取值范围为（-∞，0]，结果质量越接近于0，则其二义性越弱，质量越好。其中，文献[23]研究了不确定数据上的范围查询（Range Query）和最大值查询（MAX Query）的结果质量度量方法，文献[24]研究了不确定数据上的Top-k查询的结果质量度量方法。并且，文献[25]则重点结合了skyline和Top-k查询来对复杂情况下不确定数据的查询给出一个可信结果。现结合这部分工作可提出2点存在问题：首先，文中提出的度量在施于数据二义性时，本质上是考察查询的可能结果的数目，结果数越多，则二义性越大，但事实上，某些查询虽然会得到较多可能的查询结果，但各个查询结果之间呈现了显著可观的相似度，此时，将无法简单地断定该查询结果具有较高的二义性；其次，因为完全没有考虑查询在时间维度的特点，即使得文中提出的二义性的定义也无法直接用来解析数据的相对时效性。此外，文献[26–28]又深入研究了数据的相对完整性问题。文献[26， 27]研究了给定主数据（Master Data）Dm、约束集合V、查询Q以及数据库实例T时，T在Dm和V的约束下的相对完整性判定问题。文献[28]则代表性地给出了完整度度量模型，一方面可以表示数据集合中特定部分的完整性，称为表完整性（Table Completeness），另一方面也可以表示查询结果的完整性，称为查询完整性（Query Completeness）。这部分技术进展均能从不同角度判定数据相对完整性，但由于数据时效性与时序密切相关，则决定了这些工作仍然未能真正解决相对时效性判定问题。 [BT5]2.2小結
综上所述，目前相对数据质量判定方面的研究仍处在萌芽阶段，现有工作大多关注模型定义和问题复杂度，关键算法的研究相对匮乏。在数据相对时效性的研究中，必须考虑到查询与时序密切相关这一特点，根据查询在时间维度的特性，一方面给出合理的相对时效性的定量度量，另一方面也需给出判定相对时效性的迅捷有效的关键算法。
[BT4〗3结束语
本文讨论了当前数据时效性判定的关键理论和技术，分析了当前理论和技术的优点及不足。通过分析可知，当前数据质量领域对于时效性的研究已经有一些不同角度的较为成型的理论和方法，但综合看来此领域的研究仍然不成体系，解决时效性维度的质量问题需依次解决以下几个问题：绝对时效性判定模型、多项式时间的绝对时效性判定算法、相对时效性的形式化定义以及相应的相对时效性判定算法。在必要时，还需给出时效性修复策略以及判定和修复结果的整合策略。因此，数据时效性的研究任重而道远，仍需不断推进探索。
[HS1*2][HT5H]参考文献：[HT]
[WTBZ][ST6BZ][HT6SS][1] [ZK（#〗
[HJ*2]
REDMAN T C. The impact of poor data quality on the typical enterprise[J]. Commun. ACM， 1998， 41（2）：79-82.
[2] MILLER Jr D W， YEAST J D， EVANS R L. Missing prenatal records at a birth center： A communication problem quantified[C]//AMIA Annual Symposium Proceedings. Bethesda， MD， USA： American Medical Informatics Association， 2005：535.
[3] SWARTZ N. Gartner warns firms of ”dirty data”[J]. Information Management Journal， 2007， 41（3）：6-7.
[4] KOHN L T， CORRIGAN J M， DONALDSON M S， et al. To err is human： Building a Safer Health System[M]. Washington， D.C.： National Academies Press， 2000.
[5] Eckerson W. Data Warehousing Special Report： Data quality and the bottom line[R]. Washington： The Data Warehouse Institute， 2002.
[6] ENGLISH L P. Information quality management： The next frontier[C]//ASQ World Conference on Quality and Improvement Proceedings. Milwaukee， Wisconsin： American Society for Quality， 2001：529.
[7] Ben W， Schulz S. Credit card statistics， industry facts， debt statistics[EB/OL]. [2010-06-04]. http：//www.creditcards.com.
[8] Christopher S， Julie T. Enterprise information portals[R]. New York， NY， USA： Merrill Lynch， 1998.
[9] RAHM E， DO H H. Data cleaning： Problems and current approaches[J]. IEEE Data Eng. Bull.， 2000， 23（4）：3-13.
[10]FLESCA S， FURFARO F， GRECO S， et al. Querying and repairing inconsistent XML data[C]//Proceedings of Web Information Systems Engineering （WISE）. Berlin， Heidelberg，Germany： Springer， 2005：175-188.
[11]李建中， 刘显敏. 大数据的一个重要方面： 数据可用性[J]. 计算机研究与发展， 2015， 50（6）：1147-1162.
[12]ZHANG H， DIAO Y， IMMERMAN N. Recognizing patterns in streams with imprecise timestamps[J]. Information Systems， 2013， 38（8）：1187-1211.
[13]GRZ Q. An economicsdriven decision model for data quality improvement： A contribution to data currency[C]//AMCIS. Atlanta， Georgia， USA： AIS， 2011：1-8.
[14]HEINRICH B， KLIER M. Assessing data currency： A probabilistic approach[J]. Journal of Information Science， 2011， 37（1）：86-100. [15]HEINRICH B， KLIER M， KAISER M. A procedure to develop metrics for currency and its application in CRM[J]. Journal of Data and Information Quality （JDIQ）， 2009， 1（1）：5.
[16]CAPPIELLO C， FRANCALANCI C， PERNICI B. A model of data currency in multichannel financial architectures[C]//Proceedings of the seventh international conference on information quality. Cambridge，Massachusetts，USA：MIT’s Total Data Quality Management （TDQM）， 2002：106-118.
[17]CAPPIELLO C， FRANCALANCI C， PERNICI B. Time related factors of data accuracy， completeness， and currency in multichannel information systems[C]//Proceedings of Forum for short contributions at the 15th Conference on Advanced Information System Engineering. Berlin， Heidelberg，Germany： Springer， 2003：1-11.
[18]HEINRICH B， HRISTOVA D. A fuzzy metric for currency in the context of big data[C]//Proceedings of the 22nd European Conference on Information Systems. Atlanta， Georgia， USA： AIS， 2014：1-15.
[19]FAN W， GEERTS F， WIJSEN J. Determining the currency of data[J]. ACM Transactions on Database Systems （TODS）， 2012， 37（4）：25.
[20]FAN W， GEERTS F， TANG N， et al. Inferring data currency and consistency for conflict resolution[C]//The 29th International Conference on Data Engineering （ICDE）. New York， NY， USA： IEEE， 2013：470-481.
[21]Leung C H C， Wolfenden K. Analysis and optimisation of data currency and consistency in replicated distributed databases[J]. The Computer Journal， 1985， 28（5）：518–523.
[22]de ROUGEMONT M. The reliability of queries[C]//Proceedings of the fourteenth ACM SIGACTSIGMODSIGART symposium on Principles of database systems. New York， NY， USA： ACM， 1995：286-291.
[23]CHENG R， CHEN J， XIE X. Cleaning uncertain data with quality guarantees[J]. Proceedings of the VLDB Endowment， 2008， 1（1）：722-735.
[24]MO L， CHENG R， LI X， et al. Cleaning uncertain data for top-k queries[C]//The 29th International Conference on Data Engineering （ICDE）. New York， NY， USA： IEEE， 2013：134-145.
[25]NGUYEN H T H， CAO J. Trustworthy answers for top-k queries on uncertain Big Data in decision making[J]. Information Sciences， 2015， 318： 73-90.
[26]FAN W， GEERTS F. Relative information completeness[J]. ACM Transactions on Database Systems （TODS）， 2010， 35（4）：27.
[27]FAN W， GEERTS F. Capturing missing tuples and missing values[C]//Proceedings of the twentyninth ACM SIGMODSIGACTSIGART symposium on Principles of database systems. New York， NY， USA： ACM， 2010：169-178.
[28]RAZNIEWSKI S， NUTT W. Completeness of queries over incomplete databases[J]. Proc. VLDB Endow， 2011， 4（11）：749-760.[ZK）]
关键词：数据质量； 数据时效性； 时效性判定
中图分类号： TP391.41
文献标志码：A
文章编号： 2095-2163（2016）06-0072-04
0引言
随着大数据时代的到来，数据的“量”在飞速增长，但与此同时，数据的“质”的下降也成为了不可忽视的问题。多家机构的统计数据表明，当前各行各业中信息的可用性（即数据质量）问题亟待解决。在美国，企业中有1%～30%的数据存在各种质量问题[1]，医疗中有13.6%～81%的组成是不完整、或过时数据[2]。同时，根据国际著名科技咨询机构Gartner的调查结果，即使是在那些著名企业，如全球财富1 000强的企业中，也有超过25%的企业其信息系统中的关键信息不正确或不准确[3]。如果不能够及时有效地针对这些数据质量问题提供全面完整解决，就必将会对国民生活和企业决策形成不可预知的恶劣影响。事实上，已有多次调查结果陆续表明，如上的数据质量问题每年都会在全球范围内造成重大不良效应后果：数据质量问题在美国引发的医疗事故所导致的死亡人数高达98 000名，约等于总医疗事故致死人数的一半[4]；数据过时和错误将使得美国工业企业损失高达6 110亿美元，这一数值几乎可占美国GDP的6%[5]；标价错误还会导致美国零售业损失25亿美元[6]；数据中的不一致错误则会导致信用卡欺诈問题的深度隐藏，这在2006年曾造成48亿美元的财产损失[7]。由此，根据推算，劣质数据的处理需要花费30%～80%的开发时间和预算[8]，进而数据质量问题通常给企业增加获得同等产值约10%～20%的成本[9]。这也随即推动了数据质量工具市场的飞速增长，甚至远超IT行业的平均增长率[10]。劣质数据无时无刻都将通过网络在不同数据源之间传播，因此对数据可用性的研究已经成为数据管理领域中的首要问题内容之一。近几年来，数据库领域的顶级国际会议及期刊每年都会达成和开展多项关系着数据质量方面的相关议程和研究工作。
一般说来，要从下述5个维度来保证数据可用性[11]。现作如下论述：
1）时效性。保证数据与时俱进，不陈旧过时。例如，某数据库中的用户地址在2010年是正确的，但在2011年未必正确，即存在过时数据。
2） 一致性。保证数据不违背某些特定约束。例如，记录（邮编=“150000”，城市=“上海”）就违背了邮编和城市的对应关系，因为150000是哈尔滨的邮编、而非上海邮编。
3） 完整性。保证数据不存在缺失。例如，医疗数据库遗失某患者病史就会导致数据不完整，进而可能妨碍医生正确诊断病情。
4） 精确性。保证数据能够准确地描述对应实体。例如，哈尔滨全市总面积约为5.384万平方公里，但数据库中记录却为5万平方公里，这虽在宏观来看是合理的，但不精确。精确性和一致性并不相同，一致的信息也可能含有误差，即未必精确。
5） 实体同一性。保证描述同一实体的数据在不同数据源上是统一的。例如，可以通过对比个人信息来判断信用卡的使用者和持有者是否为同一人，从而防止欺诈。
在数据可用性的5个维度中，数据时效性的作用地位至关重要。据统计，在商业和医疗信息数据库中，约有2%的客户信息会在一个月内变得陈旧失效[5]，如果这些数据未获修复，那么在2年内，就将有近50%的记录会因为过时而使其可用性受到影响，而过时数据将会导致严重后果。在企业决策时，企业往往会因为使用了陈旧的数据而做出错误的决策，而在日常生活中，银行可能会将信用卡账单寄送到持有人搬家前的旧地址。同时，有相当一部分数据的不一致、不精确、不完整等都是由数据过时失效引起的。例如，银行未能及时更新客户的地址信息将会导致同一客户的住址和邮编难以匹配；随着人口的增长和流动，数据库中各城市的人口数会因为过时变得不再精确；新入学的学生的学籍信息未及时录入会导致记录学生信息的数据库无法趋于完整。因此，确保数据的时效性已成为热点与焦点。
判定一个给定的数据集合的时效性是确保数据时效性的第一步。只是数据时效性的判定却并非易事。同一记录的不同属性随时间变化的频率不同，使得同一记录的不同属性的新旧程度也会不同，这即使得数据时效性判定问题的研究面临严峻挑战。首先，数据库中通常没有完整、可用、精确的时间戳[12]，此时就需要建立一个不依赖于时间戳的数据时效性度量模型。使用该模型，可以对一个给定数据库，形式化地表示单个数据项、元组以及数据库整体的时效性（称为绝对时效性），并定量地判定其时效性。其次，数据库的绝对时效性可能无法直接判定，又或者判定结果不能有效地表达用户需求。为此，则需要针对该数据库上的常用查询或用户的特定需求，设计数据库的相对时效性度量模型。该模型能够度量数据库中较重要部分的时效性，如某些重要查询的提供结果的时效性，或者用户最常使用的数据集合的时效性。
基于如上的论证分析，本文将综述当前数据时效性判定的关键理论和技术，包括数据的绝对时效性和相对时效性判定模型，数据时效性修复算法及查询相关的数据时效性研究等。
[BT4]1绝对时效性判定
当前的时效性判定工作大致可以分为2类：基于时间戳的时效性判定和基于规则的时效性判定。其中，基于时间戳的时效性判定要求数据库中对每个待判定的值都存有完整、清洁、可用的时间戳，通常是事务时间，根据事务时间和数值有效性的衰减来判定当前值是否过时失效，即推断有效时间。该方法的优点是能够对于给定的时间点，判定数据在该时刻过时失效，但缺点却在于其需要大量的辅助信息，如每个值的事务时间和每个值的有效性衰减规律。由于各种属性的不同特性，这些辅助信息在真实应用中很难获得精炼提取，因此基于时间戳的时效性判定方法的适用范围随之受到一定限制。为了克服基于时间戳的方法的缺点与不足，基于规则的方法相应地据此而获提出。这类方法只需要根据少量的由领域知识得到的时效规则，就可以判断描述同一实体的不同属性值的时序关系，从而判定哪些值是过时失效的。这类方法所需的辅助信息大大减少，但其缺点却表现在当前的基于规则的方法仍不能判定某个值在给定的时间点是否过时失效。下面，即对这2类判定方法展开分析与讨论。 [BT5]1.1基于时间戳的绝对时效性判定
文献[13–18] 定义数据从上一次更新到本次使用的时间间隔为数据年龄（age（）），从不同角度定义了数据的时效性。文献[13]和文献[16]均假设数据有一个确定的保质期（ShelfLife（）），当数据的年龄大于保质期时认为数据过时失效。给定值A，文献[13]将其时效性定义为过期概率（ShelfLife（A）-age（A）>0），而文献[16]则直接使用age（A）作为数据的时效性，同时要求数据满足ShelfLife（A）-age（A）>0的约束。文献[14， 15]假设对于设定值A，A的时效性随时间流逝的减弱程度可以用时效性衰减函数decline（A）刻画，并进一步地定义A的时效性为exp（-decline（A）×age（A））。文献[17]与文献[16]类似，简单地使用数据年龄作为数据的时效性。并且，文献[18]又提出了一种基于模糊逻辑来推断时效性衰减函数的时效性判定方法，与前述工作相同，该方法也假定数据库有完整可用的时间戳来表示数据的存储时间。
文献[13–18] 提出的数据绝对时效性判定模型在数据库中有完整、清洁、可用的时间戳，且用户对数据的语义了解较为充分时可以有效地判定数据的时效性，但这些模型存在一定不足。具体阐析描述如下：
1）在实际应用中，数据库中不一定存在有效的时间戳，这就使得计算数据的年龄在多数情况下趋于困难。
2）上述工作均认为最近更新的数据就一定是最新的，这在实际应用中也不会一定成立，数据库管理人员可能只是用一个旧值替代了另一个旧值。
3）文献[13]和[16]均假设数据的保质期总是能被用户预先知晓，这在实际应用中也并不合理，而且文献[13]也没有确切给出该文献定义的数据时效性的计算方法。
4）文献[14， 15]要求数据的时效性减弱程度可以用decline（）刻画，却没有提出decline（）的获得方法，同时文献中也没有完整的理论分析来证实其时效性定义的合理性。文献[18]给出了decline（）的推断方法，却又需要额外的数据存储时间来辅助支持推断。
5）文献[16， 17]中仅用数据的年龄作为数据的时效性是远远不够的，不同数据表示的具体含义也各有不同，年齡长的数据其时效性也未必就会较差。
[BT5]1.2基于规则的绝对时效性判定
文献[19， 20]首次研究了在数据库中不存在时间戳时，如何使用规则来帮助判定数据的时效性。这些工作首次给出了不依赖于时间戳的数据时效性度量模型。该文献分3部分对数据的时效性来实现建模：时序关系（Currency Order）、时效约束（Currency Constraint）、不同数据源间的拷贝函数（Copy Function）。具体地，时序关系tiAtj表示元组ti在属性A上比元组tj旧。时效约束定义为一阶逻辑语句t1，…，tj： R（∧j∈[1，k]t1[EID]=tj[EID]∧φ→tuAtv），能够描述数据的语义信息。该约束表示如果一组元组t1，…，tj描述的实体相同（即EID相同），且满足特定条件φ，那么就有结论tuAtv。当数据来自于多个数据源时，拷贝函数R1[A→]←R2[B→]可以描述不同数据源间的依赖关系，如数据源R1的A→向量表示的属性可能就是拷贝自数据源R2的B→。
上述研究实现首次提出了时间戳不可用情况下的数据绝对时效性模型，其中虽然给出了较完整的数据时效性定义，但仍有许多问题没有解决：
1）没有给出定量地确定数据时效性的方法，仅能对给定的实体推测其属性值是否为最新。
2）没有给出任何能够判定数据库时效性的算法，而且上述工作定义的判定问题多为NP-完全或更难，这将给该模型进入实际工作带来相关困难，因此需要寻找快速的数据时效性判定算法。
3）提出的模型准确性依赖于时效约束，但是在实际应用中，用户很难给出完整正确的时效约束，该工作也没有讨论时效约束的获得方法。
4）提出的模型依赖于数据库中的冗余元组，当冗余元组不存在时，该模型就无法就直接使用。
5）文中提出的模型只能够针对不同属性值间的序关系进行建模，但是在实际应用中，数据时效性往往和具体的时间点有关，因此需要借助与时间点有关的数据语义来判定数据是否过时。
[BT5]1.3小结
综上可知，在数据绝对时效性的研究中，仍有如下关键问题亟待解决。首先应建立不依赖于时间戳和冗余元组的，能够定量度量数据绝对时效性的模型，该模型不仅要能够推断数据之间的时序关系，还要能够推断数据在给定时刻是否失效。而在此模型构建的基础上，还应给出多项式时间的数据时效性判定算法。
[BT4]2相对时效性判定
[BT5]2.1相对时效性判定方法研究
目前，相对时效性的研究工作非常有限，仅在分布式数据库环境下有类似的研究，即文献[21]。该工作研究数据分布式存储的环境下，查询结果的时效性度量，具体是将数据的更新建模为泊松过程，并计算当前查询能够用最新数据回答的概率，并以之作为数据的时效性。查询能够用最新数据回答的概率等于查询在数据过期之前发出的概率。文献[21]能够一定程度上解决相对时效性判定问题，但其不足却在于，只是考虑了数据分布式存储的情况，且假设2次更新的时间间隔长度的概率分布已知，而若数据的更新规律未知时则不可能知道更新时间间隔长度的概率分布，因此算法的使用也还未形成广泛拓展的新格局。
尽管相对时效性的研究工作迄今仍然限量可数，但是在数据可用性管理的其他领域，却也存在一些针对相对数据可用性的特征研究，这些进展成果对于相对时效性研究颇具启发意义。文献[22]是较早期的度量结果可信度的研究工作，通过将数据库构建为一个图，结点代表数据库中的元组，边表示元组间关系，边权值表示2个元组存在关系的概率。给定数据库以及特定关系R，查询要求返回那些有可能满足R的元组集合，而查询的结果可信度则定义为该结果满足R的概率。分析这一设计实现的不足可知，该文献本质上只是研究一个不确定数据库上的查询回答问题，并没有给出边权值的定义方法及来源，因此也未从本质上解决相对数据质量的判定问题。文献[23–25]研究不确定数据上查询结果的质量判定问题。文献[23， 24]均从结果二义性的角度出发，以信息熵的相反数为查询结果的质量度量指标，该指标取值范围为（-∞，0]，结果质量越接近于0，则其二义性越弱，质量越好。其中，文献[23]研究了不确定数据上的范围查询（Range Query）和最大值查询（MAX Query）的结果质量度量方法，文献[24]研究了不确定数据上的Top-k查询的结果质量度量方法。并且，文献[25]则重点结合了skyline和Top-k查询来对复杂情况下不确定数据的查询给出一个可信结果。现结合这部分工作可提出2点存在问题：首先，文中提出的度量在施于数据二义性时，本质上是考察查询的可能结果的数目，结果数越多，则二义性越大，但事实上，某些查询虽然会得到较多可能的查询结果，但各个查询结果之间呈现了显著可观的相似度，此时，将无法简单地断定该查询结果具有较高的二义性；其次，因为完全没有考虑查询在时间维度的特点，即使得文中提出的二义性的定义也无法直接用来解析数据的相对时效性。此外，文献[26–28]又深入研究了数据的相对完整性问题。文献[26， 27]研究了给定主数据（Master Data）Dm、约束集合V、查询Q以及数据库实例T时，T在Dm和V的约束下的相对完整性判定问题。文献[28]则代表性地给出了完整度度量模型，一方面可以表示数据集合中特定部分的完整性，称为表完整性（Table Completeness），另一方面也可以表示查询结果的完整性，称为查询完整性（Query Completeness）。这部分技术进展均能从不同角度判定数据相对完整性，但由于数据时效性与时序密切相关，则决定了这些工作仍然未能真正解决相对时效性判定问题。 [BT5]2.2小結
综上所述，目前相对数据质量判定方面的研究仍处在萌芽阶段，现有工作大多关注模型定义和问题复杂度，关键算法的研究相对匮乏。在数据相对时效性的研究中，必须考虑到查询与时序密切相关这一特点，根据查询在时间维度的特性，一方面给出合理的相对时效性的定量度量，另一方面也需给出判定相对时效性的迅捷有效的关键算法。
[BT4〗3结束语
本文讨论了当前数据时效性判定的关键理论和技术，分析了当前理论和技术的优点及不足。通过分析可知，当前数据质量领域对于时效性的研究已经有一些不同角度的较为成型的理论和方法，但综合看来此领域的研究仍然不成体系，解决时效性维度的质量问题需依次解决以下几个问题：绝对时效性判定模型、多项式时间的绝对时效性判定算法、相对时效性的形式化定义以及相应的相对时效性判定算法。在必要时，还需给出时效性修复策略以及判定和修复结果的整合策略。因此，数据时效性的研究任重而道远，仍需不断推进探索。
[HS1*2][HT5H]参考文献：[HT]
[WTBZ][ST6BZ][HT6SS][1] [ZK（#〗
[HJ*2]
REDMAN T C. The impact of poor data quality on the typical enterprise[J]. Commun. ACM， 1998， 41（2）：79-82.
[2] MILLER Jr D W， YEAST J D， EVANS R L. Missing prenatal records at a birth center： A communication problem quantified[C]//AMIA Annual Symposium Proceedings. Bethesda， MD， USA： American Medical Informatics Association， 2005：535.
[3] SWARTZ N. Gartner warns firms of ”dirty data”[J]. Information Management Journal， 2007， 41（3）：6-7.
[4] KOHN L T， CORRIGAN J M， DONALDSON M S， et al. To err is human： Building a Safer Health System[M]. Washington， D.C.： National Academies Press， 2000.
[5] Eckerson W. Data Warehousing Special Report： Data quality and the bottom line[R]. Washington： The Data Warehouse Institute， 2002.
[6] ENGLISH L P. Information quality management： The next frontier[C]//ASQ World Conference on Quality and Improvement Proceedings. Milwaukee， Wisconsin： American Society for Quality， 2001：529.
[7] Ben W， Schulz S. Credit card statistics， industry facts， debt statistics[EB/OL]. [2010-06-04]. http：//www.creditcards.com.
[8] Christopher S， Julie T. Enterprise information portals[R]. New York， NY， USA： Merrill Lynch， 1998.
[9] RAHM E， DO H H. Data cleaning： Problems and current approaches[J]. IEEE Data Eng. Bull.， 2000， 23（4）：3-13.
[10]FLESCA S， FURFARO F， GRECO S， et al. Querying and repairing inconsistent XML data[C]//Proceedings of Web Information Systems Engineering （WISE）. Berlin， Heidelberg，Germany： Springer， 2005：175-188.
[11]李建中， 刘显敏. 大数据的一个重要方面： 数据可用性[J]. 计算机研究与发展， 2015， 50（6）：1147-1162.
[12]ZHANG H， DIAO Y， IMMERMAN N. Recognizing patterns in streams with imprecise timestamps[J]. Information Systems， 2013， 38（8）：1187-1211.
[13]GRZ Q. An economicsdriven decision model for data quality improvement： A contribution to data currency[C]//AMCIS. Atlanta， Georgia， USA： AIS， 2011：1-8.
[14]HEINRICH B， KLIER M. Assessing data currency： A probabilistic approach[J]. Journal of Information Science， 2011， 37（1）：86-100. [15]HEINRICH B， KLIER M， KAISER M. A procedure to develop metrics for currency and its application in CRM[J]. Journal of Data and Information Quality （JDIQ）， 2009， 1（1）：5.
[16]CAPPIELLO C， FRANCALANCI C， PERNICI B. A model of data currency in multichannel financial architectures[C]//Proceedings of the seventh international conference on information quality. Cambridge，Massachusetts，USA：MIT’s Total Data Quality Management （TDQM）， 2002：106-118.
[17]CAPPIELLO C， FRANCALANCI C， PERNICI B. Time related factors of data accuracy， completeness， and currency in multichannel information systems[C]//Proceedings of Forum for short contributions at the 15th Conference on Advanced Information System Engineering. Berlin， Heidelberg，Germany： Springer， 2003：1-11.
[18]HEINRICH B， HRISTOVA D. A fuzzy metric for currency in the context of big data[C]//Proceedings of the 22nd European Conference on Information Systems. Atlanta， Georgia， USA： AIS， 2014：1-15.
[19]FAN W， GEERTS F， WIJSEN J. Determining the currency of data[J]. ACM Transactions on Database Systems （TODS）， 2012， 37（4）：25.
[20]FAN W， GEERTS F， TANG N， et al. Inferring data currency and consistency for conflict resolution[C]//The 29th International Conference on Data Engineering （ICDE）. New York， NY， USA： IEEE， 2013：470-481.
[21]Leung C H C， Wolfenden K. Analysis and optimisation of data currency and consistency in replicated distributed databases[J]. The Computer Journal， 1985， 28（5）：518–523.
[22]de ROUGEMONT M. The reliability of queries[C]//Proceedings of the fourteenth ACM SIGACTSIGMODSIGART symposium on Principles of database systems. New York， NY， USA： ACM， 1995：286-291.
[23]CHENG R， CHEN J， XIE X. Cleaning uncertain data with quality guarantees[J]. Proceedings of the VLDB Endowment， 2008， 1（1）：722-735.
[24]MO L， CHENG R， LI X， et al. Cleaning uncertain data for top-k queries[C]//The 29th International Conference on Data Engineering （ICDE）. New York， NY， USA： IEEE， 2013：134-145.
[25]NGUYEN H T H， CAO J. Trustworthy answers for top-k queries on uncertain Big Data in decision making[J]. Information Sciences， 2015， 318： 73-90.
[26]FAN W， GEERTS F. Relative information completeness[J]. ACM Transactions on Database Systems （TODS）， 2010， 35（4）：27.
[27]FAN W， GEERTS F. Capturing missing tuples and missing values[C]//Proceedings of the twentyninth ACM SIGMODSIGACTSIGART symposium on Principles of database systems. New York， NY， USA： ACM， 2010：169-178.
[28]RAZNIEWSKI S， NUTT W. Completeness of queries over incomplete databases[J]. Proc. VLDB Endow， 2011， 4（11）：749-760.[ZK）]