Bij de term 'database' wordt (voorlopig?) nog steeds eerst en vooral aan de relationele database gedacht.
In een relationele database wordt dat georganiseerd in tabellen. Elke tabel heeft een aantal vooraf gedefinieerde kolommen waarvoor telkens vooraf een vastbepaald data type vastgelegd wordt. Elk record in een tabel heeft een veld dat een unieke sleutel (primary key) voor dat record bevat. Relaties tussen tabellen worden bepaald door in een tabel verwijzingen naar de primary keys in andere tabellen op te nemen (de foreign keys). De relatie zelf wordt nergens bewaard, maar wordt bij het uitvoeren van queries opgebouwd door middel van joins tussen primary en foreign keys. Doordat de relaties bij het uitvoeren van de queries telkens opnieuw opgebouwd moeten worden zijn relationele database (in tegenstelling tot wat hun naam impliceert) niet bijzonder goed in 'relaties'.
Graph database hebben een aantal raakvlakken met relationele databases, maar werken met een aantal andere concepten
Doordat relaties samen met de nodes in een graph database bewaard worden en niet voor elke query opnieuw berekend dienen te worden, opent dit mogelijkheden voor een hele reeks use cases die met relationele databases niet mogelijk zijn:
De wiskundige theorie rond graphs is eeuwenoud, maar door de toegenomen rekenkracht van hardware en ontwikkelingen van voornamelijk marktleider Neo4J, zijn graph databases aan een razendsnelle opmars bezig.