0

所以我有这个项目扩展了现有的代码库，它建立在 MySQL 数据库上。我有一个表，其元组表示建筑物中的位置，我正在制作一个表，表示连接图中这些位置的边以进行寻路。它只是一个简单的两列表，每一列都包含一个 ID，该 ID 是引用位置表的外键。所以总结一下，情况是这样的：

CREATE TABLE node (
    ID int(10) AUTO_INCREMENT NOT NULL,
    (...)
    PRIMARY KEY(ID)
);

CREATE TABLE edge(
    ID_1 int(10),
    ID_2 int(10),
    FOREIGN KEY (ID_1) REFERENCES node(ID),
    FOREIGN KEY (ID_2) REFERENCES node(ID)
);

这是一个现有的假设，即图是对称的，即如果节点 A 与节点 B 有一条边，则节点 B 必须与节点 A 有一条边。这里忽略了单向门的情况，但似乎不适用于我的领域。因此，给定节点 A 和 B 已连接，它们的连接可以通过以下三种方式中的任何一种存储在边缘表中：

{(A,B)}
{(B,A)}
{(A,B),(B,A)}

我用这张表回答的问题是“给定这个节点，它的邻居是什么节点？” 目前我的应用程序使用这样的查询来做到这一点：

SELECT * FROM node
WHERE ID IN(
    SELECT ID_2
    FROM edge
    WHERE ID_1=?
    UNION
    SELECT ID_1
    FROM edge
    WHERE ID_2=?
);

但是，我的直觉是使用 CHECK 约束来确保只能存储后一种结构，而MySQL 显然不支持. 从那个答案来看，为了模拟这样的约束，我必须为每个操作编写触发器，以使每个边缘都存储在两个排序中。优点是它表现得比你自然期望的更好，并且可以回答这个问题

SELECT * FROM node
WHERE ID IN(
    SELECT ID_2
    FROM edge
    WHERE ID_1=?
);

一旦我读到了模拟 CHECK 的触发器，我就和一个朋友讨论过，他建议确保自反存储是浪费的（双倍存储使用），应该留给应用程序正确处理数据库。现在我有点不确定实际上最好的解决方案是什么 - 数据库是否应该通过使用触发器将插入和删除加倍来确保自反性，或者应用程序是否应该继续读取未自反存储的数据以使其看起来像它一样？让我的数据库以多种方式表示相同的数据让我有点担心。这不合理吗？UNION 等是否会造成明显的性能损失？

（针对相当小的站点，该系统不太可能超过数万个节点，典型节点最多有 6 个边）。

4

1 回答 1

0

实际上，在您的情况下，最好将每个连接视为一个连接（然后您就可以在需要时阻止！）。如果房间之间有多个连接怎么办？就像一个房间有两个独立的门进入同一个大厅？

无论如何，这些都是很好玩的东西......

就我个人而言，我会根据方向存储每个连接，所以如果 a 和 b 之间有一个双向门，我会这样存储

tbl_connections

current_room_id edge      connecting_room_id
1               north     2
2               south     1
1               east      3
1               west      4
4               east      1
1               south     5

是的，如果您有可用的数据，我会包括哪个边缘是连接 - 当他们决定包含它时，它可能会有所帮助....（在上述结构中，您可以从 1 到 3，但不能从 3 到 1）。

像这样存储，然后您可以使用以下方法简单地获取房间邻居（和方向）：

SELECT connecting_room, edge
FROM tbl_connections
WHERE current_room_id = 1;

这应该给你：

2, north
3, east
4, west
5, south

您还可以根据您所在的房间以及您打算使用此模式通过的边缘来映射路径。

存储你所说的自反数据是一种非常常见的解决方案，在这种情况下，我认为这是正确的方法。

于 2012-08-02T14:26:58.813 回答