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

Wednesday, March 21, 2018

Horizontal fragmentation in distributed database design exercise

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    











Thursday, March 8, 2018

Three Phase Commit (3PC) protocol in distributed database failure recovery

Three Phase Commit (3PC) protocol in distributed database failure recovery


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. 

***********

Go to Advantages and Disadvantages of 2PC page




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.







Saturday, May 13, 2017

What are the correctness rules for verifying fragmentation

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

***************
Go to Distributed Database home page

 

What are the correctness rules of fragmentation in distributed database





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