Derived Horizontal Fragmentation

Today, in this fresh new article, we will cover the following topics;

1. Derived Horizontal Fragmentation.
2. Owner Table in Derived Horizontal Fragmentation.
3. Member Table in Derived Horizontal Fragmentation

In Derived Horizontal Fragmentation we fragment a table based on the constraints defined on another table. Both tables are linked with each other with the help of primary and foreign key and must establish the Owner-Member relation.  We use the primary horizontal fragmentation technique when we want to horizontally fragment a table which is not dependent on any other owner table. But in most of the cases, we need to fragment a database as a whole. For example, consider a relation which is connected with another relation using foreign key concept. That is, whenever a record is inserted into the member table, the foreign key column value of the inserted record must be verified for its availability in its own table. In such a condition, we cannot fragment the parent table and the child table.

Owner Table in Derived Horizontal Fragmentation

Owner table is a parent table to which we apply the constraint.

Member Table in Derived Horizontal Fragmentation

Member table is a child table that can be fragmented but by following the constraints of the parent table.

If we fragment the tables separately, then for every insertion of records the table must verify the existence of one such value in the parent table. Hence, for this case, the Primary Horizontal Fragmentation would not work.

Let’s consider an example, where an international university maintains the information about its STUDENTs. They store information about the STUDENT in STUDENT table and the STUDENT addresses in ADDRESS table as follows;

STUDENT(RollNo, Name, Marks, Country)

ADDRESS(RollNo, Address)

Table 1: STUDENT table

Table 2: Address Table

If the organization would go for fragmenting the relation STUDENT on the Country attribute, it needs to create 4 fragments using horizontal fragmentation as mentioned in table below;

Table 3: Horizontal fragments of Table 1 on Country attribute

Now, it is necessary to fragment the second relation ADDRESS based on the fragment created in STUDENT relation. The fragmentation of ADDRESS is done as follow as a set of semi-joins as follows.

ADDRESS₁ = ADDRESS ⋉  STUDENT₁

ADDRESS₂ = ADDRESS ⋉  STUDENT₂

ADDRESS₃ = ADDRESS ⋉  STUDENT₃

ADDRESS₄ = ADDRESS ⋉  STUDENT₄

This will result in four fragments of ADDRESS where the STUDENT address of all STUDENTs of fragment STUDENT₁ will go into ADDRESS₁, and the STUDENT address of all STUDENTs of fragment STUDENT₂ will go into ADDRESS₂, and so on.

The resultant fragment of ADDRESS will be the following;

Table 4: Showing fragment 1 of “address” table

Table 5: Showing fragment 2 of “address” table

Table 6: Showing fragment 3 of “address” table

Table 7: Showing fragment 4 of “address” table

Checking the fragments for correctness in Derived Horizontal Fragmentation

Completeness: The completeness of a derived horizontal fragmentation is complex than primary horizontal fragmentation. The reason for this complexity is because the predicates used are determining the fragmentation of two different tables/relations. Formally, for fragmentation of two relations R and T, such as {R₁, R₂, …, R_n} and {T₁, T₂, … , Tn}, there should be one common attribute such as A. Then, for each tuple of relation R_i, there should be a tuple T_i which has a common value for A. This concept is called referential integrity concept.

The derived fragmentation of Address is complete. Because the value of the common attributes RollNo for the fragments STUDENT_i and Address_i are the same. For example, the value present in RollNo of STUDENT₁ is also and only present in Address₁, etc.

Reconstruction: Reconstruction of the pre-existing tables is possible by a union operation.

Disjointness:  If the minterm predicates are mutually exclusive then the disjointness rule is satisfied for Primary  Horizontal fragmentation.

Topic Covered

Derived Horizontal Fragmentation in Distributed Database Systems DDBS