Conflict Serializability

Find out conflict serializability for the given transactions

T1	T2	T3
R(X)
		R(Y)
		R(X)  t1 <- t3
	R(Y) t3 <- t2
	R(Z) t1 <- t2
		W(Y)
	W(Z) t1 <- t2 and  t1 <- t2
R(Z)
W(X)
W(Z)

Step 1: 

Conditions for read(R) and write(W)

R-W

W-R

W-W ->W-R

        ->W-W

Step 2:

Check out the conflict pairs in other transactions and then draw edges using Precedence Graph.

Precedence Graph:

Therefore the indegree of T1=2

Therefore the indegree of T2=0

Therefore the indegree of T3=1

Step 3:

Remove the indegree of T2 whose degree is 0 then the Precedence graph

Therefore the transaction to the given set is 

T2 --- T3 --- T1

Since there is no loop or cycle so it is conflict serializable which is serializable consistent.

T1 --- T2 --- T3

T1 --- T3 --- T2

T2 --- T1 --- T3

T2 --- T3 --- T1

T3 --- T1 --- T2

T3 --- T2 --- T1

Question:

check out whether the given schedule is conflict serializable or not  

T1	T2	T3
R(A) t2<-t1 t3<-t1
	W(A) t1<-t2
W(A) t3<-t1
		W(A)

Step 1: 

Conditions for read(R) and write(W)

R-W

W-R

W-W ->W-R

        ->W-W

Step 2:

Check out the conflict pairs in other transactions and then draw edges using Precedence Graph.

Precedence Graph:

Loop occurred i.e T1 --T2 -- T2 --T1 means it is not a conflict serializable

Normalization - Problem

Rules to check out in each Normalization Form layers:

BCNF:

1. It should be 3NF

2. Left hand side must be a candidate key or super key or primary key.

3NF:

1. It should be 2NF

2. Left hand side must be a candidate key or Right hand side must be a Prime Attribute 

2NF:

1.It should be 1NF

2.Left hand side must be a proper subset of a candidate key and Right hand side must be a Non - Prime Attribute 

QUESTION) 

Schema 1:Registration( rollno, course) 

given Functional Dependency { rollno->course }

Answer:

Since Left hand side rollno is a Primary key so it is in BCNF 

Schema 2:Registration( rollno, courseid, email) 

given Functional Dependency{ rollno,courseid -> email, 

                                             email->rollno }

Answer:

candidate key ={rollno,courseid}

prime attributes = {rollno,courseid}

non-prime attribute = { email }

Left hand side rollno is a candidate key or Right hand side  email (non prime) rollno (prime) so it is in 3NF 

Schema 3:Registration( rollno, courseid,marks,grade )

given Functional Dependency { rollno, courseid -> marks, grade,

                                              marks ->grade }

Answer:

candidate key ={rollno,courseid}

prime attributes = {rollno,courseid}

non-prime attribute = { marks,grade }

Left hand side marks must be a proper subset of a candidate key and Right hand side grade must be a Non - Prime Attribute so it in 2NF 

Schema 4:Registration( rollno, courseid, credit) 

given Functional Dependency{ rollno, courseid->credit,

                                             courseid->credit }

Answer:

candidate key ={courseid}

prime attributes = {rollno,courseid}

non-prime attribute = { credits }

Left hand side credit must be a proper subset of a candidate key and Right hand side rollno and courseid must be a Non - Prime Attribute so it in 1NF 

QUESTION) 

For the Given R(ABCDEF) Check out the highest Normal form for the given Functional Dependency

{ AB->C , C->DE , E->F , F->A }

Answer:

Step 1: Find all the candidate keys in relation

(BA) ⁺=BACDEF

(BC) ⁺=BCDEFA

(BD) ⁺=BD

(BE) ⁺=BEFACD

(BF) ⁺=BFACDE

Therefore, the candidate keys are {BA, BC, BE, BF}

Step 2: Write down all the prime attributes

{A, B, C, E, F}

Step 3: Write down all the non-prime attributes

{D}

Now to check the highest normal form we start with BCNF

Rules to check out in each NF layer:

BCNF:

1. It should be 3NF

2. Left hand side must be a candidate key or super key or primary key.

3NF:

1. It should be 2NF

2. Left hand side must be a candidate key or Right hand side must be a Prime Attribute 

2NF:

1.It should be 1NF

2.Left hand side must be a proper subset of a candidate key and Right hand side must be a Non - Prime Attribute 

Note:

1NF is a subset of 2NF

2NF is a subset of 3NF

3NF is a subset of BCNF

BCNF is a subset of 4NF

4NF is a subset of 5NF 

Given Functional Dependency	AB->C	C->DE	E->F	F->A
BCNF	ü	X	X	X
3NF	ü	X	ü	ü
2NF	ü	X	ü	ü
1NF	ü	ü	ü	ü