GATE CS & IT Engineering Databases Flashcards

24 sample cards from the Databases deck

Sampled from the end of the deck, so these are different cards from the ones shown on the syllabus page.

1. State Armstrong's three axioms for functional dependencies.

   Reflexivity: if $Y \subseteq X$ then $X \to Y$. Augmentation: if $X \to Y$ then $XZ \to YZ$. Transitivity: if $X \to Y$ and $Y \to Z$ then $X \to Z$.

2. What condition must a relation satisfy to be in First Normal Form (1NF)?

   Every attribute must contain only atomic (indivisible) single values; no multi-valued attributes, composite attributes, or nested/repeating groups are allowed.

3. What is the requirement for Second Normal Form (2NF)?

   The relation must be in 1NF and have no partial dependency, i.e., no non-prime attribute may depend on a proper subset of any candidate key. Every non-prime attribute must be fully functionally dependent on the whole candidate key.

4. What is the requirement for Third Normal Form (3NF)?

   The relation must be in 2NF and have no transitive dependency of non-prime attributes on candidate keys. For every FD $X \to Y$, either $X$ is a super key or $Y$ is a prime attribute.

5. How does BCNF differ from 3NF?

   BCNF is stricter: for every non-trivial FD $X \to Y$, $X$ must be a super key (no prime-attribute exception). Every BCNF relation is in 3NF, but not vice versa. 3NF is always dependency-preserving and lossless; BCNF may not be dependency-preserving.

6. What is a partial functional dependency? Give an example.

   A partial dependency occurs when a non-prime attribute depends on only part of a composite candidate key. Example: in $R(StudentID, CourseID, StudentName)$ with key $\{StudentID, CourseID\}$, $StudentID \to StudentName$ is partial. It violates 2NF.

7. What is a transitive functional dependency? Give an example.

   A transitive dependency exists when $X \to Y$ and $Y \to Z$ with $Y$ not a candidate key, so $X \to Z$ indirectly. Example: $RollNo \to DeptID$ and $DeptID \to DeptName$ gives $RollNo \to DeptName$. It violates 3NF.

8. What two properties should a good relational decomposition satisfy?

   1) Lossless-join (non-additive): the natural join of decomposed relations reconstructs exactly the original relation. 2) Dependency preservation: the union of FDs on the sub-relations implies all original FDs.

9. Compare heap (unordered) and sequential (ordered) file organization.

   Heap file: records placed in insertion order; insertion is fast (O(1) append) but searching is linear O(n). Sequential file: records stored sorted on a key; supports binary search O(log n) and efficient range queries, but insertion/deletion is costly due to reordering.

10. What is hashing (hash) file organization and its main drawback?

    Records are placed in buckets determined by a hash function on the key, giving near O(1) equality-search access. Drawbacks: poor performance for range queries and the need to handle bucket overflow (via chaining or rehashing).

11. Differentiate a primary (clustered) index from a secondary (non-clustered) index.

    A clustered/primary index is built on the ordering key field, so the physical order of records matches the index; only one per table. A secondary index is on a non-ordering field, is dense, and does not match physical order; many are allowed.

12. What is the difference between a dense and a sparse index?

    A dense index has one index entry for every search-key value (every record). A sparse index has entries for only some keys (typically one per data block); sparse indexes require ordered files.

13. What is a B-tree of order $m$?

    A balanced multiway search tree where every node has at most $m$ children and at least $\lceil m/2 \rceil$ children (root at least 2). Keys and their data pointers are stored in both internal and leaf nodes, and all leaves are at the same level.

14. In a B-tree of order $m$, how many keys can a node hold and what is the minimum for a non-root node?

    A node holds at most $m-1$ keys and at least $\lceil m/2 \rceil - 1$ keys (the root may have as few as 1 key).

15. What are the key structural differences between a B-tree and a B+ tree?

    In a B+ tree, all actual data record pointers are stored only in leaf nodes; internal nodes hold only keys for routing (keys may be duplicated). Leaves are linked in a sorted linked list. In a B-tree, data pointers exist in all nodes and there is no leaf linkage.

16. Why are B+ trees preferred over B-trees for database indexing?

    Internal nodes store only keys (no data), so they have a higher fan-out and shorter height, fewer disk I/Os. The linked leaf list makes sequential and range queries efficient, and every search traverses to a leaf giving uniform access cost.

17. In a B+ tree of order $p$ for internal nodes, how many tree pointers and keys does an internal node hold?

    An internal node holds at most $p$ tree pointers and $p-1$ keys, with a minimum of $\lceil p/2 \rceil$ tree pointers (so $\lceil p/2 \rceil - 1$ keys); the root needs at least 2 pointers.

18. Define a database transaction and name its four ACID properties.

    A transaction is a logical unit of work containing one or more operations executed as a single indivisible action. ACID: Atomicity (all or nothing), Consistency (preserves integrity constraints), Isolation (concurrent transactions don't interfere), Durability (committed changes persist).

19. Draw out the states in a transaction's state diagram.

    Active -> Partially Committed (after final operation) -> Committed (changes made permanent), or Active/Partially Committed -> Failed -> Aborted (rolled back). From Aborted it may restart or be killed.

20. When is a schedule conflict-serializable, and how is it tested?

    A schedule is conflict-serializable if it can be transformed into a serial schedule by swapping non-conflicting (non-conflicting = different transactions, not both on same data item with at least one write) adjacent operations. It is tested by checking that the precedence (serialization) graph is acyclic.

21. List the three types of problems that arise from uncontrolled concurrent execution.

    1) Lost update (write-write); 2) Dirty read / temporary update (reading uncommitted data, read of a write later rolled back); 3) Unrepeatable read and the incorrect summary / phantom problem.

22. What is Two-Phase Locking (2PL) and what does it guarantee?

    2PL is a protocol where every transaction acquires all locks in a growing phase and releases locks only in a shrinking phase (no lock acquired after the first release). It guarantees conflict-serializability. Strict 2PL holds all exclusive locks until commit/abort, also ensuring recoverability and cascade-free schedules.

23. How does timestamp-ordering concurrency control decide whether to allow an operation?

    Each transaction gets a unique timestamp $TS(T)$; each data item keeps read and write timestamps. An operation that would violate timestamp order (e.g., a write whose effect is already overwritten or read by a younger transaction) is rejected and the transaction is rolled back, ensuring serializability by timestamp order.

24. Differentiate recoverable, cascadeless, and strict schedules.

    Recoverable: a transaction commits only after all transactions whose data it read have committed. Cascadeless (avoids cascading rollback): transactions read only committed data. Strict: no transaction reads or writes a data item until the transaction that last wrote it commits/aborts. Relationship: Strict $\subseteq$ Cascadeless $\subseteq$ Recoverable.

What this deck covers

Databases flashcards FAQ