3

我的工作中有几种类型的多对多表。我有将单词与其他单词（ngram）相关联的应用程序，以及可以将用户与其他用户（朋友/关注者）相关联的数据库。

我想知道如何与这些数据建立关系，以便为我的应用程序推荐和我的用户找到有用的联系。

采用以下简单的数据库表，其中包含将节点链接到另一个节点的外键。

id | node1  | node2 
--------------------
1  |   1    |   2
2  |   1    |   3
3  |   1    |   4
4  |   2    |   1
5  |   2    |   3
6  |   2    |   5
7  |   3    |   1

例如，在上表中，很明显“1”是最受欢迎的，因为它被链接到最多（2 和 3）。很明显，也许“2”应该与“4”相关联，因为“2”与“1”有很多关系（并且“1”与“4”相关联）。

因此，例如，我可以找到：

  • 将节点连接到其他节点的路径。
  • 基于相似性的有益联系（建议）
  • 共享相关连接的节点组

user <=> friends其他常见的关系形式有or 之类的东西blog_post <=> tags。

我正在寻找可以由前端直接运行的 SQL 查询，或者可以在每晚运行以从这些数据中提取关系的 map-reduce 作业。

4

4 回答 4

1

正如 ffriend 指出的那样，您的数据结构非常适合您尝试做的事情。这更像是一个前端问题，例如，您将如何呈现信息？

需要研究的是一些节点遍历技术，以确定节点之间的跳数（相关性）、连接到单个节点的节点数（宽度）、有意义的路径可以走多少跳（深度）。我唯一会考虑的另一件事是用于帮助确定相关性。这或多或少是在使用期间节点路径已经经过多少次的计数器。这是您可以开始为特定路径分配权重的地方。例如，如果从 1 到 5 (1 -> 2 -> 5) 的路径作为第一次遍历，它可能看起来像这样......

id | node1  | node2  | count
------------------------------
1  |   1    |   2    |   1
2  |   1    |   3    |   0
3  |   1    |   4    |   0
4  |   2    |   1    |   0
5  |   2    |   3    |   0
6  |   2    |   5    |   1
7  |   3    |   1    |   0

该方法可以通过使用计数器作为权重因子来帮助识别节点之间的含义关系。

请记住，使用这种数据结构，您将需要一个方法去每个方向（1 -> 5 和 5 -> 1）

于 2012-07-16T18:28:15.843 回答
0

也许寻找 NOSQL 数据库将是解决您问题的更好方法。更具体地说，首先使用像 neo4j 这样的图形数据库来表示您的 sql 数据，而不是简单地遍历图形以查找您想要的关系和组。

在您的用例中，使用图形数据库总是更好，因为性能比在表上使用具有多个连接的 sql 时快几倍。

于 2012-12-05T14:39:24.063 回答
0

Powergagets可以使用 SQL 数据制作图形和图表。

于 2012-04-13T19:34:55.923 回答
0

根据我对图的记忆，Dijkstra-Prinn 和 Kruskal 的算法在这里可能对你有用。它们都是搜索算法（我不记得它们是 BFS 还是 DFS……已经有一段时间了：p），这将帮助您获取整个图形并找到最佳遍历路径。

他们不会为您提供 SQL 查询，但他们会提供一个数学“跳板”来帮助您获得适合您的 SQL 查询的逻辑。

正如水上乐园所说的他的计数器系统，您可以利用上述程序获取一个起点，然后使用计数器系统进行双重检查。

另外，正如 ffriend 之前所说，我不确定您是出于优化目的还是出于其他用途收集这些数据，所以我认为如果您重组您的问题，您可能会得到更好的帮助。

祝你好运。

于 2012-07-23T17:57:32.613 回答