SQL-запрос для обработки сложных отношений

Question

У меня есть сценарий, где у меня есть большое количество блогов. Все эти блоги имеют несколько сообщений. Каждое сообщение в блоге может ссылаться на сообщение в другом блоге, но тогда они должны никогда возвращать ссылку из этого блога в блог-ссылку.

Для уточнения:

• Сайт А ссылается на Сайт Б (и может ссылаться на другие Сайты)
• Сайт B, тогда не может ссылка на сайт A (но может ссылаться на другие сайты)

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

Сайт A может ссылаться на сайт B столько раз, сколько ему угодно, и каждое сообщение может ссылаться на несколько других сообщений. Пример сценария может быть:

• Сайт А ссылается на Сайт Б
• Сайт C ссылается на Сайт B
• Сайт D ссылается на Сайт A

В приведенных выше данных:

• Сайт A может ссылаться на сайт C (или сайт B снова)
• Сайт B может ссылаться на Сайт D
• Сайт C может ссылаться на сайт A или сайт D (или сайт B снова)
• Сайт D может ссылаться на сайт B или сайт C (или сайт A снова)

Вот ссылка на некоторые тестовые данные и дамп двух необходимых таблиц: http://pastie.org/1506715

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

SELECT 
t1.* , t2.* FROM test_posts t1, test_posts as t2
WHERE
t1.post_id != t2.post_id
ORDER BY
t1.post_id, t2.post_id;

Это дает мне все возможные отношения между постами. С чем я борюсь, так это как исключить отношения, которые будут противоречить вышеупомянутым правилам. Предыдущие отношения записаны в таблице test_smartlinks_to_websites, с post_id, принадлежащим «исходному» веб-сайту, и website_id, принадлежащим «конечному» сайту (помня, что отношения между веб-сайтами фактически односторонние, а не сообщения).

Я пытался использовать подзапрос NOT EXISTS, но я не уверен в точном предложении (или это правильный подход).

Answer 1

Поправь меня, если я ошибаюсь.Похоже, ваша задача - определить циклы в ориентированном графе.Это не так сложно, как кажется.Пожалуйста, смотрите этот пост в блоге о том, как это делается в SQL: http://devio.wordpress.com/2009/09/13/finding-cycles-in-directed-graphs-using-tsql/. Также смотрите эту ссылку для поиска в ширину в SQL: http://willets.org/sqlgraphs.html.

РЕДАКТИРОВАНИЕ: добавлены изображения для ясности и понимания направленного ациклическогои циклические графики.

Например, вот что-то, что напоминает вашу ситуацию.Это не один граф, а набор графов (или лес, если они были деревьями).Обратите внимание, что нет общего корня.Это просто узлы, связанные как-то.В большом подграфе есть цикл, где узлы ссылаются друг на друга.Если убрать ссылку вверх, подграф становится ациклическим.