基于数据质量规则的缺失结果解释约减  

Reducing Explanations of Non-Answers Using Data Quality Rules

作　　者：张奥千 宋韶旭[2] 王建民[3] 

机构地区：[1]清华大学软件学院,北京100084 [2]清华信息科学与技术国家实验室(筹),北京100084 [3]信息系统安全教育部重点实验室(清华大学),北京100084

出　　处：《计算机研究与发展》2013年第S1期221-229,共9页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61202008);国家"八六三"高技术研究发展计划基金项目(2012AA040911)

摘　　要：由于数据缺失等原因,用户在查询结果中可能没有得到预期的答案.现有的方法通过枚举可能的缺失记录来解释"为什么没有why-not"的问题.然而,枚举得到的解释数量庞大,用户无法逐一浏览确认缺失数据.实际上,这些可能的解释中有许多是不合理的,如何约减解释数量存在挑战.根据真实数据试验,利用数据中存在的唯一性约束来进行约减,生成的解释数量仍有几十万个.研究利用数据质量规则(如函数依赖)来高效约减缺失结果的解释.首先,提出一种基于函数依赖的解释约减算法FDR(functional dependencies-based reduction).其次,为了辅助用户浏览生成的解释,进一步研究利用近似函数依赖对解释进行排序.真实数据实验表明,FDR方法能够比现有的方法减少2~5个数量级的解释(从几十万个减少至几千个甚至几十个);利用近似函数依赖排序的Top-1解释精确率达到90%以上.Owing to missing tuples,the answers expected by users might not appear in the query results.Existing techniques enumerate possible missing tuples to explain why the expected answers are not returned,known as the 'why-not'problem. However,the number of all possible explanations can be extremely large,which is too difficult(if not impossible)for users to verify.It is challenging,however,to reduce explanations.According to our examination in real data sets,there are still hundreds of thousands of explanations after the reduction by unique constraints.In this paper,the reduction of explanations of non-answers by using data quality rules is studied,such as functional dependencies.First,a novel Functional Dependencies-based Reduction(FDR)algorithm for reduction is proposed. To support effective exploration of explanations,the ranking of explanations by approximate functional dependencies is studied.The experimental evaluation on real data sets demonstrates the superiority of the proposed techniques.Our FDR approach can reduce the number of explanations in 2~5orders of magnitude,from hundreds of thousands to dozens,compared with the state-of-the-art methods. The top-1 explanations ranked by approximate functional dependencies can achieve a high accuracy of 90%.

关 键 词：数据质量 依赖规则 缺失结果解释 函数依赖 近似函数依赖 

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