データ内の機能的な依存関係の検出は、データベース管理、データ クリーニング、データベース リバース エンジニアリング、データ探索などのデータ分析のさまざまな分野で使用されます。 依存関係自体についてはすでに公開しています アナスタシア・ビリロとニキータ・ボブロフ。 今回は、今年コンピューター サイエンス センターを卒業したアナスタシアが、センターで擁護してきた研究活動の一環として、この作品の開発について共有します。
タスク選択
CS センターで勉強している間、私はデータベース、つまり関数の依存関係や差分依存関係の検索を深く研究し始めました。 このトピックは大学でのコースワークのテーマに関連していたので、コースワークに取り組みながら、データベースのさまざまな依存関係に関する記事を読み始めました。 私はこの分野のレビューを書きました - 私の最初のレビューの XNUMX つ 英語で作成し、SEIM-2017 カンファレンスに提出しました。 結果的に彼女が採用されたと知ったときはとても嬉しくて、このテーマについてもっと深く掘り下げてみることにしました。 この概念自体は新しいものではなく、90 年代に使用され始めましたが、現在でも多くの分野で使用されています。
センターでの XNUMX 学期目に、私は関数の依存関係を見つけるためのアルゴリズムを改善する研究プロジェクトを開始しました。 彼女は、サンクトペテルブルク州立大学 JetBrains Research の大学院生ニキータ・ボブロフ氏と一緒にこの研究に取り組みました。
関数の依存関係を検索する際の計算の複雑さ
主な問題は計算の複雑さです。 可能な最小限の依存関係と自明ではない依存関係の数は、上記の値によって制限されます。 どこ — テーブル属性の数。 アルゴリズムの動作時間は、属性の数だけでなく、行の数にも依存します。 90 年代には、通常のデスクトップ PC 上の連邦法の検索アルゴリズムは、最大 20 の属性と数万行を含むデータ セットを最大数時間で処理できました。 マルチコア プロセッサ上で実行される最新のアルゴリズムは、数百の属性 (最大 200) と数十万の行で構成されるデータ セットの依存関係をほぼ同時に検出します。 しかし、これでは十分ではありません。現実世界のほとんどのアプリケーションでは、このような時間は受け入れられません。 したがって、私たちは既存のアルゴリズムを高速化するアプローチを開発しました。
パーティション交差のキャッシュ スキーム
作業の最初の部分では、パーティション交差法を使用するアルゴリズムのクラスのキャッシュ スキームを開発しました。 属性のパーティションはリストのセットであり、各リストには特定の属性の同じ値を持つ行番号が含まれます。 このような各リストはクラスターと呼ばれます。 最新のアルゴリズムの多くは、依存関係が保持されているかどうかを決定するためにパーティションを使用します。つまり、アルゴリズムは次の補題に従います。 開催される場合 。 ここに パーティションが指定され、パーティション サイズの概念 (その中のクラスターの数) が使用されます。 パーティションを使用するアルゴリズムは、依存関係に違反すると、依存関係の左側に追加の属性を追加して再計算し、パーティションの交差操作を実行します。 この操作を記事では特殊化と呼びます。 しかし、数ラウンドの特殊化後にのみ保持される依存関係のパーティションは積極的に再利用できることに気付きました。これにより、交差演算はコストがかかるため、アルゴリズムの実行時間を大幅に短縮できます。
したがって、私たちは、シャノン エントロピーとジニーの不確実性、および逆エントロピーと呼ばれるメトリックに基づいたヒューリスティックを提案しました。 これはシャノン エントロピーをわずかに変更したもので、データ セットの一意性が高まるにつれて増加します。 提案されたヒューリスティックは次のとおりです。
それは — 最近計算されたパーティションの一意性の程度 と 個々の属性の一意性の程度の中央値です。 上記の 10 つのメトリクスはすべて、一意性メトリクスとしてテストされました。 ヒューリスティックには 40 つの修飾子があることにも注目してください。 XNUMX つ目は、現在のパーティションが主キーにどの程度近いかを示し、潜在的なキーから遠いパーティションをより広範囲にキャッシュできるようにします。 XNUMX 番目の修飾子を使用すると、キャッシュの占有率を監視できるため、空き領域がある場合はキャッシュにパーティションを追加することが推奨されます。 この問題の解決に成功したことで、データセットに応じて PYRO アルゴリズムを XNUMX ～ XNUMX% 高速化することができました。 PYRO アルゴリズムがこの分野で最も成功していることは注目に値します。
以下の図では、提案されたヒューリスティックを適用した結果を、基本的なコインフリップ キャッシュ アプローチと比較して見ることができます。 X 軸は対数です。
パーティションを保存する別の方法
次に、パーティションを保存する別の方法を提案しました。 パーティションは一連のクラスターであり、各クラスターには特定の属性の同一の値を持つ多数のタプルが保存されます。 これらのクラスターには、テーブル内のデータが順序付けされている場合など、タプル番号の長いシーケンスが含まれる場合があります。 したがって、私たちはパーティションを保存するための圧縮スキーム、つまりパーティションのクラスターに値を間隔を置いて保存することを提案しました。
$$display$$pi(X) = {{アンダーブレース{1, 2, 3, 4, 5}_{最初の間隔}, アンダーブレース{7, 8}_{10 番目の間隔}, 1}}\ downarrow{ 圧縮} \ pi(X) = {{アンダーブレース{$, 5, 7}_{最初の~間隔}, アンダーブレース{8, 10}_{二番目~の間隔}, XNUMX}}$$display$$
この方法により、TANE アルゴリズムの動作中のメモリ消費量を 1 ～ 25% 削減できました。 TANE アルゴリズムは、連邦法を検索するための古典的なアルゴリズムであり、その作業中にパーティションを使用します。 実践の一環として、TANE アルゴリズムが選択されました。これは、提案されたアプローチが機能するかどうかを評価するために、たとえば PYRO よりもインターバル ストレージを実装する方がはるかに簡単だったためです。 得られた結果を下の図に示します。 X 軸は対数です。
カンファレンスADBIS-2019
研究結果をもとに、2019年XNUMX月に論文を発表しました 第 23 回データベースと情報システムの進歩に関する欧州会議 (ADBIS-2019) で。 プレゼンテーション中に、この研究はデータベース分野の重要人物であるベルンハルト・タールハイムによって注目されました。 この研究結果は、サンクトペテルブルク州立大学で数学と力学の修士号を取得した私の博士論文の基礎となり、その際、提案された両方のアプローチ (キャッシュと圧縮) が両方のアルゴリズム (TANE と PYRO) に実装されました。 さらに、結果は、両方のアルゴリズムでメモリ消費量の大幅な削減とアルゴリズムの動作時間の大幅な短縮が観察されたため、提案されたアプローチが普遍的であることを示しました。
出所： habr.com