Derived Horizontal Fragmentation in Distributed Database Systems DDBS

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.

ADDRESS1 = ADDRESS ⋉  STUDENT1

ADDRESS2 = ADDRESS ⋉  STUDENT2

ADDRESS3 = ADDRESS ⋉  STUDENT3

ADDRESS4 = ADDRESS ⋉  STUDENT4

This will result in four fragments of ADDRESS where the STUDENT address of all STUDENTs of fragment STUDENT1 will go into ADDRESS1, and the STUDENT address of all STUDENTs of fragment STUDENT2 will go into ADDRESS2, 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 {R1, R2, …, Rn} and {T1, T2, … , Tn}, there should be one common attribute such as A. Then, for each tuple of relation Ri, there should be a tuple Ti 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 STUDENTi and Addressi are the same. For example, the value present in RollNo of STUDENT1 is also and only present in Address1, 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