高效查找資料庫中的函數依賴關係

尋找資料中的函數依賴關係用於資料分析的各個領域：資料庫管理、資料清理、資料庫逆向工程和資料探索。 我們已經發布了有關依賴項本身的信息 一篇文章 阿納斯塔西婭·比里洛和尼基塔·博布羅夫。 這次，電腦科學中心今年的畢業生Anastasia分享了這項工作的進展，作為她在中心答辯的研究工作的一部分。

任務選擇

在CS中心學習期間，我開始深入研究資料庫，即函數依賴和差異依賴的搜尋。 這個主題與我在大學的課程作業主題相關，因此在學習課程作業時，我開始閱讀有關資料庫中各種依賴關係的文章。 我寫了一篇關於這個領域的評論——這是我的第一篇評論 用品 英文版並提交給 SEIM-2017 會議。 當我發現她最終被錄取時，我非常高興，並決定深入研究這個主題。 這個概念本身並不新鮮——它早在 90 年代就開始使用，但即使現在它也被用於許多領域。

在中心的第二個學期，我開始了一個研究項目，以改進查找函數依賴關係的演算法。 她與 JetBrains Research 的聖彼得堡國立大學研究生 Nikita Bobrov 一起進行了這項研究。

搜尋函數依賴關係的計算複雜度

主要問題是計算複雜度。 可能的最小和重要依賴項的數量受上述值的限制 哪裡 — 表屬性的數量。 演算法的運行時間不僅取決於屬性的數量，還取決於行的數量。 在 90 世紀 20 年代，普通桌上型電腦上的聯邦法律搜尋演算法可以在幾個小時內處理包含多達 200 個屬性和數萬行的資料集。 在多核心處理器上運行的現代演算法大約在同一時間檢測由數百個屬性（最多 XNUMX 個）和數十萬行組成的資料集的依賴性。 然而，這還不夠：這樣的時間對於大多數實際應用程式來說是不可接受的。 因此，我們開發了加速現有演算法的方法。

分區交叉點的快取方案

在工作的第一部分中，我們為一類使用分區交集方法的演算法開發了快取方案。 屬性的分區是一組列表，其中每個列表包含給定屬性具有相同值的行號。 每個這樣的列表稱為一個簇。 許多現代演算法使用分區來確定是否保留依賴關係，即它們遵循引理：依賴關係 舉行如果 。 這裡 指定一個分割區並使用分割區大小的概念－其中的群集數。 使用分區的演算法，當依賴關係被違反時，會在依賴關係的左側添加額外的屬性，然後重新計算，執行分區交集的操作。 這種操作在文章中稱為專業化。 但我們注意到，只有在幾輪專業化之後才會保留的依賴分區可以被主動重用，這可以顯著減少演算法的運行時間，因為交集操作是昂貴的。

因此，我們提出了一種基於香農熵和金尼不確定性的啟發式方法，以及我們的度量標準，我們稱之為逆熵。 它是香農熵的輕微修改，並隨著資料集的唯一性增加而增加。 提案的啟發式如下：

這裡 — 最近計算的分區的唯一性程度 和 是各個屬性的唯一性程度的中位數。 上述所有三個指標都作為唯一性指標進行了測試。 您也可以注意到啟發式中有兩個修飾符。 第一個指示當前分區與主鍵的接近程度，並允許您更大程度地緩存那些遠離潛在鍵的分區。 第二個修飾符可讓您監視快取佔用情況，從而鼓勵在可用空間可用時向快取添加更多分區。 這個問題的成功解決使我們能夠將 PYRO 演算法的速度提高 10-40%，具體取決於資料集。 值得注意的是，PYRO 演算法在這方面是最成功的。

在下圖中，您可以看到應用程式所提出的啟發式方法與基本的硬幣翻轉快取方法相比的結果。 X 軸是對數軸。

儲存分區的另一種方法

然後我們提出了另一種儲存分區的方法。 分區是一組簇，每個簇儲存多個具有相同屬性值的元組。 這些簇可能包含長的元組編號序列，例如，如果表中的資料是有序的。 因此，我們提出了一種儲存分區的壓縮方案，即分區簇中值的區間​​儲存：

$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{第一個間隔}, underbrace{7, 8}_{第二個間隔}, 10}}\ downarrow{ 壓縮} \ pi(X) = {{下括號{$, 1, 5}_{第一個~間隔}，下括號{7, 8}_{第二個~間隔}, 10}}$ $顯示$$

該方法能夠將 TANE 演算法運行期間的記憶體消耗減少 1% 至 25%。 TANE 演算法是搜尋聯邦法律的經典演算法；它在工作過程中使用分區。 作為實踐的一部分，選擇了 TANE 演算法，因為在其中實現區間儲存比在 PYRO 中實現區間儲存要容易得多，以便評估所提出的方法是否有效。 所得的結果如下圖所示。 X 軸是對數軸。

會議 ADBIS-2019

根據研究結果，我在2019年XNUMX月發表了一篇文章 用於高效功能依賴發現的智慧型緩存 在第 23 屆歐洲資料庫和資訊系統進展會議 (ADBIS-2019) 上。 在演示過程中，資料庫領域的重要人物 Bernhard Thalheim 注意到了這項工作。 研究結果構成了我在聖彼得堡國立大學數學和力學碩士學位論文的基礎，在此期間，所提出的兩種方法（緩存和壓縮）都在兩種演算法中實現：TANE 和 PYRO。 此外，結果表明所提出的方法是通用的，因為在兩種演算法上，兩種方法都觀察到記憶體消耗顯著減少，且演算法的運行時間顯著減少。

來源： www.habr.com