51

I've considered creating a Vertices table and an Edges table but would building graphs in memory and traversing sub-graphs require a large number of lookups? I'd like to avoid excessive database reads. Is there any other way of persisting a graph?

Side note: I've heard of Neo4j but my question is really how to conceptually represent a graph in a standard database. I am open to some NoSQL solutions like mongodb though.

4

4 回答 4

45

不幸的是，答案是：你的考虑在每一点上都是完全正确的。您必须将节点（顶点）存储在一个表中，并且边缘引用 FromNode 和 ToNode 以将图形数据结构转换为关系数据结构。而且您也是对的，这最终会导致大量查找，因为您无法将其划分为可能会立即查询的子图。您必须从节点遍历到边缘到节点到边缘到节点......等等（递归，而 SQL 正在使用集合）。

重点是...

关系，面向图形，面向对象，基于文档是满足不同要求的不同类型的数据结构。这就是它的全部意义所在，以及为什么会出现如此多不同的 NoSQL 数据库（其中大多数是简单的文档存储），因为以关系方式组织大数据根本没有意义。

备选方案 1 - 面向图形的数据库

但也有面向图的 NoSQL 数据库，它们使图数据模型成为像OrientDB一样的一等公民，我现在正在玩一些。它的好处是，尽管它以图形的形式保存数据，但它仍然可以以关系甚至面向对象或面向文档的方式使用（即通过使用普通的旧 SQL 进行查询）。尽管如此，遍历图表无疑是从中获取数据的最佳方式。

备选方案 2 - 使用内存中的图形

当谈到快速路由时，像Graphhopper这样的路由框架会在内存中构建完整的 Graph（Billions of Nodes）。因为 Graphhopper 使用其 GraphStore 的 MemoryMapped 实现，它甚至可以在只需要一些 MB 内存的 Android 设备上运行。完整的图表在启动时从数据库读取到内存中，然后在那里完成路由，因此您无需查找数据库。

于 2013-11-30T19:19:43.083 回答
13

我遇到了同样的问题并决定最终采用以下结构，这需要 2 个数据库查询，然后剩下的工作在内存中：

将节点存储在表中并使用每个节点记录引用图形：

Table Nodes

id  | title | graph_id
---------------------
105 | node1 | 2
106 | node2 | 2

还将边存储在另一个表中，并再次使用每条边引用这些边所属的图形：

Table Edges

id | from_node_id | to_node_id | graph_id
-----------------------------------------
1  | 105          | 106        | 2
2  | 106          | 105        | 2

用一个查询获取所有节点，然后用另一个查询获取所有边。

现在构建您的首选方式来存储图形（例如，邻接列表）并继续您的应用程序流程。

于 2017-10-29T09:40:00.947 回答
7

添加到前面的答案的事实是 MS SQL Server从 2017 开始添加了对 Graph Architecture 的支持。

它遵循具有节点和边缘表的描述模式（应使用特殊的“AS NODE”和“AS EDGE”关键字创建）。 节点和边表结构

它还引入了新的 MATCH 关键字“以支持模式匹配和遍历图”，如下所示（friend 是下例中边表的名称）：

SELECT Person2.name AS FriendName
FROM Person Person1, friend, Person Person2
WHERE MATCH(Person1-(friend)->Person2)
AND Person1.name = 'Alice';

在 redgate Hub 上还有一组关于 SQL Server 图形数据库的非常好的文章。

于 2019-06-04T09:38:58.723 回答
0

我将不同意这里的其他帖子。如果您有特殊类别的图有限制，您通常可以采用更专业的设计（例如，每个顶点的边数有限，只需要遍历一种方式等）。

然而，为了存储任意图，关系数据库做出了一组非常好的权衡，几乎在所有情况下都表现良好。此外，数据需求往往会随着时间而改变，而关系数据库让您可以轻松地更改存储和查找，而无需更改数据表示。

让我们回顾一下您的设计：

  • 一张顶点表（id，data）
  • 一张边表（startId、endId、数据）

首先观察存储是有效的，因为它与要存储的数据成正比。如果我们有 10 个顶点和 10 条边，我们存储 20 条信息。

现在，让我们看看查找。假设我们在顶点 id 上有一个索引，我们至少可以在其中查找我们想要的任何数据log(n)（根据索引可能更好）。

  • 给定一个节点，告诉我离开它的边
  • 给定一个节点，告诉我进入它的边
  • 给定一条边，告诉我它来自或进入的节点

这就是您需要的所有基本查询。

现在假设您有一个“图形数据库”，它存储离开每个顶点的边列表。这使得每个顶点的大小可变。穿越起来稍微容易一些。但是，如果你想穿越另一个方向怎么办？现在，您还存储了进入每个顶点的边列表。现在您拥有该信息的两个副本，并且数据库（或您的开发人员）必须做很多工作以确保它们永远不会不同步。

O(log(n)) 与 O(1)

关系数据库索引通常以排序形式存储数据，或者正如其他人指出的那样，也可以使用哈希表。即使您坚持使用 sorted，它也会表现得非常好。

首先请注意，big oh 衡量的是可扩展性，而不是性能。对于小型数据集，散列可能比许多循环慢。尽管对于二分搜索O(1)更好，但log2也相当不错。您可以通过 30 个步骤搜索 10 亿条记录！此外，它对缓存和分支预测器友好。

于 2022-02-23T00:00:43.673 回答