Centralized, Primary Copy & Distributed Deadlock Handling

Lecture 33 examines the deadlock problem inherent in locking-based concurrency control in distributed database management systems. A deadlock occurs when two or more transactions are in a simultaneous circular wait, each holding a lock requested by another. The lecture explores the three primary deadlock handling strategies: deadlock prevention, deadlock avoidance, and deadlock detection. Students study timestamp-based prevention schemes, contrasting Wait-Die (non-preemptive: older transactions wait, younger die) with Wound-Wait (preemptive: older wound younger, younger wait). The curriculum analyzes distributed deadlock detection using global Wait-For Graphs (WFG) and investigates Mitchell-Merritt and Chandy-Misra-Haas edge-chasing probe algorithms, tracing how distributed deadlock cycles are detected and resolved by selecting and aborting optimal victim transactions. 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. Parallel data placement techniques, including round-robin, hash partitioning, and range partitioning, illustrate workload balancing across processing nodes. Parallel join algorithms evaluate parallel nested-loop, associative, and parallel hash join executions in high-throughput query environments. Distributed Object-Oriented Database Management Systems (OODBMS) explore object identity, encapsulation, complex object hierarchies, and pointer swizzling. Client-server and page-server architectures in distributed OODBMS are analyzed for cache coherence, client caching, and transaction synchronization. Multidatabase and federated database systems illustrate how schema integration and mediation resolve semantic heterogeneity across legacy data stores. Exam preparation summaries and solved handout excerpts reinforce retention of critical mathematical proofs, fragmentation formulas, and execution algorithms.