分布式数据库系统原理(第2版)

PREFACE TO THE SECOND EDITION
PREFACE TO THE FIRST EDITION
1 1 NTRODUCTION
1.1 DISTRIBUTED DATA PROCESSING
l.2 WHAT IS A DISTRIBUTED DATABASE SYSTEM?
1.3 PROMISES OF DDBSs
1.3.1 Transparent Management of Distributed and Replicated Data
1.3.2 Reliability Through Distributed Transactions
1.3.3 Improved Performance
1.3.4 Easier System Expansion
1.4 COMPLICATING FACTORS
1.5 PROBLEM AREAS
l.5.1 Distributed Database Design
1.5.2 Distributed Query Processing
l.5.3 Distributed Directory Management
1.5.4 Distributed Concurrency Control
1.5.5 Distributed Deadlock Management
1.5.6 Reliability of Distributed DBMS
1.5.7 Operating System Support
1.5.8 Heterogeneous Databases
1.5.9 Relationship among Problems
1.6 BIBLIOGRAPHIC NOTES

2 OVERVIEW OF RELATIONAL DBMS
2.1 RELATIONAL DATABASE CONCEPTS
2.2 NORMALIZATION
2.2.1 Dependency Structures
2.2.2 Normal Forms
2.3 INTEGMTY RULES
2.4 RELATIONAL DATA LANGUAGES
2.4.1 Relational Algebra
2.4.2 Relational Calculus
2.4.3 Interface with Programming Languages
2.5 RELATIONAL DBMS
2.6 BIBLJOCRAPHIC NOTES

3 REVIEW OF COMPUTER NETWORKS
3.1 DATA COMMUNICATION CONCEPTS
3.2 TYPES OF NETWORKS
3.2.1 Topology
3.2.2 Communication Schemes
3.2.3 Scale
3.3 PROTOCOL STANDARDS
3.4 BROADBAND NETWORKS
3.5 WIRELESS NETWORKS
3.6 INTERNET
3.7 CONCLUDING REMARKS
3.8 BIBLIOGRAPHIC NOTES

4 DISTRIBUTED DBMS ARCHITECTURE
4.1 DBMS STANDARDIZATION
4.2 ARCHITECTURAL MODELS FOR DISTRIBUTED DBMSs
4.2.l Autonomy
4.2.2 Distribution
4.2.3 Heterogeneity
4.2.4 Architectural Alternatives
4.3 DISTRIBUTED DBMS ARCHITECTURE
4.3.1 Client/Server Systems
4.3.2 Peer-to-Peer Distributed Systems
4.3.3 MDBS Architecture
4.4 GLOBAL DIRECTORY ISSUES
4.5 CONCLUSION
4.6 BIBLIOGRAPHIC NOTES

5 DISTRIBUTED DATABASE DESIGN
5.l ALTERNATIVE DESIGN STRATEGIES
5.1.1 Top-Down Design Process
5.1.2 Bottom-Up Design Process
5.2 DISTRIBUTION DESIGN ISSUES
5.2.l Reasons for Fragmentation
5.2.2 Fragmentation Alternatives
5.2.3 Degree of Fragmentation
5.2.4 Correctness Rules of Fragmentation
5.2.5 Allocation Alternatives
5.2.6 Information Requirements
5.3 FRAGMENTATION
5.3.1 Horizontal Fragmentation
5.3.2 Vertical Fragmentation
5.3.3 Hybrid Fragmentation
5.4 ALLOCATION
5.4.1 Allocation Problem
5.4.2 Information Requirements
5.4.3 Allocation Model
5.4.4 Solution Methods
5.5 CONCLUSION
5.6 BIBLIOGRAPHIC NOTES
5.7 EXERCISES

6 SEMANTIC DATA CONTROL
6.1 VIEW MANAGEMENT
6.1.1 Views in Centralized DBMSs
6.1.2 Updates through Views
6.1.3 Views in Distributed DBMSs
6.2 DATA SECURITY
6.2.l Centralized Authorization Control
6.2.2 Distributed Authorization Control
6.3 SEMANTIC INTEGRITY CONTROL
6.3.l Celltra1ized Semantic Integrity Control
6.3.2 Distributed Semantic Integrity Control
6.4 CONCLUSION
6.5 BIBLIOGRAPHIC NOTES
6.6 EXERCISES

7 OVERVIEW OF QUERY PROCESSING
7.l QUERY PROCESSING PROBLEM
7.2 OBJECTIVES OF QUERY PROCESSING
7.3 COMPLEXITY OF RELATIONAL ALGEBRA OPERATJONS
7.4 CHARACTERIZATION OF QUERY PROCESSORS
7.4.l Languages
7.4.2 Types of Optimization
7.4.3 Optimization Timing
7.4.4 Statistics
7.4.5 Decision Sites
7.4.6 Exploitation of -the Network Topology
7.4.7 Exploitation of Replicated Fragments
7.4.8 Use of Semijoins
7.5 LAYERS OF QUERY PROCESSING
7.5.l Query Decomposition
7.5.2 Data Localization
7.5.3 Global Query Optimization
7.5.4 Local Query Opti1nization
7.6 CONCLUSION
7.7 BIBLIOGRAPHIC NOTES

8 QUERY DECOMPOSITION AND DATA LOCALIZATION
8.1. QUERY DECOMPOSITION
8.l.1 Normalization
8.1.2 Analysis
8.1.3 Elimination of Redundancy
8.1.4 Rewriting
8.2 LOCALIZATION OF DISTRIBUTED DATA
8.2.1 Reduction for Primary Horizolltal Fragmentation
8.2.2 Reduction for Vertical Fragmentation
8.2.3 Reduction for Derived Fragmentation
8.2.4 Reduction for Hybrid Fragmentation
8.3 CONCLUSION
8.4 BIBLIOGRAPHIC NOTES
8.5 EXERCISES

9 OPTIMIZATION OF DISTRIBUTED QUERIES
9.1 QUERY OPTIMIZATION
9.1.1 Search Space
9.l.2 Search Strategy
9.1.3 Distributed Cost Model
9.2 CENTRALIZED QUERY OPTIMIZATION
9.2.l INGRES Algorithm
9.2.2 System R A1gorithm
9.3 JOIN ORDERING IN FRAGMENT QUERIES
9.3.1 Join Ordering
9.3.2 Semijoin Based Algorithms
9.3.3 Join versus Semi join
9.4 DISTRJBUTED QUERY OPTIMIZATION ALGORITHMS
9.4.1 Distributed INpRES Algorithm
9.4.2 R* Algorithm
9.4.3 SDD-1 Algorithm
9.5 CONCLUSION
9.6 BIBLIOGRAPHIC NOTES
9.7 EXERCISES

10 INTRODUCTION TO TRANSACTION MANAGEMENT
10.1 DEFINITION OF A TRANSACTION
10.1.1 Termination Conditions of Thansactions
l0.1.2 Characterization of Transactions
10.1.3 Formalization of the Transaction Concept
10.2 PROPERTIES OF TRANSACTIONS
10.2.1 Atomicity
10.2.2 Consistency
l0.2.3 Isolation
l0.2.4 Durabi1ity
l0.3 TYPES OF TRANSACTIONS
l0.3.1 Flat Thansactions
l0.3.2 Nested Transactions
10.3.3 Workflows
l0.4 ARCHITECTURE REVISITED
l0.5 CONCLUSION
10.6 BIBLIOGRAPHIC NOTES

11 DISTRIBUTED CONCURRENCY CONTROL
11.1 SERIALIZABILITY THEORY
l1.2 TAXONOMY OF CONCURRENCY CONTROL MECHANISMS
11.3 LOCKING-BASED CONCURRENCY CONTROL ALGORITHMS
11.3.l Centralized 2PL
11.3.2 Primary Copy 2PL
11.3.3 Distributed 2PL
11.4 TIMESTAMP-BASED CONCURRENCY CONTROL ALGORITHMS
11.4.l Basic TO Algorithm
11.4.2 Conservative TO Algorithm
11.4.3 Multiversion TO Algorithm
1l.5 OPTIMISTIC CONCURRENCY CONTROL ALGORITHMS
11.6 DEADLOCK MANAGEMENT
11.6.1 Deadlock Prefelltion
l1.6.2 Deadlock Avoidance
11.6.3 Deadlock Detection and Resolution
l1.7 "RELAXED" CONCURRENCY CONTROL
11.7.1 Non-Serializable Schedules
11.7.2 Nested Distributed nansactions
11.8 CONCLUSION
11.9 BIBLIOGRAPHIC NOTES
11.10 'EXERCISES

12 DISTRIBUTED DBMS RELIABILITY
12.1 RELIABlLITY CONCEPTS AND MEASURES
12.l.1 System, State, and Failure
12.1.2 Reliability and Availability
12.1.3 Mean Time between Failures/Mean Time to Repair
12.2 FAILURES AND FAULT TOLERANCE IN DISTRIBUTED SYSTEMS
12.2.1 Reasons for Failures
l2.2.2 Basic Fault Tolerance Approaches and Techniques
12.3 FAILURES IN DISTRIBUTED DBMS
12.3.l Thansaction Failures
12.3.2 Site (System) Failures
12.3.3 Media Failures
12.3.4 Communication Failures
12.4 LOCAL RELIABILITY PROTOCOLS
l2.4.l Architectural Considerations
12.4.2 Recovery Information
12.4.3 Execution of LRM Commands
12.4.4 Checkpoillting
l2.4.5 Handling Media Failures
12.5 DISTRIBUTED RELIABILITY PROTOCOLS
12.5.1 Components of Distributed Reliability Protocols
12.5.2 Two-Phase Commit Protocol
12.5.3 Variations of 2PC
12.6 DEALING WITH SITE FAILURES
12.6.1 Termination and Recovery Protocols for 2PC
12.6.2 Three-Phase Commit Protocol
12.7 NETWORK PARTITIONING
12.7.1 Centralized Protocols
12.7.2 Voting-based Protocols
12.7.3 Replication and Replica Contro1 Protocols
l2.7.4 Strict Replica Control Protocols
l2.7.5 Lazy Replication Protocols
12.8 ARCHITECTURAL CONSIDERATIONS
12.9 CONCLUSION
12.10 BIBLIOGRAPHIC NOTES
12.11 EXERCISES

13 MRALLEL DATABASE SYSTEMS
13.1 DATABASE SERVERS
13.1.1 Database Server Approach
13.1.2 Database Servers and Distributed Data