保证唯一代理键分配 - 非二分图最大匹配

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个顶点的线图。