Data, Databases and Algorithms
What the domain tests
Data, Databases and Algorithms covers relational modelling, keys and integrity, normalisation, SQL, transaction properties, and algorithm efficiency. Expect ER-to-relational mapping, normal-form reasoning, SQL queries with joins/grouping, and Big-O/searching/sorting comparisons.
Core rules
- A relation has a primary key; foreign keys enforce referential integrity. NULL means unknown, so comparisons with NULL use IS NULL, not = NULL.
- 1NF: atomic values; 2NF: no partial dependency on part of a composite key; 3NF: no transitive dependency on non-key attributes.
- SQL logical order: FROM/JOIN, WHERE, GROUP BY, HAVING, SELECT, ORDER BY. WHERE filters rows before grouping; HAVING filters groups.
- ACID: atomicity, consistency, isolation, durability.
- Big-O describes growth: binary search O(log n) on sorted data; merge sort O(n log n); linear search O(n); hash lookup average O(1).
Worked example
Table Employee(id, dept, salary). Query departments with at least three employees earning over 20,000: SELECT dept, COUNT() AS n FROM Employee WHERE salary > 20000 GROUP BY dept HAVING COUNT() >= 3; Reasoning: WHERE removes low salaries before grouping; GROUP BY forms one group per department; COUNT() counts rows per group; HAVING keeps groups with three or more. If HAVING were replaced by WHERE COUNT()>=3, the query would fail because WHERE cannot filter aggregates.
Traps
COUNT(*) counts rows including NULLs; COUNT(column) ignores NULLs. Do not put aggregate conditions in WHERE. Do not call a table 3NF if a non-key attribute determines another non-key attribute. Binary search requires sorted data. O(n log n) is not worse than O(n²) for large n. A foreign key may be NULL unless declared NOT NULL.