函數(shù)依賴是重要的元數(shù)據(jù),用于描述數(shù)據(jù)集中列之間的關(guān)系,可以被用于很多任務中,例如范式結(jié)構(gòu)標準化,數(shù)據(jù)清洗等。很多單機和并行函數(shù)依賴發(fā)現(xiàn)算法已經(jīng)被提出。之前的單機算法在數(shù)據(jù)集較小且單機存儲的時候很高效,但是缺乏并行能力;另一方面,現(xiàn)存的并行算法存在很大的通信開銷,導致其表現(xiàn)不佳。為了解決這個問題,本文做了如下三方面的工作:首先是提出FD-Combine算法解決了“如何推導”的問題�，F(xiàn)存并行算法最大問題是通信開銷,我們嘗試通過數(shù)據(jù)并行模式的并行來避免大量的通信開銷,而數(shù)據(jù)并行模式的并行的首要問題就是”如何將部分數(shù)據(jù)上成立的函數(shù)依賴推導得到全體數(shù)據(jù)的函數(shù)依賴”,即“如何推導”的問題。為此,我們構(gòu)建了BL代數(shù)系統(tǒng)和基礎項表達,形式化了函數(shù)依賴、非函數(shù)依賴、部分函數(shù)依賴的性質(zhì)與運算關(guān)系。在BL代數(shù)系統(tǒng)內(nèi),我們提出FD-Combine算法,在每部分數(shù)據(jù)集即數(shù)據(jù)塊滿足一定條件時,可以將部分函數(shù)依賴推導得到全體數(shù)據(jù)上的函數(shù)依賴。我們對比FD-Combine算法與之前非函數(shù)依賴的推導算法,得到進一步理解,并給出FD-Combine算法的不同實現(xiàn)方式和相應的時間復雜度。然后,改造并選擇了仿射平面區(qū)組設計算... 

【文章來源】：中國科學技術(shù)大學安徽省 211工程院校 985工程院校

【文章頁數(shù)】：69 頁

【學位級別】：碩士

【文章目錄】：
摘要
abstract
第1章 緒論
    1.1 研究背景
    1.2 國內(nèi)外研究現(xiàn)狀
        1.2.1 國外研究現(xiàn)狀
        1.2.2 國內(nèi)研究現(xiàn)狀
        1.2.3 發(fā)展動態(tài)分析
    1.3 本文主要工作
    1.4 本文組織結(jié)構(gòu)
第2章 函數(shù)依賴發(fā)現(xiàn)算法概述
    2.1 定義
    2.2 三類發(fā)現(xiàn)算法
        2.2.1 單機算法過去的實驗對比
        2.2.2 模式驅(qū)動類算法
        2.2.3 數(shù)據(jù)驅(qū)動類算法
        2.2.4 混合類算法
    2.3 發(fā)現(xiàn)算法中的四種技術(shù)
        2.3.1 驗證技術(shù)
        2.3.2 搜索剪枝技術(shù)
        2.3.3 推導技術(shù)
        2.3.4 重復檢測技術(shù)
        2.3.5 分布式環(huán)境下四種技術(shù)
    2.4 分布式環(huán)境下的發(fā)現(xiàn)算法
        2.4.1 三種類型的通信開銷
        2.4.2 幾種并行算法的設計
第3章 部分數(shù)據(jù)函數(shù)依賴到全體數(shù)據(jù)函數(shù)依賴的推導
    3.1 問題的背景分析
        3.1.1 分布式環(huán)境下的通信開銷分析
        3.1.2 并行模式的分析
    3.2 問題的形式化
L代數(shù)系統(tǒng)與FD-Combine推導算法">    3.3 B_L代數(shù)系統(tǒng)與FD-Combine推導算法
L代數(shù)系統(tǒng)定義與性質(zhì)">        3.3.1 B_L代數(shù)系統(tǒng)定義與性質(zhì)
        3.3.2 基礎項及基礎項計算規(guī)則
        3.3.3 FD-Combine推導算法
    3.4 FD-Combine推導算法的進一步探索
        3.4.1 FD-Combine算法與其他推導算法的關(guān)系
        3.4.2 FD-Combine的算法實現(xiàn)方式和復雜度分析
    3.5 本章小結(jié)
第4章 數(shù)據(jù)集在各個計算節(jié)點上的分割問題
    4.1 問題的背景分析與目標
        4.1.1 FD-Combine推導條件的滿足
        4.1.2 分割算法的高效性
        4.1.3 分割結(jié)果的質(zhì)量
    4.2 問題的轉(zhuǎn)化及形式化表達
    4.3 區(qū)組設計與評估指標設計
        4.3.1 區(qū)組設計與條件放松
        4.3.2 評價指標定義與性質(zhì)
    4.4 仿射平面區(qū)組設計算法設計與分析
        4.4.1 仿射平面區(qū)組設計算法流程
        4.4.2 算法的時間復雜度分析與結(jié)果分析
    4.5 本章小結(jié)
第5章 函數(shù)依賴發(fā)現(xiàn)算法的通用并行策略與實驗
    5.1 數(shù)據(jù)并行模式的通用并行策略
        5.1.1 通用并行策略的介紹與例子
        5.1.2 策略的復雜度分析和加速比
    5.2 通用并行策略的實驗
        5.2.1 實驗設置
        5.2.2 小數(shù)據(jù)集上的實驗
        5.2.3 大數(shù)據(jù)集上的實驗
    5.3 本章小結(jié)
第6章 總結(jié)與展望
    6.1 工作總結(jié)
    6.2 未來展望
參考文獻
致謝
在讀期間發(fā)表的學術(shù)論文與取得的研究成果


【參考文獻】：
期刊論文
[1]分布式大數(shù)據(jù)多函數(shù)依賴沖突檢測[J]. 李衛(wèi)榜,李戰(zhàn)懷,姜濤.  計算機學報. 2017(01)
[2]關(guān)系數(shù)據(jù)中函數(shù)依賴檢測方法[J]. 鐘評,李戰(zhàn)懷,陳群.  計算機學報. 2017(01)
[3]基于函數(shù)依賴與條件約束的數(shù)據(jù)修復方法[J]. 金澈清,劉輝平,周傲英.  軟件學報. 2016(07)
[4]基于可能世界模型的關(guān)系數(shù)據(jù)不一致性的修復[J]. 徐耀麗,李戰(zhàn)懷,陳群,鐘評.  軟件學報. 2016(07)
[5]分布式大數(shù)據(jù)不一致性檢測[J]. 李衛(wèi)榜,李戰(zhàn)懷,陳群,楊婧穎,姜濤.  軟件學報. 2016(08)
[6]分布式大數(shù)據(jù)函數(shù)依賴發(fā)現(xiàn)[J]. 李衛(wèi)榜,李戰(zhàn)懷,陳群,姜濤,劉海龍,潘巍.  計算機研究與發(fā)展. 2015(02)
[7]基于函數(shù)依賴的結(jié)構(gòu)匹配方法[J]. 李國徽,杜小坤,胡方曉,楊兵,唐向紅.  軟件學報. 2009(10)
[8]時態(tài)函數(shù)依賴多值依賴混合集的成員籍問題研究[J]. 郝忠孝,李艷娟.  計算機研究與發(fā)展. 2006(07)
[9]具有多時間粒度的時態(tài)數(shù)據(jù)庫初等關(guān)鍵字、簡單范式分解問題研究[J]. 郝忠孝,李艷娟.  計算機研究與發(fā)展. 2005(09)
[10]函數(shù)依賴和規(guī)范化在關(guān)系和XML間的傳播[J]. 談子敬,施伯樂.  軟件學報. 2005(04)



本文編號：3159451