Query SQL per gestire relazioni complesse

Question

Ho uno scenario in cui ho un numero elevato di blog. Questi blog hanno tutti più post. Ogni post del blog può collegarsi a un post su un altro blog, ma è necessario quindi il collegamento mai da quel blog al blog di collegamento.

per chiarire:

• link sito A al sito B (e può collegarsi ad altri siti)
• del sito B, allora non può link del sito (ma può collegarsi ad altri siti)

Ogni volta che viene creato un post, memorizzo l'ID del post e l'ID del sito Web a cui si collega. È importante ricordare che una volta che un singolo post si collega a qualsiasi post su un altro sito Web che altro sito Web non può collegare da ovunque a, non solo il post a cui è collegato.

Il sito A può collegarsi al sito B tutte le volte che vuole e ogni post può collegarsi a più di un altro post. Uno scenario di esempio potrebbe essere:

• sito un link al sito B
• link del sito C al sito B
• sito link D per sito

Nella dati di cui sopra:

• Il sito A potrebbe collegarsi al sito C (o ancora al sito B)
• Il sito B potrebbe collegarsi al sito D
• sito C potrebbe collegarsi al sito o del sito D (o sito B di nuovo)
• sito D potrebbe collegarsi a B Sito o sito C (o del sito di nuovo)

Questo è il link ad alcuni dati di test e un dump dei 2 tavoli necessari: http://pastie.org/1506715

penso che ho bisogno di un cross join per ottenere tutte le possibili combinazioni di collegamento, ma poi fattore di relazioni esistenti per prevenire siti da link per tornare nella direzione opposta. La query che ho finora è:

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; 

Questo mi dà tutte le possibili relazioni tra i post. Quello a cui sto combattendo è come escludere relazioni che potrebbero contraddire le regole precedenti. Le relazioni precedenti sono registrate nella tabella test_smartlinks_to_websites, con post_id che appartiene al sito web "di origine" e website_id che appartengono al sito di "destinazione" (ricordando che la relazione è effettivamente a senso unico tra siti Web e non post).

Ho provato a utilizzare una sottoquery NON ESISTE, ma non sono sicuro della clausola esatta (o se è l'approccio corretto).

Answer 1

Correggimi se sbaglio. Sembra che il tuo compito sia determinare i cicli nel grafico diretto. Non è così complesso come sembra. Si prega di consultare questo post sul blog per come è fatto in SQL: http://devio.wordpress.com/2009/09/13/finding-cycles-in-directed-graphs-using-tsql/. Vedi anche questo link per l'ampiezza della prima ricerca in SQL: http://willets.org/sqlgraphs.html.

MODIFICATO: immagini aggiunte per la chiarezza e la comprensione dei grafici diretti aciclici e ciclici.

Ad esempio, ecco qualcosa che assomiglia alla tua situazione. Non è un singolo grafico ma un insieme di grafici (o foresta se erano alberi). Nota che non esiste una radice comune. Sono solo i nodi connessi in qualche modo. C'è un ciclo nel sottografo più grande dove i nodi si fanno riferimento l'un l'altro. Se per rimuovere il collegamento verso l'alto, il sottografo diventa aciclico.