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)

RollNo	NAME	MARKS	COUNTRY
01	Fazal	22	IRAQ
02	Abdul	66	Italy
03	Sameed	77	UK
04	Shahzeb	90	China
05	Mumraiz	66	China

Table 1: STUDENT table

 

RollNo	Address
01	City A, IRAQ
01	City A, UK
02	City D, Italy
02	City A, Pakistan
03	City D, IRAQ
04	City D, Iraq
04	City A, Pakistan
05	City B, China

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;

STUDENT1		ROLLNO	NAME	MARKS	COUNTRY
		C001	Fazal	22	IRAQ
STUDENT2		ROLLNO	NAME	MARKS	COUNTRY
		C002	Abdul	66	Italy
STUDENT3		ROLLNO	NAME	MARKS	COUNTRY
		C010	Mumraiz	66	China
		C004	Shahzeb	90	China
STUDENT4		ROLLNO	NAME	MARKS	COUNTRY
		C003	Sameed	77	UK

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;

RollNo	Address
01	City A, IRAQ
01	City A, UK

Table 4: Showing fragment 1 of “address” table

RollNo	Address
02	City D, Italy
02	City A, Pakistan

Table 5: Showing fragment 2 of “address” table

RollNo	Address
04	City D, Iraq
04	City A, Pakistan
05	City B, China

Table 6: Showing fragment 3 of “address” table

RollNo	Address
03	City D, IRAQ

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