分布式大数据多函数依赖冲突检测

发布时间：2018-10-08 10:18

【摘要】：关系数据库数据质量的一个主要问题是存在数据不一致现象.为找出不一致数据,需要进行函数依赖冲突检测.集中式数据库中可以通过SQL技术检测不一致情况,而分布式环境下的函数依赖冲突检测更富有挑战性,特别是大数据背景下,这个问题尤为突出.分布式环境下的函数依赖冲突检测通常需要进行数据迁移,而且不同的数据迁移方法会对检测效率产生一定的影响.该文提出了一种基于等价类的分布式环境多个函数依赖冲突检测的方法,给出了冲突检测的响应时间代价模型.由于分布式环境函数依赖冲突检测问题的任务分配问题为NP-难问题,多项式时间内难以得到最优解,该文将不一致性检测响应时间最小化问题转化为整数规划问题,并给出了近似最优解.针对集群规模和函数依赖个数大小不同的情况,分别给出了不同的任务分配策略,并在检测过程中实现了动态负载均衡,有效提高了负载均衡度和检测效率.在真实和人工数据集上的实验表明,相对于集中式检测方法以及基于Hadoop的naive方法,该文提出的多函数依赖冲突检测方法检测效率有明显的提升,且在数据规模、节点个数和函数依赖个数等方面扩展性能良好.
[Abstract]:One of the main problems of data quality in relational database is the inconsistency of data. In order to find inconsistent data, functional dependency conflict detection is needed. SQL technology can be used to detect inconsistency in centralized database, but in distributed environment, functional dependency conflict detection is more challenging, especially in big data background. In distributed environment, function dependency conflict detection usually requires data migration, and different data migration methods have a certain impact on detection efficiency. In this paper, a method of multi-functional dependency conflict detection in distributed environment based on equivalence class is proposed, and the response time cost model of conflict detection is given. Because the task assignment problem of distributed environment function dependent conflict detection problem is NP- problem, it is difficult to obtain the optimal solution in polynomial time. In this paper, the problem of minimizing the response time of inconsistent detection is transformed into an integer programming problem. The approximate optimal solution is given. In view of the different size of cluster and the number of functional dependencies, different task allocation strategies are proposed, and dynamic load balancing is realized in the detection process, which effectively improves the load balancing degree and detection efficiency. Experiments on real and artificial datasets show that compared with the centralized detection method and the naive method based on Hadoop, the efficiency of the multi-function dependency conflict detection method proposed in this paper is significantly improved, and the efficiency of the proposed multi-function dependency conflict detection method is improved in the data scale. The number of nodes and the number of function dependencies have good expansion performance.
【作者单位】：西北工业大学计算机学院;
【基金】：国家“九七三”重点基础研究发展规划项目基金(2012CB316203) 国家自然科学基金(61502390,61472321,61332006,61272121) 国家“八六三”高技术研究发展计划项目基金(2015AA015307)资助~~
【分类号】：TP311.13

【相似文献】