Knowledge Graph Database

Entities, facts and relations for search and AI

Design a knowledge graph that stores billions of facts about entities with their time and source, answers multi-hop queries quickly, merges duplicate entities safely, and gives an LLM verified facts to answer from.

Overview

A knowledge graph stores facts about things (people, companies, places, products) as a network: each thing is a node, and each fact is an edge, such as Acme Cloud subsidiary-of Acme Holdings. Search engines use one to answer questions directly; Google introduced its Knowledge Graph in 2012 with more than 500 million objects and 3.5 billion facts, and by 2020 reported over 500 billion facts about five billion entities. AI applications now use graphs to give a language model facts it can quote instead of guessing.

The core unit is a triple: subject, predicate, object. Real facts need more than that. A CEO holds the job for a period; a population figure has a date and a source; a claim may be disputed. Wikidata handles this with qualifiers (start time, end time and others) and ranks (preferred, normal, deprecated) on each statement, and this design does the same.

Questions to ask first

How big? — About 1 billion entities and 50 billion statements
Who queries it? — Internal services: search features, an LLM answer service, analytics
What queries? — Entity lookups, 1 to 3 hop neighborhoods, a few transitive relations
How fresh? — New facts visible within minutes; bulk imports daily
Do facts change over time? — Yes: every statement carries valid-from and valid-to where known
Where do facts come from? — Licensed datasets, open data, extraction pipelines; every statement keeps its source

What you will be able to do

Model facts with time, rank and source, and choose between RDF and a property graph.
Store the graph so a neighbor lookup costs the node's degree, not the size of the graph.
Answer transitive questions without storing a closure that explodes.
Merge duplicate entities safely with blocking, scoring, clustering and review.
Explain how the graph grounds an LLM answer with facts it can cite.

Key concepts

Triples and statements
RDF vs property graph
Qualifiers: time, rank, source
Adjacency lists and indexes
Transitive closure
Entity resolution and blocking
Edge cuts and hub vertices
Grounding LLM answers

Functional requirements

Create entities with a stable id, a label, aliases and a type
Add and retract statements with valid-from, valid-to, rank and source
Look up an entity and its neighborhood, optionally as of a date
Answer 1 to 3 hop queries and transitive relations (part-of, subsidiary-of, subclass-of)
Resolve incoming records to existing entities or create new ones; send unsure cases to review
Return the facts about the entities in a question, with sources, for an LLM to answer from

Non-functional requirements

Entity lookup and 1-hop neighborhood under 50 ms at p99 (a target we chose)
3-hop queries with limits under 500 ms at p99 (a target we chose)
New statements visible within a few minutes
No fact without a source; retracted facts kept for audit, not deleted
A wrong merge can be undone

Interview questions

How do you represent a fact that is only true for a period?
How do you answer "all subsidiaries at any depth" quickly?
How do you store the graph so neighbor lookups are fast?
How does entity resolution work at a billion records?
How would you shard it?
How does the graph help an LLM avoid wrong facts?
How do you learn facts the graph does not state yet?