Computer & Digital Awareness Module

Databases, SQL & Data Structures

Database management systems (DBMS) and data structures provide the theoretical and practical foundations for organizing, storing, and manipulating digital information. Relational Database Management Systems (RDBMS) implement Edgar F. Codd's relational model, organizing data into structured tables governed by primary keys, foreign keys, and ACID (Atomicity, Consistency, Isolation, Durability) transaction properties. Structured Query Language (SQL) facilitates data operations through Data Definition Language (DDL) and Data Manipulation Language (DML) commands. Concurrently, data structures are categorized into linear types (arrays, stacks, queues, linked lists) and non-linear hierarchical types (binary trees, graphs, heaps) optimized for algorithmic efficiency.

Practice Topic MCQs All Category Topics

Key Concepts & Examination Highlights

Dr. E.F. Codd proposed the Relational Database Model in 1970 and formulated Codd's 12 Rules defining relational database management systems (RDBMS).
ACID properties in database transactions stand for Atomicity, Consistency, Isolation, and Durability, guaranteeing transactional reliability and integrity.
SQL commands are categorized into sub-languages: DDL (Data Definition Language: CREATE, ALTER, DROP), DML (Data Manipulation Language: INSERT, UPDATE, DELETE), and DQL (Data Query Language: SELECT).
Stacks follow the Last-In-First-Out (LIFO) principle, whereas Queues operate on the First-In-First-Out (FIFO) principle; binary search trees offer O(log n) average search complexity.
Normalization is a systematic database design technique (1NF, 2NF, 3NF, BCNF) used to eliminate data redundancy and prevent insertion, update, and deletion anomalies.
Binary Search Trees (BST) are hierarchical tree structures where each node's left child contains values strictly less than the node and the right child contains values strictly greater, enabling $O(\log N)$ search time.
Hash tables map key-value pairs using a deterministic hash function, providing average-case $O(1)$ constant time complexity for insert, lookup, and delete operations.
NoSQL databases (such as MongoDB, Cassandra, and Redis) are non-relational database systems designed to handle unstructured or semi-structured data across document, key-value, column-family, and graph models.
The CAP theorem asserts that a distributed data store can simultaneously provide at most two of three guarantees: Consistency, Availability, and Partition Tolerance.
Depth-First Search (DFS) uses a stack (or recursion) to explore graph branches deeply before backtracking, while Breadth-First Search (BFS) uses a queue to traverse graphs level by level.
Database indexing creates secondary search data structures (predominantly B-Trees and B+ Trees) on specified columns to accelerate query retrieval speeds without full table scans.
Primary keys uniquely identify each record in a database table and cannot contain NULL values, whereas candidate keys are all eligible minimal superkeys that could serve as primary keys.
Foreign keys establish referential integrity between two relational tables by enforcing that values in the child table match existing primary key values in the parent table.
First Normal Form (1NF) requires atomic, non-divisible column values and unique row identifiers; Second Normal Form (2NF) eliminates partial functional dependencies on candidate keys.
Third Normal Form (3NF) requires a relation to be in 2NF with no transitive dependencies of non-prime attributes on candidate keys, while Boyce-Codd Normal Form (BCNF) requires that for every functional dependency $X \rightarrow Y$ , $X$ must be a superkey.
In SQL, the GROUP BY clause aggregates rows sharing common values into summary rows, while the HAVING clause filters aggregated results based on specified group conditions.
SQL joins include INNER JOIN (matching rows only), LEFT JOIN (all left rows and matching right rows), RIGHT JOIN, and FULL OUTER JOIN (all rows from both tables).
Array data structures provide $O(1)$ constant time access by index but require contiguous memory allocation, making insertion and deletion operations $O(N)$ in the worst case.
Singly linked lists consist of nodes containing data and a pointer to the next node, allowing dynamic memory allocation and $O(1)$ insertions at known positions without shifting elements.
Doubly linked lists contain two pointers per node (pointing to next and previous nodes), allowing bidirectional traversal at the expense of extra pointer storage overhead.
A binary search on a sorted array of $N$ elements operates by repeatedly halving the search interval, achieving $O(\log N)$ time complexity.
QuickSort uses a divide-and-conquer strategy by selecting a pivot element and partitioning the array around the pivot, achieving an average time complexity of $O(N \log N)$ .
MergeSort is a stable, comparison-based divide-and-conquer sorting algorithm that guarantees $O(N \log N)$ worst-case time complexity by recursively splitting and merging subarrays.
An AVL tree is a self-balancing binary search tree where the height difference (balance factor) between left and right subtrees of any node is at most $\pm 1$ , ensuring $O(\log N)$ lookup time.
Graph data structures consist of vertices (nodes) and edges (connections), represented computationally using adjacency matrices for dense graphs or adjacency lists for sparse graphs.
In relational databases, an entity-relationship (ER) model visually represents entities, their attributes, and relationships (one-to-one, one-to-many, many-to-many) using Chen or Crow's Foot notation.
Database constraints enforce domain integrity (NOT NULL, CHECK), entity integrity (PRIMARY KEY), and referential integrity (FOREIGN KEY with ON DELETE CASCADE actions).
SQL subqueries are categorized into non-correlated subqueries (executed once independently) and correlated subqueries (evaluated once for each row processed by the parent query).
SQL window functions (such as ROW_NUMBER(), RANK(), DENSE_RANK(), and NTILE()) compute aggregate calculations over a defined subset of rows without collapsing table rows.
A database transaction is a logical unit of work that must execute entirely or not at all, adhering to Atomicity, Consistency, Isolation, and Durability (ACID).
Transaction isolation levels defined in ANSI SQL are Read Uncommitted, Read Committed, Repeatable Read, and Serializable, preventing dirty reads, non-repeatable reads, and phantom reads.
Two-Phase Locking (2PL) is a concurrency control protocol that guarantees serializability through an expanding growing phase (acquiring locks) and a shrinking phase (releasing locks).
A deadlock occurs in databases when two or more transactions hold locks on resources that the other transactions need, resolved using wait-for graphs and transaction abort timeouts.
Database sharding is a horizontal partitioning technique that separates large database tables across multiple independent database server instances based on a shard key.
Database replication involves copying data across multiple database servers in primary-replica (master-slave) or multi-master topologies to provide high availability and read scalability.
B-Trees and B+ Trees are self-balancing multi-way search trees where internal nodes store keys and child pointers, and in B+ Trees, all actual data records and leaf nodes are linked sequentially for fast range scans.
A circular queue wraps around from the end of the array to the front using modulo arithmetic ( $(\ ext{rear} + 1) \% N$ ), preventing wasted memory in standard linear queues.
A priority queue is an abstract data type where each element has an assigned priority, typically implemented using binary heaps with $O(\log N)$ insertion and extraction time.
A binary min-heap is a complete binary tree where the key at the root is the minimum among all keys in the heap, and the same property holds recursively for all subtrees.
A binary max-heap is a complete binary tree where the key at the root is the maximum among all keys in the tree, utilized in the HeapSort algorithm ( $O(N \log N)$ ).
Trie (prefix tree) is a tree-like search data structure used to store associative arrays of strings, enabling $O(L)$ search and autocomplete lookup time where $L$ is string length.
Red-Black trees are self-balancing binary search trees that enforce color properties (nodes are red or black) to guarantee that the tree height remains bounded by $2 \log_2(N + 1)$ .
Disjoint Set Union (DSU / Union-Find) maintains partitions of elements into disjoint sets, supporting near-constant $O(\alpha(N))$ operations using union-by-rank and path compression.
Dijkstra's algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights in $O((V + E) \log V)$ time using priority queues.
The Bellman-Ford algorithm computes single-source shortest paths in graphs containing negative edge weights and detects negative weight cycles in $O(VE)$ time.
Floyd-Warshall algorithm is a dynamic programming algorithm that computes shortest paths between all pairs of vertices in a directed weighted graph in $O(V^3)$ time.
Kruskal's algorithm and Prim's algorithm are greedy algorithms that find a Minimum Spanning Tree (MST) in connected, undirected, edge-weighted graphs in $O(E \log E)$ time.
Topological sorting of a Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge $u \rightarrow v$ , vertex $u$ comes before vertex $v$ , computed using Kahn's algorithm or DFS.
Dynamic programming solves complex optimization problems by breaking them into overlapping subproblems and storing intermediate solutions using Memoization (top-down) or Tabulation (bottom-up).
Amortized time complexity calculates the average time taken per operation over a worst-case sequence of operations, exemplified by the $O(1)$ amortized insertion time in dynamic arrays (vectors).

Curriculum & Reference Sources: ACM Transactions on Database Systems, IEEE Transactions on Knowledge and Data Engineering, and standard algorithms texts (Cormen et al., Silberschatz et al.).

Sample Solved Questions & Concept Explanations

8 Verified Concept Questions

Q1.HARD

In database management systems (DBMS), what does the acronym ACID stand for in the context of transaction processing guarantees?

Q2.EASY

In a relational database table, what is the mandatory requirement for a column designated as the Primary Key?

Q3.EASY

Which SQL statement is categorized under Data Definition Language (DDL) rather than Data Manipulation Language (DML)?

Q4.EASY

Which fundamental abstract data structure operates strictly on a Last-In, First-Out (LIFO) operational principle?

Q5.EASY

What is the worst-case time complexity of the Binary Search algorithm when searching for a target element in a sorted array of size n?

Q6.EASY

What is the maximum individual single file size supported by the legacy FAT32 file system format?

Q7.EASY

What constraint in a relational database ensures that a value in a child table column matches an existing Primary Key value in a referenced parent table?

Q8.MEDIUM

In SQL, what is the fundamental functional difference between the WHERE clause and the HAVING clause?