数据时效性判定问题的求解算法  

Evaluation of Data Currency

作　　者：李默涵[1] 李建中[1] 高宏[1] 

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《计算机学报》2012年第11期2348-2360,共13页Chinese Journal of Computers

基　　金：国家"九七三"重点基础研究发展规划项目基金(2012CB316202)资助~~

摘　　要：数据的时效性问题是影响数据质量的重要因素之一.时效性差的数据会对企业决策和人们的日常生活带来许多不利影响,这使得判定数据的时效性成为必要.许多应用数据库中都没有完整、清洁、可用的时间戳,从而导致数据时效性的判定非常困难.冗余记录和时效约束能够在时间戳缺失的情况下有效地辅助恢复数据的时序关系,因而能够帮助数据时效性的判定.文中研究包含冗余记录的集合在给定时效约束下的时效性判定问题,并首次提出了时效性判定问题的求解算法.首先,文中定义了查询相关时效性和用户相关时效性.在判定查询相关时效性时,文中将查询归结为最新值查询和时效序列查询两类,并分别根据两类查询的特点,对每类查询定义了查询结果时效性和平均时效性.然后,文中提出了时效图的概念.利用时效图,文中给出了查询相关时效性和用户相关时效性判定问题的求解算法.最后给出了真实数据和虚拟数据上的实验结果,验证了文中算法较高的执行效率,并分析了各个参数对算法的影响.The problem of data currency is one of the most important issues in the area of data quality. The data with poor currency can badly influence the business decision and people＇s daily life. That highlights the needs of the evaluation of data currency. A big challenge of data currency evaluation is absence of valid timestamps. However, redundant records and currency constraints can recover the currency orders of data without using timestamps thus can be helpful when evaluating data currency. This paper investigates the methods of currency evaluation with redundant records and currency constraints. First, this paper defines data currency relative to queries and data currency relative to users. When evaluating data currency relative to queries, all the queries are classified as 2 categories, which are Current Value Query and Currency Sequence Query. For each query category, this paper discusses the definition of the currency of query result and the average currency of the entire query category. Second, the definition of currency graph is proposed in this paper. The methods of evaluating data currency relative to queries and users using currency graphs are presents. Experimental results on real and synthetic datasets are given to analyze the effect of parameters and the efficiency of algorithms.

关 键 词：数据质量 数据时效性 相关时效性 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]