Base di dati a grafo

In informatica una base di dati a grafo, o database a grafo, è una tipologia di database che utilizza nodi e archi per rappresentare e archiviare l'informazione. La rappresentazione dei dati mediante grafi offre un'alternativa al modello relazionale che fa uso di tabelle, ai database orientati al documento (che usano documenti), o altri, come i sistemi ad archivi strutturati (structured storage) basati su colonne o su cesti non interpretati di dati.

I database a grafo sono spesso più veloci di quelli relazionali nell'associazione di insiemi di dati, e mappano in maniera più diretta le strutture di applicazioni orientate agli oggetti. Scalano più facilmente a grandi quantità di dati e non richiedono le tipiche e onerose operazioni di unione (join). Dipendono meno da un rigido schema entità-relazione e sono molto più adeguati per gestire dati mutevoli con schemi evolutivi. Al contrario, i database relazionali sono tipicamente più veloci nell'eseguire le stesse operazioni su un grande numero di dati.

Modelli di riferimento

Quando si parla di modelli dei dati basati su grafo è inevitabile fare riferimento alla teoria dei grafi. In origine, i modelli di riferimento per l'implementazione dei database a grafo erano due: il property graph model e il resource description framework graph (RDF). Il primo fa riferimento principalmente al progetto Tinkerpop, mentre il secondo è il modello di riferimento del Web semantico. I database a grafo che utilizzano il modello RDF sono anche noti come Triple Store, Quad Store, o RDF Store.

I due modelli non sono del tutto coincidenti, anche se solitamente il passaggio da uno all'altro è molto intuitivo. Per entrambi esistono dei linguaggi di interrogazione specifici, ma solo per RDF esiste uno standard riconosciuto in SPARQL. Successivamente ne sono stati sviluppati altri, di seguito i modelli ad oggi esistenti,

• Modello dei dati di grafo basico: grafo diretto con nodi e archi etichettati da qualche vocabolario (Es. Gram)^[1]
• Modello dei dati a ipernodo: Si basa sulla generalizzazione di grafo: con ipernordi e iperarchi, permette la creazione di oggetti complessi, dipendenze funzionali e eredità strutturale multipla^[1]
• Modello dei dati a ipernodo con grafi annidati: modello in cui ad un ipernodo può essere esso stesso un grafo^[1]
• Modello dei dati RDF: modello raccomandato dal W3C per rappresentare metadati^[1]
• Modello dei dati del grafo di Proprietà: modello di multigrafo diretto, etichettato, con attributi (proprietà) e con archi multipli tra i nodi (Neo4j, Sparksee/DEX, InfiniteGraph)^[1]

Interrogazioni delle basi di dato a grafo

Di seguito le tipologie di interrogazioni usate nelle basi di dato a grafo^[1]:

• Pattern matching query (interrogazione per il riscontro di una configurazione)

Esempio: restituire le persone in cui l'attributo nome corrisponde a “James”.

## SPARQL 1.0 and SPARQL 1.1
SELECT ?X
FROM <http://www.socialnetwork.org>
WHERE { ?X sn:firstName "James" }
## G-SPARQL
SELECT ?X
WHERE { ?X @firstName "James" }
## CYPHER
MATCH (person:Person)
WHERE person.firstName="James"

• Adjacency query (interrogazione di adiacenza)
• Reachbility query (Interrogazione di raggiungibilità)

Esempio: trovare il nome delle persone che possono essere raggiunte da “James” dalla relazione “knows” (sa, sapere).

## SPARQL 1.1
PREFIX sn: <http://www.socialnetwork.org/>
SELECT ?N
WHERE { ?X sn:type sn:Person . ?X sn:firstName "James" .
?X sn:knows* ?Y .
?Y sn:firstName ?N }
DRAFT
## G-SPARQL
SELECT ?N
WHERE { ?X @type "Person" . ?X @firstName "James" .
?X knows* ?Y .
?Y @firstName ?N }
## CYPHER
MATCH (james:Person)-[:knows*]-(reachablePerson:Person)
WHERE james.firstName="James"
RETURN DISTINCT reachablePerson

• Graph Analytical query (interrogazione analitica del grafo)

Che si declinano nei linguaggi: SPARQL, G-SPARQL e Cypher^[1].

Sistemi di gestione delle basi di dato a grafo

I sistemi di gestione delle basi di dato a grafo (Graph Database Management System) si classificano in due categorie: Basi di dato a grafo, e framework elaboratori di grafi (graph processing framework)^[1]. I primi hanno l'obiettivo di gestire in maniera persistente il dato permettendo di archiviare transazionalmente e di accedervi in maniera persistente i secondi invece forniscono processi di batch e analisis su grandi grafi spesso in un ambiente distribuito con molte macchine^[1].

Base di dato a grafo

Di seguito basi di dato a grafo native:

• AllegroGraph [3],
• Bitsy [9],
• Cayley
• GraphBase
• Graphd
• HyperGraphDB
• IBM System G
• imGraph
• InfiniteGraph
• InfoGrid
• Neo4j
• OrientDB Archiviato il 2 febbraio 2017 in Internet Archive.
• Sparksee/DEX
• Trinity
• TurboGraph
• Amazon Neptune
• Ultipa Graph

Di seguito basi di dato a grafo non native:

• Titan che supporta: Apache Cassandra, Apache HBase e Oracle BerkeleyDB
• FlockDB è una base di dati distribuita orientata al grafo che usa MySQL come motore;
• ArangoDB
• OQGRAPH che è un motore computazionale di grafo per MySQL, MariaDB e Drizzle
• VelocityGraph: Base di dati ad oggetti che supporta i grafi
• Horton

Framework elaboratori di grafi

sistemi analitici a grafi non in rete:

• Pregel
• Apache Giraph
• GraphLab
• Apache Hama
• Catch de Wind
• GPS
• Mizan
• PowerGraph
• GraphX
• TurboGraph
• GraphChi

Sistemi di elaborazione di dati generici anche per grafi:

• Hadoop
• YARN
• Stratosphere
• Pegasus

Progetti di database a grafo

Di seguito un elenco di vari progetti su basi di dati a grafo molto conosciuti:

• AllegroGraph
• ArangoDB
• DEX - un database a grafo ad alte prestazioni
• HyperGraphDB - un database a grafo open source (LPGL) che supporta ipergrafi generalizzati dove gli archi possono puntare ad altri archi
• HyperGraphDB
• IBM System G Native Store
• InfoGrid - una base di dati a grafo open source (AGPLv3) con interfaccia web
• JanusGraph Archiviato l'11 gennaio 2022 in Internet Archive. - un database grafico scalabile e open source (Apache 2)
• Neo4j - un database a grafo commerciale e open source (AGPLv3)^[2]
• OhmDB
• Ontotext GraphDB
• OpenLink Virtuoso
• Oracle Spatial and Graph
• OrientDB Archiviato il 2 febbraio 2017 in Internet Archive. - database orientato al documento, ma con una gestione ottimizzata delle relazioni fra documenti come avviene in un database a grafo. Il linguaggio di query SQL like contiene estensioni per la gestione di alberi e grafi. Open source con licenza commercial friendly (Apache License)
• Teradata Aster
• VertexDB