1

マージする必要があるエンティティのクラスに関する複数のデータ ソースを持つデータ ウェアハウスを維持しています。各ソースには自然キーがあり、自然キーごとに常に 1 つだけの代理キーが作成されることが想定されています。特定の自然キーを持つ 1 つのソース システムからの 1 つのレコードが、別の自然キーを持つ別のソース システムからの別のレコードと同じエンティティを表す場合、同じ代理キーが両方に割り当てられます。

つまり、ソース システム A に、ソース システム B の自然キー DEF と同じエンティティを表す自然キー ABC がある場合、両方に同じ代理キーを割り当てます。テーブルは次のようになります。

SURROGATE_KEY   SOURCE_A_NATURAL_KEY    SOURCE_B_NATURAL_KEY
 1               ABC                     DEF

それが計画でした。ただし、このシステムはしばらく本番環境にあり、代理キーの割り当てがめちゃくちゃです。ソース・システム A は、ある日、ソース・システム B がそれを知る前に、ナチュラル・キー ABC を与えます。DW はそれに代理キー 1 を割り当てました。次に、ソース システム B は、ソース システム A の自然キー ABC と同じものを表す自然キー DEF を与え始めました。DW は、このコンボ サロゲート キー 2 を誤って指定しました。テーブルは次のようになります。

SURROGATE_KEY   SOURCE_A_NATURAL_KEY    SOURCE_B_NATURAL_KEY
 1               ABC                     NULL
 2               ABC                     DEF

だから倉庫がぐちゃぐちゃ。これよりもはるかに複雑な状況があります。クリーンアップのための短いタイムラインがあり、サロゲート キーから自然キーへのマッピングのクリーンなセットを見つけ出す必要があります。

少しグーグルで調べてみると、これは非二部グラフのマッチング問題としてモデル化できることがわかります。

ウィキペディア - マッチング

MIT 18.433 組み合わせ最適化 - 非二部マッチングに関する講義ノート

Edmond のパス、ツリー、および花のアルゴリズムの (最適なパフォーマンスではない) 理解しやすい実装が必要です。私は正式な数学やコンピュータ サイエンスのバックグラウンドを持っていません。私が持っているのは独学であり、今夜は数学のヘッドスペースにはいません。誰でも助けることができますか？実装に私を導くよく書かれた説明は、深く感謝されます.

編集：

グローバルな適合度を最大化したいので、数学的なアプローチが最適です。貪欲なアプローチ (最初に A のすべてのインスタンスを取得し、次に B、次に C...) を使用すると、局所的な最大値のコーナーに追い込まれます。

いずれにせよ、私はこれをビジネス アナリストに手動で行うようにプッシュしました (2,000 万人全員)。私は、グローバルな試合の質を評価する機能で彼ら​​を支援しています。とにかくサインオフするのは彼らなので、これは理想的です。

代理キーを使用しなくても、一致の問題は変わりません。発見して維持する必要がある 1:1 の自然キー マッピングがまだあります。代理キーはそのための便利なアンカーであり、それ以上のものではありません。

4

3 に答える 3

2

あなたはこれについて間違った方向に進んでいるという印象を受けます。cdonner が言うように、この混乱を経ずにキー構造を再構築する方法は他にもあります。特に、自然キーが特定のレコードに対して常に一意であることを保証する必要があります(この条件に違反すると、この混乱に陥ります!)。ABCとの両方DEFが同じレコードであることは悲惨ですが、最終的には修復可能です。なぜ代理キーが必要なのか、まったくわかりません。それらには多くの利点がありますが、純粋なリレーショナルになり、スキーマからそれらを削除することを検討します。この混乱からあなたを解放するかもしれません。しかし、それはスキーマ全体を調べた後に下さなければならない決定です。

あなたの潜在的な解決策に対処するために、ブロッサム アルゴリズムについて説明している DB West のIntroduction to Graph Theory、第 2 版の 144 ページのコピーを取り出しました。アルゴリズムに従いますが、十分に簡潔なので、役立つと思います (このルートに進むことにした場合)。説明が必要な場合は、まずグラフ理論に関するリソース (ウィキペディア、地元の図書館、Google など) を参照するか、必要な情報が見つからないかどうか尋ねてください。

3.3.17. アルゴリズム。(エドモンズのブロッサム アルゴリズム [1965a] --- スケッチ)。

入力。グラフG、一致MするG、M飽和していない頂点u。

考え。探索M- からの交互のパス、u各頂点に到達した頂点の記録、見つかったときの花の収縮。セットを維持し、アルゴリズム 3.2.1 のセットとS同様Tに、頂点が飽和エッジに沿って到達します。不飽和の頂点に到達すると、拡張が生成されます。Su

初期化。 S = {u}およびT = {}(空のセット)。

反復。Sマークされていない頂点がない場合は停止します。Mからの -augmenting パスはありませんu。それ以外の場合は、 でマークのないものを選択しvますS。から探索するには、にないものvを順に検討yします。N(v)yT

yが によって飽和されていない場合は、 (必要に応じて花を拡大しながら)mから遡って-augmenting -path を報告します。yM(u, y)

yが の場合S、ブロッサムが見つかりました。ブロッサムの探索を中断して縮小し、 の頂点をとの単一の新しい頂点にv置き換えます。小さい方のグラフで、この頂点から検索を続けます。STS

それ以外の場合は、によってysome に一致します。( から到達) に含める、および(から到達)に含める。wMyTvwSy

のそのようなすべての近傍を探索した後v、マークvして反復します。

ここで説明するアルゴリズムは、時間 O(n^4) で実行されます。ここで、n は頂点の数です。West は、O(n^5/2) または O(n^1/2 m) (m はエッジの数) の速度で実行されるバージョンへの参照を提供します。これらの参照または Edmonds の元の論文への引用が必要な場合は、質問してください。インデックスからそれらを掘り出します (この本ではこのようなものは最悪です)。

于 2009-02-22T03:47:27.403 に答える
1

一連のルールを確立し、各ルールを適用する一連の単純なクエリを使用してキー マッピング テーブルを反復的に攻撃する方がよいと思います。あなたの例は単純なので、単純化しすぎているのかもしれません。

以下はルールの例です。適用するルールを決定できるのはあなただけです。

  • 重複がある場合は、最も低い (最も古い) 代理キーを使用します
  • 最も高い (最新の) 代理キーを持つ行の自然キーを使用する
  • 最も完全なマッピング行の自然キーを使用する
  • すべての自然キーの最新の発生を使用する
  • ... ?

ルールを確立すれば、キー マッピングを再構築するクエリを作成するのは簡単です。これがどうして数学の問題になるのかわかりませんか？

于 2009-02-22T03:16:01.660 に答える
0

実装を探している場合、Eppsteins PADSライブラリにはマッチング アルゴリズムがあります。これは目的に応じて十分に高速である必要があります。一般的なマッチング アルゴリズムは CardinalityMatching.py にあります。実装のコメントは、何が起こっているかを説明しています。このライブラリは使いやすく、Python でグラフを提供するために、G[v] が頂点 v の近傍のリスト (またはセット) を与えるように、辞書 G を使用してグラフを表すことができます。

例：

G = {1: [1], 2:[1,3], 3: [2,4], 4:[3]}

4 つの頂点を持つ折れ線グラフを返します。

于 2009-03-10T02:06:51.537 に答える