Ha senso per mappare una struttura di dati del grafico in un database relazionale?

Question

In particolare uno Multigraph.

Alcuni colleghi hanno suggerito questo e sono completamente sconcertato.

Eventuali approfondimenti su questo?

Answer 1

È piuttosto semplice memorizzare un grafico in un database: si dispone di una tabella per i nodi e una tabella per i bordi, che funge da tabella di relazioni molti-a-molti tra la tabella dei nodi e la stessa. In questo modo:

create table node (
    id integer primary key 
); 

create table edge (
    start_id integer references node, 
    end_id integer references node, 
    primary key (start_id, end_id) 
); 

Tuttavia, ci sono un paio di punti su come memorizzare un grafico in questo modo.

In primo luogo, i bordi di questo schema sono diretti naturalmente - l'inizio e la fine sono distinti. Se i tuoi bordi non sono orientati, dovrai fare attenzione a scrivere le query, o memorizzare due voci nella tabella per ciascun margine, una in entrambe le direzioni (e quindi fare attenzione a scrivere query!). Se memorizzi un singolo spigolo, ti suggerirei di normalizzare il modulo memorizzato - forse considera sempre il nodo con l'ID più basso per essere l'inizio (e aggiungi un vincolo di controllo alla tabella per farlo rispettare). Si potrebbe avere una rappresentazione realmente non ordinata non avendo i bordi riferiti ai nodi, ma piuttosto una tavola di join tra loro, ma non mi sembra una grande idea.

In secondo luogo, lo schema precedente non ha modo di rappresentare una multigrafo.Puoi estenderlo abbastanza facilmente per farlo; se i bordi tra una data coppia di nodi sono indistinguibili, la cosa più semplice sarebbe aggiungere un conteggio a ciascuna riga del bordo, dicendo quanti bordi ci sono tra i nodi indicati. Se sono distinguibili, sarà necessario aggiungere qualcosa alla tabella dei nodi per consentire loro di distinguerli: un ID bordo autogenerato potrebbe essere la cosa più semplice.

Tuttavia, anche dopo aver risolto l'archiviazione, si ha il problema di lavorare con il grafico. Se si desidera eseguire tutta l'elaborazione sugli oggetti in memoria e il database è destinato esclusivamente alla memorizzazione, non ci sono problemi. Ma se vuoi fare interrogazioni sul grafico nel database, dovrai capire come eseguirle in SQL, che non ha alcun supporto integrato per i grafici, e le cui operazioni di base non si adattano facilmente a lavorare con i grafici. Può essere fatto, specialmente se si dispone di un database con supporto SQL ricorsivo (PostgreSQL, Firebird, alcuni dei database proprietari), ma ci vuole un po 'di riflessione. Se si vuole fare questo, il mio suggerimento sarebbe quello di inviare ulteriori domande sulle query specifiche.

Answer 2

Bene, le informazioni devono essere memorizzate da qualche parte, un database relazionale non è una cattiva idea.

Sarebbe solo una relazione molti-a-molti, una tabella di un elenco di nodi e una tabella di un elenco di bordi/connessioni.

Answer 3

Considerate come Facebook potrebbe implementare il grafico sociale nel loro database. Potrebbero avere un tavolo per le persone e un altro tavolo per le amicizie. La tabella delle amicizie ha almeno due colonne, ognuna delle quali è una chiave estranea alla tabella delle persone.

Poiché l'amicizia è simmetrica (su Facebook), è possibile che l'ID per la prima chiave esterna sia sempre inferiore all'ID della seconda chiave esterna. Twitter ha un grafico diretto per il suo social network, quindi non userebbe una rappresentazione canonica del genere.

Answer 4

È un approccio accettabile. È necessario considerare in che modo tali informazioni verranno manipolate. È più probabile che sia necessario un linguaggio separato dal database per eseguire calcoli relativi ai tipi di grafici che questo tipo di dati implica. Skiena's Algorithm Design Manual ha una vasta struttura di dati del grafico a sezioni e la loro manipolazione.

Senza considerare quali tipi di query è possibile eseguire, iniziare con due tabelle vertices e edges. I vertici sono semplici, un identificatore e un nome. I bordi sono complessi data la multigrafo. I bordi dovrebbero essere identificati in modo univoco da una combinazione di due vertici (ad esempio chiavi esterne) e alcune informazioni aggiuntive. Le informazioni aggiuntive dipendono dal problema che stai risolvendo. Ad esempio, se le informazioni di volo, gli orari di partenza e di arrivo e la compagnia aerea. Inoltre dovrai decidere se il bordo è diretto (vale a dire in un modo) o meno e tenere traccia di tali informazioni.

A seconda del calcolo si può finire con un problema che è meglio risolto con una sorta di algoritmo di intelligenza artificiale/apprendimento automatico. Per esempio, voli ottimali. Il libro Programming Collective Intelligence ha alcuni algoritmi utili per questo scopo. Ma dove vengono conservati i dati non cambia l'algoritmo stesso.