如何在关系数据库中保留图形数据结构？
我考虑过创建一个Vertices表和一个Edges表,但是在内存中构建图形并遍历子图需要大量的查找？我想避免过多的数据库读取.有没有其他方法可以持久保存图表？
旁注:我听说过Neo4j,但我的问题是如何在概念上代表标准数据库中的图形.我对mongodb等NoSQL解决方案持开放态度.
Jür*_*nig 30
遗憾的是答案:你的考虑在每个方面都是完全正确的.您必须将节点(顶点)存储在一个表中,并且Edges引用FromNode和ToNode以将图形数据结构转换为关系数据结构.你也是对的,这最终会导致大量的查找,因为你无法将它分成子图,可能会立即查询.您必须从节点遍历到边缘到节点到边缘到节点...依此类推(递归,而SQL正在使用集合).
重点是...
关系,面向图,面向对象,基于文档是满足不同要求的不同类型的数据结构.这就是它的全部内容以及为什么这么多不同的NoSQL数据库(大多数都是简单的文档存储)出现了,因为以关系方式组织大数据毫无意义.
备选1 - 面向图形的数据库
但是也有面向图形的NoSQL数据库,这使得图形数据模型成为像OrientDB这样的一流公民,我现在正在玩一点点.关于它的好处是,尽管它将数据保存为图形,但它仍然可以以关系或甚至面向对象或面向文档的方式使用(即通过查询普通的旧SQL).然而,遍历图表是确保从中获取数据的最佳方式.
备选方案2 - 使用内存中的图形
在快速路由方面,像Graphhopper这样的路由框架在内存中构建了完整的Graph(数十亿节点).因为Graphhopper使用其GraphStore的MemoryMapped实现,甚至可以在仅需要一些MB内存的Android设备上运行.完整的图形在启动时从数据库读入存储器,然后在那里完成路由,因此您无需查找数据库.
- +1 BTW:'graph DB'和'relational DB'之间真正唯一的区别是查找的**实现**.如果通过直接指针到达节点表中引用的边列表,则可以将其称为图形数据库,尽管数据仍然可以在表中组织!因此,如果这个查找是每个边缘列表的log(n)甚至是每个边缘,那么人们将其称为"关系数据库"并且遍历图形相当昂贵(如果存储是mmapped或内存中的事实,则无关) . (6认同)
- @Karussell值得注意的是,大多数SQL数据库都支持基于散列的索引,边缘/顶点查找是O(1),就像图形数据库一样.O(log(n))查询时间通常与基于B树的索引相关联,这些索引主要用于数据排序很重要(边缘/顶点ID通常不相关). (2认同)
小智 10
我遇到了同样的问题，并决定最终采用以下结构，这需要 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
使用一个查询获取所有节点，然后使用另一个查询获取所有边。
现在构建您的首选方式来存储图形（例如，邻接列表）并继续您的应用程序流程。
除了之前的答案之外，MS SQL Server从 2017 开始添加了对 Graph Architecture 的支持。
它遵循所描述的具有节点和边表的模式（应使用特殊的“AS NODE”和“AS EDGE”关键字创建）。
它还引入了新的 MATCH 关键字“以支持模式匹配和遍历图”，如下所示（在下面的示例中，朋友是边表的名称）：
SELECT Person2.name AS FriendName
FROM Person Person1, friend, Person Person2
WHERE MATCH(Person1-(friend)->Person2)
AND Person1.name = 'Alice';
在 redgate Hub 上还有一组非常好的关于 SQL Server 图形数据库的文章。