A structured, research-grade catalog of 1,053 open and hard problems across the database management systems (DBMS) space — from relational theory and query optimization to vector search, learned components, and self-driving databases. Each problem is a standalone Markdown page with a formal statement, the mathematical foundations it rests on, the current state of the art, the best-known upper and lower bounds (and the gap between them), active research directions as of mid-2026, and linked references.
It is meant as a map of where the hard questions are — for graduate students choosing a thesis, researchers scanning adjacent subfields, engineers who want the theory behind a system limitation, and anyone who wants to know what is actually still open in databases.
⚠️ Read the provenance & honesty note before citing anything. This is a synthesized study aid, not a primary source.
| Problems | 1,053 across 35 topics (~30 each) |
| Every problem documents | statement · math foundations · SOTA · upper bound · lower bound · the gap · current research (June 2026) · future work · references · worked example |
| Linked references | 6,700+ links to arXiv / DOI / ACM DL / DBLP, each verified or flagged *(unverified)* |
| Worked examples | 1,053 — every page has a small concrete instance |
| Content | ~1.16M words |
Status mix across the 1,053 problems:
| Status | Count | Meaning |
|---|---|---|
🔴 open |
450 | No known solution; decidability/complexity genuinely unresolved |
🟡 partially-solved |
369 | Solved for restricted cases or with caveats; general case open |
🟠 empirically-open |
227 | Works in practice, but lacks proven guarantees / matching bounds |
🟢 solved-but-impractical |
7 | Theoretically settled, but no deployable algorithm |
- 🗺️
TAXONOMY.md— the 35-topic map with scope descriptions. - 📇
INDEX.md— flat, clickable list of all 1,053 problems grouped by topic. - 📐
TEMPLATE.md— the 10-section schema every problem page follows. - 🎓 DB Internals Explained — an interactive companion that teaches how the machinery actually works (indexes, joins, cardinality estimation, the optimizer, execution plans, transactions, recovery, storage, and operations) across 8 engines. A friendly on-ramp before diving into the open problems here.
Browsing tips
- New to an area? Open the topic's
README.md(e.g.topics/02-query-optimization/) for a one-paragraph overview and a status-tagged index of its problems. - Looking for a thesis topic? Filter for 🔴
openproblems and read the The Gap section — it states exactly what would close the problem. - Want the math fast? Each page's §2 Mathematical Foundations and §10 Worked Example are self-contained.
The catalog is also a graph: problems cite shared papers, rest on shared concepts, and are worked on by the same researchers. We publish it as a portable snapshot you can load into Samyama-Graph (open-source, Apache-2.0) and query with OpenCypher in ~2 minutes:
# with samyama running on :8080
curl -L -o dbms-research.sgsnap \
https://github.com/samyama-ai/samyama-graph/releases/download/kg-snapshots-v7/dbms-research.sgsnap
curl -F file=@dbms-research.sgsnap http://localhost:8080/api/snapshot/importMATCH (per:Person)-[:ACTIVE_ON]->(p:Problem)
WHERE per.name = "Dan Suciu" RETURN p.title→ USING_WITH_SAMYAMA_GRAPH.md for the full walkthrough,
the schema (18,751 nodes / 38,539 edges; researchers resolved to DBLP profiles), and a
dozen ready-to-run queries.
Every .md follows the same 10-section schema (see TEMPLATE.md):
- Problem Statement — precise, self-contained; distinguishes decision / optimization / counting variants.
- Mathematical Foundations — the formal model, notation, and key theorems (LaTeX math).
- State of the Art — best-known algorithms/systems, separating theory-SOTA from systems-SOTA.
- Upper Bound — best algorithmic bound, naming the model (RAM, cell-probe, …).
- Lower Bound — hardness / impossibility, naming the model (NP, fine-grained/SETH, info-theoretic, communication complexity, CAP/FLP, …).
- The Gap — what separates the bounds; is it closed or genuinely open; what would close it.
- Current Research (June 2026) — active directions and the groups pursuing them.
- Future Work — open directions researchers articulate.
- Key References — canonical + recent literature, linked.
- Worked Example — a small concrete instance illustrating the problem and its bound.
dbms_research/
├── README.md ← you are here
├── TAXONOMY.md ← 35-topic map
├── INDEX.md ← flat list of all 1,053 problems (generated by gen_index.sh)
├── TEMPLATE.md ← per-problem schema
├── CLAUDE.md ← maintenance conventions
├── gen_index.sh ← regenerates INDEX.md from topics/
└── topics/
└── NN-topic-slug/
├── README.md ← topic overview + problem index
└── problem-slug.md ← one file per problem
Math renders on GitHub via MathJax. (Note: # inside math must be written \\# — GitHub strips one backslash before MathJax; see github/markup#1662.)
This catalog was synthesized primarily from established domain knowledge (canonical PODS / SIGMOD / VLDB / ICDE / CIDR results and textbook theory), then passed through automated citation-verification that fetched and confirmed reference links.
- Foundational results (Codd, Selinger, Stonebraker, Gray, Abiteboul–Hull–Vianu, Atserias–Grohe–Marx, Ngo–Ré–Rudra, Dwork, Malkov–Yashunin, …) are reliable.
- References are real and link-checked, or explicitly flagged
*(unverified)*(a handful) /[DBLP search]where no clean DOI exists. Where verification caught a citation error (wrong year/author/venue), a> **Verification note:**line records the correction. - 2025–2026 frontier claims are made to the best of current knowledge but may lag the true frontier (knowledge horizon ≈ January 2026); they are flagged inline with (frontier — verify).
- Complexity bounds reflect results believed correct and name the model they hold in; folklore/contested bounds are marked.
Do not cite this repository as a primary source. Use it to orient yourself, then read — and cite — the linked references. Corrections are very welcome (see below).
Issues and PRs are welcome — especially:
- Corrections to bounds, attributions, or citation metadata (please link a source).
- Frontier updates removing a
*(frontier — verify)*flag with a confirmed reference. - New problems — copy
TEMPLATE.md, fill all 10 sections, add it under the righttopics/NN-*/, update that topic'sREADME.md, and regenerateINDEX.mdwith./gen_index.sh. SeeCLAUDE.mdfor conventions (real references only, name the model for every bound, flag the frontier).
Content released under CC BY 4.0 — share and adapt with attribution.