The Graph Database Model

What a graph database stores

A graph database stores one big graph, which is essentially an instance of an E/R diagram. The graph is composed of nodes and directed edges.

Nodes

Nodes have a type, a unique label (or several, in Neo4j), and properties (key-value pairs). The type corresponds roughly to an entity set in the E/R model. Labels in Neo4j can serve as a lightweight classification mechanism — a node may carry multiple labels, which is useful for tagging without duplicating data.

Edges

Edges are directed between two nodes. Each edge has:

• A type (the name of the relationship).
• An optional label.
• Properties (key-value pairs).

An edge type models an E/R binary (or unary) relation. Since edges connect exactly two nodes, ternary relationships in the E/R model must be handled by other means (see a later note).

Edges, when created, need have no identifiers. This means that creating the same edge twice between the same two nodes is not idempotent in some systems — two distinct edges with the same type and properties can exist. This contrasts with the relational model, where a tuple in a relation is uniquely identified by its key, and inserting the same tuple twice is either rejected or treated as a duplicate.

Direction in storage vs. direction in queries

Edges are stored with a direction, but queries can treat them as undirected. Cypher’s (a)--(b) syntax matches edges in either direction, ignoring the stored orientation. This is important because many real-world relationships (friendship, co-authorship) are symmetric, but the DBMS still requires a direction at storage time.

Collating by type for relational conversion

Data from a graph database can be collated by type to produce RDBMS tables. For each node type, one table is formed with columns for each property. For each edge type, one table is formed with columns for the source node reference, target node reference, and each property. This is the inverse of the E/R-to-relational mapping covered earlier in the course.

Natural problem domains

The graph model is a natural representation for many real-world problems:

Domain	Nodes	Edges
Social networks	People	Friendships, follows
Metabolic pathways	Compounds, enzymes	Reactions
Road networks	Junctions, towns	Road segments
Dependency graphs	Software packages	Depends-on
The Web	Pages	Hyperlinks
Organisational charts	Employees	Reports-to

Regular expression matching and atomicity

Graph query languages often support regular expression matching on property values. This raises the question of whether it violates value atomicity — the principle that values should not have internal structure visible to queries. In the relational world, WHERE name LIKE 'Sm%' is accepted practice despite performing pattern matching on the internal characters of a string. Graph databases do the same: regular expression matching on values is analogous to LIKE predicates in SQL. The question of whether this breaks the relational model’s first normal form is largely academic; in practice, both models allow it.

Reusable queries

Queries in graph databases can be expressed as reusable functions with formal parameters. This is equally possible in RDBMSs (stored procedures, parameterised views, user-defined functions). The graph model does not have a monopoly on encapsulation.

Security

Graph databases have suffered serious security vulnerabilities (e.g., injection attacks, authentication bypasses) over the years. This is not inherent to the graph model; it reflects the immaturity of implementations. RDBMSs have had decades of hardening, but they too have suffered SQL injection and privilege-escalation vulnerabilities. The security posture of a DBMS depends on its engineering, not its data model.

Summary

• A graph database stores a typed, labelled, directed graph — essentially a running instance of an E/R diagram.
• Edges are directed in storage but can be queried as undirected.
• Edge creation is not necessarily idempotent (no inherent key constraint on edges).
• The graph model maps naturally to domains with networked structure.
• Regular expression matching in graph queries is analogous to LIKE clauses in SQL.
• Queries can be parameterised and reused in both graph and relational systems.