1

我正在维护一个数据仓库，其中包含关于必须合并的一类实体的多个数据源。每个源都有一个自然键，并且应该发生的是，始终为每个自然键创建一个且只有一个代理键。如果来自一个源系统的具有特定自然键的一条记录与来自具有不同自然键的另一个源系统的另一条记录表示相同的实体，则将为两者分配相同的代理键。

换句话说，如果源系统 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

所以仓库乱七八糟。还有比这更复杂的情况。我有一个很短的清理时间表，需要找出一组干净的自然键映射的代理键。

一点谷歌搜索表明，这可以建模为非二分图中的匹配问题：

维基百科 - 匹配

MIT 18.433 组合优化 - 非二分匹配讲义

我需要 Edmond 的路径、树和花算法的易于理解的实现（不是最佳执行）。我没有正式的数学或计算机科学背景，我所拥有的是自学的，而且我今晚不在数学上。任何人都可以帮忙吗？一个指导我实现的写得很好的解释将不胜感激。

编辑：

数学方法是最优的，因为我们想要最大化全局适应度。贪婪的方法（首先获取 A 的所有实例，然后是 B，然后是 C...）会将您绘制到局部最大值角落。

无论如何，我把这个推回业务分析师手动完成（全部 2000 万）。我正在帮助他们评估全局匹配质量。这是理想的，因为无论如何他们都是签字的人，所以我的背面被遮住了。

不使用代理键不会改变匹配问题。仍然需要发现和维护 1:1 自然键映射。代理键是一个方便的锚，仅此而已。

4

3 回答 3

2

我的印象是您以错误的方式处理此问题；正如 cdonner 所说，还有其他方法可以重建关键结构而不会经历这种混乱。特别是，您需要保证自然键对于给定记录始终是唯一的（违反此条件是您陷入困境的原因！）。拥有两者ABC并DEF识别相同的记录是灾难性的，但最终是可以修复的。我什至不确定你为什么需要代理键。虽然它们确实有很多优点，但我会考虑使用纯关系并将它们从您的模式中剔除，例如 la Celko；它可能会让你摆脱这个烂摊子。但这是在查看整个架构后必须做出的决定。

为了解决您的潜在解决方案，我拿出了我的 DB West 的图论简介，第二版，它在第 144 页描述了开花算法。您需要一些数学背景，包括数学符号和图论，才能遵循算法，但它足够简洁，我认为它可以提供帮助（如果你决定走这条路）。如果您需要解释，请先咨询有关图论的资源（维基百科、您当地的图书馆、谷歌等），或​​者询问您是否没有找到您需要的东西。

3.3.17。算法。（Edmonds 的 Blossom 算法 [1965a]---草图）。

输入。一个图G，一个匹配M，G一个-M不饱和顶点u。

主意。探索M从 的交替路径u，为每个顶点记录到达它的顶点，并在找到时收缩花朵。维护集合S，T类似于算法 3.2.1 中的集合，S包含u和 顶点沿饱和边到达。到达不饱和顶点会产生增强。

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

迭代。如果S没有未标记的顶点，则停止；没有M从u. 否则，请选择未标记v的S. 从探索开始v，依次考虑每一个y在N(v)这样y的不在的T。

如果y不饱和m，则从y（根据需要扩展花朵）追溯以报告M-augmenting (u, y)-path。

如果y在 中S，则已找到一朵花。暂停对花朵的探索v和收缩，将其顶点替换为 中的S和T中的单个新顶点S。在较小的图中从该顶点继续搜索。

否则，y与某些wby匹配M。包括y在T（从 到达v）和包括w在S（从 到达y）。

在探索了 的所有这些邻居之后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 表示图形，这样 G[v] 会给出顶点 v 的邻居列表（或集合）。

例子：

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

给出一个有 4 个顶点的折线图.

于 2009-03-10T02:06:51.537 回答