Databases for GATE DA
The relational model organizes data into tables (relations) where each row is a tuple and each column is an attribute. The relational model was proposed by...
Relational Model, SQL, and Database Design Fundamentals
The relational model organizes data into tables (relations) where each row is a tuple and each column is an attribute. The relational model was proposed by E.F. Codd in 1970 and provides a mathematical foundation for database design and querying based on set theory and predicate logic. GATE DA tests relational algebra, SQL, normalization, and transaction management.
A relation schema defines the table structure: a relation name and a list of attributes with their domains. A relational instance is a specific table with tuples conforming to the schema. A primary key uniquely identifies each tuple; it must be minimal (no proper subset is also a key). A foreign key in one table references the primary key of another, enforcing referential integrity.
Relational algebra provides formal operations for querying relations. Selection (sigma) filters rows by a condition. Projection (pi) keeps specified columns. Union combines two relations with the same schema. Set difference (minus) returns tuples in one relation but not the other. Cartesian product combines every tuple from one relation with every tuple from another. Join combines Cartesian product with a selection condition. Natural join automatically joins on attributes with the same name.
SQL implements the relational model. SELECT-FROM-WHERE is the fundamental query structure. GROUP BY aggregates rows sharing the same values; HAVING filters groups. ORDER BY sorts results. DISTINCT eliminates duplicate rows. Aggregate functions: COUNT, SUM, AVG, MIN, MAX. Subqueries appear in FROM, WHERE, and SELECT clauses. Correlated subqueries reference the outer query and are evaluated for each outer row.
GATE question type: given a schema Student(SID, Name, DeptID) and Department(DeptID, DeptName), write a query to find the names of students in the Computer Science department. The query is: SELECT Name FROM Student WHERE DeptID = (SELECT DeptID FROM Department WHERE DeptName = 'Computer Science'). Alternatively, this can be expressed as a natural join or an equijoin.
Normalization, Functional Dependencies, and ER Modeling
Normalization is the process of organizing a relational schema to minimize redundancy and prevent update anomalies. It proceeds through a series of normal forms, each eliminating a specific type of dependency violation. Understanding functional dependencies is the key to normalization.
A functional dependency X -> Y (X determines Y) holds in a relation if for every pair of tuples that agree on X, they also agree on Y. Armstrong's axioms are a complete set of inference rules: reflexivity (if Y is a subset of X then X -> Y), augmentation (if X -> Y then XZ -> YZ), and transitivity (if X -> Y and Y -> Z then X -> Z). From these, closure X+ of an attribute set X is the set of all attributes determined by X, and it can be computed by iteratively expanding using given FDs.
First Normal Form (1NF): every attribute takes atomic (indivisible) values, no multi-valued attributes or repeating groups. Second Normal Form (2NF): in 1NF and no non-key attribute is partially dependent on any candidate key (applies when keys are composite). Third Normal Form (3NF): in 2NF and no non-key attribute is transitively dependent on any candidate key. Boyce-Codd Normal Form (BCNF): for every non-trivial FD X -> Y, X is a superkey. BCNF is stronger than 3NF.
Decomposing a relation to BCNF: find a violating FD X -> Y where X is not a superkey. Split the relation into two: one containing X union Y, and one containing all original attributes except Y. Repeat until all relations are in BCNF. A lossless decomposition guarantees no spurious tuples when the pieces are joined. A dependency-preserving decomposition keeps every original FD within some relation in the decomposition. BCNF decomposition is always lossless but not always dependency-preserving; 3NF decomposition preserves both.
Entity-Relationship (ER) modeling represents the conceptual design before converting to relational schema. Entities become tables, relationships become foreign keys or join tables, and attributes become columns. A many-to-many relationship requires a separate junction table with foreign keys to both entities.
Transactions, Indexing, and Query Optimization in GATE DA
Transactions are sequences of database operations that must execute atomically. The ACID properties ensure database correctness: Atomicity means all operations in a transaction complete or none do. Consistency means a transaction brings the database from one valid state to another. Isolation means concurrent transactions execute as if they were serial. Durability means committed transactions survive failures.
Concurrency control prevents anomalies when multiple transactions execute simultaneously. Lost update: two transactions both read a value, both modify it, and one overwrites the other's change. Dirty read: a transaction reads data written by an uncommitted transaction. Non-repeatable read: a transaction reads the same data twice and gets different results because another transaction modified it in between. Phantom read: a transaction re-executes a query and finds new rows because another transaction inserted them.
Two-phase locking (2PL) protocol: a transaction acquires all needed locks before releasing any (growing phase), then releases all locks (shrinking phase). 2PL guarantees serializability but can cause deadlocks. Strict 2PL additionally holds all exclusive (write) locks until commit, preventing dirty reads and simplifying recovery. Timestamp ordering assigns each transaction a unique timestamp and uses it to order conflicting accesses.
Indexing speeds up data retrieval. A B+ tree index supports equality queries and range queries efficiently. Leaf nodes contain actual data (for clustered indexes) or pointers to data (for secondary indexes). The height of a B+ tree with n records and order m is approximately log_m(n). A hash index supports equality queries in O(1) average time but cannot support range queries.
Query optimization rewrites SQL queries into equivalent relational algebra expressions and chooses an efficient execution plan. Cost estimation uses statistics about table sizes, attribute value distributions, and index availability. Key rules: push selection early to reduce intermediate result sizes, use indexes to avoid full table scans, and choose join order to minimize intermediate result sizes. GATE questions on query optimization typically ask you to estimate the output size of a join or identify which index type suits which query.