Distributed Database Management Systems: A Practical Approach

DISTRIBUTED DATABASE MANAGEMENT SYSTEMS......Page 3
CONTENTS......Page 9
Preface......Page 27
1 Introduction......Page 37
1.1.2 Database Operations......Page 38
1.1.4 DB Clients, Servers, and Environments......Page 39
1.2.1 Services......Page 40
1.2.3 Sites......Page 41
1.3.1 Required Services......Page 42
1.3.2 Basic Services......Page 43
1.3.3 Expected Services......Page 44
1.3.4 Expected Subsystems......Page 45
1.3.5 Typical DBMS Services......Page 46
1.3.6 Summary Level Diagrams......Page 47
1.4.1 COS Distribution and Deployment......Page 49
1.4.2 COS Closedness or Openness......Page 50
1.4.3 Schema and Data Visibility......Page 51
1.4.4 Schema and Data Control......Page 52
1.5 An Example DDBE......Page 53
1.6.1 DDBE Information Architecture......Page 54
1.6.2 DDBE Software Architecture......Page 56
1.6.2.1 Components of the Application Processor......Page 57
1.6.2.2 Components of the Data Processor......Page 59
1.7 Transaction Management in Distributed Systems......Page 60
1.8 Summary......Page 67
1.9 Glossary......Page 68
References......Page 69
2 Data Distribution Alternatives......Page 71
2.1.2.2 Fully Replicated......Page 74
2.2 Fragmentation......Page 75
2.2.1 Vertical Fragmentation......Page 76
2.2.2.1 Primary Horizontal Fragmentation......Page 78
2.2.2.2 Derived Horizontal Fragmentation......Page 80
2.2.3 Hybrid Fragmentation......Page 83
2.2.4.2 Splitting......Page 85
2.2.6 Horizontal Fragmentation Generation Guidelines......Page 98
2.2.6.1 Minimality and Completeness of Horizontal Fragmentation......Page 99
2.2.7 Horizontal Fragmentation Correctness Rules......Page 102
2.3.2 Fragmentation Transparency......Page 104
2.4 Impact of Distribution on User Queries......Page 105
2.4.1 No GDD—No Transparency......Page 106
2.4.2 GDD Containing Location Information—Location Transparency......Page 108
2.5 A More Complex Example......Page 109
2.5.1 Location, Fragmentation, and Replication Transparencies......Page 111
2.5.2 Location and Replication Transparencies......Page 112
2.5.3 No Transparencies......Page 113
2.7 Glossary......Page 114
References......Page 115
Exercises......Page 116
3 Database Control......Page 119
3.1 Authentication......Page 120
3.2 Access Rights......Page 121
3.3 Semantic Integrity Control......Page 122
3.3.1.1 Relational Constraints......Page 124
3.4 Distributed Semantic Integrity Control......Page 130
3.5 Cost of Semantic Integrity Enforcement......Page 133
3.5.1 Semantic Integrity Enforcement Cost in Distributed System......Page 134
3.5.1.1 Variables Used......Page 136
3.5.1.2 Compile Time Validation......Page 138
3.5.1.3 Run Time Validation......Page 139
3.5.1.4 Postexecution Time Validation......Page 140
3.7 Glossary......Page 142
Exercises......Page 143
4 Query Optimization......Page 147
4.2 Relational Algebra......Page 148
4.2.1 Subset of Relational Algebra Commands......Page 149
4.2.1.1 Relational Algebra Basic Operators......Page 150
4.2.1.2 Relational Algebra Derived Operators......Page 152
4.3 Computing Relational Algebra Operators......Page 155
4.3.1.2 B + Tree Index on R......Page 156
4.3.1.3 Hash Index on R......Page 158
4.3.2.1 Nested-Loop Joins......Page 159
4.3.2.2 Sort–Merge Join......Page 160
4.4 Query Processing in Centralized Systems......Page 162
4.4.1 Query Parsing and Translation......Page 163
4.4.2 Query Optimization......Page 164
4.4.2.1 Cost Estimation......Page 165
4.4.2.2 Plan Generation......Page 169
4.4.2.3 Dynamic Programming......Page 171
4.4.2.4 Reducing the Solution Space......Page 177
4.4.3 Code Generation......Page 180
4.5 Query Processing in Distributed Systems......Page 181
4.5.1 Mapping Global Query into Local Queries......Page 182
4.5.2 Distributed Query Optimization......Page 186
4.5.2.1 Utilization of Distributed Resources......Page 187
4.5.2.2 Dynamic Programming in Distributed Systems......Page 188
4.5.2.3 Query Trading in Distributed Systems......Page 192
4.5.2.4 Distributed Query Solution Space Reduction......Page 193
4.5.3.1 Heterogeneous Database Systems Architecture......Page 206
4.5.3.2 Optimization in Heterogeneous Databases......Page 207
4.6 Summary......Page 208
4.7 Glossary......Page 209
References......Page 211
Exercises......Page 214
5.1.1 Database......Page 219
5.1.2 Transaction......Page 220
5.1.2.1 Transaction Redefined......Page 224
5.2.1.2 Parallel Schedule......Page 225
5.2.2.2 Reading Uncommitted Data......Page 227
5.2.3 Equivalence......Page 228
5.2.4 Serializable Schedules......Page 229
5.2.4.1 Serializability in a Centralized System......Page 230
5.2.4.2 Serializability in a Distributed System......Page 231
5.2.4.4 View Serializable Schedules......Page 232
5.2.5 Advanced Transaction Types......Page 233
5.2.5.1 Sagas......Page 234
5.2.6 Transactions in Distributed System......Page 235
5.3 Centralized DBE Concurrency Control......Page 236
5.3.1 Locking-Based Concurrency Control Algorithms......Page 237
5.3.1.2 Two-Phase Locking......Page 238
5.3.1.3 Locking in Relational Databases......Page 240
5.3.1.4 Phantom Issue......Page 242
5.3.2.1 Basic TO Concurrency Control Algorithm......Page 245
5.3.2.2 Conservative TO Algorithm......Page 246
5.3.2.3 Multiversion Concurrency Control Algorithm......Page 248
5.3.3 Optimistic Concurrency Control Algorithm......Page 249
5.3.4 Concurrency Control in a Real DBMS (Oracle)......Page 250
5.3.4.4 Enforcing Serializability in Oracle......Page 252
5.4 Concurrency Control in Distributed Database Systems......Page 258
5.4.1.1 Centralized 2PL......Page 265
5.4.1.3 Distributed 2PL......Page 266
5.4.2 Distributed Timestamp Concurrency Control......Page 268
5.4.2.1 Conflict Graphs and Transaction Classes......Page 271
5.4.3 Distributed Optimistic Concurrency Control......Page 272
5.4.4 Federated/Multidatabase Concurrency Control......Page 273
5.6 Glossary......Page 274
References......Page 278
Exercises......Page 279
6.1 Deadlock Definition......Page 283
6.2.1.1 The Preacquisition of All Locks Algorithm......Page 284
6.2.2.1 The Wait–Die Algorithm......Page 285
6.2.2.2 The Wound–Wait Algorithm......Page 287
6.3 Deadlocks in Distributed Systems......Page 288
6.3.1 The Transaction Location Issue......Page 289
6.3.3 Distributed Deadlock Prevention......Page 290
6.3.4.1 The Distributed Wait–Die Algorithm......Page 291
6.3.4.2 The Distributed Wound–Wait Algorithm......Page 292
6.3.4.3 Distributed Wound–Wait Control Alternatives......Page 293
6.3.5 Distributed Deadlock Detection......Page 296
6.3.5.3 Distributed Deadlock Detectors......Page 298
6.4 Summary......Page 306
6.5 Glossary......Page 307
Exercises......Page 308
7 Replication Control......Page 311
7.1 Replication Control Scenarios......Page 312
7.1.1 Synchronous Replication Control Approach......Page 313
7.1.2 Asynchronous Replication Control......Page 314
7.2.1 Architectural Considerations......Page 315
7.2.2 Master–Slave Replication Control Algorithm......Page 316
7.2.2.2 Centralized Transaction Application Phase......Page 317
7.2.3.2 Distributed Transaction Application Phase......Page 318
7.2.4 Majority Consensus Algorithm......Page 319
7.2.5 Circulating Token Algorithm......Page 320
7.2.5.1 Circulating Token Implementation......Page 321
7.2.6 Generalized Voting Algorithm for Replication Control......Page 323
7.2.7 Posted Update Approach......Page 326
7.3 Summary......Page 327
7.4 Glossary......Page 328
Exercises......Page 329
8.1.1 Soft Failure......Page 333
8.1.3 Commit Protocols......Page 334
8.1.3.2 Transaction Rollback (Undo)......Page 335
8.1.4 Transaction States......Page 336
8.1.6 Transaction Log......Page 338
8.1.7 DBMS Storage Types......Page 339
8.1.8.1 Deferred Update Mode Log Records......Page 340
8.1.8.2 Immediate Update Mode Log Records......Page 342
8.2.1 Local Recovery Management......Page 344
8.2.1.1 Database Buffers and Log Buffers......Page 345
8.2.1.3 Backup Types......Page 347
8.3.1 Deferred Update Transaction Steps......Page 349
8.4.1 Logging Process......Page 350
8.4.2.1 Log Information Analysis......Page 352
8.4.2.3 Recovery from Disk Failure......Page 353
8.4.2.4 Checkpointing......Page 354
8.5.2 Recovery to a Point-in-Time in the Past......Page 355
8.5.3.1 Transaction Recovery Using UNDO Scripts......Page 356
8.5.3.2 Transaction Recovery Using REDO Scripts......Page 357
8.6 Recovery Based on Redo/Undo Processes......Page 358
8.7 The Complete Recovery Algorithm......Page 359
8.8 Distributed Commit Protocols......Page 360
8.8.1 Architectural Requirements......Page 361
8.8.2 Distributed Commit Protocols......Page 362
8.8.3 One-Phase Commit......Page 363
8.8.4 Two-Phase Commit Protocol......Page 365
8.8.4.1 Resiliency of 2PC and Failure Handling......Page 368
8.8.4.2 Termination Protocols in 2PC......Page 372
8.8.4.3 Recovery Protocols in 2PC......Page 376
8.8.4.4 2PC Coordinator Recovery Process......Page 377
8.8.4.7 Multiple Site Failures in 2PC......Page 378
8.8.4.8 Two-Phase Commit Performance......Page 379
8.8.5.1 Resiliency of 3PC......Page 381
8.8.6 Network Partitioning and Quorum-Based Commit Protocol......Page 385
8.10 Glossary......Page 387
References......Page 389
Exercises......Page 390
9.1 Cryptography......Page 393
9.1.1 Conventional Cryptography......Page 394
9.1.1.1 DES/Triple DES......Page 396
9.1.1.3 RC4......Page 397
9.1.2.1 MD5 and SHA......Page 398
9.1.3 Public Key Cryptography......Page 399
9.1.4 Digital Signatures......Page 400
9.1.5 Digital Certificates and Certification Authorities......Page 401
9.2.1 SSL/TLS......Page 402
9.3.1 Authentication and Authorization......Page 404
9.3.2 Data Encryption......Page 405
9.3.3 Unvalidated Input and SQL Injection......Page 406
9.3.3.1 Bypassing the Password for Customer Login......Page 407
9.3.3.3 Vandalizing the DDBE......Page 408
9.3.4 Data Inference......Page 410
9.4 Architectural Issues......Page 411
9.5 A Typical Deployment......Page 412
9.7 Glossary......Page 413
References......Page 416
Exercises......Page 417
10 Data Modeling Overview......Page 419
10.1 Categorizing MLs and DMs......Page 420
10.1.1 The CLP Taxonomy......Page 421
10.1.2 The 3LM Taxonomy......Page 424
10.1.3 Other Categorization Approaches......Page 425
10.2.1.1 DBE Design and Implementation Independence Issues......Page 426
10.2.1.2 Abstraction Issues......Page 428
10.2.1.3 Emphasis Issues......Page 429
10.2.2.2 Supporting Forward Engineering......Page 430
10.2.2.3 Supporting Reverse Engineering......Page 431
10.3.1.1 Construct Review......Page 432
10.3.1.2 ERM Rules and Guidelines......Page 438
10.3.1.3 Traditional Chen ERD Notation......Page 441
10.3.1.4 Crow’s Foot/Feet Notation......Page 443
10.3.1.5 Unified Modeling Language......Page 444
10.4.1.1 Capture the Requirements......Page 447
10.4.1.4 Remove Ambiguities......Page 448
10.4.2.1 Purpose......Page 449
10.4.2.2 Steps to Create LDMs......Page 450
10.4.3.1 Purpose......Page 451
10.5 Using Multiple Types of Modeling......Page 452
10.5.2 Forward Engineering......Page 453
10.6 Summary......Page 454
10.7 Glossary......Page 455
References......Page 457
Exercises......Page 458
11 Logical Data Models......Page 461
11.1.1 Nomenclature......Page 462
11.1.1.1 Relations, Tuples, and Domains......Page 463
11.1.1.2 Keys......Page 464
11.1.2.1 Forward Generation of ATs......Page 465
11.1.2.3 Forward Generation of ETs......Page 469
11.1.2.4 Forward Generation of ITs......Page 470
11.1.4 Special Considerations......Page 471
11.2 The Network Data Model......Page 472
11.2.1.2 Set Types......Page 473
11.2.2.2 Forward Generation of RTs......Page 474
11.2.2.4 Forward Generation of ITs......Page 475
11.3 The Hierarchical Data Model......Page 476
11.3.1.4 Virtual Record Types and Virtual Link Types......Page 477
11.3.3 Rules for Reverse Engineering......Page 478
11.4.1.1 Properties and Methods......Page 479
11.4.2.1 Forward Generation of ATs......Page 480
11.4.4 Special Considerations......Page 481
11.6 Glossary......Page 482
References......Page 485
Exercises......Page 486
12 Traditional DDBE Architectures......Page 487
12.1 Applying Our Taxonomy to Traditional DDBE Architectures......Page 488
12.1.1.3 The SAD-VIS Level......Page 489
12.1.2 Classifying the Federated Database Architecture......Page 490
12.1.2.4 The SAD-CON Level......Page 491
12.1.3.2 The COS-COO Level......Page 492
12.2 The MDBS Architecture Classifications......Page 493
12.3.2 Bottom–Up Methodology......Page 495
12.3.2.2 Developing the Software Bottom–Up......Page 496
12.4 Deployment of DDBE Software......Page 497
12.5 Integration Challenges......Page 499
12.5.1 Software Integration Issues......Page 501
12.5.2.1 GCS Maintenance Issues......Page 502
12.5.2.2 GCS Creation Issues......Page 505
12.6 Schema Integration Example......Page 513
12.6.1 Translation Step......Page 514
12.6.3 Discovery and Resolution Steps......Page 517
12.6.4 Restructuring Step......Page 518
12.7 Example of Existing Commercial DDBEs......Page 519
12.7.1 Schema Integration in Commercial Systems......Page 521
12.7.2 Software Integration in Existing Products......Page 522
12.7.3 Microsoft Access......Page 523
12.7.4 InfoSphere Federation Server......Page 524
12.8.2 Database Distribution......Page 525
12.8.3 The Setup......Page 526
12.8.4 Setting Up Data Source Names......Page 528
12.8.4.1 Linking Data Sources into Access......Page 531
12.8.5 Linking Data Sources into Federation Server......Page 533
12.8.5.1 Creating the Nickname for the Excel Spreadsheet on C4......Page 534
12.8.5.2 Creating the Nickname for the “Empl Sal LE5K” Table......Page 535
12.8.5.3 Creating the Nicknames for Emp Sal GT5K and Child......Page 536
12.8.6 The Experiments......Page 538
12.8.7 Querying the Database from Access and Federation Server......Page 539
12.8.8 Modifying the Database from Access and Federation Server......Page 541
12.10 Glossary......Page 545
References......Page 547
Exercise......Page 548
13.1 Cooperative DBEs......Page 549
13.1.1 Subsystems Overview......Page 551
13.1.1.2 Distributed Query Service Provider......Page 553
13.1.1.3 Data Dictionary Service Provider......Page 554
13.1.1.4 Global Interface Schema......Page 555
13.1.1.5 Local Deployment Schema......Page 557
13.1.1.6 Local Query Service Provider......Page 558
13.1.2.2 The Client Sends a Query to the DQSP......Page 559
13.1.2.3 The DQSP Sends a Query to the DDSP......Page 560
13.1.2.4 The DDSP Sends a Fully Qualified Query to the DQSP......Page 561
13.1.2.5 The Election Process......Page 562
13.2.1 P2P Overview......Page 564
13.2.1.4 Query Service Provider......Page 565
13.3.1 COOP Versus P2P......Page 566
13.3.2 COOP/P2P Versus Traditional DDBEs......Page 567
13.4 Summary......Page 568
13.5 Glossary......Page 569
Exercises......Page 570
14 DDBE Platform Requirements......Page 571
14.1.2 Service Consumers and Service Providers......Page 573
14.1.3.1 The Three-Tier Model......Page 574
14.1.3.2 Service-Oriented Architecture......Page 576
14.1.4 Middleware......Page 578
14.2.1 Development Requirements......Page 580
14.2.1.1 Integration Requirements......Page 581
14.2.1.2 Extensibility Requirements (Frameworks)......Page 582
14.2.1.3 Portability Requirements......Page 583
14.2.2 Deployment Requirements......Page 584
14.2.2.2 COS Versioning Requirements......Page 585
14.2.2.4 COS Deployment Requirements......Page 586
14.2.3.1 Multitasking Requirements......Page 587
14.2.3.2 Concurrent Execution Requirements......Page 589
14.3 Distributed Process Platform Requirements......Page 591
14.3.1 Remoteability Requirements......Page 592
14.3.1.1 Remote-Code Execution......Page 593
14.3.1.2 Remote Messaging......Page 596
14.3.2 Directory Service Requirements......Page 600
14.3.2.2 Registration Service Requirements......Page 601
14.3.2.3 Lookup Service Requirements......Page 602
14.4.1.1 Security Policies......Page 603
14.4.1.4 Encryption......Page 604
14.4.2 Database Connectivity Requirements......Page 605
14.5 Preview of the DDBE Platforms Used in Chapters 15–19......Page 606
14.5.2 The Java 2 Enterprise Edition (J2EE) Platform......Page 607
14.5.3 The Microsoft .NET Framework-Based Platform......Page 608
14.6 Summary......Page 609
14.7 Glossary......Page 610
Exercises......Page 613
15 The JMS Starter Kit......Page 615
15.1.1 Architectural Overview......Page 617
15.1.1.1 Service Terminology Review......Page 618
15.1.1.2 Administered Objects......Page 619
15.1.1.4 Thread-Safety Considerations......Page 620
15.1.1.5 Destination Objects......Page 621
15.1.2 Messaging Overview......Page 622
15.1.2.1 Application-Defined Protocols......Page 623
15.1.2.2 Synchronous Versus Asynchronous Messaging......Page 624
15.1.2.3 Message Persistence......Page 625
15.1.2.4 Message Acknowledgment......Page 627
15.1.2.6 Message Errors and Exceptions......Page 629
15.1.2.7 Message Ordering......Page 630
15.1.3 Messaging Domains......Page 631
15.1.3.1 Point-to-Point (PTP) Messaging......Page 632
15.1.3.2 Publish-and-Subscribe (Pub/Sub) Messaging......Page 633
15.1.4.2 Connection......Page 634
15.1.4.3 Session......Page 635
15.1.4.4 Destination......Page 636
15.1.4.7 Message......Page 637
15.2 JMS Provider Implementation Alternatives......Page 638
15.2.1.2 Configuration......Page 639
15.2.1.4 Administration Facilities......Page 640
15.2.2.2 Configuration......Page 641
15.3 JMS Starter Kit (JMS-SKIT) Framework Overview......Page 642
15.3.1.1 Message Reliability Goals......Page 643
15.3.1.4 Software Complexity Goals......Page 644
15.3.2.1 Framework Interface Package Overview......Page 645
15.3.2.2 Framework Implementation Package Overview......Page 648
15.4.1 Sample Extension Overview......Page 649
15.4.1.2 Sample Extension Design Overview......Page 650
15.4.2 Creating New Extensions......Page 651
15.5 Summary......Page 652
15.6 Glossary......Page 653
Exercises......Page 655
16 The J2EE Platform......Page 657
16.1.1 Fundamental J2EE Vocabulary Terms......Page 658
16.1.1.3 Java Runtime Environment......Page 659
16.1.1.8 Enterprise Java Beans......Page 660
16.1.3 Development Overview......Page 661
16.2 J2EE Support for Distributed Process Platform Requirements......Page 662
16.2.1.2 XML Web Services and SOAP......Page 663
16.2.1.3 Session Beans......Page 664
16.2.2.2 Java Message Service......Page 665
16.2.3.1 The Java Naming and Directory Interface Facility......Page 666
16.3 J2EE Support for Distributed Data Platform Requirements......Page 667
16.3.2 Java Database Connectivity......Page 668
16.4 J2EE Platform Implementation Alternatives......Page 669
16.4.1 JBoss......Page 670
16.4.4 Other J2EE Platform Implementation Alternatives......Page 671
16.5 Summary......Page 672
16.6 Glossary......Page 673
References......Page 675
Exercises......Page 676
17 The J2EE Starter Kit......Page 677
17.1.1 J2EE-SKIT Goals......Page 678
17.1.2 J2EE-SKIT Architectural Overview......Page 679
17.1.2.1 J2EE-SKIT Subsystem Identification......Page 680
17.1.2.2 J2EE-SKIT Subsystem Interaction Overview......Page 681
17.1.3.2 The Parser Subsystem......Page 684
17.1.4.1 The Qualifier Subsystem......Page 685
17.1.4.3 The Dem Subsystem......Page 686
17.2.1 J2EE-SKIT Framework Design Overview......Page 687
17.2.1.1 The Ddbms Subsystem......Page 688
17.2.1.2 The Parser Subsystem......Page 689
17.2.2 J2EE-SKIT Extension Design Overview......Page 690
17.2.2.3 The Dem Subsystem......Page 691
17.2.3 Parameter Type Interfaces......Page 692
17.2.3.4 QueryResultSet......Page 693
17.2.4.1 Framework and Extension Exception Base Classes......Page 694
17.3 Summary......Page 695
17.4 Glossary......Page 696
Exercises......Page 698
18 The Microsoft .NET Platform......Page 699
18.1 Platform Overview......Page 701
18.1.1 Fundamental Platform-Specific Vocabulary Terms......Page 702
18.1.1.3 Common Language Specification......Page 703
18.1.1.4 Common Type System......Page 704
18.1.1.6 Managed/Unmanaged Components......Page 705
18.1.1.7 Assemblies......Page 707
18.1.1.9 Application Domains......Page 708
18.1.2 Architectural Overview......Page 709
18.1.3 Development Overview......Page 710
18.1.4 Assembly Deployment Overview......Page 711
18.1.4.1 Configuration......Page 712
18.1.4.2 Assembly Deployment Alternatives......Page 713
18.1.4.4 Deploying a Private Assembly......Page 714
18.2 Support for Distributed Process Platform Requirements......Page 715
18.2.1.1 .NET Remoting......Page 716
18.3 Distributed Data Platform Requirements......Page 717
18.3.3 .NET Transactions......Page 718
18.4 Summary......Page 719
18.5 Glossary......Page 720
References......Page 722
Exercises......Page 723
19 The DNET Starter Kit......Page 725
19.1 DNET-SKIT Overview......Page 726
19.1.2 DNET-SKIT Architectural Overview......Page 727
19.1.2.1 DNET-SKIT Component Identification......Page 731
19.1.2.2 DNET-SKIT Subsystem Interaction Overview......Page 732
19.1.3 DNET-SKIT Extension Architectural Overview......Page 733
19.1.3.2 The Parser Subsystem......Page 734
19.1.3.6 The Lem Subsystem......Page 735
19.2.1.1 The Framework Interfaces Area......Page 736
19.2.1.3 The Framework Parameters Area......Page 737
19.2.2 DNET-SKIT Extension Design Overview......Page 738
19.2.2.1 The Ddbms Subsystem......Page 739
19.2.2.2 The Parser Subsystem......Page 740
19.2.2.4 The Planner Subsystem......Page 741
19.2.2.6 The Lem Subsystem......Page 742
19.3 Summary......Page 743
19.4 Glossary......Page 744
Exercises......Page 746
Index......Page 747