Come mantenere una struttura di dati del grafico in un database relazionale?

Question

Ho preso in considerazione la creazione di una tabella di vertici e di una tabella di bordi ma la creazione di grafici in memoria e la visualizzazione di grafici secondari richiedono un numero elevato di ricerche? Mi piacerebbe evitare letture eccessive del database. C'è un altro modo per mantenere un grafico?

Nota a margine: ho sentito parlare di Neo4j ma la mia domanda è davvero come rappresentare graficamente un grafico in un database standard. Sono aperto ad alcune soluzioni NoSQL come mongodb però.

Answer 1

La risposta è sfortunatamente: la tua considerazione è completamente corretta in ogni punto. È necessario memorizzare Nodi (Vertices) in una tabella e Bordi che fanno riferimento a un DaNodo e un ToNodo per convertire una struttura di dati del grafico in una struttura dati relazionale. E hai anche ragione, che questo finisce in un gran numero di ricerche, perché non sei in grado di suddividerlo in sottografi, che potrebbero essere interrogati contemporaneamente. Devi passare da un nodo all'altro, da un nodo all'altro, da un nodo all'altro ... e così via (in modo ricorsivo, mentre SQL sta lavorando con gli insiemi).

Il punto è ...

relazionale, grafo orientato, object oriented, Documento base sono diversi tipi di strutture di dati che soddisfano i requisiti differenti. Ecco di cosa si tratta e perché così tanti diversi database NoSQL (la maggior parte di essi sono semplici archivi di documenti), perché non ha senso organizzare grandi dati in modo relazionale.

1 Alternativa - Grafico del database orientati

Ma ci sono anche grafo orientato database NoSQL, che rendono il modello di dati grafico un primo cittadino di classe come OrientDB che sto giocando intorno con un po 'in questo momento. La cosa bella è che, sebbene persista come un grafico, può ancora essere utilizzato in modo relazionale o anche orientato agli oggetti o orientato al documento (cioè interrogando con un semplice vecchio SQL). Ciononostante, Traversing the graph è il modo ottimale per ricavarne i dati di sicuro.

Alternativa 2 - lavorare con i grafici in memoria

Quando si tratta di instradamento veloce, quadri di instradamento come Graphhopper costruire il grafo completo (miliardi di nodi) all'interno della memoria. Perché Graphhopper utilizza un'implementazione MemoryMapped del suo GraphStore, che funziona anche su dispositivi Android con solo alcuni MB di memoria necessari. Il grafico completo viene letto dal database in memoria all'avvio, quindi il routing viene eseguito lì, quindi non è necessario cercare il database.

Answer 2

Ho affrontato questo stesso problema e ha deciso di andare, infine, con la seguente struttura, che richiede 2 query di database, poi il resto del lavoro è in memoria:

nodi Conservare in un tavolo e di riferimento il grafico con ogni annotazione nodo:

Table Nodes 

id | title | graph_id 
--------------------- 
105 | node1 | 2 
106 | node2 | 2 

negozio anche bordi in un'altra tabella e nuovamente riferimento grafico questi bordi appartengono ad ogni fronte:

Table Edges 

id | from_node_id | to_node_id | graph_id 
----------------------------------------- 
1 | 105   | 106  | 2 
2 | 106   | 105  | 2 

Ottieni tutti i nodi con una query, quindi ottieni tutti i bordi con un altro.

Ora crea il tuo modo preferito per memorizzare il grafico (ad es. Elenco di adiacenza) e procedi con il flusso dell'applicazione.