Showing posts with label Distributed Database. Show all posts
Showing posts with label Distributed Database. Show all posts

Horizontal fragmentation in distributed database design exercise

Question:
Given the following relation EMP and the predicates p1: SAL > 23000, p2: SAL < 23000
 ID Name Salary 1289 8907 7643 0988 6543 0986 2345 Guru Siva Shalini Kavin Surya Kavitha Anees 12000 67050 51980 23000 28760 23000 29999
EMP relation
a) Perform a horizontal fragmentation of the table based on the given predicates.
b) Is this a correct fragmentation?
c) If the answer to (b) is no, explain why, and give the predicates that would correctly fragment the table.

Solution:
a) Horizontal fragmentation of given table as per the given predicates is as follows;
 ID Name Salary 8907 7643 6543 2345 Siva Shalini Surya Anees 67050 51980 28760 29999
Fragment 1: According to predicate P1 (Salary > 23000)
SQL query: SELECT * FROM emp WHERE salary > 23000

 ID Name Salary 1289 Guru 12000
Fragment 2: According to predicate P2 (Salary < 23000)
SQL query: SELECT * FROM emp WHERE salary < 23000

b) This fragmentation is not correct. We have fragmented the given table into two fragments. Because none of the predicates include the equality condition, the records with the salary value 23000 has not listed in either fragments.
The following two records from the base table are not available in none of the fragments. Hence, the fragmentation that we did is incorrect.
 ID Name Salary 0988 0986 Kavin Kavitha 23000 23000

c) When we fragment the relation using the given predicates we end up excluding one tuple, which violates the completeness rule for correct fragmentation. Correct predicates should be one of the following;

• P1: SAL >= 23000, P2: SAL < 23000
or

• P1: SAL > 23000, P2: SAL <= 23000.
**************

distributed database solved exercise
fragmentation in distributed database
horizontal and vertical fragmentation in distributed database
how to fragment a relation horizontally
fragment using simple predicates
horizontal fragmentation solved exercises

Three Phase Commit (3PC) Protocol

Two Phase Commit (2PC) is one of the failure recovery protocols commonly used in distributed database management system. It has a disadvantage of getting blocked under certain circumstances. For example, assume a case where the coordinator of a particular transaction is failed, and the participating sites have all sent <READY T> message to the coordinator. Now, participating sites do not have either <ABORT T> or <COMMIT T>. At this stage, no site can take a final decision on its own. Only solution is to wait for the recovery of the coordinator site. Hence, 2PC is a blockingprotocol.

3PC is a protocol that eliminates this blocking problem on certain basic requirements;

• No network partitioning
• At least one site must be available
• At most K simultaneous site failures are accepted
2PC has two phases namely voting phase and decision phase. 3PC introduces pre-commit phase (serves as a buffer phase) as the third phase. 3PC works as follows;

Phase 1 (WAIT/VOTING):
Transaction Coordinator (TC) of the transaction writes BEGIN_COMMIT message in its log file and sends PREPARE message to all the participating sites and waits.
Upon receiving this message, if a site is ready to commit, then the site’s transaction manager (TM) writes READY in its log and send VOTE_COMMIT to TC.
If any site is not ready to commit, it writes ABORT in its log and responds with VOTE_ABORT to the TC.

Phase 2 (PRE-COMMIT):
If TC received VOTE_COMMIT from all the participating sites, then it writes PREPARE_TO_COMMIT in its log and sends PREPARE_TO_COMMIT message to all the participating sites.
On the other hand, if TC receives any one VOTE_ABORT message, it writes ABORT in its log and sends GLOBAL_ABORT to all the participating sites and also writes END_OF_TRANSACTION message in its log.
On receiving the message PREPARE_TO_COMMIT, the TM of participating sites write PREPARE_TO_COMMIT in their log and respond with READY_TO_COMMIT message to the TC.
If they receive GLOBAL_ABORT message, then TM of the sites write ABORT in their logs and acknowledge the abort. Also, they abort that particular transaction locally.

Phase 3 (COMMIT/DECIDING):
If all responses are READY_TO_COMMIT, then TC writes COMMIT in its log and send GLOBAL_COMMIT message to all the participating sites’ TMs. The TM of those sites then writes COMMIT in their log and sends an acknowledgement to the TC. Then, TC writes END_OF_TRANSACTION in its log.

***********

How does 3PC protocol work?
How does three phase commit protocol handles transactions failure recovery in ddbms?
Example of 3PC protocol
What is the third phase that included to eliminate blocking problem?
Why 3PC is a non-blocking transaction failure recovery protocol.

What are the correctness rules for verifying fragmentation? How do we verify the correctness of fragmentation?

Correctness rules of fragmentation

Fragmentation is the major concept in distributed database. We fragment a table horizontally, vertically, or both and distribute the data to different sites (servers at different geographical locations). While we perform the fragmentation process, as a result we expect the following as outcomes;

• We should not lose data because of fragmentation
• We should not get redundant data because of fragmentation
Hence, to ensure these properties we need to verify that whether we performed the fragmentation correctly or not. For this verification we use the correctness rules. The rules are as follows;

• Completeness - To ensure that there is no loss of data due to fragmentation. Completeness property ensures this by checking whether all the records which were part of a table (before fragmentation) are found in at least one of the fragments after fragmentation.
• Reconstruction - This rule ensures the ability to re-construct the original table from the fragments that are created. This rule is to check whether the functional dependencies are preserved or not.
If a table R is partitioned into fragments R1, R2, …, Rn, then Reconstruction insists the following;
R = R1 U R2 U … U Rn

• Disjointness - This rule ensures that no record will become a part of two or more different fragments during the fragmentation process.
If a table R is partitioned into fragments R1, R2, …, Rn, then Disjointness insists the following;
R1 ∩ R2 ∩ … ∩ Rn = Null set

***************