DBMS Quick Revision Notes

These notes follow a standard undergraduate DBMS syllabus: the definitions you are expected to reproduce, the rules that settle short-answer and numerical questions, and one small example per topic. Use them to revise after you have studied the subject once.

Most examples share one schema: employee(emp_id, name, salary, dept_id), department(dept_id, dept_name), works_on(emp_id, proj_id) and project(proj_id, proj_name).

Keys

The definitions use student(roll_no, email, name, dept_id), where roll_no and email are each unique and dept_id refers to department.

• Every candidate key is a super key, but not the reverse. A key with more than one attribute is composite.
• The primary key enforces entity integrity (no NULLs). A foreign key enforces referential integrity; its values can repeat or be NULL, and it can reference any UNIQUE column set.
• A prime attribute belongs to at least one candidate key. 2NF and 3NF are defined using this.
• Counting super keys: with n attributes and one single-attribute candidate key, every superset of it is a super key: 2^(n−1). For R(A, B, C, D) with key A, that is 8. With candidate keys A and B: 2³ + 2³ − 2² = 12.

ER model

An entity is a thing with independent existence, such as a student. Attributes can be composite, multivalued (several phone numbers) or derived (age from date of birth). A relationship associates entities; its degree is the number of entity sets involved.

Cardinality ratio is the maximum number of relationship instances per entity: 1:1 (department and head), 1:N (department and employees), M:N (students and courses). Participation is the minimum: total if every entity must take part, partial otherwise.

A weak entity has no key of its own. It is identified by its owner's key plus its partial key, through an identifying relationship in which it participates totally. Example: dependent of employee, identified by (emp_id, dependent_name).

Minimum number of tables: two strong entities need 3 with an M:N relationship, 2 with 1:N, and 1 with a 1:1 relationship where both sides participate totally. Each multivalued attribute adds one.

Relational algebra

Relational algebra is the procedural language underneath SQL. Operators take and return relations, which are sets, so results never contain duplicates.

The first six are fundamental; ∩, ⋈ and ÷ can be written using them.

Employees earning more than 50000:        σ salary > 50000 (employee)
Name and salary of every employee:        π name, salary (employee)
Employees with their department names:    π name, dept_name (employee ⋈ department)
Employees on project P1 or P2:            π emp_id (σ proj_id = 'P1' (works_on)) ∪ π emp_id (σ proj_id = 'P2' (works_on))
Employees on no project:                  π emp_id (employee) − π emp_id (works_on)
Employees on every project:               works_on ÷ π proj_id (project)

A theta join is σθ (R × S), an equi-join uses only equality, and a natural join is an equi-join on all same-named attributes, keeping one copy of each. Outer joins (⟕, ⟖, ⟗) also keep unmatched rows, padded with NULLs.

Union, intersection and difference need union-compatible relations: the same number of attributes, with compatible domains in the same order.

Division. If works_on pairs E1 with P1 and P2, E2 with P1 only, and E3 with P1 and P2, then works_on ÷ π proj_id (project) returns E1 and E3. With A the attributes of R not in S: R ÷ S = π A (R) − π A ((π A (R) × S) − R).

Sizes. R × S has |R| × |S| rows. A natural join on a non-NULL foreign key of R referencing the primary key of S returns exactly |R| rows.

SQL essentials

CREATE TABLE employee (
  emp_id  INT PRIMARY KEY,
  name    VARCHAR(100) NOT NULL,
  salary  DECIMAL(10, 2) CHECK (salary > 0),
  dept_id INT,
  FOREIGN KEY (dept_id) REFERENCES department (dept_id) ON DELETE SET NULL
);
 
INSERT INTO employee (emp_id, name, salary, dept_id) VALUES (1, 'Asha', 62000, 10);
UPDATE employee SET salary = salary * 1.10 WHERE dept_id = 10;
DELETE FROM employee WHERE emp_id = 1;

DELETE (DML) removes matching rows, fires delete triggers and can be rolled back. TRUNCATE removes every row and DROP removes the table; both are DDL, and whether they can be rolled back depends on the DBMS.

Joins: INNER JOIN keeps matching pairs; LEFT and RIGHT JOIN keep every row of one side, with NULLs where the other has no match; FULL OUTER JOIN keeps both (MySQL lacks it); CROSS JOIN is the Cartesian product.

SELECT dept_id, COUNT(*) AS headcount, AVG(salary) AS avg_salary
FROM employee
WHERE salary > 30000        -- filters rows before grouping
GROUP BY dept_id
HAVING COUNT(*) >= 5        -- filters groups after aggregation
ORDER BY avg_salary DESC;

• WHERE runs before groups exist, so it cannot use aggregates; conditions on aggregates go in HAVING.
• In standard SQL, every selected column must appear in GROUP BY or inside an aggregate.
• Aggregates ignore NULLs: COUNT(*) counts rows, COUNT(salary) counts non-NULL salaries. x = NULL is never true; use IS NULL.
• UNION removes duplicate rows; UNION ALL keeps them.

-- Correlated subquery: employees paid above their own department's average
SELECT e.name FROM employee e
WHERE e.salary > (SELECT AVG(x.salary) FROM employee x WHERE x.dept_id = e.dept_id);
 
-- Second-highest salary
SELECT MAX(salary) FROM employee
WHERE salary < (SELECT MAX(salary) FROM employee);

A correlated subquery refers to the outer row, so it is logically evaluated once per outer row.

Normalization up to BCNF

Normalization splits tables to remove redundancy caused by functional dependencies. Redundancy causes update, insertion and deletion anomalies: one fact stored in many rows, a fact that cannot be stored without an unrelated one, and a deletion that loses an unrelated fact.

A functional dependency X → Y means rows that agree on X also agree on Y. The closure X⁺ is everything X determines: start with X and keep adding the right side of any dependency whose left side is included. X is a super key when X⁺ contains every attribute.

For any "highest normal form" question, find every candidate key first, then test each dependency. An attribute that never appears on the right side of a dependency is part of every candidate key.

Worked example: one table from 1NF to BCNF

A college records each student's courses, tutors and grades. A course can have several tutors, but each tutor teaches one course. Each student belongs to one department, which has one head (HOD). One row per enrollment gives a 1NF table:

FD1: student_id → name, dept
FD2: dept → hod
FD3: student_id, course_id → tutor, grade
FD4: tutor → course_id

student_id is on no right side, so it is in every key. (student_id, course_id)⁺ covers every attribute, and so does (student_id, tutor)⁺ (FD4 adds course_id, then FD3 applies). Both are candidate keys, so student_id, course_id and tutor are prime and the rest are non-prime. Redundancy shows: changing the CSE head means editing several rows, and deleting S2 loses the fact that Kapoor teaches DB101.

To 2NF. name, dept and, through FD2, hod depend on student_id alone, which is only part of each key. Move them out: student(student_id, name, dept, hod) and enrollment(student_id, course_id, tutor, grade). FD4 does not break 2NF, because course_id is prime.

To 3NF. In student, student_id → dept → hod is transitive: dept is not a super key and hod is non-prime. Split it into student(student_id, name, dept) and department(dept, hod). enrollment is already in 3NF: in FD4, tutor is not a super key, but course_id is prime, which 3NF allows.

To BCNF. FD4 violates BCNF, because tutor is not a super key of enrollment. Decompose on it into tutor_course(tutor, course_id), keyed by tutor, and enrollment(student_id, tutor, grade), keyed by (student_id, tutor).

Every split is lossless, since the shared attribute is a key of one side. But FD3 is no longer preserved: no table holds student_id, course_id and tutor together, so the schema cannot stop S1 from taking DB101 with both Mehta and Kapoor. That rule now needs a trigger or an application check.

• Splitting R into R1 and R2 is lossless if the shared attributes are a super key of R1 or of R2.
• A lossless, dependency-preserving decomposition into 3NF always exists. A lossless one into BCNF always exists, but it may lose dependencies, as here.
• Every relation with only two attributes is in BCNF.

Transactions and ACID

A transaction is a sequence of operations forming one logical unit of work. It ends with COMMIT, which makes its changes permanent, or ROLLBACK, which undoes them.

START TRANSACTION;
UPDATE account SET balance = balance - 500 WHERE acc_no = 'A101';
UPDATE account SET balance = balance + 500 WHERE acc_no = 'B202';
COMMIT;

States: active → partially committed → committed; or, on failure, failed → aborted, after which the transaction is rolled back and restarted or discarded.

Recovery: every update is logged with its old and new values, and under write-ahead logging the log record reaches stable storage before the data page. After a crash, transactions with a commit record are redone and the rest undone. Deferred update needs only redo; immediate update needs both.

Concurrency control

Uncontrolled interleaving causes lost updates (one write overwrites another), dirty reads (reading uncommitted data that is later rolled back), unrepeatable reads (the same row read twice gives different values) and phantoms (a repeated query returns newly inserted rows).

Serializability

A schedule interleaves several transactions' operations, keeping each transaction's own order. It is serializable if it is equivalent to some serial schedule. Two operations conflict when they are from different transactions, touch the same item, and at least one is a write.

To test conflict serializability, draw a precedence graph: one node per transaction, and an edge Ti → Tj when an operation of Ti conflicts with a later one of Tj. No cycle means conflict serializable, and a topological order gives the equivalent serial order.

S1: R1(A) W1(A) R2(A) W2(A) R1(B) W1(B)   edges T1 → T2 only: serializable as T1, T2
S2: R1(A) R2(A) W1(A) W2(A)               T1 → T2 and T2 → T1: cycle, not serializable

S2 is a lost update. Every conflict-serializable schedule is also view serializable, but not the reverse.

Recoverability, from weakest to strongest: recoverable (if Tj reads a value written by Ti, Ti commits before Tj), cascadeless (transactions read only committed values) and strict (no read or write of an item until its last writer has committed or aborted).

Two-phase locking

A shared (S) lock allows reading; an exclusive (X) lock allows writing. S is compatible only with S; X is compatible with nothing.

Under 2PL, a transaction acquires locks in a growing phase and releases them in a shrinking phase, never acquiring after its first release. This guarantees conflict serializability but not freedom from deadlock.

Deadlocks and isolation levels

A wait-for graph detects deadlock: a cycle means deadlock, and the system rolls back a victim. In timestamp-based prevention, a restarted transaction keeps its original timestamp, so it cannot starve:

Real systems may be stricter than the standard: PostgreSQL's repeatable read also prevents phantoms.

Indexing

An index maps search-key values to record locations, so a lookup reads a few blocks instead of the whole file, at the cost of storage and slower writes.

A file is sorted on one field, so it has a primary or a clustering index, not both. Sparse indexes work only on a file sorted by their key.

Numerical. A sorted file has 30,000 records of 100 bytes, blocks of 1,024 bytes, 9-byte keys and 6-byte block pointers.

1. ⌊1024 / 100⌋ = 10 records per block, so 3,000 blocks. Binary search on the file: ⌈log₂ 3000⌉ = 12 block accesses.
2. Index entries are 9 + 6 = 15 bytes, so ⌊1024 / 15⌋ = 68 fit per block. One entry per data block needs ⌈3000 / 68⌉ = 45 index blocks.
3. With the index: ⌈log₂ 45⌉ = 6 accesses, plus 1 data block, is 7.

B+ tree

• Balanced: every leaf is at the same depth, so every lookup reads the same number of nodes.
• Internal nodes hold only keys and child pointers. Record pointers are all in the leaves, which are linked in key order for range scans.
• Every node except the root is at least half full. Insertion splits full nodes, possibly adding a level at the root; deletion borrows or merges.
• A B tree also stores record pointers in internal nodes, which lowers its fan-out, and its leaves are not linked.

Order. With 512-byte blocks, 9-byte keys, 6-byte block pointers and 7-byte record pointers: an internal node with p pointers and p − 1 keys needs 6p + 9(p − 1) ≤ 512, so p = 34. A leaf with p_leaf (key, record pointer) pairs and a next-leaf pointer needs 16 × p_leaf + 6 ≤ 512, so p_leaf = 31.

A hash index answers equality lookups in close to constant expected time but cannot answer range queries. Primary key and unique constraints get an index automatically; other columns, including foreign keys in PostgreSQL, need one created explicitly.

CREATE INDEX idx_employee_dept ON employee (dept_id);

Last-minute checklist

• Define each type of key and count super keys
• Map weak entities, M:N relationships and multivalued attributes to tables
• Write σ, π, ⋈, ∪, − and ÷ expressions for a query in words
• Explain WHERE versus HAVING, and why NOT IN fails with NULLs
• Find candidate keys with closure and take a table from 1NF to BCNF
• State when a decomposition is lossless and dependency preserving
• State ACID and which component ensures each property
• Decide conflict serializability with a precedence graph
• Compare the 2PL variants, and wait-die with wound-wait
• Fill in the isolation level table from memory
• Compute block accesses with an index and the order of a B+ tree