The ER model (Entity-Relationship model) is a way to draw a picture of your data before you build the database. You describe the real world using entities, attributes, and relationships. Then you turn the picture into tables.

An entity is a real thing we store data about. Example: a student named Rahim. An entity set is the group of all similar entities. Example: all students. In the diagram, an entity set is a rectangle.

An attribute is a property of an entity. It is drawn as an ellipse. There are several kinds:

• Simple: cannot be divided. Example: age.
• Composite: can be split into parts. Example: name = first_name + last_name.
• Single-valued: one value per entity. Example: sid.
• Multivalued: can have many values. Example: phone (a student may have 2 phones). Drawn as a double ellipse.
• Derived: can be computed from other data. Example: age from date_of_birth. Drawn as a dashed ellipse.
• Key attribute: uniquely identifies an entity. Example: sid. Its name is underlined.

A relationship connects two (or more) entity sets. It is drawn as a diamond. Example: Student Enrolls in Course. A relationship can also have its own attribute (like grade).

Cardinality tells how many entities can join the relationship on each side:

• 1:1 (one-to-one): one entity matches at most one on the other side. Example: one department has one head; one teacher heads one department.
• 1:N (one-to-many): one entity on the left matches many on the right. Example: one department has many students, but each student belongs to one department.
• M:N (many-to-many): many on both sides. Example: one student takes many courses, and one course has many students.

Participation says whether every entity must join the relationship:

• Total (full) participation: every entity takes part. Drawn with a double line. Example: every Enroll row must have a student.
• Partial participation: some entities may not take part. Drawn with a single line. Example: some students may not enroll in any course yet.

A weak entity has no key of its own. It depends on a strong (owner) entity to be identified. It is drawn as a double rectangle, and the identifying relationship is a double diamond. Its partial key (discriminator) gets a dashed underline.

Example: Section(sec_no, day, time) of a Course. Section 1 of CSE101 and Section 1 of CSE201 both have sec_no = 1. So sec_no alone cannot identify a section. Full key of Section = owner key + partial key = (cid, sec_no).

1. Strong entity: becomes a table. Attributes become columns. Key attribute becomes primary key. Student(sid, name) → table Student.
2. Composite attribute: keep only the parts as columns (first_name, last_name), not the whole.
3. Multivalued attribute: make a separate table. phone → table StudentPhone(sid, phone), key = (sid, phone).
4. Derived attribute: usually not stored. Compute it when needed.
5. Weak entity: table with owner's key + partial key as primary key. Section → Section(cid, sec_no, day), PK = (cid, sec_no), FK cid → Course.
6. 1:1 relationship: put the key of one side as a foreign key in the other side (prefer the side with total participation), or merge the two tables.
7. 1:N relationship: put the key of the "1" side as a foreign key in the "N" side. BelongsTo → add column dno in Student.
8. M:N relationship: make a new table with both keys plus relationship attributes. Enrolls → Enroll(sid, cid, grade), PK = (sid, cid).

In the relational model, all data lives in relations (tables). This is the model SQL databases use.

• Relation: a table. Example: Student.
• Tuple: one row of the table. Example: (101, 'Rahim', 'CSE').
• Attribute: one column. Example: name.
• Domain: the set of allowed values for an attribute. Example: credit must be a positive number.
• Degree (arity): number of attributes. Student(sid, name, dept) has degree 3.
• Cardinality: number of tuples (rows) in the relation.

Schema notation: we write a relation as Student(sid, name, dept). The primary key is underlined: Student(sid, name, dept).

• Superkey: any set of attributes that uniquely identifies a tuple. Example: {sid}, {sid, name}, {sid, dept} are all superkeys of Student.
• Candidate key: a minimal superkey — remove any attribute and it stops being a key. Example: {sid}. If email is also unique, {email} is another candidate key.
• Primary key: the one candidate key we choose to identify rows. It can never be NULL.
• Alternate key: a candidate key that was not chosen as primary. Example: {email}.
• Composite key: a key made of more than one attribute. Example: (sid, cid) in Enroll.
• Foreign key: an attribute in one table that points to the primary key of another table. Example: Enroll.sid → Student.sid.

• Domain constraint: every value must come from the attribute's domain. Example: age cannot be 'abc'.
• Key constraint: no two tuples can have the same value of a candidate key.
• Entity integrity: primary key can never be NULL. Reason: we could not identify the row.
• Referential integrity: a foreign key value must exist in the referenced table (or be NULL). Example: you cannot insert Enroll with sid = 999 if no Student has sid 999.

SQL (Structured Query Language) is the language we use to create tables and work with data. Through this whole chapter we use one sample schema:

Our sample data (used in every example below):

SQL commands fall into four families. The exam often gives you a list of commands and asks which family each one belongs to.

CREATE TABLE makes a new table with column types and keys:

INSERT adds a row, UPDATE changes rows, DELETE removes rows:

A written question often says: "Create the tables with proper constraints." There are five constraint types you must know:

• PRIMARY KEY: unique + not null. Identifies each row.
• FOREIGN KEY: value must exist in the referenced table. ON DELETE CASCADE means: if the parent row is deleted, the child rows are deleted too.
• NOT NULL: the column can never be empty.
• UNIQUE: no two rows can have the same value (but NULL may be allowed).
• CHECK: every value must pass a condition, like salary > 0.

What each line protects: you cannot insert two employees with the same emp_id (PRIMARY KEY), or a nameless employee (NOT NULL), or two employees with the same email (UNIQUE), or a salary of 0 or less (CHECK), or an employee in a department that does not exist (FOREIGN KEY). And if a department is deleted, all its employees go with it (ON DELETE CASCADE).

Sometimes one UPDATE must apply DIFFERENT changes to different rows. CASE ... WHEN ... THEN ... ELSE ... END does this: for each row, it picks the first matching WHEN branch.

Problem (exam style): table Product(pid, pname, cost). Increase cost by 20% if cost is below 100, by 10% if cost is 100 to 500, and by 5% otherwise — in ONE statement.

Get CSE students, sorted by name, only first 2 rows:

Order of writing: SELECT → FROM → WHERE → GROUP BY → HAVING → ORDER BY → LIMIT. WHERE can use AND, OR, NOT, BETWEEN, IN, LIKE (pattern: 'R%' = starts with R), and comparisons like credit >= 3 or credit < 4.

Aggregates work on a group of rows: COUNT, SUM, AVG, MAX, MIN. GROUP BY makes the groups. HAVING filters the groups after grouping.

Count students in each department, but keep only departments with more than 1 student:

A join combines rows from two tables using a matching condition. We will join Student and Enroll on sid. Note: Nadia (104) has no enrollment, and there is no enroll row without a student.

• INNER JOIN: only matching rows from both sides.
• LEFT JOIN: all rows of the left table; NULLs where the right side has no match.
• RIGHT JOIN: all rows of the right table; NULLs on the left side.
• FULL JOIN: all rows of both; NULLs where there is no match.

RIGHT JOIN here gives the same rows as INNER JOIN, because every Enroll row already has a matching student. FULL JOIN here gives the same as LEFT JOIN. In general: FULL = LEFT ∪ RIGHT.

A subquery is a query inside another query. Three common patterns:

1) IN — set membership. Names of students enrolled in the Database course:

2) Scalar subquery — one value. Courses with credit higher than the average credit:

3) EXISTS — correlated subquery. The inner query uses a value from the outer row. Students who enrolled in at least one course:

A trigger is a stored program attached to a table that the database runs automatically when a certain event happens — an INSERT, UPDATE, or DELETE. You never call a trigger yourself; it fires by itself. A trigger has three parts:

• Event: what fires it — INSERT, UPDATE, or DELETE on a table.
• Timing: BEFORE the change (good for checking/fixing values) or AFTER the change (good for logging and updating other tables).
• Action: the SQL that runs, often with an optional WHEN condition.

Row level vs statement level: a row-level trigger (FOR EACH ROW) runs once for EVERY row the statement changes — if one UPDATE touches 50 rows, it fires 50 times. A statement-level trigger runs once per statement, no matter how many rows changed. Inside a row-level trigger, OLD holds the row's values before the change and NEW holds them after.

When to use a trigger: audit logs (who changed what), keeping a computed/summary table in sync, enforcing rules a normal constraint cannot express (like "salary can never decrease"). When to avoid: heavy business logic — triggers are hidden, so code becomes hard to debug; a trigger firing another trigger can cause chains (even infinite loops); and row-level triggers on bulk updates can be slow.

Relational algebra is the math behind SQL. Each operator takes one or two relations and gives a new relation. Same schema as before: Student, Course, Enroll.

Normalization means breaking a badly designed table into smaller, cleaner tables. The goal is to remove redundancy (same data stored many times) and anomalies:

• Update anomaly: change one fact, must update many rows.
• Insert anomaly: cannot add a fact without another unrelated fact.
• Delete anomaly: deleting a row silently deletes a different fact too.

A functional dependency \( X \to Y \) means: if two rows agree on X, they must also agree on Y. In words, "X determines Y".

Example: sid → name (one sid always has one name). sid, cid → grade (one student in one course has one grade).

• Reflexivity: if \( Y \subseteq X \), then \( X \to Y \). (AB → A is always true.)
• Augmentation: if \( X \to Y \), then \( XZ \to YZ \). (Add the same thing to both sides.)
• Transitivity: if \( X \to Y \) and \( Y \to Z \), then \( X \to Z \).

Derived rules: Union (X→Y and X→Z give X→YZ), Decomposition (X→YZ gives X→Y and X→Z), Pseudo-transitivity.

The closure of X, written \( X^+ \), is the set of ALL attributes X can determine. To find it: start with X, and keep adding the right side of any FD whose left side is already inside.

Rule: every cell holds ONE atomic value. No lists, no repeating groups.

Violation:

Fix: one phone per row — or better, a separate table StudentPhone(sid, phone).

Rule: 1NF + no non-prime attribute depends on a part of a composite key. (A "non-prime" attribute is one that is not in any candidate key.)

Violation: Enroll2(sid, cid, grade, sname), key = (sid, cid). Here sid → sname: sname depends on only PART of the key.

"Rahim" is stored twice — redundancy. Fix: split into Student(sid, sname) and Enroll(sid, cid, grade).

Rule: 2NF + no non-prime attribute depends on another non-prime attribute (non-key → non-key is banned).

Violation: Student2(sid, dept, dept_head), key = sid. FDs: sid → dept, dept → dept_head. So sid → dept_head is transitive.

"Dr. Alam" repeats. If CSE gets a new head, we must update many rows (update anomaly). Fix: Student(sid, dept) + Dept(dept, dept_head).

Rule: for EVERY non-trivial FD \( X \to Y \), X must be a superkey. Stricter than 3NF.

Violation: Teach(sid, course, teacher). Rules: each teacher teaches only one course; a course can have many teachers; a student takes a course with one teacher. FDs: teacher → course and (sid, course) → teacher. Candidate keys: (sid, course) and (sid, teacher). The FD teacher → course breaks BCNF because teacher is not a superkey. But it does NOT break 3NF, because course is a prime attribute (part of a key).

Fix (BCNF decomposition): split on the bad FD: TeacherCourse(teacher, course) and StudentTeacher(sid, teacher).

A transaction is a group of operations that must run as one unit. Classic example: transfer 500 taka from account A to account B — subtract from A, add to B. Both must happen, or neither.

• Atomicity: all or nothing. If the system crashes after subtracting from A but before adding to B, the subtraction is rolled back.
• Consistency: the database moves from one valid state to another. Total money before = total money after.
• Isolation: running transactions do not see each other's half-done work. Two people booking the last seat cannot both get it.
• Durability: once committed, the change survives crashes and power loss (written to permanent storage / log).

A schedule is the order in which operations of several transactions run, mixed together. A serial schedule runs one full transaction, then the next — always safe, but slow. A schedule is serializable if its final effect equals SOME serial schedule. That is the safety goal: run in parallel, but behave like serial.

Two operations conflict if: they are from different transactions, touch the same data item, and at least one is a WRITE. So conflicts are read–write, write–read, write–write. Read–read never conflicts.

Precedence graph test: make a node for each transaction. If an operation of \( T_i \) conflicts with a LATER operation of \( T_j \), draw edge \( T_i \to T_j \). The schedule is conflict serializable if and only if the graph has no cycle. A topological order of the graph gives the equivalent serial order.

Locks control access to data items. A shared lock (S) lets many transactions read. An exclusive lock (X) lets one transaction write — nobody else can read or write it.

Two-Phase Locking (2PL): each transaction has a growing phase (only takes locks) and then a shrinking phase (only releases locks). Once it releases any lock, it can never take a new one. 2PL guarantees conflict serializability. Strict 2PL holds all exclusive locks until commit — this also avoids cascading rollback.

The lost update is the classic problem that locking exists to solve. Two transactions read the same value, both compute a new value from it, and both write. The second write silently overwrites the first — so one update is lost, as if it never happened.

How strict 2PL prevents it: T1 takes an exclusive (X) lock on A before reading and updating it, and holds it until commit. When T2 asks for its own X lock on A at step 2, the request blocks — T2 must wait. Only after T1 commits (balance = 150) does T2 get the lock, read the fresh value 150, and write 150 − 30 = 120. Correct answer, no lost update. The schedule becomes equivalent to running T1 then T2 one after another (serializable).

Deadlock: T1 holds a lock on X and waits for Y; T2 holds Y and waits for X. Both wait forever. Detection: build a wait-for graph; a cycle = deadlock. The system then aborts one transaction (the victim). Prevention schemes: wait-die (older waits, younger dies) and wound-wait (older wounds younger, younger waits), or simply lock items in a fixed global order.

Quick meanings: dirty read = reading uncommitted data of another transaction; non-repeatable read = same row gives a different value when read twice; phantom = re-running a query finds new rows that appeared in between.

Without an index, finding a row means scanning the whole table — like reading a whole book to find one word. An index is like the book's index page: a sorted structure of (search key, pointer to row). It makes lookup fast, but takes extra space and slows down inserts/updates a little (the index must be updated too).

• Dense index: one index entry for EVERY search-key value in the file. Faster lookup, more space.
• Sparse index: index entries for only SOME values (usually one per block/page). To find a key, go to the largest index entry ≤ key, then scan that block. Needs the data file to be sorted on the key. Less space, slightly slower.

• Primary (clustering) index: built on the key the data file is SORTED by. At most one per table. Can be sparse.
• Secondary index: built on any other attribute; the file is not sorted by it. Must be dense (every value needs its own pointer). A table can have many secondary indexes.

A B-tree is a balanced search tree where each node holds many keys (high fan-out) and all leaves are at the same depth. Data pointers can sit at every node. A node of order \( n \) has at most \( n \) children and at least \( \lceil n/2 \rceil \) (root excepted); this keeps the tree balanced and the height around \( O(\log n) \) with a very large base.

A B+ tree is the database version of a B-tree:

• All records/data pointers live ONLY in the leaf nodes. Internal nodes hold only keys for routing.
• Leaves are linked left-to-right like a linked list.
• Every search goes root → leaf, so every lookup costs the same (height of tree, usually 3–4 disk reads even for millions of rows).

Why databases prefer B+ tree: (1) internal nodes hold only keys, so more keys fit per disk block → bigger fan-out → shorter tree → fewer disk reads; (2) the linked leaves make range queries (WHERE sid BETWEEN 100 AND 200) a simple walk along the leaf chain; (3) uniform search cost.

Problem: build a B+ tree of order \( n = 5 \) by inserting 12, 14, 19, 30, 21, 22, 13, 34, 18, 23, 38, 40 in this order. Order 5 means: a node has at most 5 pointers, so at most 4 keys.

Split rules (memorize): when a 5th key would enter a leaf, split it — the first \( \lceil 5/2 \rceil = 3 \) keys stay in the left leaf, the last 2 go to a new right leaf, and the FIRST key of the right leaf is copied up into the parent (copied, because in a B+ tree every key must also stay at the leaf level). If an internal node overflows, its middle key moves up instead (not needed in this problem).

A hash index applies a hash function to the key: \( h(key) \) gives the bucket where the record sits. Equality search (WHERE sid = 101) is O(1) on average — even faster than a B+ tree. But hashing keeps NO order, so it is useless for range queries (BETWEEN, <, >) and sorting. Static hashing fixes the bucket count (overflow chains grow); extendible/dynamic hashing grows the directory as data grows.

Indexes make search fast, but the data itself lives on disks — and disks fail. RAID (Redundant Array of Independent Disks) combines several disks into one logical unit to get more speed, more safety (redundancy), or both. Each "level" is a different trade-off between performance, capacity, and how many disk failures you can survive.

Two building ideas: striping = split data into blocks and spread them across disks (many disks work in parallel → fast). Mirroring = keep a full copy of the data on another disk (a disk dies → the copy survives). Parity = store an extra XOR block; if one disk dies, its data can be rebuilt from the others plus the parity.

• RAID 0 (striping): blocks A1, A2, A3, A4 go round-robin across disks. Reads and writes are fast (parallel), and you use 100% of the space. But there is no redundancy: if any one disk fails, the whole array's data is gone. Use only for speed, never for important data.
• RAID 1 (mirroring): every block is written to two disks. Full redundancy — one disk of a pair can die and nothing is lost. Reads can be served by either disk (fast reads), but you only get 50% usable capacity.
• RAID 5 (striping + distributed parity): data is striped, and for each stripe one parity block (XOR of the data blocks) is stored — rotated across all disks so no single disk is the "parity disk". Needs at least 3 disks. Survives exactly 1 disk failure: the missing block is rebuilt as XOR of the surviving blocks. Usable capacity = (n−1)/n. Writes are a bit slower (parity must be updated).
• RAID 6: like RAID 5 but with two independent parity blocks per stripe — survives any 2 disk failures; capacity (n−2)/n; needs ≥ 4 disks.
• RAID 10 (1+0): make mirror pairs first, then stripe across the pairs — the speed of RAID 0 with the safety of RAID 1, at 50% capacity; needs ≥ 4 disks.