数据时效性判定关键理论和技术-精品文档资料

1、数据时效性判定：关键理论和技术0引言随着大数据时代勺到来，数据勺“量”在飞速增长，但与此同时，数 据勺“质”勺下降也成为了不可忽视勺问题。多家机构的统计数据表明，当 前各行各业中信息的可用性（即数据质量）问题亟待解决。在美国，企业中 有1%八30%勺数据存在各种质量问题1，医疗中有13.6%81%勺组成是不完整、或过时数据2。同时，根据国际著名科技咨询机构Gartner勺调查结果，即使是在那些著 名企业，如全球财富1 000强勺企业中，也有超过25%勺企业其信息系统中勺关键信息不正确或不准确3。如果不能够及时有 效地针对这些数据质量问题提供全面完整解决，就必将 会对国民生活和企业 决策形成不可

2、预知勺恶劣影响。事实上，已有多次调查结果陆续表明，如 上勺数据质量问题每年都会在全球 范围内造成重大不良效应后果：数据质量 问题在美国引发勺医疗 事故所导致勺死亡人数高达98 000名，约等于总医 疗事故致死人数勺一半4；数据过时和错误将使得美国工业企业损失高 达6 110亿美元，这一数值几乎可占美国GDP勺6%5；标价错误还会导致美国零售业损失25亿美元6；数据中勺不一致错误则会导致信 用卡欺诈题勺深度隐藏，这在2006年曾造成48亿美元勺财产损失7。由此，根据推算，劣质数据勺处理需要花费30%80% 勺开发时间和预算8，进而数据质量问题通常给企业增加获得同等产值约10%-20%勺成本9。这

3、也随即推动了数据质量工 具市场的飞速 增长，甚至远超IT行业的平均增长率10。劣质数据无时无刻都将通过 网络在不同数据源之间传播，因此对数据 可用性勺研究已经成为数据管理领 域中勺首要问题内容之一。近 几年来，数据库领域勺顶级国际会议及期刊每 年都会达成和开展多项关系着数据质量方面勺相关议程和研究工作。一般说来，要从下述5个维度来保证数据可用性11。现作 如下论 述：1 ）时效性。保证数据与时俱进，不陈旧过时。例如，某数据库中勺用 户地址在2010年是正确勺，但在2011年未必正确，即存在过时数据。2）致性。保证数据不违背某些特定约束。例如，记录（邮编 =“150000”，城市二“上海”）就违

4、背了邮编和城市勺对应关 系，因为 150000是哈尔滨勺邮编、而非上海邮编。3）完整性。保证数据不存在缺失。例如，医疗数据库遗失某患者病史 就会导致数据不完整，进而可能妨碍医生正确诊断病情。4）精确性。保证数据能够准确地描述对应实体。例如，哈尔滨全市总 面积约为5.384万平方公里，但数据库中记录却为5万平方公里，这虽在宏观来看是合理勺，但不精确。精确性和一致性并不相 同，一致勺信息也可能含有误差，即未必精确。5）实体同一性。保证描述同一实体勺数据在不同数据源上是统一的。例如，可以通过对比个人信息来判断信用卡的使用者和持有者是 否为同一人，从而防止欺诈。在数据可用性的5个维度中，数据时效性的作

5、用地位至关重要。据统计，在商业和医疗信息数据库中，约有2%的客户信息会在一个月内变得陈旧失效5，如果这些数据未获修复，那么在2年内，就将有近50%的记录会因为过时而使其可用性受到影响，而过时数据将会导致严重后果。在企业决策时，企业往往会因为使用了 陈旧的数据而做出错误的决策，而在日常生活中，银行可能会将信用卡账单寄送到持有人搬家前的旧地址。同时，有相当一部分数据的不一致、不精确、不完整等都是由数据过时失效引起 的。例如，银行未能及时更新客户的地址信息将会导致同一客户的住址和邮编难以匹配；随着人口的增长和流动，数据库中各城市的人口数会因为过时变得不再精确；新入学的学生的学籍信息未及时录入会导致记

6、录学生信息的数据库无法趋于完整。因此，确保数据的时效性已成为热点与焦点。判定一个给定的数据集合的时效性是确保数据时效性的第迪只是数据时效性的判定却并非易事。同一记录的不同属性随时间变 步。化的频率不同，使得同一记录的不同属性的新旧程度也会不同，这即使得数据时效性判定问题的研究面临严峻挑战。首 先，数据库中通常没有完整、可用、精确的时间戳12，此时就需要建立一个不依赖于时间戳的数据时效性度量模型。使用该模型，可以对一个给定数据库，形式化地表示单个数据项、元组以及数据库整体的时效性（称为绝对时效性），并定量地判定其时效性。其 次，数据库的绝对时效性可能无法直接判定，又或者判定结果不能有效地表 达用

7、户需求。为此，则需要针对该数据库上 的常用查询或用户的特定需求，设计数据库的相对时效性度量模型。该模型能够度量数据库中较重要部分的时效性，如某些重要查询的提供结果的时效性，或者用户最常使用的数据集合的时效性。基于如上的论证分析，本文将综述当前数据时效性判定的关键理论和 技术，包括数据的绝对时效性和相对时效性判定模型，数据时效性修复算法 及查询相关的数据时效性研究等。BT41绝对时效性判定当前的时效性判定工作大致可以分为2类：基于时间戳的时效性判定 和基于规则的时效性判定。其中，基于时间戳的时效性判定要求数据库中 对每个待判定的值都存有完整、清洁、可用的时间戳，通常是事务时 间，根据事务时间和数

8、值有效性的衰减来判定当前值是否过时失效，即推 断有效时间。该方法的优点是能够对于给定的时间点，判定数据在该时刻 过时失效，但缺点却在于其需要大量的辅助信息，如每个值的事务时间和 每个值的有效性衰减规律。由于各种属性的不同特性，这些辅助信息在真 实应用中很难获得精炼提取，因此基于时间戳的时效性判定方法的适用范 围随之受到一定限制。为了克服基于时间戳的方法的缺点与不足，基于规 则的方法相应地据此而获提出。这类方法只需要根据少量的由领域知识得到的时效规则，就可以判断描述同一实体的不同属 性值的时序关系，从而判定哪些值是过时失效的。这类方法所需的辅助信 息大大减少，但其缺点却表现在当前的基于规 则的方

9、法仍不能判定某个值在给定的时间点是否过时失效。下面，即对这2类判定方法展开分析与讨论。BT51.1基于时间戳的绝对时效性判定文献13?C18定义数据从上一次更新到本次使用的时间间隔为数据 年龄(age ()，从不同角度定义了数据的时效性。文献13和文献16均假设数据有一个确定的保质期ShelfLife ()，当数据的年龄大于保质期时认为数据过时失效。给定值 A文献13将其时效性定义为过期概率(ShelfLife(A) -age (A) 0)，而文献16则直接使用age (A)作为数据的时效性，同时要求数据满足ShelfLife(A) -age( A) 0的约束。文献14， 15假设对于设定值A

10、，A的时效性随时间流逝的减弱程度可以用时效性衰减函数decli ne (A)刻画，并进步地定义A的时效性为exp (-decli ne(A)x age (A)。文献17与文献16类似，简单地使用数据年龄作为数据的时效性。并 且，文献18又提出了一种基于模糊逻辑来推断时效性衰减函数的时效 性判定方法，与前述工作相同，该方法也假定数据库有完整可用的时间戳 来表示数据的存储时间。文献13?C18提出的数据绝对时效性判定模型在数据库中有完整、 清洁、可用的时间戳，且用户对数据的语义了解较为充分时可以有效地判定 数据的时效性，但这些模型存在一定不足。具体阐析描述如下：在实际应用中，数据库中不一定存在有效

11、的时间戳，这就使得计算数据的年龄在多数情况下趋于困难。上述工作均认为最近更新的数据就一定是最新的，这在实际应用中也不会一定成立，数据库管理人员可能只是用一个旧值替代了 另一个旧值。3）文献13和16均假设数据的保质期总是能被用户预先知晓， 这在实际应用中也并不合理，而且文献13也没有确切给出该文献定义 的数据时效性的计算方法。4）文献14，15要求数据的时效性减弱程度可以用decline）刻画，却没有提出decline （）的获得方法，同时文献中也没有完整 的理论分析来证实其时效性定义的合理性。文献18给出了 decline （）的推断方法，却又需要额外的数据存储时间来辅助支 持推断。5）文献

12、16， 17中仅用数据的年龄作为数据的时效性是远远不够的，不同数据表示的具体含义也各有不同，年？g长的数据其时效性也未必就会较差。BT51.2基于规则的绝对时效性判定文献19，20首次研究了在数据库中不存在时间戳时，如何使用 规则来帮助判定数据的时效性。这些工作首次给出了不依赖于时间戳的数 据时效性度量模型。该文献分3部分对数据的时效性来实现建模：时序关系（Currency Order ）、时效约束Currency Constraint）、不同数据源间的拷贝函数（CopyFunction）。具体地，时序关系tiAtj表示元组ti在属性A上 比元组 tj旧。时效约束定义为一阶逻辑语句t1，tj

13、: R(A j 1 , kt1EID=tjEID A - tuAtv )，能够描述数据的语义信息。该约束表示如果一组元组t1，tj描述的实体相同（即EID相同），且满足特定条件，那么就有结论tuAtv。当数据来自于多个数据源时，拷贝函数R1Af jR2Bf 可以描述不同数据源间的依赖关系，如数据源R1的A-向量表示的属性可能就是拷贝自数据源R2的4。上述研究实现首次提出了时间戳不可用情况下的数据绝对 时效性模 型，其中虽然给出了较完整的数据时效性定义，但仍有许多问题没有解 决：1）没有给出定量地确定数据时效性的方法，仅能对给定的 实体推测其属性值是否为最新。2）没有给出任何能够判定数据库时效性

14、的算法，而且上述 工作定义的判定问题多为NP-完全或更难，这将给该模型进入实 际工作带来相关困难，因此需要寻找快速的数据时效性判定算法。3）提出的模型准确性依赖于时效约束，但是在实际应用中，用户很 难给出完整正确的时效约束，该工作也没有讨论时效约束 的获得方法。4）提出的模型依赖于数据库中的冗余元组，当冗余元组不 存在时，该模型就无法就直接使用。5）文中提出的模型只能够针对不同属性值间的序关系进行建模，但是在实际应用中，数据时效性往往和具体的时间点有关，因此需要借助与时间点有关的数据语义来判定数据是否过时。BT51.3 小结综上可知，在数据绝对时效性的研究中，仍有如下关键问题亟待解 决。首先应

15、建立不依赖于时间戳和冗余元组的，能够定量度量数据绝对时 效性的模型，该模型不仅要能够推断数据之间的时序关系，还要能够推断 数据在给定时刻是否失效。而在此模型构建的基础上，还应给出多项式时 间的数据时效性判定算法。BT42相对时效性判定BT52.1相对时效性判定方法研究目前，相对时效性的研究工作非常有限，仅在分布式数据库环境下有 类似的研究，即文献21。该工作研究数据分布式存储的环境下，查 询结果的时效性度量，具体是将数据的更新建模为泊松过程，并计算当前 查询能够用最新数据回答的概率，并以之作为数据的时效性。查询能够用 最新数据回答的概率等于查询在数据过期之前发出的概率。文献21能 够一定程度上

16、解决相对时 效性判定问题，但其不足却在于，只是考虑了数 据分布式存储的情况，且假设2次更新的时间间隔长度的概率分布已知， 而若数 据的更新规律未知时则不可能知道更新时间间隔长度的概率分布， 因此算法的使用也还未形成广泛拓展的新格局。尽管相对时效性的研究工作迄今仍然限量可数，但是在数据 可用性管 理的其他领域，却也存在一些针对相对数据可用性的特 征研究，这些进展 成果对于相对时效性研究颇具启发意义。文献22是较早期的度量结果可信度的研究工作，通过将数据库构建为一个 图，结点代表数据库中的元组，边表示元组间关系，边权值表示2个元组存在关系的概率。给定数据库以及特定关系R，查询要求返回那些有可能满足

17、R的元组集合，而查询的结果可信度则定义为该结果满足R的概率。分析这一设计实现的不足可知，该文献本 质上只是研究一个不确定数据库上的查询回答问题，并没有给出边权值的定 义方法及来源，因此也未从本质上解决相对数据质量的判定问题。文献 23?C25研究不确定数据上查 询结果的质量判定问题。文献23，24均 从结果二义性的角度出发，以信息熵的相反数为查询结果的质量度量指标， 该指标取值范围为（-0，结果质量越接近于0,则其二义性越弱，质量越好。其中，文献23研究了不确定数据上的范围查询(Range Query)和最大值查询(MAXQuery)的结果质量度量方法，文献24研究了不确定数据上的Top-k查

18、询的结果质量度量方法。并且，文献25则重点结合了 skyline和Top-k查询来对 复杂情况下 不确定数据的查询给出一个可信结果。现结合这部分工作可提出2点存在 问题：首先，文中提出的度量在施于数据二义性时，本质上是考察查询的 可能结果的数目，结果数越多，则二义性越大，但事实上，某些查询虽然会得到较多可能的查询结果，但各 个查询结果之间呈现了显著可观的相似度，此时，将无法简单地断定该查询 结果具有较高的二义性；其次，因为完全没有考虑查询在时间维度的特 点，即使得文中提出的二义性的定义也无法直接用来解析数据的相对时效 性。此外，文献26?C28又深入研究了数据的相对完整性问题。文献26，27研究了给 定主数 据(Master Data ) Dm约束集合V查询Q以及数据库实例T时，T在Dm和V的约束下的相对完整性