11CS 245: Database SystemPrinciplesDistributed Databases(Slides by Hector Garcia-Molina,http://www-db.stanford.edu/~hector/cs245/notes.htm)2Distributed DatabasesdataDBMSdataDBMSdataDBMSdataDBMSDistributed Database System3Advantages of a DDBS• Modularity• Fault Tolerance• High Performance• Data Sharing• Low Cost Components24Issues• Data Distribution• Exploiting Parallelism• Concurrency and Recovery• Heterogeneity5Parallelism: Pipelining• Example:– T1 ← SELECT * FROM A WHERE cond– T2 ← JOIN T1 and BAB(with index)selectjoin6Parallelism: Concurrent Operations• Example: SELECT * FROM A WHERE condA whereA.x < 10selectselectA where10 ≤ A.x < 20selectA where20 ≤ A.xmergedata location isimportant...37Join Processing• Example: JOIN A, B over attribute XA1A2B1B2A.x < 10A.x ≥ 10B.x < 10 B.x ≥ 10join strategy8Join Processing• Example: JOIN A, B over attribute XA1A2B1B2A.z < 10A.z ≥ 10B.z < 10 B.z ≥ 10join strategy9Concurrency & Recovery• Two Phase CommitATMBankMainframe4102PC: ATM Withdrawl• Mainframe is coordinator• Phase 1: ATM checks if moneyavailable; mainframe checks if accounthas funds (money and funds are“reserved”)• Phase 2: ATM releases funds;mainframe debits account11Replicated Data Mangement• Key to fault-tolerance, durability• Illustrates transaction processing issues• Various concurrency control/recoveryalgorithms available12Primary Copy Algorithm• Updates run at primary site• Backups repeat writes;backups allow “out-of-date” readsPrimary SiteA 3B 8C 4D 25Backup Site 1A 3B 8C 4D 25Backup Site 2A 3B 8C 4D 255697T1: A:5; C:6T2: B:9; C: 7propagate in
View Full Document