6.5k views

Consider the schema $R=(S,T, U, V)$ and the dependencies $S \rightarrow T, T \rightarrow U, U \rightarrow V$ and $V \rightarrow S$. Let $R = (R1\text{ and } R2)$ be a decomposition such that $R1 \cap R2 \neq \phi$. The decomposition is

1. not in $2NF$
2. in $2NF$ but not $3NF$
3. in $3NF$ but not in $2NF$
4. in both $2NF$ and $3NF$
edited | 6.5k views

$R_1 \cap R_2 \neq \phi.$ This makes the decomposition lossless join, as all the attributes are keys, $R_1 \cap R_2$ will be a key of the decomposed relations (lossless condition says the common attribute must be a key in at least one of the decomposed relation).  Now, even the original relation $R$ is in $3NF$ (even $\text{BCNF}$)as all the attributes are prime attributes (in fact each attribute is a candidate key).  Hence, any decomposition will also be in $3NF$ (even $\text{BCNF}$). Option $D$.

PS: Decomposition in $3NF$ means decomposed relations are in $3NF$. But when we consider any decomposed relation, we must also include any FD which are being implied by the original relational schema. For example, in a decomposed relation $STU,$ there will be a FD $U\to S$ as well.
edited by
0
@Arjun : I agree since all the attributes are Candidate Keys. Now whatever the decomposition is, the decomposed relations will be in BCNF. But still there is a confusion which you stated above that Normal Form is on Relation rather decomposition. Till now whatever books i read they all suggested Normal Form on Relation rather than decomposition.
+2
Decomposition-  means for decomposed relations. The question was not correct earlier and my comments were made then.
+1

@Arjun Sir, Is this question correctly copied ?

check question number 2.7 here http://gateforum.com/wp-content/uploads/2013/01/CS-1999.pdf

which says R1 ∩ R2 =

+1
0
If some 1 would clarify a lil doubt i would be grateful. The attributes are prime attributes in the parent relation but suppose the decomposition is done as R1 :S,T,U R2 :U,V . then in this case the relation in R1 U will not be prime attribute right ? because there is no V. So from transitive clousure S woud be the candidate key.Then wouldnt this relation  be under transitive dependency as S->T and T -> U.U is non prime and T is not key ? Can some 1 explain !!!
+1
In STU, S, T and U are keys and in UV, U and V are keys. There aren't any composite attributes- so no chance of partial dependency.
0
Here how can be S,T,U will be keys in decomposed relation STU ?? and U, V are the keys in relation UV ???
+10
In $STU$, $S\to T, T\to U, U \to S$. The last dependency coming from transitive dependency $U\to V, V\to S$. In $UV, U\to V, V\to U$, again the second one is via transitive dependency. But in both cases transitive dependency is involving only prime attributes and hence not violating 3NF.
+1
@arjun sir :had the condition been $R1 \cap R2=\phi$

then relation will be in $2NF$ but not in $3NF$.right?

Example-:$R_{1}=STU ,R_{2}=V$
0
no both would be in highest normal from i.e.BCNF reason of R1(STU) is discussed above and in R2(v) there would be no functional dependency so it would also be in highest normal form
+1
but BCNF decomposition cannot be lossy .since there is no attribute in common in R1(STU) and R2=(V)

how can they be in BCNF
0

If R1={S,T,U}

R2={V}

How can functional dependencies be preserved in this?
0
i think in this we lost the dependencies   U->V and  V->S and also it is lossy decomposition
0
Here it is lossless decomposition. And moreover it is dependency preserving.

Dependency preservation is not mandatory for normalization. (it is mandatory for 3nf).
0
For lossless join we will only check for R1 intersection R2 == {} or not??

if no lossless join?

As i know for lossless join it should be key in one of the relation.
0

#Basic Confusion

R(A,B,C)

FD{ A>B,B>C }

decomposed into  R1(AC) and R2(BC). if we see directly no fd satisfying for R1.but transitively A>C can be there and for R2 it will be B>C.

R1(AC)             R2(BC)

FD { }                FD={B>C}

So what is the way to add Fd to decompose table? through closure of attribute??

0
can any1 help me with this @Shaik Masthan, @sushmita or any1,

R = {s, t, u, v}

suppose R1 = {s, t, u} & R2 = {u, v}

for R1 : s->t, t->u        for R2 : u->v

this will be lossless decomposition and dependency not preserving

but R1 is not in 3NF, how ? where am i wrong

0

@Arjun sir thanks , this cleared my doubt.

$U \rightarrow V$ and  $V\rightarrow S$ implies  $U\rightarrow S$

this is not something given but to be concluded by us, bcoz it doesn't affect the FD's (ofcourse this extra conclusion will not let FD's  remain minimal) but that's okay.

Answer : In both 2NF and 3NF

Dependencies are

S --> T, T --> U, U -->V  V --> S

S+ = STUV          U+ = UVST

T+ = UVST          V+ = VSTU

There is no Partial Dependencies here So it is in 2 NF

RHS of every Dependencies  is a Key as well as all are Prime Attributes So it is in 3 NF.

0
@shekhar sir,

here  the decomposition is not lossless .. rt?
0
whenever extra tuples are added then we call it dataloss and called it lossy decomposition
0
so, this is lossy..
0
yes
0
The question is about the decomposition and not about the relation R. Obviously R is in 3NF but I think the decomposition is lossy which is not allowed in 2NF, 3NF.
0

Decomposition is not lossy because of given in the question that intersection of two relations is not empty.

Which means there is something in the intersection and by looking at the FD's it definitely become Lossless and Dependency preserving too.

R1 ∩ R2 != ∅. This makes the decomposition lossless join and as all the attributes are prime, so whatever is the decomposition, it will be 2NF and 3NF. So, Ans will be option d.

0
here it's R1 ∩ R2 =∅ .i.e, lossy
(d) both in 2nf and 3nf

since r1 and r2 does not have any common attributes , and if we decomse it to relation having 2 attributes, then they are by default in 3nf , Suppose if we decompose r1 with 1 attribute and r2 with 3 attributes, since all of them are dependent all of them could be a prime attribute in this case also they are in 3nf, since they are in 3nf, 2nf by default satisfy
+3
since all attributes are prime attributes (in fact candidate keys) can't we straight away say that R1 and R2 are in 3NF?
0
if a decomposition is lossy, then is it a valid decomposition ?
0
@Danish No. But does that help?
0
^ cannot view the above link (ristricted)
+2
@Arjun Sir I read that for a lossless decomposition of a relation R into R1 and R2, R1(inter)R2->R1 or R1(inter)R2->R2 But here R1(inter)R2 is phi, so how can it be lossless ? and if it is not lossless then how can it be a valid decomposition ? and if its not a valid decomposition how can it be 2nf or 3nf ?
+1
Obviously it is lossy decomposition. But I don't know to answer the remaining questions. Because I assume a normal form is applied to a relation and not to a decomposition. I searched a bit but couldn't find a solid reference saying either way. Have you seen anywhere saying that a lossy decomposition produces relations which won't have a particular normal form?
+4

Sir this is what  found in elmasri

"Normal forms, when considered in isolation from other factors, do not guarantee a good database design. It is generally not sufficient to check separately that each relation schema in the database is, say, in BCNF or 3NF. Rather, the process of normalization through decomposition must also confirm the existence of additional properties that the relational schemas, taken together, should possess. These would include two properties:

The nonadditive join or lossless join property, which guarantees that the spurious tuple generation problem discussed in Section 15.1.4 does not occur with respect to the relation schemas created after decomposition.
The dependency preservation property, which ensures that each functional dependency is represented in some individual relation resulting after decomposition.

The nonadditive join property is extremely critical and must be achieved at any cost, whereas the dependency preservation property, although desirable, is sometimes sacrificed."

+2
Yes. Thats true. But whether a lossy decomposed relation do not have a normal form is not clear, at least for me :)
0

@Aravind

"since r1 and r2 does not have any common attributes"

On your this statement please tell me how R1 and R2 doesn't have something common.

as clearly mentioned in the question that R1∩R2≠ϕ means their intersection is not empty. right ?

so they have something common. Isn't it?

since no partial dependency and non key to non key

every determinant is deriving all atributes so in bcnf

by default 1nf

so it is all 1nf,2nf,3nf, and bcnf
If all the attributes are candidate keys, then any subset of attributes will be a super key

Whatever FD you can form, your LHS will have a subset of attributes

From above stataments, we can say that any FD that can be formed will have LHS as a super-key

This is good enough to say that the relation is in BCNF ...

This is also applicable even after the decomposition of relation irrespective of what common attributes we have (even if there is no common attributes, though lossy decompositions are not recommended)

2