関数従属性の紹介

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

リレーショナル データベースのコンテキストにおける機能的依存性を考慮します。大まかに言えば、このようなデータベースでは情報はテーブルの形式で保存されます。以下では、厳密なリレーショナル理論では互換性のない近似概念を使用します。テーブル自体をリレーション、列属性（そのセットはリレーション スキーマ）、属性のサブセット上の行値のセットをタプルと呼びます。

例えば、上の表では、 （ベンソン、M、Mオルガン）は属性のタプルである （患者、ポール、医師）.
より正式には次のように書きます。 [患者、ポール、医師] = （ベンソン、M、Mオルガン）.
ここで、機能依存性 (FD) の概念を導入することができます。

定義 1. 関係RはFD X → Y（ただしX, Y ⊆ R）を満たす場合、任意の組に対して , ∈ Rが満たされる場合： [X] = [X]、その後 [Y] = [Y]。このような場合、X (決定要因、または定義属性セット) が Y (従属セット) を機能的に決定すると言えます。

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

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

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

したがって、機能的依存関係により、テーブル属性セット間の既存の関係を判別できます。ここからは、最も興味深い関連性、より正確には、 X → Yそれらは次のとおりです。

• 非自明である、つまり依存関係の右側は左側の部分集合ではない （Y̸⊆X）;
• 最小限、つまりそのような依存関係はない Z → Yその Z⊂X.

これまで検討した依存関係は厳密なものであり、つまり、テーブルに違反は規定されていませんが、それに加えて、タプルの値の間にある程度の不整合を許容する依存関係もあります。このような依存関係は、近似と呼ばれる別のクラスに配置され、特定の数のタプルで違反することが許可されます。この量は最大エラーインジケーター emax によって規制されます。例えば、エラー率 = 0.01 は、考慮されている属性セット上の利用可能なタプルの 1% によって依存関係が違反される可能性があることを意味する場合があります。つまり、1000 件のレコードのうち、最大 10 タプルが連邦法に違反する可能性があります。比較したタプルのペアごとに異なる値に基づいた、少し異なるメトリックを検討します。依存症の場合 X → Y 態度について r 計算は次のようになります。

誤差を計算してみましょう 医師 → 患者 上記の例から。属性の値が異なる2つのタプルがあります 患者さん、しかしそれらは一致する 医者: [医師、患者] = (ロビン、エリス）そして、 [医師、患者] = (ロビン、グラハム）。エラーの定義に従うと、すべての矛盾するペアを考慮する必要があり、次の 2 つが考えられます。(, ）とその反転（, ）。これを式に代入すると次のようになります。

さて、「なぜこんなことが起こるのか？」という疑問に答えてみましょう。実際、連邦法にはさまざまな種類があります。最初のタイプは、データベース設計段階で管理者によって定義される依存関係です。これらは通常、数が少なく、厳密であり、主な用途はデータの正規化とリレーショナル スキーマの設計です。

2 番目のタイプは依存関係で、「非表示」のデータと、属性間のこれまで不明だった関係を表します。つまり、このような依存関係は設計時には考慮されておらず、既存のデータ セットで見つかったため、後で識別された FD のセットに基づいて、保存された情報について何らかの結論を導き出すことができます。私たちはまさにそのような依存関係のもとで働いています。これらは、さまざまな検索技術とそれを基盤としたアルゴリズムを備えたデータマイニングの分野全体で処理されます。発見された機能的依存関係 (正確または近似) がどのようなデータでもどのように役立つかを理解しましょう。

現在、依存関係の主な適用領域の 1 つはデータのクリーニングです。これには、「ダーティデータ」を識別して修正するためのプロセスの開発が含まれます。 「ダーティデータ」の一般的な例としては、重複、データエラーやタイプミス、欠落値、古いデータ、余分なスペースなどが挙げられます。

データエラーの例:

データ内の重複の例:

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

もう一つの人気の応用分野はデータベース設計です。ここで、正規形と正規化を思い出す価値があります。正規化とは、関係を特定の要件セットに準拠させるプロセスであり、各要件は独自の方法で正規形によって定義されます。さまざまな正規形の要件については説明しません (これは初心者向けの DB コースのどの本でも行われています)。ただし、それぞれの正規形が機能的依存性の概念を独自の方法で使用していることに注意します。結局のところ、FC は本質的に、データベースを設計するときに考慮される整合性制約です (このタスクのコンテキストでは、FC はスーパーキーと呼ばれることもあります)。

下の図で、4 つの正規形への適用を見てみましょう。ボイス・コッド正規形は 3 番目の形式よりも厳密ですが、4 番目の形式ほど厳密ではないことに注意してください。後者については、その定式化には多値依存関係の理解が必要ですが、この記事では関心がないため、ここでは考慮しません。

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

データセット内で連邦法を検索するためのアルゴリズムは数多くあります (最新のものもそれほど最新ではないものも)。このようなアルゴリズムは、次の 3 つのグループに分けられます。

• 格子走査アルゴリズムを用いたアルゴリズム
• 差異集合アルゴリズムと一致集合アルゴリズム
• 依存性誘導アルゴリズム

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


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

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

まず、2 番目のタイプのアルゴリズムで使用される、単純な差異集合と一致集合から始めましょう。相違セットは値が一致しないタプルのセットですが、一致セットは値が一致するタプルのセットです。この場合、依存関係の左側のみを考慮していることに注意してください。

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

格子の概念を導入するには、半順序集合 (または略して poset) の定義が必要です。

定義 2. 集合Sは、任意のa、b、c∈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 つの要素から別の要素に到達できる場合、それらの要素は順序関係にあります。

数学の分野からのさらに 2 つの簡単な定義、上限と下限が必要になります。

定義 3. ⟨S, ⩽⟩ を半順序集合 A ⊆ S とする。A の上限は u ∈ S の要素で、 ∀x ∈ S: x ⩽ u となるものである。 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, ⩽⟩ を、すべての2要素部分集合が最小の上限と最小の下限を持つような半順序集合とする。このとき、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} を組み合わせることによって得られます。

FD を検出するためのアルゴリズムでは、検索空間は多くの場合、格子の形式で表現されます。格子では、1 つの要素のセット (依存関係の左側が 1 つの属性で構成される検索格子の最初のレベルを参照) が元の関係の各属性を表します。
最初に、∅ → 型の依存関係が考慮される。 単一属性。 この手順では、どの属性が主キーであるかを判別できます (このような属性には決定要因がないため、左側は空になります)。そして、そのようなアルゴリズムはグリッドの上に移動します。グリッド全体をトラバースすることはできないことに注意してください。つまり、左側部分の必要な最大サイズが入力に渡された場合、アルゴリズムはこのサイズのレベルを超えることはありません。

下の図は、FD を見つける問題で代数格子がどのように使用されるかを示しています。ここで各エッジ（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) と呼ばれます。長さ 1 のクラスターは、常に簡単に判別できる一意の値を持つレコード番号のみを含むクラスターであるため、PLI 圧縮の目的で除外されます。

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

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

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

簡単に言えば、例えば列によるパーティションを取得するには ABC、パーティションを取ることができます AC и B (またはその他の互いに素な部分集合の集合) を交差させます。 2 つのパーティションの交差演算では、両方のパーティションに共通する最長の長さのクラスターが選択されます。

例を見てみましょう:

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

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

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

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

補題1。依存関係A, B → Cが成立するのは、

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

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

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

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

参考文献:

1. Huhtala Y. 他TANE: 機能的依存関係と近似依存関係を発見するための効率的なアルゴリズム //The computer journal. – 1999年. – V. 42. – No. 2. – P. 100-111.
2. Kruse S.、Naumann F. 近似依存関係の効率的な検出 // VLDB Endowment の議事録。 – 2018年. – V. 11. – No. 7. – P. 759-772.
3. Papenbrock T.、Naumann F. 機能的依存性の検出に対するハイブリッドアプローチ //2016 年国際データ管理会議の議事録。 – ACM、2016年。– pp.821-833。
4. Papenbrock T. 他機能的依存性の発見: 2015 つのアルゴリズムの実験的評価 //VLDB Endowment の議事録。 – 8年 – 第10巻 – 第1082号 – 1093-XNUMX​​XNUMX頁。
5. クマール A. 他参加するべきか、参加しないべきか?: 特徴選択の前に参加についてよく考える //2016 年国際データ管理会議の議事録。 – ACM、2016年。– P.19-34。
6. Abo Khamis M. 他スパーステンソルを使用したデータベース内学習 // データベースシステムの原理に関する第 37 回 ACM SIGMOD-SIGACT-SIGAI シンポジウムの議事録。 – ACM、2018年。–pp.325-340。
7. Hellerstein JM 他MADlib 分析ライブラリ: または MAD スキル、SQL //VLDB Endowment の議事録。 – 2012年. – V. 5. – No. 12. – P. 1700-1711.
8. Qin C.、Rusu F. テラスケール分散勾配降下法最適化のための推測近似 //クラウドでのデータ分析に関する第 2015 回ワークショップの議事録。 – ACM、1年。– P.XNUMX。
9. Meng X. 他Mllib: Apache Spark での機械学習 //The Journal of Machine Learning Research。 – 2016年. – V. 17. – No. 1. – P. 1235-1241.

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

出所： habr.com