SQL-Abfrage zur Behandlung komplexer Beziehungen

Question

Ich habe ein Szenario, in dem ich eine große Anzahl von Blogs habe. Diese Blogs haben alle mehrere Beiträge. Jeder Blogbeitrag kann auf einen Beitrag in einem anderen Blog verweisen, aber sie sollten dann nunca Link zurück von diesem Blog zu dem verlinkenden Blog.

Zur Klarstellung:

• Site A verlinkt auf Site B (und kann auf andere Sites verlinken)
• Standort B dann kann nicht Link zu Site A (kann aber zu anderen Sites verlinken)

Jedes Mal, wenn ein Beitrag erstellt wird, speichere ich die ID des Beitrags und die ID der Website, auf die er verlinkt. Es ist wichtig, sich daran zu erinnern, dass, sobald ein einzelner Beitrag zu einem Beitrag auf einer anderen Website verlinkt, die andere Website nicht mehr von dieser zurückverlinkt werden kann überall und nicht nur den Beitrag, mit dem er verlinkt ist.

Website A kann beliebig oft auf Website B verlinken, und jeder Beitrag kann auf mehr als einen anderen Beitrag verweisen. Ein Beispielszenario könnte sein:

• Website A verlinkt zu Website B
• Website C verlinkt zu Website B
• Website D verlinkt zu Website A

In den oben genannten Daten:

• Website A könnte auf Website C (oder wieder auf Website B) verlinken
• Standort B könnte auf Standort D verweisen
• Site C könnte einen Link zu Site A oder Site D (oder wieder Site B) herstellen
• Site D könnte einen Link zu Site B oder Site C (oder wieder Site A) herstellen

Hier ist ein Link zu einigen Testdaten und einem Dump der 2 benötigten Tabellen: http://pastie.org/1506715

Ich denke, ich brauche eine Querverbindung, um alle möglichen Link-Kombinationen zu erhalten, aber dann auch bestehende Beziehungen zu berücksichtigen, um zu verhindern, dass Websites in die entgegengesetzte Richtung zurückverlinkt werden. Die Abfrage, die ich bis jetzt habe, lautet:

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;

Dadurch erhalte ich alle möglichen Beziehungen zwischen Pfosten. Das Problem ist, wie ich Beziehungen ausschließen kann, die den oben genannten Regeln widersprechen würden. Die bisherigen Beziehungen werden in der Tabelle test_smartlinks_to_websites aufgezeichnet, wobei post_id zur "Ursprungs"-Website und website_id zur "Ziel"-Website gehört (wobei zu bedenken ist, dass die Beziehung effektiv einseitig zwischen Websites und nicht zwischen Beiträgen besteht).

Ich habe versucht, eine NOT EXISTS-Unterabfrage zu verwenden, aber ich bin mir über die genaue Klausel nicht sicher (oder ob das der richtige Ansatz ist).

Answer 1

Korrigieren Sie mich, wenn ich falsch liege. Ihre Aufgabe scheint darin zu bestehen, Zyklen in einem gerichteten Graphen zu bestimmen. Es ist nicht so komplex, wie es scheint. In diesem Blogbeitrag erfahren Sie, wie das in SQL gemacht wird: http://devio.wordpress.com/2009/09/13/finding-cycles-in-directed-graphs-using-tsql/ . Siehe auch diesen Link für die Breitensuche in SQL: http://willets.org/sqlgraphs.html .

BEARBEITET: Bilder zur Verdeutlichung und zum Verständnis von gerichteten azyklischen und zyklischen Graphen hinzugefügt.

Hier ist zum Beispiel etwas, das Ihrer Situation ähnelt. Es handelt sich nicht um einen einzelnen Graphen, sondern um eine Reihe von Graphen (oder einen Wald, wenn es sich um Bäume handelt). Beachten Sie, dass es keine gemeinsame Wurzel gibt. Es sind nur Knoten, die irgendwie miteinander verbunden sind. Es gibt einen Zyklus in dem größeren Teilgraphen, in dem zwei Knoten aufeinander verweisen. Entfernt man den Link nach oben, wird der Teilgraph azyklisch.