[發明專利]一種自動生成近似函數依賴規則的方法

有效

• 申請號: 201210471793.6
• 申請日: 2012-11-20
• 公開（公告）號: CN103077181B
• 公開（公告）日: 2017-02-08
• 發明（設計）人: 王明興;賈西貝
• 申請（專利權）人: 深圳市華傲數據技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 深圳市華優知識產權代理事務所(普通合伙)44319
• 代理人: 余薇

一、技術領域

本發明涉及到一種數據庫的處理方法，尤其涉及到一種自動生成近似函數依賴規則的方法。

二、背景技術

隨著社交網絡、移動計算和傳感器等新的渠道和技術不斷涌現，大量新型數據應運而生。我們生活在一個數據成指數式急劇增的時代，常規技術已經難以應對PB(1024TB)級的大規模數據量。

分析調研機構IDC在其發布的數字宇宙研究報告(Digital?Universe?Study)——《從混沌中提取價值》(Extracting?Value?from?Chaos)中指出，全球信息總量每過兩年，就會增長一倍。2011年，全球被創建和被復制的數據總量為1.8ZB。相較2010年同期，這一數據上漲了超過1ZB。在被創建的信息數據總量中，有75％來自于個人，這包括文字、圖片、視頻和音樂。這些個人數據的蔓延增速要比數據的創建速度更加迅猛。不過，在報告中IDC同時也認為，企業級的應用數據有朝一日將會占據數據總量的80％。

如何從這些爆炸式增長的數據量中，收集、存儲和發掘利用海量數據以獲取洞見，為世界經濟創造巨大的價值，是人們急需面對的一個難題。麥肯錫全球研究院在它的《海量數據：創新、競爭和提高生產率的下一個新領域》報告中預測，擅用海量數據產生價值的行業巨頭戰勝不擅利用海量數據的對手，已經越來越成為了顯性的趨勢。

在當前海量數據環境下或者大數據時代，怎樣快速的找出數據之間的規則，分析、挖掘數據的規律，為企業決策者提供建設性的建議，是IT技術人員需要考慮的問題。本發明正是在此背景之下，針對海量數據，提出的一種新的、適用海量數據環境的一種自動生成近似函數依賴規則的方法。

三、發明內容

為了實現本發明目的，本發明提供一種自動生成近似函數依賴規則的方法。所述自動生成近似函數依賴規則的方法包含以下幾個步驟：步驟S100：對數據庫r的所有列進行掃描分析，生成候選列R，并構建所述候選列R各列的分區P(R)；步驟S200：對所述候選列R按照一定的順序排序，采用策略搜索出所有滿足條件的規則左部；步驟S300：對所述策略搜索的搜索空間，采用修剪規則進行修剪，壓縮所述策略搜索的搜索空間；步驟S400：對所述壓縮的搜索空間進行計算并生成近似函數依賴規則的右部，同時生成近似函數依賴規則。

應當理解，以上總體說明和以下詳細說明都是說明性和實例性的，旨在提供對所要求的本發明的進一步說明。

四、附圖說明

所包含的附圖用于提供對本發明的進一步理解，其被并入說明書并構成其一部分，附圖說明了本發明的實施例，并與說明書一起用于理解本發明的原理。

圖1是本發明一種自動生成近似函數依賴規則的方法流程圖。。

圖2是本發明較佳實施例的計算生成近似函數依賴規則的右部的方法流程圖。

圖3是本發明較佳實施例的計算當前freesetCol的閉集closedCol和候選子集candidates方法流程圖。

圖4是本發明較佳實施例的逆序遍歷候選子集candidates方法流程圖。

圖5是本發明較佳實施例的遞增策略搜索結構圖。

五、具體實施方式

為了使本發明的目的、技術方案及優點更加清楚明白，以下結合附圖及實施例，對本發明進行進一步詳細說明。應當理解，此處所描述的具體實施例僅僅用于解釋本發明，并不用于限定本發明。

相關概念和定義

函數依賴(functional?dependency，簡稱FD)：是指關系數據庫中列與列之間的關系，其含義為一個列的值由其他某些列的值唯一確定，比如：一數據庫中，郵政編碼是由城市和街道地址決定的。

考慮數據庫r，定義r中所有列的集合為R，函數依賴可描述為：X→A，其中A∈R對r中的所有數據組合t和u，當對所有的B∈X都有t[B]＝u[B]時，t[A]＝u[A]，則稱函數依賴X→A在r上成立。即如果在數據庫r中，X列的值相同時，A的值也相同，則X→A成立。

對于X→A，如果不存在一個X的子集Y，使得Y→A成立，則稱函數依賴X→A是最小的，或稱Y→A是冗余的。如果A∈X，則X→A是沒有意義的。函數依賴挖掘的中心任務是從數據庫中挖掘出所有非冗余的且有意義的規則。

近似函數依賴：是指函數依賴X→A近似成立。比如一個人姓名中的名通常決定了性別。近似函數依賴評價標準有多種，最常用的是依據從數據庫r最少刪除多少行后X→A成立。我們在此定義近似函數依賴X→A的誤差為需要最少刪除的行數比上數據總行數，即