[發明專利]一種最小函數依賴的增量計算方法

有效

• 申請號: 201510072548.1
• 申請日: 2015-02-11
• 公開（公告）號: CN104699761B
• 公開（公告）日: 2017-11-21
• 發明（設計）人: 劉波;周健昌
• 申請（專利權）人: 暨南大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 廣州市華學知識產權代理有限公司44245
• 代理人: 陳燕嫻,劉巧霞

技術領域

本發明涉及計算機數據處理領域，特別涉及一種最小函數依賴的增量計算方法。

背景技術

隨著信息化進程在各行各業的快速推進，海量、動態數據庫的涌現使數據分析與處理面臨嚴峻考驗。數據庫是變化的，數據所反映的知識也是變化的，如何高效、動態地維護數據挖掘所得知識是數據庫領域的一個重要課題。近些年來，數據庫完整性約束正被廣泛應用于數據分析與處理，以及檢測不一致數據、提高數據質量等方面。

目前，政府部門、企業等單位的信息系統及數據中心絕大部分以關系數據庫管理為核心，為了從中快速、準確地識別出錯誤、不一致等異常數據需要高效可行的技術與方法支持，數據質量檢測工具需求越來越大。從用途方面上考慮，數據質量檢測方法適用于：業務數據處理與統計、數據歸檔、數據倉庫維護、數據清洗、數據集成或整合之中。為此，未來幾年在政府、事業、企業等單位的信息化建設過程中引入數據質量管理平臺，建立各個層次上數據質量檢測系統，將成為必然趨勢。錯誤、不一致等異常數據檢測方法及相應的檢測工具具有很好的產業前景。

函數依賴(Functional Dependency，縮寫為FD)是關系數據庫的重要約束之一，不僅是數據庫設計的基礎，而且是數據質量監測、控制的依據。雖然函數依賴可以在數據庫管理系統作為數據約束定義，但許多情況下，在構建數據庫時，沒有明確定義函數依賴，或者并非在構造數據庫時能夠明確制定，需要通過數據集挖掘或計算函數依賴，并且隨著數據庫的變化還需要對它們進行維護，以保證檢測異常數據的準確性。

關于函數依賴集的計算算法已研究多年，最具代表性的兩種算法是按照層次的算法(例如Y.Huhtala,J.Karkk ainen等在1999年公開的《TANE:An efficient algorithm for discovering functional and approximate dependencies》)和深度優先的算法(例如C.M.Wyss,C.Giannella,E.L.Robertson等在2001年公開的《FastFDs:A heuristic-driven,depth-first algorithm for mining functional dependencies from relation instances-extended for abstract》)，隨著數據庫的變化，函數依賴也可能發生變化，即原有的函數依賴不再成立、新的函數依賴產生。目前計算數據庫變化后的函數依賴及最小函數依賴的方式主要有兩種：

(1)重新計算：針對變化后的數據庫按照某一函數依賴計算方法重新計算函數依賴，不利用數據集變化的部分(即增加的元組，刪除的元組，修改的元組)、原來計算出的最小函數依賴集及劃分信息。

(2)增量計算：主要根據數據集變化的部分、原有的最小函數依賴集及劃分信息，增量檢測原有的最小函數依賴是否成立，并計算新增的最小函數依賴。

目前，針對動態變化的數據庫，計算函數依賴集及最小函數依賴的算法均是采用重新計算的方式，如TANE算法和FastFDs算法以及基于它們改進的算法。針對變化的數據庫，采用重新計算最小函數依賴方式，重復計算與變化前數據庫相同的最小函數依賴，隨著數據庫的增大，時間效率較低。在實際應用中，隨著數據庫的變化，大部分最小函數依賴仍然不變或成立，因此，重新計算是沒有必要的。

所以，提出一種計算效率高、靈活性強、通過增量計算方式來計算最小函數依賴的方法具有重要的應用價值。

發明內容

本發明的目的在于克服現有技術的缺點與不足，提供一種最小函數依賴的增量計算方法，該方法是采用增量計算的方式，從變化的關系數據集中計算最小函數依賴，計算效率高，且計算結果準確。

為了克服現有方法和技術的不足，本發明根據變化數據集、關系表變化前的最小函數依賴集及劃分信息，增量檢測原有的最小函數依賴是否成立，并計算新增的最小函數依賴。

本發明技術方案所涉及的數學定義首先列舉如下：

函數依賴的定義：令R是一個關系模式，Y∈R，函數依賴X→Y成立的條件是：對于模式為R的關系表r及r中任意兩個元組t₁和t₂，以及所有B∈X，如果t₁[B]＝t₂[B]，則t₁[Y]＝t₂[Y]。若Y∈X，X→Y是平凡的。

最小函數依賴的定義：令R是一個關系模式，Y∈R，函數依賴X→Y成立，若對于任意非空Z→Y不成立，則X→Y是最小函數依賴。