关系数据库的数据结构:如何在关系数据库中持久化图形数据结构

我已经考虑过创建一个 Vertices 表和一个 Edges 表,但会在内存中构建图形并遍历子图需要大量的查找?我想避免过多的数据库读取。还有其他方法来持久化图吗?

旁注:我听说过 Neo4j,但我的问题是如何在标准数据库中概念性地表示一个图。

50

答案是不幸的:你的考虑在每一点上都是完全正确的。你必须将节点 (Vertices) 存储在一个表中,并且 Edges 引用 FromNode 和 ToNode 来将图形数据结构转换为关系数据结构。而且你也是对的,这最终会导致大量的查找,因为你无法将其分区为子图,可能会立即被查询。你必须从 Node 到 Edge 遍历到 Edge...

重点是...

关系,面向图形,面向对象,基于文档是满足不同要求的不同类型的数据结构。这就是为什么出现了这么多不同的 NoSQL 数据库(其中大多数是简单的文档存储),因为以关系方式组织大数据根本没有意义。

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

但是也有面向图的 NoSQL 数据库,这使得图数据模型成为像OrientDB这样的一流公民,我现在正在玩一点。关于它的好处是,尽管它将数据保存为图,但它仍然可以以关系甚至面向对象或面向文档的方式使用(即通过使用普通的旧 SQL 查询)。尽管如此,Traversing the graph是确保获取数据的最佳方法。

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

当涉及到快速路由时,像Graphhopper这样的路由框架在内存中构建了完整的 Graph(数十亿个节点)。由于 Graphhopper 使用其 GraphStore 的 MemoryMapped 实现,因此甚至可以在只需要一些 MB 内存的 Android 设备上运行。启动时将完整的图从数据库读取到 memor 中,然后在那里进行路由,因此您无需查找数据库。

14

我遇到了同样的问题,并决定最终使用以下结构,这需要 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

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

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

8

添加到前面的答案的事实,MS SQL Server 添加support for Graph Architecture starting with 2017

It follows the described pattern of having Nodes and Edges tables (which should be created with special "AS NODE" and "AS EDGE" keywords). Node and edge tables structure

它还引入了新的 MATCH 关键字“以支持模式匹配和遍历图形”,如下所示(friend 是示例中edge表的名称):

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

还有一组非常好的文章on SQL Server Graph Databases on redgate Hub

1

我不同意这里的其他帖子,如果你有特殊类的图形有限制,你通常可以摆脱更专业的设计(例如,每个顶点的边数量有限,只需要遍历一种方式等)。

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

让我们来看看你的设计:

一个表的顶点(ID,数据)

一个表的边缘(startId,endId,数据)

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

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

给定一个节点告诉我离开它的边缘

给定一个节点告诉我进入它的边缘

给定一个边缘告诉我它来自或进入的节点

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

现在假设您有一个“图形数据库”,其中存储了离开每个顶点的边的列表。这使每个顶点的大小可变。遍历起来更容易。但是,如果要遍历另一个方向怎么办?现在,您还可以存储进入每个顶点的边的列表。现在,您有了该信息的两个副本,数据库(或开发人员)必须做很多工作,以确保它们永远不会不同步。

O (log (n)) vs O (1)

关系数据库索引通常以排序的形式存储数据,或者正如其他人所指出的那样,也可以使用哈希表。

首先请注意,大 oh 衡量的是可伸缩性,而不是性能。对于小数据集,哈希可能比许多循环要慢。即使哈希O(1)更好,二进制搜索O(log2)也非常好。您可以在 30 个步骤中搜索十亿条记录!此外,它是缓存和分支器友好的。

本站系公益性非盈利分享网址,本文来自用户投稿,不代表边看边学立场,如若转载,请注明出处

(645)
Fx5u编程手册:如何在Python中将1分钟打开-高-低-关闭数据转换为另一个时间范围(fx:5分钟 1小时)
下一篇

相关推荐

发表评论

登录 后才能评论

评论列表(38条)