Skip to content
Tutorials Center
My learning

Topics

Lesson 64 of 79 ยท Distributed Databases, NoSQL and Analytics

Distributed Database Types and Fragmentation

Compare homogeneous and heterogeneous distributed databases, learn horizontal, vertical and mixed fragmentation with runnable SQL, and see how data placement drives query cost.

A distributed database is a collection of logically related data spread over several computers (called sites or nodes) that are connected by a network. A distributed DBMS (DDBMS) is the software that manages it and makes the whole thing look like one database to users and programs. The reasons are the ones you met in replication, sharding and distributed transactions: data too big for one machine, availability when a machine dies, and speed by keeping data close to the users who need it, for example European customers in a European data center.

That lesson was about mechanisms. This one is about design. What kinds of distributed database exist, how do you cut a table into pieces, and where do you put the pieces? The answers decide how fast queries run and how hard the system is to keep consistent.

Kinds of distributed databases

Homogeneous Same DBMS on every site.
Heterogeneous Different DBMSs, models or schemas.

Heterogeneous systems need translation layers.

1 / 2

Homogeneous and heterogeneous systems

In a homogeneous distributed database every site runs the same DBMS product and uses the same data model and compatible schemas. The sites cooperate closely and present one logical database. Examples are a PostgreSQL cluster with sharding, or a MongoDB cluster. Homogeneous systems are easier to administer, and the DDBMS can optimize queries across all sites because it knows how every site behaves.

In a heterogeneous distributed database the sites differ: perhaps an Oracle database at headquarters, MySQL in a branch office, and a MongoDB store in a web team. Such systems arise from mergers and from departments that picked their own tools. They are also called federated or multidatabase systems, and each site often keeps autonomy: it has local users, runs its own transactions and may refuse global requests. A federation needs layers that translate between the sites:

  • Wrappers (or gateways, drivers) convert between a local DBMS's language and the global one.
  • A mediator or global schema combines the local schemas into one view and splits global queries into local ones.

Semantic heterogeneity

The hardest differences are not technical but about meaning. This is semantic heterogeneity: the sites store data about the same real-world things with different structures or interpretations. Typical conflicts:

  • Naming: the same concept has different names (customer against client), or different concepts share a name (balance meaning the account balance in one site and the invoice balance in another).
  • Units and formats: prices in euros or dollars, dates as 2025-03-02 or 02/03/2025, weights in kg or lb.
  • Coding: gender stored as M/F, 0/1 or male/female.
  • Structure: one site stores an address as a single text column, another as street, city and postal code in a separate table.

Resolving them is the job of schema integration, which the schema design strategies lesson covers.

Architectures: client-server and peer-to-peer

The sites can be organized in two basic ways:

  • Client-server: a few server sites hold the data and run the DBMS; many client machines send requests. Responsibility is split clearly (clients handle presentation, servers handle storage and queries), but the servers can become a bottleneck.
  • Peer-to-peer: all sites are equal. Every site stores part of the data, can act as a client or a server and can accept any query, forwarding sub-requests to the others. It scales and has no single point of failure, but needs more coordination for naming, replication and transactions.
  • Multidatabase architecture (the federated case above) sits on top of existing autonomous databases and gives them a common global schema.

Fragmentation

To distribute a relation we first cut it into fragments, then store each fragment at one or more sites. A good fragmentation obeys three rules:

  1. Completeness: every data item of the relation appears in at least one fragment, so nothing is lost.
  2. Reconstruction: a relational operation can rebuild the original relation from the fragments.
  3. Disjointness: (for horizontal fragments) an item appears in only one fragment. Replication, if wanted, is added explicitly in the allocation step, not by accident in the fragmentation.

Horizontal fragmentation

Horizontal fragmentation splits a relation into subsets of its rows. Each fragment is defined by a selection, ฯƒ condition (R), and keeps all the columns. Reconstruction is the union of the fragments. The usual criterion is where the data is used: customers of the EU region at the European site, and so on. A common variant is derived horizontal fragmentation: the orders table is fragmented the same way as the customers it references (by a semijoin with the customer fragments), so each customer's orders live at the same site as the customer.

SQL Horizontal fragmentation and reconstruction

Press Run (or Ctrl + Enter) to see the result here.

The view customer_global is the idea of distribution transparency in miniature: users query one name and never see the three fragments. The empty result of the check query shows completeness and reconstruction. The last query shows the performance payoff: a question about EU customers is answered entirely by one fragment, which in a real system means one site and no network traffic to the others.

Vertical fragmentation

Vertical fragmentation splits a relation by columns. Each fragment is a projection, ฯ€ attributes (R), and every fragment must repeat the primary key (or a tuple id) so that the original rows can be rebuilt. Reconstruction is a join on that key. Typical reasons are to keep frequently used small columns separate from big rarely used ones (a notes field or an image), or to keep sensitive columns at a more protected site.

SQL Vertical fragmentation and reconstruction

Press Run (or Ctrl + Enter) to see the result here.

Mixed (hybrid) fragmentation

When one split is not enough you apply the other to the result. First cut customer vertically into core and notes, then cut customer_core horizontally by region. The fragments are described by a small tree, and the original relation is rebuilt bottom-up: union the horizontal pieces, then join the vertical pieces.

flowchart TB
  C["customer (global relation)"]
  C -->|"vertical: id, name, region, credit_limit"| Core["customer_core"]
  C -->|"vertical: id, notes"| Notes["customer_notes"]
  Core -->|"horizontal: region = EU"| E["core_eu"]
  Core -->|"horizontal: region = US"| U["core_us"]
  Core -->|"horizontal: region = ASIA"| A["core_asia"]

Mixed fragmentation: a vertical split followed by a horizontal split of one of the results.

Allocation

Allocation decides which site stores which fragment. There are three basic strategies, and the replication variants are explained in Replication types and schemes:

  • No replication (partitioned): each fragment is stored at exactly one site. Storage is minimal and updates are simple, but a site failure makes its fragments unavailable and a remote user pays network latency on every access.
  • Full replication: every site holds a complete copy. Reads are local and fast and the system survives site failures, but every update must reach every site, and storage is multiplied.
  • Partial replication: each fragment is stored at some sites, typically those that use it most. This is the common compromise: hot reference data is copied widely, large fragmented tables are kept near their users.

The allocation depends on the workload: which queries run where, how often, and how many are reads versus updates. A relation that is read everywhere and rarely changed is a good candidate for replication; one that is updated constantly and mostly used at one site should live at that site.

Transparency

A distributed DBMS tries to hide the complexity. The levels of transparency are usually listed as:

  • Fragmentation transparency: users query the global relation and do not know it is fragmented (the view in the example).
  • Location transparency: users know there are fragments but not where they are stored.
  • Replication transparency: users do not know that copies exist; the system keeps them consistent.
  • Naming transparency: every object has a unique name across all sites, whichever site asks for it.
  • Failure and concurrency transparency: transactions look atomic and isolated even across sites (the job of two-phase commit and distributed locking).

Distributed query processing: where does the data move?

The dominant cost of a distributed query is not the CPU or the disk but moving data over the network. When a query joins tables stored at different sites, the optimizer chooses among plans that ship different amounts of data. Consider customers at site A and orders at site B, and a query at A asking for the total order value of EU customers. A semijoin reduces what must travel: send only the join column (the ids of the EU customers) to the other site, and get back only the matching rows.

Python Comparing data shipping plans

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All three plans give the same answer, yet they move 5000, 251 and 1500 rows. Plan 2 wins here because the result is a single aggregate that site B can compute itself. If site A needed the full joined rows, plan 3 would beat plan 1 by more than three to one. A distributed optimizer weighs these costs using statistics, together with the usual local costs from cost-based optimization. Fragment pruning (skipping fragments that cannot match the predicate, as the EU query did) is the cheapest optimization of all.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What distinguishes a heterogeneous distributed database from a homogeneous one?

    In a homogeneous system every site runs the same DBMS with compatible schemas. Heterogeneous (federated) systems combine different products or models and need wrappers and a global schema.
  2. 2. Which is an example of semantic heterogeneity?

    Semantic heterogeneity is about differing meaning, units, names or codes for the same data, not about hardware or network differences.
  3. 3. How is a vertically fragmented relation reconstructed?

    Vertical fragments are projections that each keep the key, so a join on the key puts the columns back together. Horizontal fragments are rebuilt with a union.
  4. 4. Which rule says that no data may be lost by fragmentation?

    Completeness requires that every data item of the original relation appears in at least one fragment.
  5. 5. Why is a semijoin useful in a distributed query?

    Network transfer usually dominates distributed query cost. A semijoin ships the small set of join values instead of a whole table.

Summary

  • A distributed database spreads logically related data over networked sites; a DDBMS makes it look like one database.
  • Homogeneous systems run one DBMS everywhere; heterogeneous or federated systems combine different products with wrappers, a mediator and a global schema, and must resolve naming, unit, coding and structural (semantic) conflicts.
  • Architectures are client-server, peer-to-peer or multidatabase.
  • Horizontal fragments split rows (rebuilt by union), vertical fragments split columns and repeat the key (rebuilt by join), and mixed fragmentation applies both; a good fragmentation is complete, reconstructible and disjoint.
  • Allocation chooses where fragments live: no replication, full replication or partial replication, based on the workload.
  • Transparency hides fragmentation, location, replication and failures; the main cost of distributed queries is data shipped over the network, which semijoins and fragment pruning reduce.

Next: CAP, BASE and Consistency Models.