Friday, March 31, 2017

Primary horizontal fragmentation solved exercise

Primary horizontal fragmentation solved exercise, how to find simple predicates and min-term predicates, primary horizontal fragmentation of a relation in distributed database

Consider the following relation schema and the set of applications that are frequently accessing the relation;
DEPARTMENT (DeptNo, DeptName, School, Phone)
Application 1: Find the department details of SITE school.
Application 2: Find the phone of ‘Digital communication’ department.
Fragment the given table horizontally according to the requirement and check for correctness of the fragments.

Simple predicates:
From the applications, we can identify the simple predicates. The first application access the department table using the school name. Hence, the simple predicate is School = ‘SITE’. The second application access the data on the condition DeptName = ‘Digital communication’. Hence, our set of simple predicates Pr can be written as follows;
Pr = { p1: School = ‘SITE’, p2: DeptName = ‘Digital communication’ }

Min-term predicates:
Min-term predicates can be derived from set of simple predicates by ANDing and NEGATing all the simple predicates as follows;
m1 = { School = ‘SITE’ DeptName = ‘Digital communication’ }
m2 = { School = ‘SITE’ ¬(DeptName = ‘Digital communication’) }
m3 = { ¬( School = ‘SITE’) DeptName = ‘Digital communication’ }
m4 = { ¬(School = ‘SITE’) ¬(DeptName = ‘Digital communication’) }

We have negated each simple predicate so as not to miss any records from the tables. For example, when we mention school = ‘SITE’ it implicitly means that there are other schools other that SITE. And the condition school = ‘SITE’ includes SITE school and the negations of this i.e., school <> ‘SITE’ will include all the other schools.
Primary Horizontal Fragmentation:
The table DEPARTMENT can be horizontally fragmented using the Primary Horizontal Fragmentation technique using these min-term predicates m1, m2, m3 and m4. For example, the fragment 1 stores the data as per the min-term predicate m1 using the following query;
SELECT * FROM Department WHERE School = ‘SITE’ AND DeptName = ‘Digital communication’;
At the end of fragmentation, we have 4 fragments of Department table viz. DEPT1, DEPT2, DEPT3, and DEPT4.

Correctness of Fragmentation:

After fragmenting a table, the very next step is to check whether the fragments are correct or not. This could be verified using the following correctness properties;
Completeness – Each record of table DEPARTMENT should be found in any one of the fragments DEPT1, DEPT2, DEPT3, and DEPT4. As our simple predicates are complete and minimal, we can say that the fragments are complete.
Reconstruction – We must be able to reconstruct DEPARTMENT from the fragments DEPT1, DEPT2, DEPT3, and DEPT4. The following relational algebra operation on fragments will get us DEPARTMENT;
Dis-jointness – The result of the intersect operation between fragments should give me a empty set as result;
All these three properties are verified. Hence, our primary horizontal fragmentation is correct.


No comments:

Post a Comment

Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents

data recovery