Моделирование смежности стран в 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
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 3

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

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 4

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

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'

Answer 5

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