Моделирование смежности страны в SQL

Question

Я пытаюсь моделировать, какие страны граничат друг с другом в MySQL. У меня есть три таблицы:

nodes 
----- 
node_id MEDIUMINT 

countries 
--------- 
country_id MEDIUMINT (used as a foreign key for nodes.node_id) 
country CHAR(64) 
iso_code CHAR(2) 

node_adjacency 
-------------- 
node_id_1 MEDIUMINT (used as a foreign key for nodes.node_id) 
node_id_2 MEDIUMINT (used as a foreign key for nodes.node_id) 

Ценит таблица узлов избыточна в этом примере, но это является частью более крупной архитектурой, где узлы могут представлять множество других предметов, кроме стран.

Вот некоторые данные (идентификаторы (которые появляются во всех трех таблицах) и страны)

59 Bosnia and Herzegovina 
86 Croatia 
130 Hungary 
178 Montenegro 
227 Serbia 
232 Slovenia 

Хорватия граничит со всеми другими странами, и это представлено в таблице node_adjacency как:

59 86 
86 130 
86 178 
86 227 
86 232 

Знак Сербии может отображаться как node_id_1 или node_id_2. Данные в этой таблице являются, по существу, не направленными данными графа.

Вопросы:

Учитывая название «Хорватия», то, что SQL я должен использовать для получения своих соседей?

Bosnia and Herzegovina 
Hungary 
Montenegro 
Serbia 
Slovenia 

Будет ли полученная прибыль от повышения эффективности при хранении информации о смежности в виде данных ориентированного графа? Например. Хорватия граничит Венгрия, Венгрия и Хорватия граничит, по сути дублируют хранения отношений:

86 130 
130 86 

Answer 1

Это недалеко от верхней части моей головы, так что я не знаю, если это самый производительный решение, и это, возможно, потребуется подправить, но я думаю, что это должно работать:

SELECT 
    BORDER.country 
FROM 
    Countries AS C 
LEFT OUTER JOIN Node_Adjacency NA1 ON 
    NA1.node_id_1 = C.country_id OR 
    NA1.node_id_2 = C.country_id 
INNER JOIN Countries AS BORDER ON 
    (
    BORDER.country_id = NA1.node_id_1 OR 
    BORDER.country_id = NA1.node_id_2 
    ) AND 
    BORDER.country_id <> C.country_id 
WHERE 
    C.country = 'CROATIA'   

С вашего графика не направлено, я не думаю, что имеет смысл хранить его как ориентированный граф. Вы также можете захотеть Google «Celko SQL Graph», поскольку он провел много расширенной работы над деревьями, графиками и иерархиями в SQL и имеет отличную книгу, посвященную теме.

Answer 2

Я бы сохранить оба отношения (Венгрия граничит Хорватия, Хорватия граничит Венгрия), так что вы только когда-либо нужно запросить один столбец.

SELECT c.country FROM countries AS c 
INNER JOIN node_adjacency AS n 
ON n.node_id_1 = c.countryID 
WHERE c.countryID = 86 

Answer 3

Если вы копируете отношения (т.е. страны А разделяет границу с B и B акции границы с А), вы можете получить путь с простым выбором. Если вы сохраняете только одну взаимосвязь на пару стран, вам нужно будет искать по обоим столбцам в таблице node_adjacency (выполняется два оператора select и выполняется объединение).

Answer 4

Для этого оба колонок, просто накидных два запроса вместе (заимствования Мэтью Джонса):

SELECT c.country FROM countries AS c 
INNER JOIN node_adjacency AS n 
ON n.node_id_1 = c.countryID 
WHERE c.countryID = 86 
UNION 
SELECT c.country FROM countries AS c 
INNER JOIN node_adjacency AS n 
ON n.node_id_2 = c.countryID 
WHERE c.countryID = 86 

Если вы делаете это таким образом, вы продублировать запрос вместо данных (использовать 50% меньше мест) , и это все еще очень просто.

Answer 5

Вы можете создать представление накидной, чтобы избежать дублирования:

CREATE VIEW adjacency_view (node_id_1, node_id_2) 
AS 
SELECT node_id_1, node_id_2 FROM node_adjacency 
UNION ALL 
SELECT node_id_2, node_id_1 FROM node_adjacency 

Таким образом, ваш запрос становится достаточно прост:

SELECT c1.country 
FROM adjacency_view 
INNER JOIN countries AS c1 on c1.country_id = adjacency_view.node_id_1 
INNER JOIN countries AS c2 on c2.country_id = adjacency_view.node_id_2 
WHERE c2.country = 'CROATIA'