P-II.IV. Database Systems

---

Topics by Area

🏛️ Foundations

🔍 Querying (Relational Data Model's language side)

🔗 Conceptual Design

📝 Programmability

⚙️ Storage, Processing & Transactions

🌐 Advanced & Interoperability

🔐 Security

---

High-Yield (past paper repeats, 2016–2025)

• 2016: SQL subqueries/pattern-match/DML vs DDL, ACID properties, trigger forms, transitive/full/partial dependency
• 2017: Normalization (1NF/2NF/3NF), centralized vs distributed database
• 2018: Super/candidate/foreign key, relational algebra set-operation sizing, physical vs logical data independence
• 2019: ER Model design (worked example), database security scheme (applied), top-down vs bottom-up distributed DB design
• 2020: SQL joins (inner/left/right/full), ER diagram construction, Two-Phase Locking (2PL)
• 2021: Relational algebra expression writing, gerund/associative entity concept
• 2023: SQL search conditions (compound/range/set), ACID, transitive dependency
• 2024: Evolution of database systems, SQL + query optimization pitfalls, distributed database advantages/challenges
• 2025: SQL subqueries + role of indexes, BCNF/normalization MCQs, transaction rollback-on-failure MCQ
• Perennial (near every year): SQL joins & subqueries, Normalization, ACID/2PL, ER Model, keys & constraints
• Lowest frequency (still syllabus-named — keep as short-note/MCQ prep, not a full-answer focus): XML Documents & Web Services, PL/SQL stored procedures (as distinct from triggers), Object-Oriented Databases

---

Self-Test Questions (model answers in the toggles at the bottom)

1. List the ACID properties of a transaction and briefly define each.
2. Distinguish 2NF and 3NF by the type of dependency each eliminates; where does BCNF go further than 3NF?
3. What is the difference between relational algebra and relational calculus?
4. Explain the purpose of a database trigger with one example scenario, and name its two independent "forms" (timing × granularity).
5. Distinguish a primary key, candidate key, and foreign key — and a super key from a candidate key.
6. Given |R|=M and |S|=N tuples (M>N>0), what are the min/max sizes of R∪S, R∩S, R−S, and R×S?
7. Why is a B+-Tree preferred over a B-Tree for a database index?
8. What is a gerund/associative entity, and when should a relationship be converted into one?
9. Differentiate DAC, MAC, and RBAC.
10. Differentiate horizontal and vertical fragmentation in a distributed database.

🧭 How to Use This Section

🎯

Every subpage now ends with three study blocks: 📘 Enrichment (worked examples/numericals with outputs), ✍️ Model Answers (toggle questions — attempt first, then open), and ⚡ 60-Second Revision (last-week recap). Suggested order: read notes → solve worked examples on paper → write one model answer under timed conditions → revise.

🗺️ Topic Map

mindmap
  root((Database Systems))
    Foundations
      DBMS vs files
      ANSI-SPARC 3 levels
      Data independence
      Evolution to NoSQL/NewSQL/vector
    Relational model
      Keys
      Integrity constraints
      Codd rules
    Query languages
      SQL joins subqueries
      Relational algebra
      TRC and DRC
    Design
      ER model and mapping
      FDs and normalization
    Programmability
      PL/SQL procedures
      Triggers and cursors
    Internals
      Indexing B+ tree hashing
      Query optimization
      Transactions ACID 2PL recovery
    Advanced
      OODB and ORDBMS
      Distributed DB 2PC CAP
      XML and web services
      Security DAC MAC RBAC

📅 Priority Study Plan (by past-paper yield)

📝 Answer-Writing Template for CSS Computer Science (Database questions)

1. Definition (1–2 lines, textbook-precise) — name the originator where relevant (Codd 1970, Chen 1976 for ER).
2. Explanation in points or a comparison table — examiners scan for headings.
3. Worked example / numerical / code — SQL with the output table, algebra expression, or ER diagram. This is where marks separate.
4. Diagram — ANSI-SPARC levels, ER diagram, B+-tree, precedence graph, 2PC flow; label everything.
5. Real-world link — banking (ACID), NADRA (large central DB), Raast (high-volume OLTP), e-commerce (NoSQL scale).
6. Conclusion — one balanced line on trade-offs (e.g., normalization vs performance, consistency vs availability).

• Marks guide: 5–6-mark part → definition + 4–5 points + small example (~1 page). 10–12-mark part → all six steps (~2–2.5 pages). 20-mark question → split into its parts and give each the template.

Quick Reference — Syllabus Line → Page Map

Textbook Cross-Check — Extra Topics Beyond the Bare Syllabus Lines

The standard CSS textbook chapter lists a few headings the FPSC syllabus folds into other lines. All are now covered — this table says where.

✅ Self-Test Model Answers (attempt first, then open)

1. ACID properties

Atomicity — all or nothing (undo on failure). Consistency — valid state → valid state (constraints hold). Isolation — concurrent transactions do not see each other's uncommitted work. Durability — committed changes survive crashes (log/WAL). Example: Rs 5,000 transfer between two accounts. Full answer: Query Processing & Transaction page, Model Answer Q1.

2. 2NF vs 3NF vs BCNF

2NF removes partial dependency (non-key attribute on part of a composite key); 3NF removes transitive dependency (non-key → non-key). BCNF goes further: every determinant must be a candidate key — catches cases 3NF allows when a non-key determinant points to a prime attribute (Teacher → Subject). BCNF may lose dependency preservation; 3NF never does.

3. Relational algebra vs calculus

Algebra is procedural (sequence of operations: σ, π, ⋈ …); calculus (TRC/DRC) is declarative (describes the result with predicate logic). Equal expressive power for safe expressions (Codd's theorem). Algebra: π Name(σ City='Lahore'(Student)); TRC: the set of t.Name where t ∈ Student and t.City = 'Lahore'.

4. Purpose of a trigger and its two "forms"

A trigger auto-executes on an event (INSERT/UPDATE/DELETE) to enforce rules, audit or maintain derived data. Forms = timing (BEFORE / AFTER / INSTEAD OF) × granularity (row-level FOR EACH ROW / statement-level). Example: AFTER DELETE row-level trigger copying :OLD values into an audit table.

5. Primary, candidate, foreign, super key

Super key — any set that uniquely identifies tuples; candidate key — minimal super key; primary key — chosen candidate key, NOT NULL; foreign key — references another relation's PK, may be NULL. Student(RollNo, CNIC, Name, DeptID): {RollNo, Name} super; RollNo and CNIC candidates; RollNo primary; DeptID foreign.

6. Sizes of R∪S, R∩S, R−S, R×S (M greater than N greater than 0)

∪: M to M+N · ∩: 0 to N · −: M−N to M · ×: exactly M×N. Minimums/maximums occur when S ⊆ R or when R and S are disjoint — state the condition for each.

7. Why a B+-tree over a B-tree

Data pointers only at leaves → internal nodes hold more keys (higher fan-out, shallower tree, fewer disk accesses); leaves linked → efficient range queries and ordered scans; every lookup ends at the same depth → predictable cost.

8. Gerund / associative entity

A relationship treated as an entity (diamond inside rectangle). Convert when the relationship has its own attributes (Loan: IssueDate, ReturnDate; Registration: Grade) or must participate in another relationship. Maps to a junction table keyed by the participants' keys; not always necessary to eliminate.

9. DAC vs MAC vs RBAC

DAC — owner grants at discretion (GRANT … WITH GRANT OPTION); flexible, weaker. MAC — system-enforced labels, Bell–LaPadula (no read up, no write down); strict, military. RBAC — privileges attached to roles, users assigned roles; scalable, supports least privilege — most common in banks and enterprises.

10. Horizontal vs vertical fragmentation

Horizontal — split by rows using σ (Lahore customers at Lahore site), rebuilt with ∪. Vertical — split by columns using π, primary key kept in each fragment, rebuilt with ⋈. Both must satisfy completeness, reconstruction and disjointness.

---

🚫 Common Mistakes That Cost Marks

• Writing only definitions with no example, output table or diagram.
• Using WHERE COUNT(*) > 1 instead of HAVING; comparing with = NULL.
• Hunting for 2NF violations in a table whose key is a single attribute — partial dependency is only possible with a composite key; such a table is in 2NF as soon as it is in 1NF.
• Forgetting the owner's key in a weak entity's table, or creating a separate table for a 1:N relationship.
• Saying 2PL prevents deadlock (it does not) or that plain 2PL prevents cascading rollback (only strict 2PL does).
• Mixing up sparse/dense and claiming a table can have several clustering indexes.
• Stating "MAC = owner decides" (that is DAC).

🎯 Rapid MCQ Drill (answers in brackets)

1. Which level of ANSI-SPARC describes how data is physically stored? (Internal)
2. A relation with a single-attribute primary key that is in 1NF is automatically in … (2NF)
3. Which operator answers "students enrolled in all courses"? (Division ÷)
4. Which join returns unmatched rows from both tables? (FULL OUTER JOIN)
5. COUNT(column) ignores … (NULL values)
6. Which property of ACID is ensured by the recovery manager together with Atomicity? (Durability)
7. A cycle in the precedence graph means the schedule is … (not conflict-serializable)
8. In Wound-Wait, an older transaction requesting a lock held by a younger one … (wounds/aborts the younger)
9. How many clustering indexes can one table have? (One)
10. Every valid XML document is also … (well-formed)
11. "No write down" is a property of which model? (Bell–LaPadula / MAC)
12. On restart, a transaction with a start record but no commit record is … (undone / rolled back)
13. Which normal form deals with multivalued dependencies? (4NF)
14. The pseudo-record unavailable in a DELETE trigger is … (:NEW)
15. Which theorem says a distributed system cannot guarantee C, A and P together? (CAP / Brewer's theorem)