You can recite the definition of 3NF, GROUP BY, a queue and a heap and still lose the thread when one question moves from a flat table to a query and then to an in-memory operation. One seven-row student-result table holds that whole chain together: it normalises into six tables, feeds a single grouped SQL query, and its seven marks build a max heap whose first three extractions are 91, 88 and 84. Database Management System and Data Structures are separate Part 3 units in KnowledgeGate's BPSC TRE Exam Preparation track, so one dataset that crosses both earns its keep twice. The student names, IDs and marks below are teaching data, not figures from any real result sheet.
1. Start with one result system and three invariants
Begin with ResultRaw(student_id, student_name, dept_id, dept_name, offering_id, course_id, course_title, instructor_id, instructor_name, term, marks, status). O201 means C201, DBMS, I7, Rao, T1; O202 means C202, Data Structures, I8, Sen, T1. In that attribute order, the seven rows are:
(S101,Asha,D1,"Computer Science",O201,C201,DBMS,I7,Rao,T1,78,complete)
(S101,Asha,D1,"Computer Science",O202,C202,"Data Structures",I8,Sen,T1,84,complete)
(S102,Ravi,D1,"Computer Science",O201,C201,DBMS,I7,Rao,T1,91,complete)
(S102,Ravi,D1,"Computer Science",O202,C202,"Data Structures",I8,Sen,T1,73,complete)
(S103,Meera,D2,Mathematics,O201,C201,DBMS,I7,Rao,T1,88,complete)
(S104,Kabir,D2,Mathematics,O201,C201,DBMS,I7,Rao,T1,60,complete)
(S104,Kabir,D2,Mathematics,O202,C202,"Data Structures",I8,Sen,T1,75,complete)Three design invariants come first: each (student_id, offering_id) appears at most once; marks is an integer from 0 through 100; every result references an existing student and offering.
2. Find the key and dependencies before naming a normal form
Every attribute must be atomic. course_ids = 'C201,C202' hides two offerings. The candidate key is (student_id, offering_id).
The functional dependencies are:
student_id -> student_name, dept_iddept_id -> dept_nameoffering_id -> course_id, instructor_id, termcourse_id -> course_titleinstructor_id -> instructor_name(student_id, offering_id) -> marks, status
Student and offering facts depend on part of the composite key, so the relation fails 2NF. The paths student_id -> dept_id -> dept_name, offering_id -> course_id -> course_title and offering_id -> instructor_id -> instructor_name are transitive dependencies relevant to 3NF.
Renaming D1 to Computing needs four raw-row updates. Deleting S103's only result loses Meera's stored facts. O203 cannot exist before a result without an invented null-key row.
3. Decompose to 3NF and reconstruct one row exactly
Use Department(dept_id PK, dept_name), Student(student_id PK, student_name, dept_id FK), Course(course_id PK, course_title), Instructor(instructor_id PK, instructor_name), Offering(offering_id PK, course_id FK, instructor_id FK, term) and Result(student_id FK, offering_id FK, marks, status, PK(student_id, offering_id)). Each table owns its fact; the Result key blocks duplicate student-offering results.
Join Result(S101,O202,84,complete) to Student(S101,Asha,D1), Department(D1,Computer Science), Offering(O202,C202,I8,T1), Course(C202,Data Structures) and Instructor(I8,Sen). This reconstructs S101's twelve-value Data Structures row. Decomposition gives each fact one owner, not freedom from joins. A D1 rename changes one Department row, but a result screen needs joins. See DBMS Normalization Explained Simply (With the Questions That Test It) for a refresher.
4. Trace JOIN, WHERE, GROUP BY and HAVING
Use the seven rows with this query:
SELECT s.student_id,
s.student_name,
COUNT(*) AS course_count,
AVG(r.marks) AS avg_marks
FROM Student AS s
JOIN Result AS r
ON r.student_id = s.student_id
JOIN Offering AS o
ON o.offering_id = r.offering_id
WHERE o.term = 'T1'
AND r.status = 'complete'
GROUP BY s.student_id, s.student_name
HAVING COUNT(*) >= 2
AND AVG(r.marks) >= 80
ORDER BY AVG(r.marks) DESC, s.student_id;Joins produce seven matches; WHERE keeps all seven. Groups are S101: count 2, 78 + 84 = 162, average 162 / 2 = 81; S102: count 2, 91 + 73 = 164, average 82; S103: count 1, sum 88, average 88; S104: count 2, 60 + 75 = 135, average 67.5. HAVING retains (S102, Ravi, 2, 82), then (S101, Asha, 2, 81) after ordering.
WHERE AVG(r.marks) >= 80 is wrong because row filtering occurs before group averages exist. For more practice, use SQL Queries and Joins in DBMS: sublanguages, joins, and GROUP BY worked out.
5. Test changed conditions and common SQL traps
Remove COUNT(*) >= 2 and S103 enters because 88 >= 80. Put that condition back and raise the average threshold to 82: only S102 survives, because 82 qualifies while S101's 81 fails. At 83, nothing survives.
A CROSS JOIN, or comma join missing its student-key predicate, pairs four Student rows with seven Result rows: 4 x 7 = 28. Their aggregates remain wrong. ORDER BY r.marks DESC LIMIT 3 returns marks 91, 88, 84, not the top three student averages.
Work any variant in that order: mark the keys, predict the join cardinality, separate row predicates from group predicates, compute each group, then order what survives.
6. Choose a data structure from the required operation
The scan array is [78, 84, 91, 73, 88, 60, 75]. Zero-based position 4 returns 88. Finding 60 checks positions 0 through 5, six comparisons. Indexing is constant time under the array model; an unsuccessful linear search can inspect seven values.
Enqueue review items E1=S101/O201/78, E2=S102/O202/73, E3=S104/O201/60, E4=S104/O202/75. Two FIFO dequeues return E1 then E2, leaving front E3 and rear E4. Removing E4 first is not FIFO.
For LIFO undo, push U1=S104/O201, 60 -> 68, then U2=S102/O202, 73 -> 79. Pop U2 to restore 73, then U1 to restore 60.
Hash the numeric ID part with h(id) = id mod 3: S101 maps to 2, S102 to 0, S103 to 1 and S104 to 2. Chained bucket 2 is S101 -> S104; S104 needs two comparisons. Expected constant-time lookup needs a suitable hash and controlled load. A chain can approach linear time.
7. Build a max heap and extract the top three marks
Keep row identity in tuples: [(78,S101,O201), (84,S101,O202), (91,S102,O201), (73,S102,O202), (88,S103,O201), (60,S104,O201), (75,S104,O202)]. Compare marks first, then student and offering IDs for ties.
Start bottom-up from [78,84,91,73,88,60,75]. Index 2 satisfies 91 >= 60,75. At index 1, swap 84 with 88: [78,88,91,73,84,60,75]. At index 0, swap 78 with 91: [91,88,78,73,84,60,75]. Parents cover children: 91 covers 88,78; 88 covers 73,84; 78 covers 60,75. A heap is not sorted.
Extract 91, move 75 to root and repair: [75,88,78,73,84,60] -> [88,75,78,73,84,60] -> [88,84,78,73,75,60]. Extract 88 and repair to [84,75,78,73,60]; next is 84. The top tuples are (91,S102,O201), (88,S103,O201), (84,S101,O202).
Bottom-up construction is O(n); each extraction is O(log n), so draining all seven marks in order costs O(n log n), which is exactly heapsort.
8. Common distractors and the next 45 minutes
distractor | why it fails | repair |
|---|---|---|
A composite key means the table is already in 2NF | Ignores partial dependencies | Test attributes against the whole key |
Every 3NF table needs a single-column key | Confuses key shape with dependency rules | Analyse dependencies |
| Applies a group condition before groups exist | Use |
The highest average is S103 with 88 | Ignores the two-course condition | Apply both conditions |
A heap array is fully sorted | Mistakes partial for total order | Check parent-child order |
Hash lookup is always O(1) | Ignores collisions and worst-case chains | State assumptions |
The KnowledgeGate question bank carries over 700 BPSC practice questions across the exam's subjects, not Computer Science alone. For where these three topics sit against the rest of the Computer Science part, see BPSC Teaching Computer Science Syllabus: Topic Map and Boundaries.
Drill for 45 minutes: 12 for the six-table decomposition, 12 for four SQL groups and two final rows, 8 for queue and stack, 8 for heap construction and repair, and 5 to explain two distractors. Check: 12 + 12 + 8 + 8 + 5 = 45.
The short version: determine keys before normal forms, follow SQL's logical stages before reading output, and choose a data structure from its required operation. If you want that sequencing built out across the whole Computer Science part, the BPSC TRE 4.0 Preparation Course carries Database Management System and Data Structures as separate Part 3 lesson tracks.
