DataBase Management System

Contents

• Introduction and overview
• 0. Review: sets, relations, complexity
• 1. The relational model and algebra
• 2. SQL: queries, aggregates, windowing
• 3. Design: dependencies and normal forms
• 4. Storage: pages, files, external sorting
• 5. Indexes: B+ trees and hashing
• 6. Transactions and concurrency
• 7. The log and crash recovery
• 8. Query optimization
• 9. Beyond relational: NoSQL, graphs, vectors
• 10. Web data and heterogeneous integration
• 11. Course research notes — CEDAR (Mohanty)
• Exercises
• Projects and assessment
• References

Introduction and overview

Audience: an engineer who already connects an LLM or a graph to data and wants that connection to be reliable — correct queries, fast access, no lost updates. Empirical first: each topic starts from a failure you can observe — a query that works in the lab and times out in production for lack of an index, a RAG system that hallucinates because a join was wrong — and only then names the theory behind it: relational model, ACID transactions, optimizer, vector stores.

This module is the “data” side of the program: how to store, query and secure data before learning from it.

What you will be able to do

• Express a query in both relational algebra and SQL, including aggregates and window functions.
• Design a clean schema: functional dependencies, normal forms, and know when to denormalize wisely.
• Explain how a query actually executes: pages, files, external sorting, B+ trees, hashing.
• Reason about a transaction: ACID, isolation levels, concurrency, deadlocks.
• Describe the crash recovery guarantee provided by the log (WAL) — what makes a database trustworthy.
• Read an execution plan and optimize a slow query (indexes, rewriting, cost).
• Choose between relational, NoSQL, graph database, and vector database depending on the workload and the data model.
• Integrate heterogeneous web data and assess its trustworthiness, up to data fact-checking.

Official objectives and syllabus (2026-2027 catalog)

In the official catalog, the course unit Système de Gestion de Base de Données (X3A VE3) sets itself the objective of a “broad and in-depth presentation of the fundamental concepts in very large-scale data management”, drawing on PostgreSQL to introduce declarative queries, query optimization, data modeling, concurrency control and crash recovery, with labs where students load and query a real database, including through a web application.

This is exactly the arc followed by these materials, from the relational model to optimization — and our closing chapters (NoSQL, web data) extend this foundation toward the vector and graph stores that RAG and GraphRAG systems query. The sheet lists no prerequisites (not disclosed); the assessment combines a final written exam and three graded tests in small classes.

Every official theme of the syllabus is covered; crash recovery, mentioned in the official description, is the subject of chapter 7. Our additions, beyond the official syllabus: the review chapter 0 (sets, relations, complexity), chapter 9 (NoSQL, graph and vector databases), chapter 10 (web data and heterogeneous integration) and chapter 11 (the work of the CEDAR team). Note: this course unit does not appear in the LLGA-1-S1 track list of the 2026-2027 catalog, although its sheet remains published there and scheduled in period 1.

Where this course fits in the program

Notes kept for reference: this course unit is not in the LLGA 2026–2027 lists (it is still scheduled in Period 1 for other tracks of the École, 36 h), so no LLGA module requires it. Official prerequisites: not stated on the sheet; these materials lay down the Refresher in Computer Science module as their foundation, whose sets, relations and complexity analysis they constantly mobilize — external sorting and indexes are reasoned about in algorithmic cost.

For an LLGA student, the course is an optional complement to three modules; none of them assumes it.

• Graph Machine and Deep Learning for Generative AI: the property graphs and RDF of ch. 9 are the storage side of the knowledge graphs that its GraphRAG chapter queries.
• Large Language Models (M2): ch. 9 details the ANN indexes (IVF, HNSW, PQ) behind the dense retrievers of its RAG chapter; retrieval-augmented generation itself is taught there, not here.
• ML Ops and LLM Engineering Principles (M2): transactions, the log and reliability (ch. 6–7) for its data pipelines.

The research of the CEDAR team (Inria) on knowledge graphs and fact-checking also announces concrete internship topics.

Course outline

• Review: sets, relations, complexity: the mathematical and algorithmic foundation taken up from the Refresher in Computer Science.
• The relational model and algebra: the theory behind SQL — operators, semantics, equivalences.
• SQL: queries, aggregates, windowing: the most directly reusable skill of the master’s program.
• Design: dependencies and normal forms: designing schemas without redundancy or anomalies.
• Storage: pages, files, external sorting: what happens under the query, when data overflows memory.
• Indexes: B+ trees and hashing: fetching information without reading everything — the real performance gain.
• Transactions and concurrency: ACID, isolation, locks — many users, one consistent database.
• The log and crash recovery: why a well-designed database loses nothing, even on a crash.
• Query optimization: execution plans, rewrites, costs — diagnosing and speeding up.
• Beyond relational: NoSQL, graphs, vectors: the modern database families, and when each one wins — the storage side of the RAG and GraphRAG systems met in other modules.
• Web data and heterogeneous integration: confronting multiple, inconsistent, sometimes false sources.
• Course research notes — CEDAR (Mohanty): the research of the CEDAR team (Inria) — knowledge graphs and data fact-checking.

Session plan

36 h in class = 12 sessions of 3 h. The volume is the one of the SynapseS 2026–2027 sheet (36 h in person); the sheet publishes no session-by-session programme, so the split below is our proposal for covering these notes in that time. Level 1 = foundations (reviews, definitions, first worked examples), 2 = core: the internals of a relational DBMS, 3 = advanced material beyond the relational core (distributed and vector databases, heterogeneous data); the level never goes down from one session to the next.

Self-study, outside the 36 h (about 1.5 h in total): ch. 11 Course research notes — CEDAR (Mohanty): RDF summaries, ConnectionLens, computational fact-checking, read as preparation for Ex. 9 and the project topics (≈ 1.5 h).

How to study this module

• Practice SQL from the first week on a real database (SQLite or PostgreSQL): the SQL chapter is a gesture, kept up by typing queries.
• For each internal mechanism (index, log, external sorting), ask yourself “what happens if the data is a hundred times the memory?” — that is the question that structures the course.
• Go back if needed to the complexity chapter of the Refresher in Computer Science module: B+ trees and optimization are reasoned about in big-O.
• Build a small schema yourself, populate it, then deliberately degrade it (concurrency, wild deletions) to observe transactions and the log at work.
• Pay particular attention to the “Beyond relational” chapter: it is the one that directly connects to Graph ML and to the M2 LLMs.
• Do the optimization exercises on real execution plans (EXPLAIN): knowing how to read a plan is highly valued in internships and jobs alike.

0. Review: sets, relations, complexity

A database is, mathematically, a collection of finite relations, and its engine is judged by the cost of its algorithms on data larger than memory. This chapter recalls the set theory, logic and complexity that the rest of the module uses, and proves the first size bounds that an optimizer relies on.

1. The relational model and algebra

Concrete scene: a business dashboard shows wrong totals because a join duplicated rows. To understand why, one needs a precise model of what a table is and of what each operation does to it; this chapter gives that model — relations and relational algebra — on which SQL, design and optimization are all built.

The relational model, proposed by E. F. Codd in 1970, rests on a radically simple idea: representing data as (mathematical) relations, that is, sets of tuples, and querying them with operations that are closed on these sets. The physical structure is invisible: this separation between the declarative and the physical is what made the model successful, and it is what will make the automatic optimization of chapter 8 possible.

2. SQL: queries, aggregates, windowing

SQL is a declarative language: one describes the result, not the algorithm. Its logical semantics is understood in three stages, which one must know in order to predict what a query returns — and which every optimizer rewrites in its own way (ch. 8):

1. FROM produces the Cartesian product/joins;
2. WHERE selects row by row;
3. then GROUP BY + SELECT group, aggregate, and project.

-- table parent(parent, child): one row per parent-child edge
WITH RECURSIVE ancestor(a, d) AS (          -- a ancestor of d
  SELECT parent, child FROM parent
  UNION                                    -- UNION (without ALL) = deduplicated
  SELECT p.parent, a.d
  FROM ancestor a JOIN parent p ON p.child = a.a
)
SELECT d, COUNT(DISTINCT a) AS num_ancestors FROM ancestor GROUP BY d;
-- semantics: fixed point; at each iteration, only the tuples
-- produced at the previous iteration are expanded (semi-naive evaluation).

import sqlite3
from sqlalchemy import create_engine, MetaData, Table, Column, Integer, String, ForeignKey, select

# --- 1. SQLite: everything lives in one file, ACID transactions included
con = sqlite3.connect("school.db")
con.execute("PRAGMA foreign_keys = ON")        # optional but recommended
con.executescript("""
CREATE TABLE IF NOT EXISTS student(
  id INTEGER PRIMARY KEY, name TEXT NOT NULL, major TEXT);
CREATE TABLE IF NOT EXISTS course(
  code TEXT PRIMARY KEY, title TEXT, credits INTEGER CHECK (credits > 0));
CREATE TABLE IF NOT EXISTS enrolled(
  id INTEGER REFERENCES student(id),
  code TEXT REFERENCES course(code),
  year INTEGER, PRIMARY KEY (id, code));
""")
con.executemany("INSERT OR IGNORE INTO student VALUES (?,?,?)",
                [(1043, "Anna", "DS"), (1088, "Bruno", "AI"), (2101, "Chloé", "DS")])
con.executemany("INSERT OR IGNORE INTO course VALUES (?,?,?)",
                [("DB", "Databases", 4), ("DL", "Deep Learning", 5), ("OT", "Optimal Transport", 3)])
con.executemany("INSERT OR IGNORE INTO enrolled VALUES (?,?,?)",
                [(1043, "DB", 2025), (1043, "DL", 2026), (1088, "DB", 2025),
                 (1088, "OT", 2025), (2101, "DL", 2025)])
con.commit()                                   # close the implicit transaction

# each student's courses, ranked by year with a window function
q = """
SELECT e.name, c.title, i.year,
       RANK() OVER (PARTITION BY e.id ORDER BY i.year) AS year_rank,
       COUNT(*) OVER (PARTITION BY e.id)                AS num_courses
FROM enrolled i
JOIN student e ON e.id = i.id
JOIN course   c ON c.code = i.code
WHERE c.credits >= 3
"""
for row in con.execute(q):
    print(row)

# explicit transaction: all or nothing
try:
    con.execute("BEGIN")
    con.execute("UPDATE student SET major='AI' WHERE id=2101")
    con.execute("INSERT INTO enrolled VALUES (2101, 'DB', 2026)")
    con.commit()
except sqlite3.IntegrityError as err:        # e.g. foreign key violated
    con.rollback()
    print("cancelled:", err)

# execution plan (useful for ch. 8):
for row in con.execute("EXPLAIN QUERY PLAN " + q):
    print(row)

# --- 2. SQLAlchemy Core: composable queries, DBMS-independent
engine = create_engine("sqlite:///school.db", echo=False)
md = MetaData()
student = Table("student", md, Column("id", Integer, primary_key=True),
                 Column("name", String), Column("major", String))
enrolled = Table("enrolled", md, Column("id", Integer, ForeignKey("student.id"),
                 primary_key=True), Column("code", String, primary_key=True),
                 Column("year", Integer))
with engine.connect() as cn:
    stmt = (select(student.c.name, enrolled.c.code)
            .join(enrolled, student.c.id == enrolled.c.id)
            .where(enrolled.c.year == 2025).order_by(student.c.name))
    print(cn.execute(stmt).fetchall())

3. Design: dependencies and normal forms

A poorly designed database leads to the three classic anomalies: insertion (impossible to record one fact without another), deletion (losing one fact while deleting another), update (repeating the same fact in several places). Normalization theory, also due to Codd and developed by Bernstein, Rissanen and others, diagnoses and corrects these defects through functional dependencies.

4. Storage: pages, files, external sorting

A DBMS lives on a hierarchy of memories with performance gaps of several orders of magnitude. The whole discipline of storage follows from this brute fact:

5. Indexes: B+ trees and hashing

An index is a secondary structure that speeds up locating records without scanning them all. Two families dominate: B+ trees for range queries and sorting, hashing for exact equality. The DBMS maintains the index at every write: each additional index slows down insertions — there is no free index.

                    [20]
             ┌────────┴────────┐
           [15]              [30, 40]
         ┌──┴──┐        ┌──────┼──────┐
      [5,10]  [15]   [20,25] [30,35] [40,45]
      ──────── leaves chained ────────▶

6. Transactions and concurrency

Several programs access the same data at the same time. The transaction is the unit of consistency: a sequence of read (r) and write (w) operations that must execute as if it were alone. The ACID acronym summarizes the contract:

• Atomicity (all or nothing);
• Consistency (constraints hold);
• Isolation (equivalence to a serial execution);
• Durability (a commit survives a crash — the subject of ch. 7).

7. The log and crash recovery

Durability requires writing to persistent storage before answering “commit”, and atomicity requires being able to undo — even after a crash right in the middle. Both requirements are solved by one and the same structure: the log (write-ahead log, WAL), an ordered sequence of records describing every modification, written sequentially (hence fast, see ch. 4).

8. Query optimization

SQL is declarative: the execution plan — the order of operations, the join algorithms, the indexes used — is chosen by the optimizer. The principle:

1. rewrite the query as an algebraic tree;
2. generate the equivalent plans via the laws of Proposition 1.4;
3. estimate their cost with a model;
4. keep the cheapest. It is a closed loop between theory (equivalences) and physics (the cost model of ch. 4).

9. Beyond relational: NoSQL, graphs, vectors

The relational model dominates transactional workloads, but three developments of the 2000-2020 period seeded new models: horizontal scale (NoSQL), data as graphs (knowledge graphs), and search by similarity over vectors — the fuel of learning systems and of RAG (see the Large Language Models module, chapter 7).

MATCH (a:Person {name: "Anna"})-[:ENROLLED_IN*1..3]->(c:Course)
WHERE c.credits >= 3
RETURN DISTINCT c.code;

SELECT DISTINCT ?code WHERE {
  :Anna :enrolledIn+ ?c .            # path of length ≥ 1 (SPARQL 1.1)
  ?c :credits ?cr . FILTER(?cr >= 3)
  ?c :code ?code . }

import numpy as np
from sklearn.cluster import MiniBatchKMeans

rng  = np.random.default_rng(0)
X    = rng.normal(size=(100_000, 64)).astype("float32")   # vector "database"
q    = rng.normal(size=(64,)).astype("float32")

def normalize(A): return A / np.linalg.norm(A, axis=1, keepdims=True)
Xn, qn = normalize(X), q / np.linalg.norm(q)

# --- 1. exact search (brute force): O(n d)
d_all = Xn @ qn
top10_exact = set(np.argsort(d_all)[-10:])

# --- 2. IVF: nlist cells by k-means, we probe nprobe cells
nlist, nprobe = 256, 8
km = MiniBatchKMeans(n_clusters=nlist, n_init=3, random_state=0).fit(Xn)
cell_of_X = km.labels_
d_centro  = np.linalg.norm(km.cluster_centers_ - qn, axis=1)
probes    = np.argsort(d_centro)[:nprobe]
cand      = np.where(np.isin(cell_of_X, probes))[0]
top10_ivf = set(cand[np.argsort(Xn[cand] @ qn)[-10:]])

print(len(top10_exact & top10_ivf) / 10, "recall@10")
# ~0.3 here: isotropic random vectors have no cluster structure, the worst
# case for IVF; raise nprobe to watch the recall/cost trade-off
print(f"exact: {len(Xn)} distances; IVF: {len(cand) + nlist} distances")

10. Web data and heterogeneous integration

The web is the largest database in the world — without schema, without keys, without constraints. The data feeding learning (and data journalism) arrives as HTML pages, semi-structured files (JSON, XML), tables, documents. This chapter addresses the specific problems: extract, match, merge.

11. Course research notes — CEDAR (Mohanty)

The module is led by Madhulika Mohanty, Inria researcher (chargée de recherche) in the CEDAR team (Inria Saclay — École Polytechnique), founded and led by Ioana Manolescu, Inria senior researcher (directrice de recherche), a specialist in complex and heterogeneous data management.

The team’s work draws the arc of this module: from the foundations of data systems to the web of data, then to the use of data to verify information — Madhulika Mohanty contributes in particular on the querying and exploration of graph data. Verified selection:

• Foundations and teaching of the field. S. Abiteboul, I. Manolescu, P. Rigaux, M.-C. Rousset, P. Senellart, Web Data Management, Cambridge University Press, 2011 — the reference treatise on web data management, freely available online. With Z. Kaoudi and S. Zampetakis, I. Manolescu also wrote Cloud-Based RDF Data Management (Morgan & Claypool, 2020) — the RDF of ch. 9 seen from the cloud and distribution side.
• RDF graph summaries. Real knowledge graphs are too large to be “seen” at a glance: F. Goasdoué, P. Guzewicz, I. Manolescu, “RDF Graph Summarization for First-Sight Structure Discovery”, VLDB Journal 29(5), 2020 — building quotient summaries that approximate the graph in small fractions of its size, with a guarantee of exactness for “typical” query answers.
• Heterogeneous integration: ConnectionLens. The ConnectionLens platform (C. Chanial, R. Dziri, H. Galhardas, J. Leblay, M.-H. Le Nguyen, I. Manolescu, demo PVLDB 11(12), 2018) integrates relational databases, JSON, CSV, XML trees, and texts into a single graph; the long version (A. C. Anadiotis, O. Balalau, C. Conceição, H. Galhardas et al., Graph integration of structured, semistructured and unstructured data for data journalism, Information Systems 104, 2022) formalizes the model: the direct follow-up of ch. 10. A spectacular application: the automated detection of scientific conflicts of interest (CIKM 2021) by crossing author statements, patents, clinical trials, and funding.
• Fact-checking and data journalism. Starting with “Computational fact-checking: a content management perspective” (S. Cazalens, J. Leblay, I. Manolescu, P. Lamarre, X. Tannier, PVLDB 11(12), 2018), the team treats claim verification as a data management problem: finding the sources, aligning them, evaluating the claims. The line continued with the verification of numbers (Balalau et al., Truth and Trust Online 2022, and the StatCheck demonstrator, CIKM 2022) then with the generation of factual counter-arguments; the ANR/DGA SourceSay project (with the Décodeurs of Le Monde) equips journalists to find the first source of a digital rumor.
• AI × data. CEDAR’s current program connects LLMs and graphs (FactSpotter, Findings of EMNLP 2023, checks that a text generated from a graph stays faithful to it), heterogeneous data querying, and trust — the meeting of ch. 10 with the NLP and LLMs modules of the master’s program. See the CEDAR page and the dblp list.

Exercises

1. ★ Algebra and SQL (solved). On the database of Example 1.2, express in algebra then in SQL: (a) the majors of the students enrolled in the DB course; (b) the students enrolled in all courses of at least 4 credits; (c) the courses with no enrollee.

   Solution.

   (a) The algebra expression is \pi_{\texttt{major}}(\texttt{Student} \Join \sigma_{\texttt{code}=DB}(\texttt{Enrolled})) — SQL: join + WHERE.

   (b) Division: \pi_{\texttt{id},\,\texttt{code}}(\texttt{Enrolled}) \div \pi_{\texttt{code}}(\sigma_{\texttt{credits}\geq4}(\texttt{Course})) (the dividend must contain the divisor’s attribute code, Def. 1.6), then join with Student: only 1043 (Anna) takes both DB and DL. In SQL, NOT EXISTS (SELECT … FROM Course c WHERE credits >= 4 AND NOT EXISTS (SELECT … FROM Enrolled i WHERE i.id = e.id AND i.code = c.code)) — the double negation of Prop. 2.2, applied to the division of ch. 1.

   (c) The difference \pi_{\texttt{code}}(\texttt{Course}) - \pi_{\texttt{code}}(\texttt{Enrolled}), SQL: NOT EXISTS or LEFT JOIN … WHERE i.id IS NULL — the anti-join.

2. ★ Closure and 3NF (solved). R(A,B,C,D,E), F = \{A \to B,\; BC \to D,\; D \to E\}. (a) Compute the keys. (b) Is the relation in 3NF? (c) Decompose into 3NF without loss and verify each step with Theorem 3.5.

   Solution.

   (a) Closure of AC: (AC)^{+}:\ A \text{ gives } B,\ ABC \text{ gives } D,\ D \text{ gives } E \ \to\ \text{everything}, so AC is a key. Neither A nor C alone is: A^{+} = AB, C^{+} = C. Prime attributes: A, C.

   (b) No. Not 3NF: in D \to E the determinant is not a superkey (D^{+} = DE) and E is not prime; BC \to D fails in the same way (BC^{+} = BCDE).

   Not even 2NF: in A \to B the determinant A is a strict subset of the key AC and B is not prime — a partial dependency, the first defect that Example 3.6 removes.

   (c) By 3NF synthesis (minimal cover \{A\to B, BC\to D, D\to E\}, one schema per determinant, plus a key): (AB, BCD, DE, AC) — lossless and FD-preserving.

   The “by hand” decomposition (ABCD, DE) then (AB, ACD) is lossless (at the second step the intersection A determines AB, Thm 3.5) and preserves A\to B.

   But it loses the dependency BC \to D: no schema contains B, C and D together, so the constraint can no longer be checked locally. Synthesis avoids precisely this pitfall.

3. ★ B+ by hand (solved). Insert in order 2, 4, 6, 8, 10, 12, 14 into a B+ tree of order d=1; give the final tree and its height (same conventions as Example 5.4: when a leaf [a,b,c] splits, the copied separator is c, the first key of the right leaf).

   Solution.

   • 2 then 4: leaf [2,4].
   • The 6 overflows [2,4,6] → [2,4] / [6], copy of 6: root [6].
   • The 8: leaf [6,8].
   • The 10: [6,8,10] → [6,8] / [10], copy of 10: root [6,10], leaves [2,4] [6,8] [10].
   • The 12: leaf [10,12].
   • The 14: [10,12,14] → [10,12] / [14], copy of 14: the root [6,10,14] overflows (3 keys); internal split: the median key 10 is moved to the new root, internal children [6] and [14].

   Final tree:

                 [10]
             ┌──────┴──────┐
           [ 6 ]         [ 14 ]
         ┌──┴──┐        ┌──┴──┐
       [2,4] [6,8]   [10,12] [14]

   Height: 3. Check: all leaves at the same level, 1 ≤ keys ≤ 2 everywhere — the invariants of Definition 5.1 hold at every step.

4. ★ Serializability (solved). Let H = r_1(X)\, r_2(X)\, w_1(X)\, w_2(X)\, r_1(Y)\, w_1(Y)\, c_1\, c_2 . Build SG(H); is H serializable? recoverable? What would 2PL do?

   Solution.

   • Conflicts on X: r_1<w_2 (T1→T2), r_2<w_1 (T2→T1), w_1<w_2 (T1→T2). On Y: T2 does not write Y.
   • Graph: T1↔︎T2 → cycle → not serializable (Thm 6.2).
   • Recoverable? T2 reads X (original value) then writes X after w_1: T2 reads nothing written by T1 → yes, recoverable — but with a lost update.
   • Under 2PL with shared and exclusive locks, both transactions hold a shared lock on X after their reads; w_1(X) then waits for T_2’s lock and w_2(X) for T_1’s: a deadlock (Prop. 6.6).

   The DBMS aborts one of them, say T_2, lets T_1 finish and replays T_2 — the non-serializable interleaving is impossible, Theorem 6.5 in action, at the price of an abort.

5. ★ External sort. N = 2\times10^5 pages, M = 500. Compute the initial runs, passes, total I/O cost; how long on a disk at 20,000 pages/s?

   Hint. 400 runs, fan-in 499 → \lceil\log_{499} 400\rceil = 1, p = 2, cost 2Np = 8\times10^5 pages → 40 s.

6. ★ Vectors: sizing. 10^7 embeddings in d = 768 (float32): memory size? Number of multiplications for an exact k-NN? With IVF n_{list} = 4096, n_{probe} = 32 (balanced cells): comparative work performed, and gain?

   Hint. 30.7 GB; 7.68\times10^{10} products; IVF: 10^7/4096 \times 32 \approx 78\,000 vectors probed + distances to the centroids, i.e. ~1% of the exact work, at the price of recall.

7. ★★ Plan choice. Join R \Join S with B_R = 200, B_S = 10\,000, M = 52, a selection on R of selectivity 1/100 that can be pushed before the join.

   Compare: sort-merge on (R,S); hashing; and the order S \Join \sigma(R) in block nested loops.

   Hint. Filtering R costs one scan (200 pages) and leaves \sigma(R) = 2 pages, which fit in memory. A block nested loop with \sigma(R) as the outer relation then scans S once: 200 + 10\,000 = 10\,200 \text{ pages in total}, against about 3\times(200 + 10\,000) = 30\,600 for a hash join of the unfiltered inputs.

   Rule: push the selection down, then keep the small relation in memory as the outer loop.

8. ★★ SQLite recursion. Write in recursive SQL: (a) the degree (distance) of separation of each pair of users of a network (table follow(a,b)); (b) the connected components of an undirected graph.

   Hint. (a) propagate the length by accumulating and take the MIN per pair (window or GROUP BY), and stop at a depth bound (a shortest path has fewer edges than there are users): on a cyclic network the accumulated lengths keep growing, so even UNION would never reach a fixed point (Def. 2.6); (b) propagate the MIN of reached identifiers up to the fixed point.

9. ★★★ Open design. A journalist receives 5 CSV files (elections, demographics, funding, companies, press). Propose an architecture to cross-check and trace the numerical claims of an article: target schema, indexes, provenance, typical queries (reread ch. 10-11).

Projects and assessment

The fiche of this page quotes the assessment of the SynapseS sheet: “50% final written exam (paper documents allowed) · 50% three 30-minute tests in small classes starting mid-October”. The course unit is not in the LLGA 2026–2027 lists, so no LLGA assessment applies to it. Everything below is a proposal of these notes, for a student who takes the course in another track or works through the notes for reference: the written exam keeps the sheet’s format, and a project can replace or extend the three short tests.

The projects exercise mainly O7 (hands-on and industry practice: SQL, transactions, execution plans, benchmarks), O3 through the guarded text-to-SQL subject and O5 through the provenance-aware knowledge graph that a GraphRAG retriever queries. O4 (graph-structured data) enters with property graphs and RDF, and O8 (trustworthy AI) with provenance and the verification of published numbers.

Solo projects

1. [Solo · ≈ 20 h] Build your own ANN index: a paper study of product quantization. How much recall do the approximate indexes of Def. 9.4 give up, for how much speed and memory, and why does the answer depend on the data?
   • Implement: in NumPy, exact k-NN, IVF with k-means cells, product quantization with asymmetric distances, and IVF-PQ, following H. Jégou, M. Douze and C. Schmid, “Product Quantization for Nearest Neighbor Search”, IEEE TPAMI, 2011. Compare with HNSW from hnswlib (Malkov and Yashunin, 2018) and, as an option, with pgvector inside PostgreSQL.
   • Data: SIFT1M from the TEXMEX corpus of the PQ paper (one million 128-dimensional descriptors, 10,000 queries, exact neighbours given); GloVe-100 as packaged by ANN-Benchmarks (Aumüller, Bernhardsson and Faithfull, Information Systems, 2020); isotropic Gaussian vectors of the same sizes as a control.
   • Success criterion: recall@10 plotted against queries per second and bytes per vector for every index, swept over n_{\text{probe}}, the number m of sub-vectors and the HNSW search width; the hand-written IVF-PQ within 0.03 recall@10 of FAISS IndexIVFPQ at equal parameters, or the gap explained; the Gaussian-versus-real gap of Example 9.5 measured and explained.
   • Deliverables: code with tests, a 4–6 page report, a 10-minute talk. Chapters 5 and 9 (Def. 9.4, Example 9.5, Ex. 6). The index is the one behind the dense retrievers of Large Language Models, ch. 7 (the ANN box of §7.2).
2. [Solo · ≈ 20 h] A mini storage engine with crash recovery: a paper study of ARIES. Do a page file, an external merge sort, a B+ tree and a write-ahead log written from scratch reach the I/O counts and the recovery guarantee that chapters 4, 5 and 7 predict?
   • Implement: in Python, a page file with an I/O counter behind a small buffer pool (Def. 4.5); external merge sort (Theorem 4.3); a B+ tree with leaf and internal splits (Def. 5.1); a WAL with LSNs and an ARIES-style analysis, redo and undo with compensation records (Prop. 7.2); a switch that kills the process at random points.
   • Data and paper: the lineitem table of the TPC-H benchmark, generated with its dbgen tool at scale factor 0.1 (about 600,000 rows); C. Mohan, D. Haderle, B. Lindsay, H. Pirahesh and P. Schwarz, “ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging”, ACM TODS, 1992.
   • Success criterion: counted sort I/Os equal to the 2Np of Theorem 4.3 for several pairs (N, M); tree heights within the bound of Theorem 5.2; after at least 1,000 random crashes, some of them during recovery itself, the database holds exactly the committed transactions; the trace of Example 7.3 replayed step by step.
   • Deliverables: code with tests, a 4–6 page report, a 10-minute talk. Chapters 4, 5, 7.

Group projects

1. [Group of 3 · ≈ 30 h each] Guarded text-to-SQL over a normalized schema. Can an LLM answer questions in natural language over a database that the team designed, without ever writing to it or running a query above a cost budget — and where does it still return a plausible wrong number?
   • Implement: a 3NF schema derived from functional dependencies (ch. 3); an LLM (a small open model run locally, or an API) prompted with the schema; a guard that runs every generated query in a read-only transaction (ch. 6) and rejects it when PostgreSQL’s EXPLAIN estimates a cost above a budget (ch. 8), or, on SQLite, which gives no cost estimate, when an instruction budget set with set_progress_handler runs out; an execution-feedback loop on errors.
   • Data: the dev split of BIRD (J. Li et al., NeurIPS 2023 Datasets and Benchmarks track), plus 60 hand-written questions over the team’s own schema that stress NULL logic, universal quantification with NOT EXISTS and window functions (ch. 2).
   • Work split: schema design and loading; prompting and the feedback loop; the guard, the hand-written test set and the error analysis with the taxonomy of From Boosting to Foundation Models, ch. 7.
   • Success criterion: execution accuracy (Def. 7.4 of that page) on both sets, with and without the guard and the feedback loop; no write ever reaches the database; every failure classified, with the silent wrong answers reported apart from the queries that fail with an error.
   • Deliverables: a repository, a 6-page report, a 15-minute talk with a live demonstration. Chapters 2, 3, 6, 8.
2. [Group of 3 · ≈ 30 h each] Heterogeneous sources into a provenance-aware knowledge graph. In the spirit of ConnectionLens (ch. 11), can a team merge a CSV register, a JSON dump and a set of texts about one domain into a single graph whose every value is traced to its source, and answer multi-hop questions over it?
   • Implement: entity extraction from the texts with an off-the-shelf NER model; entity resolution with blocking and Jaccard similarity (Def. 10.2, Prop. 10.3); loading into RDF with one named graph per source, or into a property graph with a source property on every edge (Def. 9.3); SPARQL or Cypher queries; a GraphRAG retriever that hands the matched subgraph to an LLM.
   • Data: the French companies of one sector, from three sources: the Sirene register of INSEE (CSV, on data.gouv.fr), their Wikidata entities as JSON from the Wikidata Query Service, and their Wikipedia articles as text.
   • Work split: ingestion and extraction; entity resolution and the provenance model; queries, the GraphRAG retriever and the evaluation.
   • Success criterion: entity-resolution precision and recall against the SIREN numbers that Wikidata stores (property P1616), held out from the matching features; blocking recall reported (the share of true pairs that share a block); 30 hand-written multi-hop questions answered with the source of every value; GraphRAG compared with text-only retrieval on these questions.
   • Deliverables: a repository, a 6-page report, a 15-minute talk. Chapters 9, 10, 11 and Ex. 9. It prepares the GraphRAG chapter of Graph ML.
3. [Group of 3 · ≈ 25 h each] Checking published statistics against open data. Extending Ex. 9: how often do numerical claims in news articles match the official data they cite, and when they do not, is the claim or the query wrong?
   • Implement: a set of 100 numerical claims taken from news articles (unemployment, population, election results); for each one, a SQL aggregation over open datasets loaded in a normalized schema; a provenance store with the claim, the query, the dataset version and the verdict; a classification of the failures (join duplication, NULL handling, wrong period or perimeter).
   • Data and paper: INSEE local statistics and the official French election results published on data.gouv.fr; O. Balalau et al., “Fact-checking Multidimensional Statistic Claims in French”, Truth and Trust Online (TTO), 2022 — the StatCheck line of ch. 11.
   • Work split: claim collection and annotation; loading, schema and the claim-to-query mapping; the provenance store, the verdicts and the failure analysis.
   • Success criterion: two members map each claim independently and their agreement (Cohen’s κ) is reported; every verdict re-runs from the stored query and dataset version; the causes of failure tallied, with the query errors separated from the false claims.
   • Deliverables: a repository, a 6-page report, a 15-minute talk. Chapters 2, 3, 10, 11.

Written exam (proposal)

Format: 2 hours, paper documents allowed (as on the sheet), no electronic device; four independent questions — a course question, two computations and a short proof.

1. Question (5 points). Course question. State the WAL rule. Explain why a STEAL / NO-FORCE buffer policy needs both undo and redo, then describe the three passes of ARIES and say why its redo pass also replays the writes of uncommitted transactions.

   Expected:

   • WAL: the log record of a modification reaches the disk before the modified page (Def. 7.1).
   • STEAL lets an uncommitted page reach the disk, so recovery must undo it from the before-image; NO-FORCE lets a committed change live only in memory, so recovery must redo it from the after-image.
   • Analysis rebuilds the transaction table and the dirty page table from the last checkpoint; redo replays, in LSN order, every change newer than the LSN stored in its page; undo rolls back the unfinished transactions in reverse LSN order and writes CLRs (Prop. 7.2).
   • Repeating history restores the exact state at the crash, so undo works on consistent pages; page LSNs make redo idempotent, and CLRs make undo restartable after a second crash.

2. Question (6 points). Computation. A relation R of B_R = 2000 pages is joined with S of B_S = 400 pages, with M = 41 buffer pages; use Theorem 4.3 and Def. 8.2, and ignore the cost of writing the result.

   (a) Give the number of initial runs, the number of passes and the I/O cost of sorting R. (b) Give the cost of block nested loops with each relation as the outer one. (c) Give the cost of sort-merge and of the hash join, and say which plan the optimizer keeps.

   Expected:

   • (a) \lceil 2000/41\rceil = 49 runs; the fan-in is 40 < 49, so two merge passes and p = 3; cost 2 \times 2000 \times 3 = 12\,000 pages.
   • (b) S outer: 400 + \lceil 400/40\rceil \times 2000 = 20\,400; R outer: 2000 + 50 \times 400 = 22\,000. The smaller relation goes outside.
   • (c) Sorting S: 10 runs, one merge pass, cost 1,600. Sort-merge: 12\,000 + 1\,600 + 2\,400 = 16\,000. Hash join: 3 \times (2000 + 400) = 7\,200, feasible since 400 pages split into 40 partitions of about 10 pages, each fitting in memory. The optimizer keeps the hash join.

3. Question (5 points). Computation. The table Emp(id, dept, salary) holds (1, ‘A’, 3000), (2, ‘A’, NULL), (3, ‘B’, 2000) and (4, NULL, 2500). (a) What does SELECT COUNT(*), COUNT(salary), AVG(salary) FROM Emp return? (b) How many rows does SELECT * FROM Emp WHERE dept <> 'A' return, and why? (c) Write with NOT EXISTS the departments in which every employee earns at least 2500, and give the answer on this instance.

   Expected:

   • (a) 4, 3 and 2500: COUNT(*) counts rows, the other aggregates ignore the NULL (Def. 2.5).

   • (b) One row, employee 3: for employee 4 the comparison NULL <> 'A' is UNKNOWN, and WHERE keeps only the TRUE rows.

   • (c) With the double negation of Prop. 2.2:

     SELECT DISTINCT d.dept FROM Emp d
     WHERE d.dept IS NOT NULL AND NOT EXISTS (
       SELECT 1 FROM Emp e WHERE e.dept = d.dept AND NOT (e.salary >= 2500));

     It returns A only. B fails through employee 3; the NULL salary of employee 2 makes NOT (e.salary >= 2500) UNKNOWN, so it is not a counterexample. Writing the last condition of the subquery as (NOT (e.salary >= 2500) OR e.salary IS NULL) would treat the unknown salary as a counterexample and exclude A as well.

4. Question (4 points). Short proof. Using only Armstrong’s axioms (Theorem 3.2), prove (a) the union rule: if X \to Y and X \to Z then X \to YZ; (b) the pseudo-transitivity rule: if X \to Y and WY \to Z then WX \to Z.

   Expected:

   • (a) Augmenting X \to Y by X gives X \to XY, since XX = X.
   • Augmenting X \to Z by Y gives XY \to YZ; transitivity on the two results gives X \to YZ.
   • (b) Augmenting X \to Y by W gives WX \to WY; transitivity with WY \to Z gives WX \to Z.

Grading rubric (proposal)

References

• E. F. Codd, “A Relational Model of Data for Large Shared Data Banks”, Communications of the ACM 13(6), 1970 — the founding paper of the relational model.
• S. Abiteboul, R. Hull, V. Vianu, Foundations of Databases, Addison-Wesley, 1995 — the theoretical reference: algebra/calculus (Thm 1.7), dependencies, chase, normal forms.
• A. Silberschatz, H. Korth, S. Sudarshan, Database System Concepts, 7th ed., McGraw-Hill, 2019 — the course textbook: storage, B+ trees, transactions, ARIES, distributed.
• H. Garcia-Molina, J. Ullman, J. Widom, Database Systems: The Complete Book, 2nd ed., Prentice Hall, 2008 — ch. 13-14 (storage and indexes, B+ trees), 15-16 (query execution and the query compiler), 17 (recovery), 18-19 (concurrency and transaction management).
• D. Comer, “The Ubiquitous B-Tree”, ACM Computing Surveys 11(2), 1979 — the classic survey on B-trees.
• G. Graefe, “Query Evaluation Techniques for Large Databases”, ACM Computing Surveys 25(2), 1993 — joins, costs, optimization, the source of ch. 8.
• P. Bernstein, V. Hadzilacos, N. Goodman, Concurrency Control and Recovery in Database Systems, Addison-Wesley, 1987 — the theorems of ch. 6 (2PL, serializability), freely consultable online.
• C. Mohan, D. Haderle, B. Lindsay, H. Pirahesh, P. Schwarz, “ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Roll-Backs Using Write-Ahead Logging”, ACM TODS 17(1), 1992 — the paper of ch. 7.
• S. Gilbert, N. Lynch, “Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services”, SIGACT News 33(2), 2002 — the formalization of CAP (Thm 9.1).
• N. Francis et al., “Cypher: An Evolving Query Language for Property Graphs”, SIGMOD 2018 — the language of property graphs; on the RDF side: W3C, RDF 1.1 Concepts and SPARQL 1.1.
• Y. Malkov, D. Yashunin, “Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs”, IEEE TPAMI 2018 — arXiv 1603.09320; H. Jégou, M. Douze, C. Schmid, “Product Quantization for Nearest Neighbor Search”, IEEE TPAMI 33(1), 2011 — the two pillars of ch. 9.
• J. Johnson, M. Douze, H. Jégou, “Billion-scale Similarity Search with GPUs”, IEEE Trans. Big Data 2017 — arXiv 1702.08734: the FAISS library, the standard tool for vector labs.
• S. Abiteboul, I. Manolescu, P. Rigaux, M.-C. Rousset, P. Senellart, Web Data Management, Cambridge University Press, 2011 — free online edition; Z. Kaoudi, I. Manolescu, S. Zampetakis, Cloud-Based RDF Data Management, Morgan & Claypool, 2020.
• C. Chanial et al., “ConnectionLens: Finding Connections across Heterogeneous Data Sources”, PVLDB 11(12), 2018; A. C. Anadiotis et al., “Graph integration of structured, semistructured and unstructured data for data journalism”, Information Systems 104, 2022 — the CEDAR team in action (ch. 10-11); complete publication list on dblp.
• Documentation: SQLite window functions, MVCC in PostgreSQL, MongoDB manual, pgvector.