Consulta SQL para manejar relaciones complejas

Question

Tengo un escenario donde tengo una gran cantidad de blogs. Todos estos blogs tienen múltiples publicaciones. Cada entrada de blog puede vincular a una publicación en otro blog, pero luego deben nunca vincular desde ese blog al blog de enlace.

Para aclarar:

• enlaces del sitio A al sitio B (y puede enlazar a otros sitios)
• sitio B a continuación no puede enlace al sitio (pero puede enlazar a otros sitios)

Cada vez que se realiza una publicación, guardo el ID de la publicación y la ID del sitio web al que enlaza. Es importante recordar que, una vez que una publicación única se vincula a cualquier publicación en otro sitio web, ese otro sitio web no puede enlazar desde en cualquier lugar, no solo la publicación a la que está vinculado.

El sitio A puede enlazar al sitio B tantas veces como quiera, y cada publicación puede vincular a más de una publicación. Un escenario de ejemplo podría ser:

• enlaces sitio A al sitio B
• sitio C enlaces a sitio B
• sitio Enlaces D a sitio

En los datos anteriores:

• El sitio A podría vincular al sitio C (o al sitio B nuevamente)
• El sitio B podría enlazar al sitio D
• Sitio C podría enlazar a sitio o sitio D (o sitio B de nuevo)
• sitio D podría enlace al sitio B o Sitio C (o del sitio de nuevo)

Aquí hay un enlace a algunos datos de prueba y un volcado de las 2 tablas necesarias: http://pastie.org/1506715

Creo que necesito una unión cruzada para obtener todas las combinaciones de enlaces posibles, pero luego factor en las relaciones existentes para evitar que los sitios se vinculen en la dirección opuesta. La consulta que tengo hasta ahora es:

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; 

Esto me da todas las relaciones posibles entre las publicaciones. Lo que estoy luchando es cómo excluir las relaciones que contradicen las reglas anteriores. Las relaciones anteriores se registran en la tabla test_smartlinks_to_websites, con post_id que pertenece al sitio web "originating" y al website_id que pertenecen al sitio "destination" (recordando que la relación es efectivamente unidireccional entre sitios web, no publicaciones).

He intentado usar una subconsulta NOT EXISTS, pero no estoy seguro de la cláusula exacta (o si ese es el enfoque correcto).

Answer 1

Corrígeme si me equivoco. Parece que su tarea es determinar los ciclos en el gráfico dirigido. No es tan complejo como parece. Por favor, consulte esta publicación de blog para saber cómo se hace en SQL: http://devio.wordpress.com/2009/09/13/finding-cycles-in-directed-graphs-using-tsql/. También vea este enlace para la primera búsqueda de amplitud en SQL: http://willets.org/sqlgraphs.html.

EDITADO: se han agregado imágenes para mayor claridad y comprensión de gráficos cíclicos y acíclicos dirigidos.

Por ejemplo, aquí hay algo que se parece a su situación. No es un solo gráfico sino un conjunto de gráficos (o bosque si fueran árboles). Tenga en cuenta que no hay una raíz común. Solo son nodos conectados de alguna manera. Hay un ciclo en el subgrafo más grande donde los nodos se referencian entre sí. Si para eliminar el enlace hacia arriba, el subgrafo se vuelve acíclico.