将图形数据结构映射到关系数据库是否有意义？

Question

特别是一个Multigraph.

一些同事提出了这一点,我完全感到困惑.

有什么见解吗？

Answer 1

将图形存储在数据库中非常简单:您有一个节点表和一个边表,它充当节点表和它自身之间的多对多关系表.像这样:

create table node (
  id integer primary key
);

create table edge (
  start_id integer references node,
  end_id integer references node,
  primary key (start_id, end_id)
);

但是,关于以这种方式存储图形存在一些棘手的问题.

首先,这个方案中的边缘是自然导向的 - 起点和终点是不同的.如果你的边是无向的,那么你要么在编写查询时要小心,要么在表中为每个边存储两个条目,一个在任一方向(然后小心写查询!).如果您存储单个边缘,我建议对存储的表单进行规范化 - 可能始终将具有最低ID的节点视为开始(并向表中添加检查约束以强制执行此操作).你可以有一个真正无序的表示,没有边缘引用节点,而是在它们之间有一个连接表,但这对我来说似乎不是一个好主意.

其次,上面的模式无法表示多图.你可以很容易地扩展它来做到这一点; 如果给定节点对之间的边缘是不可区分的,最简单的方法是向每个边缘行添加一个计数,说明所引用节点之间有多少条边.如果它们是可区分的,那么您将需要向节点表添加一些内容以允许它们被区分 - 自动生成的边缘ID可能是最简单的事情.

但是,即使整理了存储,您也会遇到使用图表的问题.如果你想对内存中的对象进行所有处理,而数据库纯粹用于存储,那么没问题.但是如果你想对数据库中的图形进行查询,那么你将不得不弄清楚如何在SQL中执行它们,它没有对图形的任何内置支持,并且其基本操作不容易适应使用图表.它可以完成,特别是如果你有一个带有递归SQL支持的数据库(PostgreSQL,Firebird,一些专有数据库),但它需要一些思考.如果你想这样做,我的建议是发布有关特定查询的进一步问题.