GATE CSE 2009 | Question: 56

Question

Consider the following relational schema:

• $\text{Suppliers}(\underline{\text{sid:integer}},\text{ sname:string, city:string, street:string})$ 
• $\text{Parts}(\underline{\text{pid:integer}}, \text{ pname:string, color:string})$ 
• $\text{Catalog}(\underline {\text{sid:integer, pid:integer}}, \text{cost:real})$

Assume that, in the suppliers relation above, each supplier and each street within a city has unique name, and (sname, city) forms a candidate key. No other functional dependencies are implied other than those implied by primary and candidate keys. Which one of the following is $\text{TRUE}$ about the above schema?

• A. The schema is in $\text{BCNF}$
• B. The schema is in $\text{3NF}$ but not in $\text{BCNF}$
• C. The schema is in $\text{2NF}$ but not in $\text{3NF}$
• D. The schema is not in $\text{2NF}$

Comments

bro @Golla Sai Venkatesh every primary key is a ck which is superkey and minimal too . and (sname, city) they gave as ck we are not explicitly assuming this thing from our side.

---

@satvik_t The first statement says that in the schema, there are only those FDs whose LHS is a SK.

And as for your second doubt, no city-->street and city-->name are not valid fds. They are violating the concept of FDs.

City	Street
Mumbai	A
Mumbai	B

 

Now, according to the question yes Street names are unique within a city. But look at this instance:

Using Mumbai can you determine street? Like there are 2 different street values for Mumbai which is violation of FD. If there are two tuples with same A values, then their corresponding B values should be same. If their corresponding B values are different, then the FD will be invalid.

 

Same goes for City-->Sname too.

 

---

"each supplier and each street within a city has unique name"

each supplier, within a city - unique name that means $(sname, city)$ is a candidate key.

each street, within a city - unique name that means $(street, city)$ is also a candidate key.
 

Answer 1

The non-trivial $\text{FD}$s are 

1. (sname, city) $\to$ street
2. sid $\to$ street
3. (sname, city) $\to$ sid
4. sid $\to$ sname
5. sid $\to$ city

For all these, $\text{LHS}$ is a super key and hence $\text{BCNF}$ condition is satisfied. But we have some more dependencies here:

"each supplier and each street within a city has unique name"

This basically means each supplier in a city has unique name making (sname, city) determine sid and hence making it a candidate key. Each street within a city also has a unique name and so (street, city) is also a candidate key. Even then with all $3$ candidate keys (for Suppliers schema), for any $\text{FD}$, the $\text{LHS}$ is a super key here, and hence the relation schema (for other two relations it is straight forward) is in $\text{BCNF}$.

http://db.grussell.org/section009.html

Correct Answer: $A$

Comments

@Arjun

Sir,

each supplier and each street within a city has unique name

For this you have mentioned below

 

This means when supplier name cannot repeat within a city and same for street.

CITY -> Street,Supplier is wrong as it basically says all street and supplier must be same for a city.

 My question is this : Does that mean that for each CITY Street or Supplier can have multiple values.

For Example –

CITY = “ Delhi”  Street = “MG Road” Supplier = “ABC”

CITY = “ Delhi”  Street = “Nehru Road” Supplier = “EFG”

CITY = “ Mumbai” Street = “MG Road” Supplier = “EFG”

CITY = “ Mumbai” Street = “Nehru Road” Supplier = “ABC”

Is above valid ? If yes , doesn’t it means that they form Multi-valued Dependency?

Please correct if I am wrong.

---

@Arjun Sir @srestha ma’am 

Is the table represent the above question statement…..

sid	sname	city	street
1	Amit	Pune	A
2	Ravi	Pune	B
3	Ravi	Kolkata	C
4	Amit	Kolkata	B
5	Soham	Pune	E

here, sid→ sname,sid→ city,sid→ street;

(sname,city)→ sid;  (sname,city)→ street;

Also for the statement in the suppliers relation above, each supplier and each street within a city has unique name  means (Look at above table)

(street,city)→ sname;  (street,city)→ sid;

Thank you for reading…..

  

---

how did we say that primaru key is pid, its not given in question. right? so should we generally consider the ids as primary key?

 

Answer 2

"No other functional dependencies are implied other than those implied by primary and candidate keys"

This line is sufficient to indicate that we have superkeys on LHS always which is the necessary condition to be the relation in BCNF.

So, option A is correct.

Comments

Yes true. I don’t get it why people are bothered about other things :(

---

@Deepak Poonia sir, can we declare directly ??

Answer 3

From the given data the FDs will be ,

(Sid, Street) $\rightarrow$  Sname

As Sid is a primary key, then
(Sid, Street) will be super key.
Hence, it is in BCNF.

Answer 4

i  think ans is d

because street and sname functionally depend on city (acc to question)

Comments

D can not be possible since that combination is given as candidate key .so it satisfy bcnf

---

"each supplier and each street within a city has unique name"

@indrajeet
I guess here you think that,  City->name , City->street
It is wrong. 

It means  
name,City -> sid
street,City -> sid
So BCNF.

 

---

No other functional dependencies are implied other than those implied by primary and candidate keys.

 

dont this directly says that it is in BCNF.

---

@manav ,exactly i also think the same.

Answer 5

In Supplier relation:

sid → sid, sname, city, street
sname, city → sid, sname, city, street (given)

Primary attributes are: sname, city, sid

 

• Check 2NF.
  Part of CK → non-prime attributes? No. So, 2NF.
   
• Check 3NF
  Non-prime attribute → Non-prime attribute? No. So, 3NF.
   
• Check BCNF
  For every X → Y, is X a Superkey? Yes. So, BCNF.

Option A.

 

PS: We can't directly check BCNF. Start with 2NF (Assuming 1NF is always satisfied)

Comments

sir why are we not considering these dependencies

$pid \rightarrow pname, color$

$sid, pname\rightarrow cost$

These clearly seem to be lossless and dependency preserving decomposition of the whole schema. And the question is asking

“which one of the following is true about the above schema”

And then because of $pid \rightarrow pname, color$ FD, it is not even in 2NF.

Answer 6

Please explain clearly i am not getting the concept that how we can conclude BCNF without FD's and by theory i think we can only derive that (sname , city) is candidate key and city --> sname but how bcnf is concluded ?

Comments

What i understood is in a city the street names are unique. But in a street there can be multiple suppliers residing. And candidate key basically means it should identify a row uniquely. But (street, city) returns multiple sid's. How can it be candidate key?

Please correct me if i am wrong.

---

@Arjun sir please help.

I still do not understand how (street,city) can uniquely identify a supplier.