関数の依存関係の概要

この記事では、データベースの機能依存関係について説明します。依存関係とは何か、どこで使用されるのか、依存関係を見つけるためにどのようなアルゴリズムが存在するのかについて説明します。

リレーショナル データベースのコンテキストで機能の依存関係を検討します。 非常に大まかに言うと、このようなデータベースでは、情報はテーブルの形式で保存されます。 次に、厳密なリレーショナル理論では互換性のない近似概念を使用します。テーブル自体をリレーション、列 - 属性 (そのセット - リレーション スキーマ)、および属性のサブセットの行値のセットをリレーションと呼びます。 - タプル。

たとえば、上の表では、 (ベンソン、M、M オルガン) は属性のタプルです (患者、ポール、医師).
より正式には、これは次のように書かれます。 [患者、性別、医師] = (ベンソン、M、M オルガン).
ここで、関数依存性 (FD) の概念を導入できます。

定義 1. リレーション R は、タプルについての場合に限り、連邦法 X → Y (X, Y ⊆ R) を満たします。 , ∈ R は次の条件を満たします。 [X] = [X]、その後 [Y] = [Y]。 この場合、X (行列式、または属性の定義セット) が Y (従属セット) を関数的に決定すると言います。

言い換えれば、連邦法の存在 X→Y これは、XNUMX つのタプルがある場合を意味します。 R そしてそれらは属性において一致します X、その後、それらは属性で一致します Y.
そして今、順番に。 属性を見てみよう 患者さん и 性別 それらの間に依存関係があるかどうかを調べたいと考えています。 このような属性のセットには、次の依存関係が存在する可能性があります。

1. 患者 → 性別
2. 性別 → 患者

上で定義したように、最初の依存関係を維持するには、それぞれの一意の列値が必要です。 患者さん XNUMX つの列値のみが一致する必要があります 性別。 テーブルの例では、これが実際に当てはまります。 ただし、これは逆方向には機能しません。つまり、XNUMX 番目の依存関係が満たされず、属性が 性別 の決定要因ではありません 忍耐強い。 同様に、依存性を取ると、 医師→患者、値が次のとおりであるため、違反していることがわかります。 ロビン この属性にはいくつかの異なる意味があります - エリスとグラハム.

したがって、関数の依存関係により、テーブル属性のセット間の既存の関係を判断できるようになります。 ここからは、最も興味深い接続、またはむしろそのような接続について考えていきます。 X→Y彼らが何でありますか：

• 自明ではない、つまり、依存関係の右側は左側のサブセットではありません。 (Y̸⊆X);
• 最小限、つまりそのような依存性はありません Z→Yその Z⊂X.

この時点までに考慮された依存関係は厳密なものでした。つまり、テーブル上の違反は規定されていませんでしたが、それに加えて、タプルの値間の不一致を許容するものもあります。 このような依存関係は、近似と呼ばれる別のクラスに配置され、特定の数のタプルに対して違反が許可されます。 この量は、最大誤差指標 emax によって規制されます。 たとえば、エラー率 = 0.01 は、考慮されている属性セットで使用可能なタプルの 1% によって依存関係が違反される可能性があることを意味する場合があります。 つまり、1000 レコードの場合、最大 10 タプルが連邦法に違反する可能性があります。 比較されるタプルのペアごとに異なる値に基づいて、わずかに異なるメトリックを検討します。 中毒者向け X→Y 態度について r それは次のように考えられます。

の誤差を計算してみましょう 医師→患者 上の例から。 属性の値が異なる XNUMX つのタプルがあります 患者さん、しかし一致します 医者: [医師、患者] = (ロビン、エリス）そして、 [医師、患者] = (ロビン、グラハム）。 エラーの定義に続いて、すべての競合するペアを考慮する必要があります。つまり、それらのうち XNUMX つが存在することになります: (, ) とその逆 (, ）。 それを数式に代入して次を取得しましょう。

では、「なぜそれがすべてなのですか?」という質問に答えてみましょう。 実際、連邦法は異なります。 XNUMX つ目のタイプは、データベース設計段階で管理者によって決定される依存関係です。 通常、それらは数が少なく、厳密であり、主な用途はデータの正規化とリレーショナル スキーマの設計です。

XNUMX 番目のタイプは依存関係であり、「隠された」データと属性間のこれまで知られていなかった関係を表します。 つまり、そのような依存関係は設計時には考慮されておらず、既存のデータセットで見つかったため、後で特定された多くの連邦法に基づいて、保存された情報について何らかの結論を引き出すことができます。 私たちが扱うのはまさにこれらの依存関係です。 これらは、さまざまな検索技術とそれに基づいて構築されたアルゴリズムを使用したデータ マイニングの全分野によって処理されます。 データ内で見つかった関数の依存関係 (正確または近似) がどのように役立つかを考えてみましょう。

現在、依存関係の主な用途の XNUMX つはデータ クリーニングです。 これには、「ダーティ データ」を特定し、それを修正するプロセスの開発が含まれます。 「ダーティ データ」の主な例としては、重複、データ エラーまたはタイプミス、欠損値、古いデータ、余分なスペースなどが挙げられます。

データエラーの例:

データの重複の例:

たとえば、表と、実行する必要がある一連の連邦法があります。 この場合のデータ クリーニングには、連邦法が正しくなるようにデータを変更することが含まれます。 この場合、変更の数は最小限にする必要があります (この手順には独自のアルゴリズムがありますが、この記事では取り上げません)。 以下にそのようなデータ変換の例を示します。 左側は元の関係ですが、明らかに必要な FL が満たされていません (FL の XNUMX つの違反の例が赤で強調表示されています)。 右側は更新された関係で、緑色のセルは変更された値を示しています。 この手順の後、必要な依存関係が維持され始めました。

もう XNUMX つの人気のあるアプリケーションはデータベース設計です。 ここで正規形と正規化を思い出す価値があります。 正規化は、関係を特定の一連の要件に準拠させるプロセスであり、それぞれの要件は独自の方法で正規形式によって定義されます。 さまざまな標準形式の要件については説明しません (これは、初心者向けのデータベース コースに関するどの書籍でも説明されています)。ただし、それぞれの形式が関数の依存関係の概念を独自の方法で使用していることだけを説明します。 結局のところ、FL は本質的にデータベースの設計時に考慮される整合性制約です (このタスクの文脈では、FL はスーパーキーと呼ばれることもあります)。

下の図にある XNUMX つの正規形への応用を考えてみましょう。 ボイス-コッド標準形は XNUMX 番目の形式より厳密ですが、XNUMX 番目の形式よりは厳密ではないことを思い出してください。 後者については、その定式化に多値の依存関係を理解する必要があるため、今のところ考慮しませんが、この記事では関心がありません。

依存関係が応用できるもう 5 つの分野は、単純ベイズ分類器の構築、重要な特徴の特定、回帰モデルの再パラメーター化などのタスクにおける特徴空間の次元の削減です。 元の記事では、このタスクは冗長性と機能の関連性の決定と呼ばれています [6、7]。データベースの概念を積極的に使用することで解決されます。 このような作品の出現により、今日では、データベース、分析、および上記の最適化問題の実装を 8 つのツールに統合できるソリューションが求められていると言えます [9、XNUMX、XNUMX]。

データ セット内の連邦法を検索するためのアルゴリズム (最新のものとそうでないものの両方) が多数あり、そのようなアルゴリズムは XNUMX つのグループに分類できます。

• 代数格子の走査を使用したアルゴリズム (格子走査アルゴリズム)
• 合意された値の検索に基づくアルゴリズム (差分集合アルゴリズムおよび合意集合アルゴリズム)
• ペアごとの比較に基づくアルゴリズム (依存関係誘導アルゴリズム)

各タイプのアルゴリズムの簡単な説明を以下の表に示します。


この分類の詳細については、[4] を参照してください。 以下に、各タイプのアルゴリズムの例を示します。

現在、機能の依存関係を見つけるためのいくつかのアプローチを組み合わせた新しいアルゴリズムが登場しています。 このようなアルゴリズムの例としては、Pyro [2] や HyFD [3] があります。 彼らの研究の分析は、このシリーズの次の記事で行われる予定です。 この記事では、依存関係検出手法を理解するために必要な基本概念と補題のみを検討します。

XNUMX 番目のタイプのアルゴリズムで使用される、単純なアルゴリズムから始めましょう。差集合と同意集合です。 difference-set は同じ値を持たないタプルのセットですが、agree-set は逆に同じ値をもつタプルです。 この場合、依存関係の左側のみを考慮していることに注意してください。

上で説明したもう XNUMX つの重要な概念は、代数格子です。 最新のアルゴリズムの多くはこの概念に基づいて動作するため、それが何であるかを理解する必要があります。

ラティスの概念を導入するには、部分的に順序付けられたセット (または部分的に順序付けられたセット、poset と略記) を定義する必要があります。

定義 2. すべての a、b、c ∈ S について次の特性が満たされる場合、集合 S は二項関係 ⩽ によって部分的に順序付けされていると言われます。

1. 反射性、つまり a ⩽ a
2. 反対称、つまり a ⩽ b かつ b ⩽ a の場合、a = b
3. 推移性、つまり、a ⩽ b および b ⩽ c の場合、 a ⩽ c となります。

このような関係を（緩やかな）半順序関係と呼び、集合自体を半順序集合と呼びます。 正式表記：⟨S、⩽⟩。

部分順序集合の最も単純な例として、通常の順序関係 ⩽ を持つすべての自然数 N の集合を取ることができます。 必要な公理がすべて満たされていることを検証するのは簡単です。

もっと意味のある例。 包含関係 ⊆ で順序付けされたすべての部分集合の集合 {1, 2, 3} を考えます。 実際、この関係はすべての半順序条件を満たしているため、⟨P ({1, 2, 3}), ⊆⟩ は半順序集合です。 以下の図は、このセットの構造を示しています。ある要素に別の要素への矢印で到達できる場合、それらは順序関係にあります。

数学の分野からさらに XNUMX つの単純な定義、最高値と下限値が必要になります。

定義 3. ⟨S, ⩽⟩ を半順序集合 A ⊆ S とします。A の上限は、∀x ∈ S: x ⩽ u となる要素 u ∈ S です。 U を S のすべての上限のセットとします。U に最小の要素がある場合、それは上限と呼ばれ、sup A と表示されます。

正確な下限の概念も同様に導入されます。

定義 4. ⟨S, ⩽⟩ を半順序集合 A ⊆ S とします。A の下限は、∀x ∈ S: l ⩽ x となる要素 l ∈ S です。 L を S のすべての下限の集合とします。L に最大の要素がある場合、それは下限値と呼ばれ、inf A と表されます。

例として、上記の部分的に順序付けされた集合 ⟨P ({1, 2, 3}), ⊆⟩ を考えて、その中の最高値と下限値を見つけます。

これで、代数格子の定義を定式化できます。

定義 5. ⟨P,⩽⟩ を、すべての XNUMX 要素サブセットが上限と下限を持つような部分的に順序付けられたセットであるとします。 このとき、P は代数格子と呼ばれます。 この場合、sup{x, y} は x ∨ y と表記され、inf {x, y} は x ∧ y と表記されます。

作業例 ⟨P ({1, 2, 3}), ⊆⟩ が格子であることを確認してみましょう。 実際、任意の a について、b ∈ P ({1, 2, 3})、a∨b = a∪b、および a∧b = a∩b です。 たとえば、集合 {1, 2} と {1, 3} を考えて、それらの下限と上限を見つけます。 それらを交差すると、セット {1} が得られ、これが下限になります。 それらを組み合わせて最高値を取得します - {1, 2, 3}。

物理的問題を特定するアルゴリズムでは、検索空間はラティスの形式で表されることが多く、XNUMX つの要素のセット (依存関係の左側が XNUMX つの属性で構成される検索ラティスの最初のレベルを読み取ります) が各属性を表します。元の関係の。
まず、形式 ∅ → の依存関係を考えます。 単一属性。 このステップにより、どの属性が主キーであるかを判断できます (そのような属性には決定要因がないため、左側は空になります)。 さらに、そのようなアルゴリズムは格子に沿って上に移動します。 格子全体を走査できるわけではないことに注意してください。つまり、左側の希望の最大サイズが入力に渡された場合、アルゴリズムはそのサイズのレベルを超えて進むことはありません。

以下の図は、FZ を見つける問題で代数格子をどのように使用できるかを示しています。 ここで各エッジ (X、XY) 依存関係を表します X→Y。 たとえば、私たちは最初のレベルを通過し、依存症が維持されていることがわかります。 A→B (これを頂点間の緑色の接続として表示します A и B）。 これは、さらに格子に沿って上に移動すると、依存関係をチェックできない可能性があることを意味します。 A、C→B、最小ではなくなるからです。 同様に、依存関係が保持されているかどうかはチェックしません。 C→B.

さらに、原則として、連邦法を検索するための最新のアルゴリズムはすべて、パーティション (元のソースではストリップされたパーティション [1]) などのデータ構造を使用します。 パーティションの正式な定義は次のとおりです。

定義 6. X ⊆ R を関係 r の属性のセットとする。 クラスターは、X に同じ値を持つ r 内のタプルのインデックスのセットです。つまり、c(t) = {i|ti[X] = t[X]}。 パーティションは、単位長のクラスターを除いたクラスターのセットです。

簡単に言うと、属性のパーティションです。 X はリストのセットであり、各リストには同じ値を持つ行番号が含まれます。 X。 現代の文献では、パーティションを表す構造はポジション リスト インデックス (PLI) と呼ばれています。 単位長クラスターは、常に識別しやすい一意の値を持つレコード番号のみを含むクラスターであるため、PLI 圧縮の目的では除外されます。

例を見てみましょう。 患者と同じテーブルに戻り、列のパーティションを構築しましょう 患者さん и 性別 (左側に新しい列が表示され、テーブルの行番号がマークされています):

また、定義によれば、列のパーティションは 患者さん 単一クラスターがパーティションから除外されるため、実際には空になります。

パーティションは、いくつかの属性によって取得できます。 これを行うには XNUMX つの方法があります。テーブルを参照することによって、必要な属性をすべて一度に使用してパーティションを構築するか、属性のサブセットを使用してパーティションの交差の操作を使用してパーティションを構築します。 連邦法の検索アルゴリズムは XNUMX 番目のオプションを使用します。

簡単に言うと、たとえば列によるパーティションを取得するには ABC、パーティションを取得できます AC и B (または他の素なサブセットのセット) を相互に交差させます。 XNUMX つのパーティションの交差操作により、両方のパーティションに共通する最大長のクラスターが選択されます。

例を見てみましょう:

最初のケースでは、空のパーティションを受け取りました。 テーブルをよく見ると、確かに 1 つの属性に同じ値はありません。 テーブルを少し変更すると (右側のケース)、すでに空ではない交差が得られます。 さらに、行 2 と XNUMX には実際には同じ属性の値が含まれています。 性別 и 医師.

次に、パーティションサイズなどの概念が必要になります。 正式には:

簡単に言えば、パーティション サイズはパーティションに含まれるクラスターの数です (単一クラスターはパーティションに含まれないことに注意してください)。

これで、特定のパーティションに対して依存関係が保持されているかどうかを判断できる重要な補題の XNUMX つを定義できます。

補題 1。 依存関係 A、B → C は、次の場合にのみ成立します。

補題によれば、依存関係が成立するかどうかを判断するには、次の XNUMX つの手順を実行する必要があります。

1. 依存関係の左側のパーティションを計算します。
2. 依存関係の右側のパーティションを計算します。
3. 最初のステップと XNUMX 番目のステップの積を計算します
4. 最初の手順と XNUMX 番目の手順で取得したパーティションのサイズを比較します。

以下は、この補題に従って依存関係が成立するかどうかを確認する例です。

この記事では、関数依存性、近似関数依存性などの概念を検討し、それらがどこで使用されているか、および物理関数を検索するためのアルゴリズムが存在するかを調べました。 また、連邦法を検索するための最新のアルゴリズムで積極的に使用されている、基本的かつ重要な概念についても詳細に検討しました。

参考文献:

1. Huhtala Y. et al. TONE: 機能的および近似的な依存関係を発見するための効率的なアルゴリズム //コンピューター ジャーナル。 – 1999. – T. 42. – いいえ。 2. – ページ 100-111。
2. Kruse S.、Naumann F. 近似依存関係の効率的な発見 // VLDB 基金の議事録。 – 2018. – T. 11. – いいえ。 7. – ページ 759-772。
3. Papenbrock T.、Naumann F. 関数依存関係発見へのハイブリッド アプローチ //データ管理に関する 2016 年国際会議の議事録。 – ACM、2016 – pp. 821-833。
4. Papenbrock T. et al. 関数の依存関係の発見: 2015 つのアルゴリズムの実験的評価 //VLDB 基金の議事録。 – 8. – T. 10. – いいえ。 1082. – ページ 1093-XNUMX​​XNUMX。
5. Kumar A. et al. 参加するか否か: 機能を選択する前に、参加についてよく考えてください //2016 年データ管理に関する国際会議の議事録。 – ACM、2016 – ページ 19-34。
6. アボ カミス M. et al. スパース テンソルを使用したデータベース内学習 //データベース システムの原理に関する第 37 回 ACM SIGMOD-SIGACT-SIGAI シンポジウムの議事録。 – ACM、2018 – pp. 325-340。
7. Hellerstein JM et al. MADlib 分析ライブラリ: または MAD スキル、SQL //VLDB 寄付金の議事録。 – 2012. – T. 5. – いいえ。 12. – ページ 1700-1711。
8. Qin C.、Rusu F. テラスケール分散勾配降下最適化の推測的近似 //クラウドでのデータ分析に関する第 2015 回ワークショップの議事録。 – ACM、1. – P. XNUMX.
9. Meng X. et al. Mllib: Apache Spark での機械学習 //機械学習研究ジャーナル。 – 2016. – T. 17. – いいえ。 1. – ページ 1235-1241。

記事の著者: アナスタシア・ビリロ、研究者 JetBrains リサーチ, CSセンター生 и ニキータ・ボブロフ、研究者 JetBrains リサーチ

出所： habr.com