Distributed Data Design

Introduction

Distributed data design is the systematic process of deciding how logical data structures should be divided, replicated, placed, and accessed across multiple networked database sites. Unlike centralized design, in which storage location is largely an implementation concern, distributed design directly affects query performance, availability, consistency, security, scalability, and operating cost.

A distributed database presents users with a logically integrated database while storing data at several geographically or organizationally separate sites. The design challenge is therefore to preserve a coherent global view while exploiting locality. A well-designed distribution strategy places frequently used data near its consumers, reduces unnecessary communication, balances storage and processing workloads, and maintains correctness under failures and concurrent updates.

Two broad approaches are used. Top-down design begins with global requirements and a global schema, then derives fragments and site allocations. Bottom-up design begins with existing local databases and integrates them into a global schema. In practice, large organizations often use a hybrid approach: new systems are designed top-down, while acquired or legacy systems are integrated bottom-up.

Learning Objectives

After studying this chapter, a learner should be able to:

1. Distinguish top-down and bottom-up distributed database design.
2. Explain horizontal, vertical, hybrid, derived, and replicated fragmentation.
3. Evaluate fragmentation using correctness properties.
4. Allocate and place fragments according to workload, cost, and reliability requirements.
5. Explain localization and schema integration techniques.
6. Apply a structured design method to a realistic distributed database problem.
7. Critically assess consistency, security, governance, and operational trade-offs.

1. Design Context and Terminology

A distributed database consists of a global schema, one or more fragment schemas, and physical copies stored at sites. A site may be a data centre, cloud region, branch server, or computational node. A distributed database management system (DDBMS) hides distribution through transparency mechanisms.

Important forms of transparency include:

• Location transparency: users need not know where data is stored.
• Fragmentation transparency: users query global relations rather than individual fragments.
• Replication transparency: users need not identify which copy is being accessed.
• Failure transparency: the system masks or manages site and network failures as far as possible.
• Performance transparency: the system attempts to optimize execution despite distribution.

A distributed design normally proceeds through five related decisions:

1. Fragmentation: Which subsets of a relation should be created?
2. Replication: Which fragments require multiple copies?
3. Allocation: Which sites should store each fragment or replica?
4. Placement: How should fragments be mapped to storage, processors, and regions?
5. Localization: How should a global query be transformed into operations on local fragments?

The terms allocation and placement are sometimes used interchangeably. In a precise design discussion, allocation identifies the sites assigned to fragments, whereas placement includes the physical and operational details of storing, indexing, and serving those fragments.

2. Top-Down and Bottom-Up Design

2.1 Top-down design

Top-down design starts from enterprise requirements. Designers first construct or validate a global conceptual model, commonly using entities, relationships, constraints, and business rules. The global relational schema is then fragmented and allocated.

A typical sequence is:

1. Requirements analysis and workload characterization.
2. Global conceptual and logical schema design.
3. Identification of fragmentation predicates and attributes.
4. Fragmentation and correctness validation.
5. Allocation and replication analysis.
6. Physical design, indexing, and localization.
7. Testing under normal and failure workloads.

Top-down design is appropriate when an organization is developing a new platform, replacing a fragmented legacy architecture, or enforcing enterprise-wide governance. Its major advantage is global consistency. Its limitation is that it may underestimate the complexity of existing systems, local autonomy, incompatible data definitions, and migration costs.

2.2 Bottom-up design

Bottom-up design integrates pre-existing local databases. Each local schema is first documented and analyzed. Correspondences are then identified among local entities, attributes, identifiers, data types, and constraints. The designer resolves conflicts and constructs a global schema or federated view.

Typical conflicts include:

• Naming conflicts: CustomerNo and Client_ID may identify the same concept.
• Structural conflicts: one database stores address as one field while another separates street, city, and postal code.
• Type conflicts: an account number may be numeric in one system and character-based in another.
• Semantic conflicts: “active customer” may mean a recent purchase in one system and an open account in another.
• Key conflicts: local identifiers may not be globally unique.
• Constraint conflicts: local systems may impose different valid ranges or null rules.

Bottom-up design preserves local investment and autonomy, but integration can produce duplicated data, inconsistent semantics, and expensive query mediation. Metadata management and explicit data stewardship are essential.

2.3 Comparative evaluation

3. Fragmentation Models

Fragmentation is meaningful only when users can reconstruct the intended global relation and constraints are preserved. A relation may be fragmented horizontally, vertically, or by a combination of both.

3.1 Horizontal fragmentation

Horizontal fragmentation divides a relation into subsets of tuples. Let relation R be divided using predicates p₁, p₂, ..., p_n. A primary horizontal fragment is:

where σ is the relational selection operator. If predicates are mutually exclusive and collectively exhaustive, then the fragments are disjoint and their union reconstructs the original relation:

For example, an ORDERS relation might be divided by sales region: North, South, East, and West. Horizontal fragmentation is effective when transactions are geographically or organizationally local.

Derived horizontal fragmentation divides a relation according to the fragmentation of another related relation. If CUSTOMER is fragmented by region, ORDER can be fragmented by joining orders with customers and applying the customer fragments. This keeps related records near one another, reducing distributed joins.

A derived fragment can be expressed conceptually as:

where ⋉ denotes a semijoin-based derivation and CUSTOMER_i is a customer fragment. The exact implementation depends on keys and referential integrity.

3.2 Vertical fragmentation

Vertical fragmentation divides a relation by columns. Each fragment should normally include the primary key so that the original relation can be reconstructed by joining fragments.

If relation R has attribute sets A₁ and A₂, with key K included in each fragment:

Reconstruction is:

The join is valid when the key uniquely identifies tuples and the fragments retain the same tuple identity. Vertical fragmentation is useful when different applications use different attribute groups—for example, operational services may need customer identity and contact data, while a restricted financial service needs credit information.

Including the key in every vertical fragment adds storage overhead, but omitting it generally prevents reliable reconstruction and complicates tuple matching.

3.3 Hybrid fragmentation

Hybrid fragmentation applies horizontal and vertical operations in sequence. For example, customer data may first be separated by region and then divided into public-contact and confidential-financial attributes within each region.

Hybrid fragmentation is powerful but increases metadata complexity. Designers must document the fragment-generation order, reconstruction expression, security classification, and update paths. A fragment should not be created merely because the operation is possible; it should support a stable workload or governance requirement.

3.4 Replication

Replication stores multiple copies of a fragment. A full replica may be placed at several sites; partial replication stores only selected fragments. Replication can reduce read latency and improve availability, but updates require coordination.

Three common policies are:

• Primary-copy replication: one designated copy accepts updates.
• Synchronous replication: copies are updated before a transaction commits.
• Asynchronous replication: copies converge after the primary update commits.

Synchronous replication offers stronger consistency but increases commit latency and may reduce availability during network partitions. Asynchronous replication improves performance and geographical resilience but permits temporary divergence and requires conflict or staleness policies.

4. Correctness Criteria for Fragmentation

A fragmentation scheme should satisfy four principal properties.

Completeness

Every data item in the global relation must appear in at least one fragment. If a tuple or required attribute is omitted, the global relation cannot be reconstructed.

Reconstruction

There must be a relational expression that reconstructs the original relation. Horizontal fragments generally use union; vertical fragments generally use a key-based join; hybrid schemes combine these operations.

Disjointness

For non-replicated horizontal fragments, a tuple should normally belong to only one fragment. For vertical fragments, non-key attributes should normally occur in only one fragment. Disjointness reduces update ambiguity and storage waste. Replication is an intentional exception.

Semantic correctness

Fragments must preserve primary keys, foreign keys, functional dependencies, domain constraints, and security rules as required. A scheme can be syntactically reconstructable yet semantically unsafe if it creates invalid references or permits unauthorized combinations of data.

5. Fragmentation Design Method

A rigorous design begins with workload rather than intuition.

Step 1: Characterize the workload

Collect query frequencies, transaction frequencies, accessed attributes, selection predicates, join paths, response-time requirements, update rates, and site origins. Distinguish peak from average workload.

Step 2: Identify locality

Determine whether users primarily access local customers, regional orders, departmental attributes, or global aggregates. Locality is valuable only when it is stable enough to justify fragmentation.

Step 3: Select fragmentation predicates

A good horizontal predicate is frequently used, selective, stable, and compatible with organizational boundaries. A volatile predicate can cause records to move repeatedly and generate expensive reorganization.

Step 4: Test reconstruction and constraints

Write the reconstruction expression explicitly. Check keys, foreign keys, null behavior, and updates. Test unusual cases such as missing references, changed regions, and newly introduced categories.

Step 5: Estimate fragment sizes and access patterns

For a relation with N tuples and selectivity s_i for predicate p_i, an approximate fragment cardinality is:

This estimate assumes the selectivity is measured against the same population and that predicate effects are sufficiently understood. For correlated predicates, independence assumptions must not be used without validation.

6. Allocation and Placement

After fragments are defined, the designer determines where they should reside. Allocation is a multi-objective decision involving communication, storage, computation, availability, regulatory constraints, and operational complexity.

A simplified communication-cost model for a workload can be written as:

Here, Q is the set of query or transaction classes, f_q is the frequency of class q, and the three cost terms represent network transfer, computation, and storage-related cost. The model is an approximation: actual systems also incur coordination, locking, recovery, and cloud egress costs.

For a replicated fragment, a simplified expected read cost is:

where P_j is the probability that site or user group j issues the read and C_j is the cost of serving it from the selected replica. This expression does not by itself determine the optimal placement because write cost, failure risk, storage cost, and consistency requirements must also be considered.

Allocation alternatives

• Centralized allocation: all fragments at one site. This simplifies administration but provides little locality or fault tolerance.
• Partitioned allocation: each fragment at one principal site. This reduces update duplication but may make global queries expensive.
• Fully replicated allocation: every site stores every fragment. Reads are local, but storage and update coordination can become prohibitive.
• Selective replication: heavily read or critical fragments have multiple copies, while volatile or large fragments remain partitioned.

Practical placement criteria

1. Access locality: place data near dominant consumers.
2. Update locality: place the authoritative copy near the transaction origin when possible.
3. Join locality: co-locate frequently joined fragments.
4. Capacity: account for storage, memory, CPU, and network limits.
5. Availability: replicate critical data across failure domains.
6. Regulation: respect residency, sovereignty, retention, and privacy rules.
7. Elasticity: consider future growth and rebalancing cost.

7. Schema Integration

Schema integration constructs a coherent global representation from heterogeneous sources. It is not merely renaming tables; it is a semantic process requiring data governance.

7.1 Schema matching

Schema matching identifies correspondences between local elements. Evidence may include names, definitions, data types, value distributions, key relationships, documentation, and sample records. Automated tools can propose matches, but domain experts must validate them.

7.2 Schema transformation

Transformation resolves differences through:

• renaming and synonym mapping;
• decomposition or composition of attributes;
• unit conversion and code translation;
• data-type normalization;
• identifier cross-reference tables;
• derivation rules for calculated attributes.

7.3 Conflict resolution

Conflicts should be resolved through documented policy rather than ad hoc query logic. For example, if one system records gender as a controlled code and another as free text, the integrated model should define an approved vocabulary, mapping for legacy values, treatment of unknown values, and stewardship responsibility.

7.4 Global identifiers

Local keys should not be assumed to be globally unique. Options include globally generated identifiers, source-system-qualified keys, or a master-data cross-reference. Identifier design must support merges, correction, auditability, and privacy requirements.

7.5 Global-as-view and local-as-view approaches

In a global-as-view architecture, the global schema is defined over local sources. It is convenient for integration but query rewriting can be complex. In a local-as-view architecture, each source is described as a view over a global schema. This supports a canonical model but may require source transformations and mappings. Materialized global stores combine integration with performance, at the cost of refresh and consistency management.

8. Query Localization

Localization transforms a global query into operations on fragments. Consider a global relation CUSTOMER horizontally fragmented into CUSTOMER_EAST and CUSTOMER_WEST. A query requesting customers from the East can be directed solely to the East fragment rather than scanning both fragments. This is called fragment elimination or partition pruning.

For vertical fragmentation, a query requiring only name and address can avoid retrieving confidential credit attributes. For joins, semijoin reduction may transmit only join keys or qualifying rows, reducing network traffic. However, semijoins add processing and may not help when the reduction is small.

Localization must preserve query semantics, including null behavior, duplicate handling, authorization predicates, and transaction isolation. Query optimization should consider data statistics at each site, network latency, current load, and replica freshness—not only local CPU cost.

9. Worked Example: Regional Retail Database

Assume a retailer operates three regional sites. The global relations include:

CUSTOMER(CustomerID, Name, Region, Email, CreditLimit)

ORDER(OrderID, CustomerID, OrderDate, Region, Amount, Status)

Regional staff frequently access customers and orders from their own region. A central finance team frequently accesses CreditLimit and monthly order totals.

Fragmentation

First, create primary horizontal customer fragments:

and analogous North and West fragments. Orders are derived horizontally from the customer or order region, provided the region attribute is governed consistently and referential integrity is maintained.

Next, vertically fragment customer data:

The key CustomerID appears in both fragments. Regional sites receive contact fragments. Finance receives the finance fragments, with controlled access to any necessary replicated summary.

Allocation

Regional contact and order fragments are placed at their respective regional sites. Finance fragments are placed in a protected finance region. A read-optimized, asynchronously refreshed order summary may be replicated to regional dashboards, while authoritative orders remain at regional sites.

Analysis

This design reduces the cost of common regional queries and limits exposure of credit data. Its main risks are inconsistent region values, cross-region orders, customer relocation, and stale summaries. A customer changing region should be handled as a controlled master-data event, not by silently moving records during an ordinary query.

10. Illustrative Case: Integrated Health-Service Network

The following is an illustrative case, not a report of a specific organization.

Background

A health-service network has hospital, clinic, laboratory, and billing systems acquired at different times. Each site maintains patients locally. The network wants a unified analytics platform without exposing clinical details to billing users.

Problem

Patient identifiers conflict, clinical terms vary, and data-residency rules require some records to remain within national boundaries. Analysts need longitudinal data, while clinicians require low-latency access to local records.

Analysis

A bottom-up assessment discovers that “patient” has different definitions, laboratory codes differ by site, and some legacy systems lack reliable update timestamps. A purely centralized migration would create substantial operational and privacy risk.

Approach

The design team establishes a canonical patient model and a cross-reference service for local identifiers. Clinical data is horizontally partitioned by legal jurisdiction and operational site. Sensitive attributes are vertically separated from scheduling data. Standardized terminology mappings are maintained as governed reference data. Local systems retain operational authority, while a controlled analytical store receives validated, pseudonymized extracts.

Data lineage records source, transformation, timestamp, and responsible steward. Access decisions use role, purpose, jurisdiction, and patient-consent policies. Replication is selective: appointment availability is replicated for coordination, whereas detailed clinical notes remain close to the originating system.

Outcome

Clinicians retain local performance and availability, analysts obtain a consistent analytical view, and billing users receive only required financial attributes. The architecture accepts some analytical latency in exchange for privacy and operational safety.

Learning points

1. Schema integration is inseparable from semantic governance.
2. Fragmentation can enforce least-privilege access when designed with security boundaries.
3. Replication policy should differ by data sensitivity and volatility.
4. A canonical model does not eliminate the need for source-specific mappings.

11. Challenges, Governance, and Contemporary Practice

Consistency and transactions

Distributed transactions may require coordination across sites. Strong consistency can be necessary for financial balances, inventory reservations, or safety-critical records. Eventual consistency may be acceptable for search indexes, recommendations, and dashboards. The choice must be explicit and tied to business invariants.

Failure and recovery

Designers must plan for site failure, network partition, replica lag, clock differences, and partial commit. Recovery procedures should identify authoritative copies, replay rules, conflict handling, and reconciliation ownership.

Security and privacy

Fragmentation is not automatically a security control. Encryption in transit and at rest, identity management, authorization, key management, auditing, masking, tokenization, and retention policies remain necessary. Replicas expand the attack surface and may create unauthorized copies across jurisdictions.

Data quality and lineage

Distributed systems amplify quality problems. A wrong code replicated across ten sites becomes ten copies of wrong data. Profile data before fragmentation, validate mappings, monitor freshness, and maintain lineage from source to consumer.

AI and automated design

Machine-learning tools can assist with workload clustering, schema matching, anomaly detection, and placement recommendations. They should be treated as decision-support tools. Automated recommendations require explainability, representative workload data, privacy protection, and human approval, particularly where placement affects regulated data or service availability.

Best practices

• Begin with workload and business invariants, not storage technology.
• Document global schemas, fragment predicates, reconstruction expressions, and ownership.
• Prefer stable, selective predicates.
• Co-locate data only when join and access benefits justify coupling.
• Replicate selectively and define freshness guarantees.
• Test failover, stale reads, rebalancing, and schema evolution.
• Treat metadata, lineage, and terminology as production assets.
• Reassess placement as workloads, regulations, and organizational boundaries change.

Chapter Summary

Distributed data design transforms a global logical database into fragments, replicas, and site allocations while preserving correctness and useful transparency. Top-down design derives distribution from enterprise requirements; bottom-up design integrates existing local schemas. Horizontal fragmentation divides tuples, vertical fragmentation divides attributes while retaining keys, and hybrid fragmentation combines both. Derived fragmentation maintains locality across related relations.

Correct fragmentation requires completeness, reconstruction, suitable disjointness, and semantic preservation. Allocation and placement balance locality, communication cost, storage, availability, consistency, security, and regulation. Schema integration requires matching, transformation, conflict resolution, global identifiers, and governed semantics. Query localization then rewrites global operations into efficient local operations. Effective designs are workload-driven, explicitly documented, tested under failure, and continuously governed.

Key Terms

Fragmentation: Division of a global relation into logically meaningful subrelations.

Horizontal fragmentation: Division of a relation by tuples using selection predicates.

Vertical fragmentation: Division of a relation by attributes, normally repeating the key.

Hybrid fragmentation: Fragmentation that combines horizontal and vertical operations.

Derived fragmentation: Fragmentation of one relation based on fragments of a related relation.

Replication: Storage of multiple copies of a fragment.

Allocation: Assignment of fragments or replicas to database sites.

Placement: Physical and operational arrangement of data, indexes, and services at sites.

Location transparency: Ability to access data without knowing its physical site.

Fragmentation transparency: Ability to query global relations without naming fragments.

Schema integration: Construction of a coherent global schema from heterogeneous schemas.

Schema matching: Identification of correspondences between schema elements.

Global schema: Enterprise-level logical representation of distributed data.

Localization: Transformation of global queries into fragment-level operations.

Selectivity: Proportion of tuples satisfying a predicate.

Primary-copy replication: Replication policy with one authoritative update copy.

Eventual consistency: Model in which replicas converge if updates cease.

Data lineage: Record of data origin, transformations, and movement.

Fragment elimination: Avoidance of irrelevant fragments during query processing.

Review Questions

Short Answer Questions

1. What is the principal difference between top-down and bottom-up distributed database design?
2. Why is a primary key normally included in every vertical fragment?
3. Define derived horizontal fragmentation.
4. State two benefits and two costs of replication.
5. What is query localization?

Long Answer Questions

1. Explain horizontal, vertical, and hybrid fragmentation, including their reconstruction requirements.
2. Compare global-as-view and local-as-view approaches to schema integration.
3. Discuss the principal factors that influence fragment allocation and placement.
4. Explain how semantic, structural, naming, and key conflicts arise during bottom-up integration.
5. Discuss the relationship between consistency requirements, replication strategy, and failure handling.

Analytical / Application Questions

1. A university has separate databases for each campus. Design a fragmentation and allocation strategy for students, courses, and examination results. Justify your choices using locality, privacy, and cross-campus query requirements.
2. A relation is vertically fragmented into identity and financial fragments, but the identity key is omitted from the financial fragment. Analyze the consequences and propose a redesign.
3. A retail company observes that 90% of reads are regional but 70% of updates are initiated at headquarters. Propose a replication policy and explain the consistency, latency, and failure trade-offs.

Multiple Choice Questions with Answers

Question 1

Which operation normally reconstructs a relation from disjoint horizontal fragments?

A. Union

B. Cartesian product

C. Projection

D. Difference

Correct Answer: A. Union

Question 2

Why is the primary key included in each vertical fragment?

A. To increase duplicate non-key data

B. To support reconstruction through tuple matching

C. To eliminate all joins

D. To enforce geographic locality

Correct Answer: B. To support reconstruction through tuple matching

Question 3

Which design approach begins with existing local databases?

A. Top-down design

B. Centralized design

C. Bottom-up design

D. Physical-only design

Correct Answer: C. Bottom-up design

Question 4

A fragment created according to the fragmentation of a related relation is called:

A. Replicated fragmentation

B. Derived horizontal fragmentation

C. Independent vertical fragmentation

D. Temporal fragmentation

Correct Answer: B. Derived horizontal fragmentation

Question 5

Which replication policy designates one authoritative copy for updates?

A. Primary-copy replication

B. Fully decentralized replication

C. Random-copy replication

D. Read-only fragmentation

Correct Answer: A. Primary-copy replication

Question 6

If a relation has 10,000 tuples and a validated predicate selectivity of 0.25, the approximate fragment size is:

A. 250

B. 1,000

C. 2,500

D. 25,000

Correct Answer: C. 2,500

Question 7

Which property ensures that all required data items occur in at least one fragment?

A. Disjointness

B. Completeness

C. Localization

D. Replication

Correct Answer: B. Completeness

Question 8

What is the main purpose of query localization?

A. To remove all integrity constraints

B. To transform global queries into operations over relevant fragments

C. To convert relational data into unstructured data

D. To guarantee synchronous replication

Correct Answer: B. To transform global queries into operations over relevant fragments

Question 9

Which issue is a semantic integration conflict?

A. Different meanings of “active customer” in two systems

B. Different network cable lengths

C. Different disk capacities

D. Different screen resolutions

Correct Answer: A. Different meanings of “active customer” in two systems

Question 10

Which strategy generally provides stronger replica consistency but can increase commit latency?

A. Asynchronous replication

B. Synchronous replication

C. Unlogged replication

D. Predicate-only replication

Correct Answer: B. Synchronous replication