MySQL - 无向图表示

Question

我有以下问题，我想知道是否可以用 native SQL 解决它。假设我有一个无向图，它在 2 个节点之间不能包含超过一条边。

我想在数据库表中表示它，例如以下方案及内容:

    ID|Node1|Node2|
    ---------------
    1 | A   | B   |
    2 | B   | C   |
    3 | D   | E   |
    4 | F   | D   |

我想在 MySQL 中的数据库级别设置一个约束，以防止我可以将以下记录添加到上面的表中

    5 | B   | A   |

有人知道在 MySQL 中对此有任何解决方案吗？

提前致谢!

Answer 1

如果 MySQL 支持 CHECK 约束，您可以简单地:

CREATE TABLE Edge (
    Node1 VARCHAR(50),
    Node2 VARCHAR(50),
    Direction ENUM('forward', 'backward'),
    PRIMARY KEY (Node1, Node2),
    INDEX (Node1, Node2),
    CHECK (Node1 <= Node2) -- Use < if you don't want self-referencing.
);

INSERT INTO Edge VALUES
    ('A', 'B', 'forward'),
    ('B', 'C', 'forward'),
    ('D', 'E', 'forward'),
    ('D', 'F', 'backward');

[SQL Fiddle]

然后，如果您尝试以下操作，则会违反 PRIMARY KEY:

INSERT INTO Edge VALUES ('A', 'B', 'backward');

不幸的是，MySQL 将允许...

INSERT INTO Edge VALUES ('B', 'A', 'forward');

...尽管有 CHECK 约束，所以您必须在触发器或应用程序逻辑中防止这种情况。