che rappresenta il grafico utilizzando il database relazionale

Question

Ho bisogno di rappresentare le informazioni del grafico con il database relazionale.

Diciamo che a è collegato a b, c e d.

 
a -- b 
|_ c 
|_ d 

posso avere un tavolo nodo per a, b, c, d, e posso anche avere una tabella di collegamento (Da, A) -> (a, b), (a, c), (anno Domini). Per altre implementazioni potrebbe esserci un modo per memorizzare le informazioni del collegamento come (a, b, c, d), ma il numero di elementi nella tabella è variabile.

• Q1: esiste un modo per rappresentare elementi variabili in una tabella?
• Q2: Esiste un modo generale per rappresentare la struttura del grafico utilizzando il database relazionale?

Answer 1

Q1: esiste un modo per rappresentare elementi variabili in una tabella [database]?

Immagino tu intenda qualcosa del genere?

from | to_1 | to_2 | to_3 | to_4 | to_5 | etc... 
1 | 2 | 3 | 4 | NULL | NULL | etc... 

Questa non è una buona idea. Viola lo first normal form.

Q2: Esiste un modo generale per rappresentare la struttura del grafico utilizzando il database?

Per un grafo orientato è possibile utilizzare una tabella edges con due colonne:

nodeid_from nodeid_to 
1   2 
1   3 
1   4 

Se non v'è alcuna informazione in più su ciascun nodo (come ad esempio un nome del nodo) questo può essere memorizzata in un'altra tabella nodes.

Se il grafo è non orientato sono disponibili due opzioni:

• memorizzare entrambe le direzioni (cioè negozi 1-> 2 e 2-> 1)
• utilizzare un vincolo che nodeid_from deve essere inferiore a nodeid_to (cioè negozio 1-> 2 ma 2-> 1 è implicito).

Il primo richiede due volte lo spazio di archiviazione ma può rendere l'interrogazione più facile e veloce.

Answer 2

Ho memorizzato più nodi "TO" in una rappresentazione relazionale di una struttura di un grafico. Sono stato in grado di farlo perché il mio grafico è stato diretto. Ciò significava che se volevo sapere a quali nodi "A" era connesso, avevo solo bisogno di selezionare un singolo record dalla mia tabella di connessioni. Ho archiviato i nodi TO in una stringa facile da analizzare e ha funzionato alla grande, con una classe in grado di gestire la conversione da stringa a raccolta e viceversa.

Answer 3

Oltre al percorso due tavoli citato da Mark un'occhiata al seguente link:

http://articles.sitepoint.com/article/hierarchical-data-database/2

questo articolo preordini in sostanza gli elementi nella struttura di assegnazione di valori di sinistra e destra.Sarai quindi in grado di selezionare porzioni o tutti gli alberi usando una singola istruzione select.

Node | lft | rght 
----------------- 
    A | 0 | 7 
    B | 1 | 2 
    C | 3 | 4 
    D | 5 | 6 

EDIT: Se avete intenzione di aggiornare l'albero fortemente questa non è una soluzione ottimale in tutto l'albero deve essere ri-numerata

Answer 4

raccomando guardando database del grafico dedicato, come suggerisce Nawroth. Un esempio potrebbe essere il database "Trinity", adatto a dataset di grandi dimensioni. Ma ce ne sono altri.

Ascoltare il podcast by Scott Hanselman on Hanselminutes about Trinity. Ecco lo text transcript.