Background of Relational Database Management Systems

Lecture 3 provides a comprehensive review of classical Relational Database Management System (RDBMS) foundations essential for understanding distributed data processing. The curriculum revisits the relational data model, formal definitions of relations, tuples, attributes, domains, and candidate/primary/foreign key integrity constraints. Students examine procedural relational algebra operators—including unary operations (selection and projection), binary set operations (union, intersection, difference, and Cartesian product), and derived relational operations (theta joins, equijoins, natural joins, and semijoins). Non-procedural relational calculus is contrasted with algebraic expressions. The lecture emphasizes normalization theory, reviewing functional dependencies, First Normal Form (1NF), Second Normal Form (2NF), Third Normal Form (3NF), and Boyce-Codd Normal Form (BCNF) as foundational precursors to horizontal and vertical data fragmentation. Serializability theory and conflict equivalence criteria provide mathematical foundations for proving the correctness of interleaved transaction schedules. Locking-based concurrency control protocols, including Two-Phase Locking, Distributed 2PL, and primary copy 2PL, are scrutinized for lock contention trade-offs. Distributed deadlock detection and resolution algorithms examine wait-for graphs, probe messages, and priority-based prevention strategies. Timestamp-ordering concurrency control mechanisms illustrate how physical and logical timestamps enforce serial ordering without deadlock vulnerability. Multi-version and conservative timestamp ordering algorithms are analyzed for read-heavy workloads and long-duration distributed transactions. Distributed query processing lifecycles trace query decomposition, algebraic normalization, semantic analysis, and elimination of redundant operations. Data localization algorithms transform global algebraic operator trees into localized fragment queries using relational reduction rules. Heuristic query optimization techniques illustrate how selection and projection operations are pushed down close to local physical fragments. Cost-based query optimization models analyze CPU overhead, disk page access costs, and communication network transmission delays. Distributed join optimization strategies contrast broadcast joins, partitioned hash joins, and semi-join reducers like the SDD-1 algorithm. Distributed reliability architectures examine failure classifications, including transaction aborts, site crashes, and network partitioning anomalies. Atomic commitment protocols, notably Two-Phase Commit (2PC) and Three-Phase Commit (3PC), are demonstrated with formal state transition diagrams. Parallel database system architectures, spanning Shared-Memory, Shared-Disk, and Shared-Nothing topologies, are contrasted for speedup and scaleup performance.