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

EN

在数据库中存储图形非常简单:您有一个用于节点的表和一个用于边的表，该表充当节点表和其自身之间的多对多关系表。如下所示：

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没有任何对图形的内置支持，并且其基本操作不容易适应图形。这是可以做到的，特别是如果您有一个支持递归SQL的数据库(PostgreSQL、Firebird、一些专有数据库)，但这需要一些考虑。如果你想这样做，我的建议是发布更多关于特定查询的问题。

这是一种可以接受的方法。您需要考虑如何处理这些信息。更有可能的是，您需要一种独立于数据库的语言来执行这种类型的数据所暗示的与图形相关的计算。Skiena's 具有广泛的剖面图数据结构及其操作。

不考虑您可能执行的查询类型，先从两个表vertices和edges开始。顶点很简单，一个标识符和一个名称。给定多重图，边是复杂的。边应该由两个顶点(即外键)和一些附加信息的组合唯一地标识。附加信息取决于您正在解决的问题。例如，如果航班信息，起飞和到达的时间和航空公司。此外，您还需要确定边缘是否定向(即单向)，并跟踪该信息。

根据计算的不同，你可能会得到一个问题，而这个问题可以用某种人工智能/机器学习算法来更好地解决。例如，最佳航班。Programming Collective Intelligence一书中有一些用于此目的的有用算法。但是数据保存在哪里并不会改变算法本身。

嗯，信息必须存储在某个地方，关系数据库不是一个坏主意。

它只是一个多对多的关系，一个包含节点列表的表，以及一个包含边/连接列表的表。