0

有这两张表：

TableA
ID  Opt1    Opt2    Type
1   A       Z       10
2   B       Y       20
3   C       Z       30
4   C       K       40

和

TableB
ID  Opt1    Type
1   Z       57
2   Z       99
3   X       3000
4   Z       3000

什么是找到这两个表之间任意关系的好算法？在这个例子中，我希望它找到包含Op1 = C在 TableA 和Type = 3000TableB 中的记录之间的明显关系。

我可以以某种方式考虑先验，但似乎不太实用。你们说什么？

谢谢。

4

2 回答 2

1

这听起来像是一个关系数据挖掘问题。我建议尝试罗斯昆兰的 FOIL：http ://www.rulequest.com/Personal/

于 2011-11-04T12:50:21.633 回答
1

在伪代码中，一个简单的实现可能如下所示：

  1. for each column c1 in table1
  2.    for each column c2 in table2
  3.      if approximately_isomorphic(c1, c2) then
  4.         emit (c1, c2)

  approximately_isomorphic(c1, c2)
  1. hmap = hash()
  2. for i = 1 to min(|c1|, |c2|) do
  3.    hmap[c1[i]] = c2[i]
  4. if |hmap| - unique_count(c1) < error_margin then return true
  5. else then return false

这个想法是这样的：对每列的元素与其他列的元素进行成对比较。对于每一对列，构造一个连接两列对应元素的哈希映射。如果哈希映射包含与第一列的唯一元素相同数量的链接，那么你有一个完美的同构；如果你有更多，你有一个近同构；如果你有更多，直到第一列中的元素数量，你有可能不代表任何相关性。

您输入的示例：

  ID & anything  : perfect isomorphism since all of ID are unique

  Opt1 & ID      : 4 mappings and 3 unique values; not a perfect
                  isomorphism, but not too far away.
  Opt1 & Opt1    : ditto above
  Opt1 & Type    : 3 mappings & 3 unique values, perfect isomorphism

  Opt2 & ID      : 4 mappings & 3 unique values, not a perfect
                  isomorphism, but not too far away
  Opt2 & Opt2    : ditto above
  Opt2 & Type    : ditto above

  Type & anything: perfect isomorphism since all of ID are unique

为获得最佳结果，您可以通过两种方式执行此过程 - 即将 table1 与 table2 进行比较，然后将 table2 与 table1 进行比较 - 以查找双射映射。否则，您可能会被琐碎的情况甩掉……第一个中的所有值都不同（完全同构）或第二个中的所有值都相同（完全同构）。另请注意，此技术提供了一种对列的相似或不同程度进行排名或测量的方法。

这是朝着正确的方向发展吗？顺便说一句，这是 O(ijk)，其中 table1 有 i 列，table 2 有 j 列，每列有 k 个元素。从理论上讲，如果您可以在不进行成对比较的情况下找到相关性，那么您可以为一种方法做的最好的事情是 O(ik + jk)。

于 2011-11-04T17:12:16.910 回答