MySQL - представление непрямого графа

Question

У меня есть следующая проблема, и мне интересно, можно ли ее решить в native SQL. Предположим, что у меня есть неориентированный граф, который не должен содержать более одного ребра между двумя узлами.

Я хотел бы представить его в таблице базы данных, которая имеет, например, следующая схема и содержание:

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

Я хотел бы установить ограничение на уровне базы данных в MySQL, который предотвращает, что я мог бы добавить следующую запись в таблице выше

5 | B | A | 

Кто-то знает любое решение для этого в MySQL?

Заранее благодарен!

Answer 1

Если MySQL поддерживается проверочные ограничения, вы могли бы просто:

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, поэтому вам придется защищать этот случай от триггеров или логики приложения.

Answer 2

Вы в порядке с 'сортировкой' имен узлов? То есть, Node1 гарантированно будет меньше значения Node2.

Например, пара (С, А) гарантированно будет записана в виде: (A, C)

Ваш код должен позаботиться об этом; вы можете использовать min/max для его обработки.