CSE Roadmap

Core tier · about 3 hours · 8 parts

Part 6 of 8 · 3 min read

The graph model

Vertices and edges for data where the links are the point.

Think of a map of who knows whom at a large company. The questions are about paths: who is a friend of a friend, and how many steps apart are two people. A list of names is not much use. The strings between the photos are what matter.

Graph

A graph is a set of vertices (the things) and edges (the links between them). In the property graph model, each vertex and each edge can carry a label and a set of properties.

Example: the vertices "Lucy" and "Alain" with an edge labelled "married to" between them, and a vertex "London" with edges "lives in" from both.

The book gives the parts of the property graph model. A vertex has an identifier, incoming and outgoing edges and properties. An edge has an identifier, a tail vertex, a head vertex, a label and properties. Any vertex can link to any other, with no schema that restricts what may link to what. Given a vertex, both its incoming and outgoing edges can be found efficiently, so a path can be followed.

The book notes a useful fact: a graph can be stored in two relational tables, one for vertices and one for edges. The difference is not in what can be stored, but in how easy it is to ask questions about paths.

Typical uses in the book: social networks (people linked by "knows"), the web (pages linked by hyperlinks), road networks (junctions and roads). It also notes that one graph can hold many different types of things, such as people, places, events and comments.

A worked example. Each person has 200 friends (made up). The question: how many people are within three steps?

  • Step 1: 200 friends.
  • Step 2: up to 200 × 200 = 40,000 friends of friends.
  • Step 3: up to 200 × 200 × 200 = 8,000,000.
  • These are upper limits, since friends overlap.

In a relational design, each step is a join of the friendship table with itself. Three steps are three joins, and the number of rows touched grows with each. A graph database follows the stored links from each vertex, so the work depends on the number of vertices visited and not on the size of the whole table.

Graph query languages exist, such as Cypher. The question "who lives in London and was born in the United States" is written as a pattern of vertices and edges, and the database finds matches. The book notes that the same query in SQL needs a more awkward recursive query.

Graph databases are rarely the first choice in system design interviews, but they appear when a problem is dominated by relationships: friend recommendations, fraud rings, route finding. Many large social products keep the main data in other stores and use a graph store for the relationship questions.

Common mistake

Using a graph database for data with simple links. If every question is "get a user's orders", a relational join is enough. A graph earns its place when the questions are about paths several steps long.

Check yourself:

  • What is a vertex, and what is an edge?
  • Why does a three-step friend question grow so quickly?