Databases

Subject 4 of 10 · ER diagrams, the relational model, keys, relational algebra, SQL, normalization, transactions, concurrency control, and indexing.

1. ER Model

Entity sets and attributes

An entity is a real-world object (a student, a course); an entity set is a collection of similar entities (all students). An attribute is a property of an entity (name, age). Attributes come in flavors: simple (atomic, like age), composite (splittable, like name → first/last), derived (computed from another, like age from DOB), multivalued (several values, like phone numbers), and key attributes that uniquely identify an entity.

Cardinality constraints (1:1, 1:N, M:N)

Cardinality (mapping cardinality) says how many entities on each side can participate in a relationship. One-to-one: each A links to at most one B and vice versa (person ↔ passport). One-to-many: one A links to many B (department → employees). Many-to-many: many on both sides (students ↔ courses). Total participation means every entity must participate (double line); partial participation means it may or may not (single line).

Weak entity sets

A weak entity set has no key of its own and depends on an identifying (owner) entity — e.g. a Building owns Rooms; room number alone is ambiguous, so the weak entity uses a partial key (room number) plus the owner's key. Its relationship to the owner is an identifying relationship (double diamond).

ER to relational mapping

2. Relational Model

Relation schema and instance

A relation (table) has a schema — the structure: relation name plus attribute names and domains — and an instance — the actual set of tuples (rows) at a moment in time. The degree is the number of attributes (columns); the cardinality is the number of tuples (rows). Tuples are unordered and no two tuples are identical; attribute values are atomic.

Integrity constraints

Domain constraints restrict each attribute to its allowed values. Entity integrity: no primary key attribute may be NULL. Referential integrity: a foreign key must reference an existing tuple or be NULL. Key constraints: each key value must be unique across the table.

3. Keys

Super, candidate, primary, alternate

Referential integrity actions

When the referenced row is deleted or updated, the foreign key declares what happens:

4. Relational Algebra

Relational algebra is the procedural query language behind SQL. Each operator takes relations in and returns a relation out.

Union compatibility: ∪, ∩, and − need both relations to have the same number of attributes with matching domains. Degree/cardinality: σ keeps the degree, shrinks cardinality; π shrinks the degree; R × S has degree(R)+degree(S) and |R|·|S| tuples.

5. SQL Fundamentals

Types of SQL

DDL: CREATE, ALTER, DROP

CREATE TABLE students (id INT PRIMARY KEY, name VARCHAR(50) NOT NULL, age INT); defines a table. ALTER TABLE students ADD email VARCHAR(100); modifies structure after creation. DROP TABLE students; deletes the table and its data permanently; TRUNCATE TABLE students; deletes all rows but keeps the structure.

DML: INSERT, UPDATE, DELETE

INSERT INTO students VALUES (1, 'Asha', 20); — add one row; with a column list you can insert into specific columns. UPDATE students SET age = 21 WHERE id = 1; — always use WHERE, or every row changes. DELETE FROM students WHERE id = 1; — no WHERE means the whole table is emptied.

SELECT and WHERE

SELECT name, age FROM students; picks columns; SELECT * FROM students; picks all. SELECT DISTINCT city FROM students; removes duplicate values. Aliases rename output columns: SELECT name AS student_name FROM students;.

Aggregate functions and GROUP BY

COUNT(*) counts rows (including NULLs); COUNT(col) counts non-NULL values. SUM, AVG, MIN, MAX ignore NULLs. GROUP BY dept splits rows into groups so each aggregate runs per group; HAVING filters groups afterward (WHERE filters rows before grouping).

SELECT dept, AVG(salary) FROM emp GROUP BY dept HAVING AVG(salary) > 50000;

ORDER BY

ORDER BY marks DESC; sorts results; default is ascending (ASC). Multiple columns sort by the first, then the second within ties: ORDER BY dept, salary DESC;.

6. Joins & Constraints in SQL

JOINs

Joins combine rows from two tables on a matching condition, usually a foreign key equality.

SELECT s.name, c.title FROM students s INNER JOIN enroll e ON s.id = e.sid INNER JOIN courses c ON e.cid = c.id;

Constraints

7. Normalization

Why normalize: the three anomalies

Bad design repeats data, and repeated data rots three ways. Insertion anomaly: you cannot add a fact without adding an unrelated one (can't add a department with no employees yet). Update anomaly: changing one fact means editing many rows, and missing one corrupts the data. Deletion anomaly: deleting a row destroys an unrelated fact (last employee of a department deletes the department info). Normalization restructures tables to kill redundancy while preserving information.

Goals of normalization

Eliminate data redundancy, ensure each piece of information is stored once, protect data integrity during inserts/updates/deletes, and keep the design flexible. The price: more tables, so queries need more joins — normalization trades query simplicity for update safety.

Functional dependencies

A functional dependency X → Y means: if two tuples agree on X, they must agree on Y — X determines Y. Trivial FD: Y ⊆ X (e.g. {A,B} → A) — always true, tells you nothing. Non-trivial FD: Y ⊄ X — the ones that matter. A full FD means no proper subset of X determines Y; otherwise it is partial.

Armstrong's axioms

The three axioms generate every FD implied by a set:

Derived rules you will actually use: union (X → Y and X → Z gives X → YZ), decomposition (X → YZ gives X → Y and X → Z), pseudotransitivity (X → Y and WY → Z gives WX → Z).

Canonical cover (minimal cover)

The minimal equivalent set of FDs. Steps: (1) split right sides so each FD has a single attribute; (2) remove extraneous attributes from left sides — drop A from XY → Z if Z is still in (X)⁺ without A; (3) remove redundant FDs — drop X → Y if Y is in X⁺ computed from the other FDs. The result has no redundant FD and no FD with an extraneous attribute.

First Normal Form (1NF)

A table is in 1NF when every attribute holds an atomic, single value — no lists, no repeating groups, no composite values stuffed into one cell. 1NF is the entry ticket; every normalized design starts here.

8. Lossless Join Decomposition

A decomposition splits R into R1 and R2. It is lossless if joining the pieces gives back exactly the original table — no spurious tuples, no lost ones. The test: the decomposition is lossless iff the common attributes R1 ∩ R2 form a super key of R1 or of R2 — i.e. (R1 ∩ R2) → R1 or (R1 ∩ R2) → R2 holds in the FD set.

Losslessness is about information preservation: the decomposition must not add or lose data. It says nothing about whether the FDs still hold — that is the next chapter's job.

9. Dependency Preserving Decomposition

A decomposition is dependency preserving if every FD of the original can be enforced by checking the decomposed tables individually — equivalently, the union of the FDs projected onto each piece implies all original FDs. To test: for each FD X → Y in the original set, check whether Y ⊆ X⁺ computed using only FDs whose attributes lie within a single decomposed relation; if every FD passes, dependencies are preserved.

Example: R(A,B,C) with A → B, B → C decomposed into R1(A,B) and R2(B,C) is lossless (B is common and a key of R2) and dependency preserving (A → B lives in R1, B → C lives in R2, and A → C follows by transitivity).

10. Transactions

ACID properties

Classic example: transferring ₹500 from account A to B. Atomicity means you never see the debit without the credit; durability means a crash right after commit loses nothing.

Transaction states

Active → executing; partially committed → last statement done, commit not yet recorded; committed → changes permanent; failed → something broke; aborted → rolled back to the pre-transaction state.

TCL commands

11. Concurrency Control

Schedules

A schedule is the interleaved order of operations from concurrent transactions. A serial schedule runs one transaction fully before the next — always correct, but slow. A concurrent schedule interleaves operations for throughput and better response time, but risks interference. A schedule is serializable if its effect equals some serial schedule — that is the correctness bar.

Conflict serializability

Two operations conflict if they are from different transactions, touch the same data item, and at least one is a write. A schedule is conflict serializable if conflicting operations can be reordered into a serial order without changing the outcome. The test: build a precedence graph — a node per transaction, an edge Ti → Tj for every conflict where Ti's operation came first. If the graph has no cycle, the schedule is conflict serializable.

View serializability

A weaker test with three conditions against a serial schedule: (1) initial reads — each transaction reads the same initial values; (2) updated reads — every read sees the value written by the same transaction; (3) final writes — the last writer of each item is the same. Every conflict-serializable schedule is view serializable, but not vice versa — blind writes (writes with no preceding read) are the classic counterexample.

Recoverable schedules

Locks

Lock compatibility: S–S compatible; S–X, X–S, X–X all conflict. Lock granularity — how big a chunk you lock — trades concurrency against overhead: database → table → page → row → field. Finer granularity means more concurrency but more lock bookkeeping; coarser means less overhead but transactions block each other more.

Two-Phase Locking (2PL)

Growing phase: acquire locks, never release. Shrinking phase: release locks, never acquire. Any schedule obeying 2PL is conflict serializable. The moment between the last acquire and first release is the lock point. Upgrades (S → X) are allowed in the growing phase. 2PL guarantees serializability but not freedom from deadlock or cascading rollback.

Timestamp ordering protocol

Each transaction gets a unique timestamp at start; older = smaller. For data item Q keep read_TS(Q) and write_TS(Q) — the largest timestamps that read/wrote it. A read by Ti succeeds only if TS(Ti) ≥ write_TS(Q); a write by Ti succeeds only if TS(Ti) ≥ read_TS(Q) and TS(Ti) ≥ write_TS(Q). Violations abort and restart the transaction with a new timestamp. No locks, no deadlocks — but aborts and restarts cost throughput.

12. Indexing & File Organization

Index types

Dense vs sparse index

Dense: one index entry per data record — larger, but finds any record directly. Sparse: one entry per data block — smaller, but you may scan within the block after the lookup. Primary and clustering indexes can be sparse; secondary indexes must be dense.

Index math

Let BFR be the blocking factor (records per block) and the index blocking factor = entries per index block. Number of first-level index blocks = ceil(number of data blocks / index blocking factor). A multilevel index stacks sparse indexes: each level's entries point to blocks of the level below, shrinking by the blocking factor each time until one root block remains. Search cost = n + 1 block accesses, where n is the number of index levels (plus 1 for the data block). Example: 1000 data blocks with blocking factor 100 → 10 level-1 blocks → 1 root: 3 levels, 11 index blocks, 4 accesses per search.

B-tree vs B+ tree

Node capacity: for an internal node of order p, p·(block pointer size) + (p−1)·(key size) ≤ block size; for a leaf node of order p_leaf, (p_leaf−1)·(key size + record pointer size) + block pointer ≤ block size — the extra pointer links to the next leaf.