微函数依赖及其推理  

Reasoning About Micro Dependencies

作　　者：孙纪舟[1] 李建中[1] 高宏[1] 刘显敏[2] 

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

出　　处：《计算机学报》2016年第10期2134-2148,共15页Chinese Journal of Computers

基　　金：国家"九七三"重点基础研究发展规划项目基金(2012CB316202);中央高校基本科研业务费专项资金(HIT.NSRIF.201649);国家自然科学基金(61502121)资助~~

摘　　要：起初,作为一个数据库模式设计的工具,函数依赖理论得到了很多的关注,而在数据修复中,该理论并不是十分有效.近年来,针对不一致数据的检测和修复问题,更多的约束被提出来,包括条件函数依赖、修复规则以及编辑规则等.然而,这些方法都只关注了属性整体之间的依赖关系,而实际应用中的数据通常有属性部分之间的依赖关系.例如,某单位员工的工号前两位决定了其所属的部门,而此类依赖信息就被已有方法忽略.该文首先提出了一类更一般化的约束——微函数依赖,微函数依赖引入提取函数,用来表示属性的部分信息.利用提取函数之间的依赖关系,能够检测出更多的不一致数据.理论方面,该文首先研究了微函数依赖的可满足性问题和蕴含问题,然后提供了一个正确且完备的推理系统.最后,通过实验证实了微函数依赖能够在可接受的时间开销内检测出更多的错误数据.Originally, functional dependency theory tool, which is not so effective in data repairing. got a lot of attentions Recent years, more as a schema designing constrains have been proposed to detect and repair inconsistent data, including conditional functional dependencies （CFDs）, fixing rules and editing rules, etc. However, to the best of our knowledge, all of the proposals focus on dependencies between entire attributes, while there are ubiquitous dependencies between partial information of the attributes in the real world. For example, the id＇s 2-length prefix of an employee may determine her department, while this kind of dependencies have been ignored by previous proposals. In this paper, we firstly propose a class of more general constrains, referred to as micro-dependencies（MDs）. Extracting functions（EFs） are involved into MDs to extract partial information from attributes. With dependencies between EFs, more inconsistent data in a dataset can he detected. For static analysis of MDs, we then investigate the satisfiability problem and the implication problem analogous to those for CFDs. And then a sound and complete inference system for implication analysis is developed. Finally, we experimentally show that MDs can detect much more errors in data with an acceptable time cost.

关 键 词：微函数依赖 提取函数 可满足性问题 蕴含问题 推理系统 

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