保證唯一代理鍵分配 - 非二分圖最大匹配

Question

我正在維護一個數據倉庫，其中包含多個關於必須合併的實體類的數據源。每個來源都有一個自然鍵，並且應該發生的是，始終爲每個自然鍵創建一個且僅有一個代理鍵。如果來自具有特定自然鍵的源系統的一個記錄表示與來自具有不同自然鍵的另一個源系統的另一個記錄相同的實體，則相同的替代鍵將被分配給兩者。換句話說，如果源系統A具有與源系統B的自然鍵DEF相同的實體的自然鍵ABC，那麼我們將爲兩者分配相同的代理鍵。該表如下所示：

SURROGATE_KEY SOURCE_A_NATURAL_KEY SOURCE_B_NATURAL_KEY 
1    ABC      DEF 

這是計劃。但是，這個系統已經投入生產了一段時間，而且代理鍵分配一團糟。在源系統B知道它之前，源系統A將在一天內給出自然密鑰ABC。 DW爲其分配了代理鍵1。然後源系統B開始給出自然鍵DEF，這與源系統A的自然鍵ABC表示相同的東西。 DW錯誤地給了這個組合代理鍵2.表看起來像這樣：

SURROGATE_KEY SOURCE_A_NATURAL_KEY SOURCE_B_NATURAL_KEY 
1    ABC      NULL 
2    ABC      DEF 

所以倉庫是一團糟。比這更復雜的情況。我有一個簡短的清理時間表，需要找出一組乾淨的代理鍵來自然鍵映射。

一個小Googling表明，這可以在非二分圖被模擬成一個匹配的問題：

Wikipedia - Matching

MIT 18.433 Combinatorial Optimization - Lecture Notes on Non-Bipartite Matching

我需要一個容易理解的實現（不是最佳表演）愛德蒙的路徑，樹木和花朵算法。我沒有正式的數學或CS背景，而我所擁有的是自學成才的，今晚我並沒有進入數學領域。誰能幫忙？深受讚賞的是，一篇寫得很好的解釋指導我實施。

編輯：

數學方法是最優的，因爲我們要最大限度地提高全球健康。一個貪婪的方法（首先採取A的所有實例，然後B，然後C ...）將您繪製到當地最大角落。

在任何情況下，我都會將這個推回到業務分析師手動執行（全部2000萬）。我正在幫助他們評估全球比賽質量。這是理想的，因爲他們是反正簽署的，所以我的背面被覆蓋。

不使用代理鍵不會改變匹配問題。仍然有1：1的自然鍵映射必須被發現和維護。代理鍵是一個方便的錨，僅此而已。

Answer 1

我收到你對這個錯誤的印象;正如CDonner所說，還有其他方法可以在不經歷這個混亂的情況下重建關鍵結構。特別是，你需要保證對於給定的記錄，自然鍵是總是唯一（違反這個條件是什麼讓你陷入這個混亂！）。同時有ABC和DEF識別相同的記錄是災難性的，但最終可修復。我甚至不確定爲什麼你需要代理鍵;雖然他們確實有很多優勢，但我會考慮進行純關係，並從您的架構中解脫出來，一個Celko;它可能會讓你擺脫這個混亂。但是，這是在查看完整模式後必須作出的決定。爲了解決您的潛在解決方案，我已經拿出了我的DB West的介紹圖論，第二版，其中介紹了第144頁上的開花算法。您需要一些數學背景，數學和數學符號和圖論，遵循算法，但它足夠簡潔，我認爲它可以幫助（如果你決定走這條路線）。如果您需要解釋，請首先諮詢圖論（維基百科，您當地的圖書館，Google，任何地方）的資源，或者詢問您是否找不到您需要的資源。

3.3.17。算法。（Edmonds'Blossom Algorithm [1965a] --- sketch）。

輸入。圖G，匹配M的G,M-不飽和頂點u。

想法。探索M-u的交錯路徑，記錄每個頂點到達它的頂點，並在找到時收縮花朵。維護集S和T類似於算法3.2.1中的那些，其中S由u組成，頂點沿着飽和邊達到。達到不飽和頂點會產生增強效果。

初始化。S = {u}和T = {}（空集）。

迭代。如果S沒有未標記的頂點，則停止;沒有M從u的高級路徑。否則，請在S中選擇未標記的v。爲了從v中探索，先後考慮y中的每個N(v)，使得y不在T中。

如果y由m不飽和的，然後從y（根據需要擴大花）追溯到報告一個M -augmenting (u, y) -path。

如果y在S，那麼已經發現開花。暫停v的探索並收縮開花，將其頂點S和T替換爲S中的單個新頂點。繼續從較小圖中的頂點搜索。

否則，y通過M匹配到一些w。包括y於T（從v達到），並且包括w於S（從y達到）。

在探索v的所有這樣的鄰居之後，標記v並重復。

這裏描述的算法運行時間爲O（n^4），其中n是頂點的數量。 West給出了與O（n^5/2）或O（n^1/2 m）（m是邊數）一樣快的版本。如果你想要這些參考文獻，或引用Edmonds的原始論文，只要問一下，我會把它們從索引中挖出來（這本書很吸引人）。

Answer 2

我認爲，通過建立一套規則並用一組簡單的查詢攻擊你的密鑰映射表來實現更好，這些查詢以迭代方式強制實施每個規則。也許我太簡單了，因爲你的例子很簡單。

以下是規則的例子 - 只有你自己才能決定哪些應用：

• 如果有重複，用最低的（舊）代理鍵
• 使用自然鍵從與行最高（最新）代理鍵
• 使用自然鍵從最完整映射行
• 使用的每一個自然鍵
• 最近occurence ...？

一旦建立了規則，編寫重建鍵映射的查詢就很簡單了。我不確定這可能是一個數學問題？

Answer 3

如果您正在尋找一個實現，Eppsteins PADS庫有一個匹配的算法，這應該足夠快，爲您的目的，一般匹配算法在CardinalityMatching.py。實施中的評論解釋了正在發生的事情。該庫易於使用，在Python中提供一個圖表，您可以使用字典G來表示圖形，例如G [v]給出頂點v的鄰居列表（或集合）。

示例：

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

給出了具有4個頂點的線圖。