ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2015, Vol. 52 ›› Issue (2): 282-294.doi: 10.7544/issn1000-1239.2015.20140229

所属专题: 2015大数据管理

• 软件技术 • 上一篇    下一篇

分布式大数据函数依赖发现

李卫榜,李战怀,陈群,姜涛,刘海龙,潘巍   

  1. (西北工业大学计算机科学学院 西安 710072) (wbli2003@163.com)
  • 出版日期: 2015-02-01
  • 基金资助: 
    基金项目:国家“九七三”重点基础研究发展计划基金项目(2012CB316203);国家自然科学基金项目(61472321,61033007);国家“八六三”高技术研究发展计划基金项目(2012AA011004);西北工业大学基础研究基金项目(3102014JSJ0005,3102014JSJ0013)

Functional Dependencies Discovering in Distributed Big Data

Li Weibang, Li Zhanhuai, Chen Qun, Jiang Tao, Liu Hailong, Pan Wei   

  1. (College of Computer Science, Northwestern Polytechnical University, Xi’an 710072)
  • Online: 2015-02-01

摘要: 在关系数据库中,函数依赖发现是一种十分重要的数据库分析技术,在知识发现、数据库语义分析、数据质量评估以及数据库设计等领域有着广泛的应用.现有的函数依赖发现算法主要针对集中式数据,通常仅适用于数据规模比较小的情况.在大数据背景下,分布式环境函数依赖发现更富有挑战性.提出了一种分布式环境下大数据的函数依赖发现算法,其基本思想是首先在各个节点利用本地数据并行进行函数依赖发现,基于以上发现的结果对函数依赖候选集进行剪枝,然后进一步利用函数依赖的左部(left hand side, LHS)的特征,对函数依赖候选集进行分组,针对每一组候选函数依赖并行执行分布式环境发现算法,最终得到所有函数依赖.对不同分组情况下所能检测的候选函数依赖数量进行了分析,在算法的执行过程中,综合考虑了数据迁移量和负载均衡的问题.在真实的大数据集上的实验表明,提出的检测算法在检测效率方面与已有方法相比有明显的提升.

关键词: 函数依赖发现, 函数依赖, 大数据, 知识发现, 并行计算

Abstract: Discovering functional dependencies (FDs) from relational databases is an important database analysis technique, which has a wide range of applications in knowledge discovery, database semantics analysis, data quality assessment and database design. Existing functional dependencies discovery algorithms are mainly applied in centralized data, and are suitable to the case of small data size only. However, it is far more challenging to discover functional dependencies in distributed databases, especially with big data. In this paper, we propose a novel functional dependencies discovering approach in distributed big data. Firstly we execute functional dependencies discovering algorithm in parallel in each node, then prune the candidate set of functional dependencies based on the results of discovery. Secondly we group the candidate set of functional dependencies according to the features of candidate functional dependencies’ left hand side, and execute functional dependencies discovery algorithm based on each candidate set in parallel, and get all the functional dependency eventually. We analyze the number of candidate functions with regard to different groups, and data shipment and load balance are taken into account when discovering functional dependencies. Experiments on real-world big datasets demonstrate that compared with previous discovering methods, our approach is more effective in efficiency.

Key words: discovering functional dependencies, functional dependencies, big data, knowledge discovery, parallel computing

中图分类号: