2.1 [GATE 1994 : 1 Mark]
Question:
State True or False with reason:
There is always a decomposition into Boyce-Codd Normal Form (BCNF) that is lossless and dependency preserving.
Answer: False
solution:
BCNF में हमेशा Lossless decomposition मिल जाता है, लेकिन Dependency Preserving हर बार नहीं मिलता।
Example: R(A,B,C) with AB->C and C->A. ये 3NF में है लेकिन BCNF में नहीं है। अगर BCNF में तोड़ोगे तो AB->C वाली dependency खो जाएगी।
1-Line Trick: BCNF = Lossless तो पक्का, Dependency Preserving = किस्मत।
2.2 [GATE 1995 : 2 Marks]
Question:
Consider the relation schema R(A, B, C) with functional dependencies:
AB -> C
C -> A
(a) Show that scheme R is in Third Normal Form (3NF) but not in Boyce-Codd Normal Form (BCNF).
(b) Determine the minimal keys of relation R.
Answer: Keys = AB and BC. 3NF = Yes, BCNF = No.
solution:
Step 1 – Keys निकालो: AB का closure = ABC (सब आ गया), BC का closure = ABC. तो Keys हैं AB और BC.
Step 2 – 3NF Check: 3NF का Rule है – LHS Key हो या RHS Prime Attribute (Key का हिस्सा) हो। C->A में LHS C Key नहीं है, लेकिन RHS A है जो Prime है (AB और BC में है)। तो 3NF Pass.
Step 3 – BCNF Check: BCNF का Rule सख्त है – LHS हमेशा Super Key होना चाहिए। C->A में C Super Key नहीं है। तो BCNF Fail.
1-Line Trick: Prime Attribute RHS में हो तो 3NF बच जाता है, लेकिन BCNF नहीं बचेगा।
2.3 [GATE 1997 : 2 Marks]
Question:
For a database relation R(a, b, c, d) where domains include only atomic values, only the following functional dependencies and those that can be inferred from them hold:
a -> c
b -> d
This relation is
(a) in first normal form but not in second normal form
(b) in second normal form but not in third normal form
(c) in third normal form
(d) None of the above
Answer: (a) in first normal form but not in second normal form
solution:
Atomic values बोला है मतलब 1NF तो है ही।
Key क्या है? a,b मिलकर ही c,d को ला पा रहे हैं, तो Key = ab.
अब a->c है। यहाँ a Key का हिस्सा है (Partial Dependency) – पूरी Key ab नहीं है, सिर्फ a से c आ रहा है। 2NF Partial Dependency को Allow नहीं करता। तो 2NF में नहीं है।
1-Line Trick: Key का हिस्सा -> Non-Key को Determine करे = Partial Dependency = 2NF Fail.
2.4 [GATE 1997 : 2 Marks]
Question:
Let R(a, b, c) and S(d, e, f) be two relations in which d is the foreign key of S that refers to the primary key of R. Consider the following four operations on R and S:
(i) Insert into R
(ii) Insert into S
(iii) Delete from R
(iv) Delete from S
Which of the following is true about the referential integrity constraint above?
(a) None of (i), (ii), (iii) or (iv) can cause its violation
(b) All of (i), (ii), (iii) and (iv) can cause its violation
(c) Both (i) and (iv) can cause its violation
(d) Both (ii) and (iii) can cause its violation
Answer: (d) Both (ii) and (iii) can cause its violation
solution:
Foreign Key S में है, Primary Key R में है।
(i) Insert into R: R में डाल रहे हो, कोई दिक्कत नहीं, क्योंकि S को R की जरूरत है, उल्टा नहीं।
(ii) Insert into S: S में नया d डाल रहे हो, अगर वो d R में नहीं है तो Fail। Violation होगा।
(iii) Delete from R: R से कोई tuple उड़ा दिया, लेकिन S में उसको Use करने वाला बच्चा बैठा है, तो S अनाथ हो जाएगा। Violation होगा।
(iv) Delete from S: S से उड़ाने में किसी को फर्क नहीं पड़ता।
1-Line Trick: Insert into Child (S) और Delete from Parent (R) हमेशा खतरनाक होता है।
2.5 [GATE 1998 : 1 Mark]
Question:
Which normal form is considered adequate for normal relational database design?
(a) 2 NF
(b) 5 NF
(c) 4 NF
(d) 3 NF
Answer: (d) 3 NF
solution:
Industry में 3NF तक ही सब Normal करते हैं। 3NF तक सारी Insertion/Deletion Anomaly खत्म हो जाती है। BCNF, 4NF, 5NF सिर्फ Theory के लिए है, Practical में 3NF ही Adequate है।
1-Line Trick: GATE को 3NF से प्यार है – हमेशा Adequate = 3NF बोलना।
2.6 [GATE 1998 : 1 Mark]
Question:
There are five records in a database:
Name Age Occupation Category
Rama 27 CON A
Abdul 22 ENG A
Jeniffer 28 DOC B
Maya 32 SER D
Dev 24 MUS C
There is an index file associated with this and it contains the values 1, 3, 2, 5 and 4. Which one of the fields is the index built from?
(a) Age
(b) Name
(c) Occupation
(d) Category
Answer: (c) Occupation
solution:
Index File का मतलब होता है Data को Sort करके उसका Pointer रखना। Values हैं 1,3,2,5,4.
Occupation को Alphabetically Sort करो:
CON (Rama) -> 1
DOC (Jeniffer) -> 2nd but list में 3rd पर है? Check:
CON=1 (Rama is 1st row)
DOC=2nd row original? Jeniffer 3rd row hai.
Actually Sort: CON(1), DOC(3), ENG(2), MUS(5), SER(4) = 1,3,2,5,4 जो Index से Exact Match करता है।
Age Sort से 22,24,27,28,32 = 2,5,1,3,4 बनता, Match नहीं करता।
Name Sort से Abdul, Dev, Jeniffer, Maya, Rama = 2,5,3,4,1 बनता।
1-Line Trick: Index Values को Sort करके देखो, कौन सा Column उसी Order में आता है।
2.7 [GATE 1998 : 2 Marks]
Question:
Consider the following database relations containing the attributes
Book_id
Subject_Category_of_book
Name_of_Author
Nationality_of_Author
With book_id as the primary key.
(a) What is the highest normal form satisfied by this relation?
(b) Suppose the attributes Book_title and Author_address are added to the relation, and the primary key is changed to {Name_of_Author, Book_title}, what will be the highest normal form satisfied by the relation?
Answer: (a) 2NF (b) 1NF
solution:
(a) book_id -> Name_of_Author और Name_of_Author -> Nationality_of_Author. मतलब book_id -> Nationality via Transitive. Transitive Dependency है तो 3NF Fail, लेकिन 2NF Pass क्योंकि Key Single है तो Partial नहीं है। तो Highest = 2NF.
(b) New Key = {Author, Title}. अब Author -> Author_address है। यहाँ Author Key का हिस्सा है (Partial), पूरा Key नहीं। तो Partial Dependency आ गई। 2NF भी Fail। सिर्फ 1NF रहेगा।
1-Line Trick:
Transitive = 3NF Fail (2NF तक ठीक)
Partial = 2NF Fail (1NF ही बचेगा)
2.8 [GATE 1999 : 1 Mark]
Question:
Let R = (A, B, C, D, E, F) be a relation scheme with the following dependencies C -> F, E -> A, EC -> D, A -> B. Which of the following is a key for R?
(a) CD
(b) EC
(c) AE
(d) AC
Answer: (b) EC
solution:
Closure निकालो।
EC+ = EC
E -> A से A आ गया = ECA
A -> B से B आ गया = ECAB
C -> F से F आ गया = ECABF
EC -> D से D आ गया = ECABFD = सब आ गया।
तो EC Key है। CD से E नहीं आएगा, AC से E नहीं आएगा, AE से C,F,D नहीं आएगा।
1-Line Trick: EC से सब आता है, EC ही असली Key है।
2.9 [GATE 1999 : 1 Mark]
Question:
Consider the schema R = (S T U V) and the dependencies S -> T, T -> U, U -> V and V -> S. Let R = (R1 and R2) be a decomposition such that R1 ∩ R2 = ∅. The decomposition is
(a) not in 2NF
(b) in 2NF but not in 3NF
(c) in 3NF but not in 2NF
(d) in both 2NF and 3NF
Answer: (d) in both 2NF and 3NF
solution:
S->T->U->V->S ये पूरा Cycle है।
S+ = STUV, T+ = TUVS, U+ = UVST, V+ = VSTU। मतलब हर Single Attribute Key है।
तो कोई Non-Prime Attribute ही नहीं है, सब Prime है। जब सब Prime है तो 2NF और 3NF तो पक्का Pass है।
R1 ∩ R2 = ∅ का मतलब Lossless नहीं है, लेकिन Normal Form से उसका कोई लेना-देना नहीं।
1-Line Trick: सब Attribute Prime हो = Automatic 3NF।
2.10 [GATE 2000 : 2 Marks]
Question:
Given the following relation instance
X Y Z
1 4 2
1 5 3
1 6 3
3 2 2
Which of the following functional dependencies are satisfied by the instance?
(a) XY -> Z and Z -> Y
(b) YZ -> X and Y -> Z
(c) YZ -> X and X -> Z
(d) XZ -> Y and Y -> X
Answer: (b) YZ -> X and Y -> Z
solution:
Check करो:
YZ -> X: YZ के Pair देखो – (4,2)->1, (5,3)->1, (6,3)->1, (2,2)->3। कोई भी YZ Pair Duplicate नहीं है अलग X के साथ, तो YZ->X True है।
Y -> Z: Y देखो – 4->2, 5->3, 6->3, 2->2। कोई भी Y Duplicate नहीं है जिसका Z अलग हो। तो Y->Z भी True है।
X->Z Fail है क्योंकि X=1 के लिए Z=2 और 3 दोनों है।
1-Line Trick: Table में Duplicate LHS पर अलग RHS मिले तो FD Fail।
2.11 [GATE 2001 : 1 Mark]
Question:
Consider a schema R(A,B,C,D) and functional dependencies A -> B and C -> D. Then the decomposition of R into R1(AB) and R2(CD) is
(a) dependency preserving and lossless join
(b) lossless join but not dependency preserving
(c) dependency preserving but not lossless join
(d) not dependency preserving and not lossless join
Answer: (c) dependency preserving but not lossless join
solution:
Dependency: A->B R1 में है, C->D R2 में है, तो दोनों Preserve हो गई।
Lossless: R1 ∩ R2 = ∅ (Common कुछ नहीं)। Lossless के लिए Common Attribute होना चाहिए, तो ये Lossless नहीं है।
1-Line Trick: Intersection Empty = Lossless Fail, FD अपने-अपने Table में = Dependency Pass।
2.12 [GATE 2001 : 2 Marks]
Question:
R(A, B, C, D) is a relation. Which of the following does not have a lossless join, dependency preserving BCNF decomposition?
(a) A -> B, B -> CD
(b) A -> B, B -> C, C -> D
(c) AB -> C, C -> AD
(d) A -> BCD
Answer: (c) AB -> C, C -> AD
solution:
(c) में AB Key है (AB+ = ABCD), लेकिन C -> AD में C Key नहीं है तो BCNF Fail।
BCNF में तोड़ोगे तो R1(CAD) और R2(BC) बनेगा, लेकिन AB->C वाली Dependency खो जाएगी। इसलिए ये वाला Dependency Preserving BCNF नहीं दे सकता।
बाकी सब में हो जाता है।
1-Line Trick: AB->C वाला Case ही GATE का Evergreen Trap है – BCNF में Dependency जाती है।
2.13 [GATE 2002 : 1 Mark]
Question:
Relation R with an associated set of functional dependencies, F, is decomposed into BCNF. The redundancy (arising out of functional dependencies) in the resulting set of relations is
(a) Zero
(b) More than zero but less than that of an equivalent 3NF decomposition
(c) Proportional to the size of F’
(d) Indeterminate
Answer: (a) Zero
solution:
BCNF का मतलब ही है – कोई भी FD ऐसी नहीं जहाँ LHS Key ना हो। तो सारी Redundancy खत्म। 3NF में थोड़ी Redundancy बचती है, BCNF में Zero।
1-Line Trick: BCNF = Zero Redundancy।
2.14 [GATE 2002 : 2 Marks]
Question:
Relation R is decomposed using a set of functional dependencies, F, and relation S is decomposed using another set of functional dependencies, G. One decomposition is definitely BCNF, the other is definitely 3NF, but it is not known which is which. To make a guaranteed identification, which one of the following tests should be used on the decompositions? (Assume that the closures of F and G are available).
(a) Dependency-preservation
(b) Lossless-join
(c) BCNF definition
(d) 3 NF definition
Answer: (c) BCNF definition
soution:
BCNF और 3NF दोनों Lossless होते हैं, दोनों में Dependency का चक्कर हो सकता है। फर्क सिर्फ Definition से पता चलेगा।
BCNF Check करोगे – अगर सारे FDs में LHS Super Key है तो BCNF है, वरना दूसरा वाला 3NF होगा। 3NF से Check करोगे तो दोनों Pass हो सकते हैं।
1-Line Trick: Doubt हो तो हमेशा BCNF Definition Check करो – सबसे सख्त है।
2.15 [GATE 2002 : 2 Marks]
Question:
From the following instance of a relation scheme R(A, B, C), we can conclude that:
A B C
1 1 1
1 1 0
2 3 2
2 3 2
(a) A functionally determines B and B functionally determines C
(b) A functionally determines B and B does not functionally determine C
(c) B does not functionally determine C
(d) A does not functionally determine B and B does not functionally determine C
Answer: (b) A functionally determines B and B does not functionally determine C
solution:
A->B: A=1 पर B=1,1 Same है, A=2 पर B=3,3 Same है, तो A->B True है।
B->C: B=1 पर C=1 और 0 अलग-अलग है, तो B->C Fail है।
1-Line Trick: Same LHS पर Different RHS मिला तो FD Fail।
2.16 [GATE 2002 : 2 Marks]
Question:
Consider the following functional dependencies in a database:
Date_of_Birth -> Age
Age -> Eligibility
Name -> Roll_number
Roll_number -> Name
Course_number -> Course_name
Course_number -> Instructor
(Roll_number, Course_number) -> Grade
Answer: This question asks for Highest Normal Form / Keys – Full question photo में cut है
solution:
इसमें Roll_number और Name एक दूसरे को Determine करते हैं (Candidate Keys), Course_number अकेला Course_name और Instructor को देता है। (Roll_number, Course_number) Composite Key बनकर Grade देता है।
यहाँ Partial और Transitive दोनों Dependency हैं, इसलिए यह 3NF में नहीं होगा।
1-Line Trick: Roll_number <-> Name = Equivalent Keys, Course_number -> Course_name = Transitive।
2.17 [GATE 2004 : 1 Mark]
Question:
Consider the following relation schema pertaining to a students database:
Student (rollno, name, address)
Enroll (rollno, courseno, coursename)
where the primary keys are shown underlined. The number of tuples in the student and Enroll tables are 120 and 8 respectively. What are the maximum and minimum number of tuples that can be present in (Student * Enroll), where * denotes natural join?
(a) 8, 8
(b) 120, 8
(c) 960, 8
(d) 960, 120
Answer: (a) 8, 8
solution:
Student का PK rollno है और Enroll में rollno FK है। मतलब Enroll का हर rollno Student में होना ही चाहिए। तो Natural Join करने पर Enroll की 8 rows ही Student से Match करेंगी।
तो Max = 8 और Min = 8, दोनों Same।
1-Line Trick: Child Table (Enroll) में जितनी Rows, Natural Join में उतनी ही Rows = 8.
2.18 [GATE 2004 : 2 Marks]
Question:
The relation scheme student Performance (name, courseNo, rollNo, grade) has the following functional dependencies:
name, courseNo -> grade
RollNo, courseNo -> grade
name -> rollNo
rollNo -> name
The highest normal form of this relation scheme is
(a) 2 NF
(b) 3 NF
(c) BCNF
(d) 4 NF
Answer: (b) 3 NF
solution:
Keys निकालो: name+courseNo से सब आ जाता है, rollNo+courseNo से भी सब आ जाता है। तो Keys हैं (name,courseNo) और (rollNo,courseNo).
FD name->rollNo में LHS name अकेला Key नहीं है, लेकिन RHS rollNo Prime Attribute है (Key का हिस्सा है)। तो 3NF Pass।
BCNF में LHS को Super Key होना चाहिए, name Super Key नहीं है, तो BCNF Fail। इसलिए Highest = 3NF.
1-Line Trick: LHS Key नहीं लेकिन RHS Prime हो = 3NF Pass, BCNF Fail.
2.19 [GATE 2004 : 2 Marks]
Question:
Relation Empdtl is defined with attributes empcode (unique), name, street, city, state and pincode. For any pincode, there is only one city and state. Also, for any given street, city and state, there is just one pincode. In normalization terms, Empdtl is a relation in
(a) 1NF only
(b) 2NF and hence also in 1NF
(c) 3NF and hence also in 2NF and 1NF
(d) BCNF
Answer: (b) 2NF and hence also in 1NF
solution:
FDs: pincode -> city, state और (street, city, state) -> pincode.
Key है empcode (Single Attribute)। Single Attribute Key होने से कोई Partial Dependency नहीं होती, इसलिए 2NF तो है।
लेकिन pincode -> city में pincode Key नहीं है, और city Prime भी नहीं है, तो Transitive आ गई। इसलिए 3NF Fail।
1-Line Trick: Single Key = 2NF पक्का, लेकिन pincode -> city Transitive है तो 3NF Fail.
2.20 [GATE 2005 : 1 Mark]
Question:
A relation has fields F1, F2, F3, F4, F5 with the following functional dependencies
F1 -> F3, F2 -> F4, (F1, F2) -> F5
In terms of Normalization, this table is in
(a) 1 NF
(b) 2 NF
(c) 3 NF
(d) None of these
Answer: (a) 1 NF
solution:
Key है (F1,F2) क्योंकि दोनों मिलकर F5 लाते हैं और F1->F3, F2->F4 से सब Cover।
अब F1 -> F3 में F1 Key का हिस्सा है, पूरा Key नहीं – ये Partial Dependency है।
Partial होते ही 2NF Fail, तो सिर्फ 1NF में है।
1-Line Trick: Key का हिस्सा -> Non-Key = Partial = 2NF Fail = 1NF only.
2.21 [GATE 2005 : 1 Mark]
Question:
Which one of the following statements about normal forms is FALSE?
(a) BCNF is stricter than 3 NF
(b) Loss less, dependency-preserving decomposition into 3NF is always possible
(c) Loss less, dependency-preserving decomposition into BCNF is always possible
(d) Any relation with two attributes is in BCNF
Answer: (c) Loss less, dependency-preserving decomposition into BCNF is always possible
solution:
(a) True है – BCNF 3NF से ज्यादा Strict है।
(b) True है – 3NF में Lossless + Dependency Preserve दोनों हमेशा Possible है।
(c) FALSE है – BCNF में Lossless तो Possible है, लेकिन Dependency Preserve हर बार Possible नहीं है।
(d) True है – 2 Attribute वाली Relation हमेशा BCNF में होती है।
1-Line Trick: 3NF = Lossless + Dependency दोनों पक्का, BCNF = Dependency की Guarantee नहीं।
2.22 [GATE 2005 : 2 Marks]
Question:
Consider a relation scheme R = (A, B, C, D, E, H) on which the following functional dependencies hold: {A -> B, BC -> D, E -> C, D -> A}
What are the candidate keys of R?
(a) AE, BE
(b) AE, BE, DE
(c) AEH, BEH, BCH
(d) AEH, BEH, DEH
Answer: (d) AEH, BEH, DEH
solution:
H कहीं भी RHS में नहीं है, तो H तो हर Key में आएगा ही।
E भी किसी FD में RHS में नहीं है (सिर्फ LHS में है E->C), तो E भी हर Key में आएगा।
तो EH तो पक्का Key में है। अब EH का Closure = EHC (E->C)।
- AEH+ = AEH + B(A->B) + C + D(BC->D) = AEHBCD = सब आ गया।
- BEH+ = BEH + C(E->C) + D(BC->D) + A(D->A) = सब आ गया।
- DEH+ = DEH + A(D->A) + B(A->B) + C(E->C) = सब आ गया।
तो Keys हैं AEH, BEH, DEH।
1-Line Trick: जो Attribute कभी RHS में ना आए, वो हर Key में आएगा – E और H।
2.23 [GATE 2005 : 2 Marks]
Question:
In a schema with attributes A, B, C, D and E following set of functional dependencies are given
A -> B
A -> C
CD -> E
B -> D
E -> A
Which of the following functional dependencies is NOT implied by the above set
(a) CD -> AC
(b) BD -> CD
(c) BC -> CD
(d) AC -> BC
Answer: (b) BD -> CD
solution:
Closure से Check करो:
- CD+ = CDEAB (CD->E, E->A, A->B) तो CD->AC True है।
- BC+ = BCDAE (B->D, CD->E, E->A) तो BC->CD True है।
- BD+ = BDEAC (B->D, E->A, A->C) लेकिन C इसमें कैसे आएगा? B और D से C नहीं आता। तो BD->CD Fail है।
- AC+ = ABCDE तो AC->BC True है।
1-Line Trick: Closure निकालो, RHS उसमें है तो FD True, नहीं तो False।
2.24 [GATE 2006 : 1 Mark]
Question:
Consider the relations r1(P, Q, R) and r2(R, S, T) with primary keys P and R respectively. The relation r1 contains 2000 tuples and r2 contains 2500 tuples. The maximum Size of the join r1 ⋈ r2 is:
(a) 2000
(b) 2500
(c) 4500
(d) 5000
Answer: (a) 2000
solution:
r1 का R, r2 के PK R को Refer कर रहा है। r2 का R Unique है, तो r1 की एक Row r2 की Maximum 1 Row से ही Join होगी।
तो Join की Size r1 से ज्यादा नहीं हो सकती। r1 में 2000 है तो Max 2000 ही होगा।
1-Line Trick: Child ⋈ Parent (PK) = Max Size = Child Table की Size।
2.25 [GATE 2006 : 2 Marks]
Question:
Consider a relation R with five attributes V, W, X, Y, and Z. The following functional dependencies hold: VY -> W, WX -> Z, and ZY -> V. Which of the following is a candidate key for R?
(a) VXZ
(b) VXY
(c) VWXY
(d) VWXYZ
Answer: (b) VXY
solution:
VXY का Closure:
VXY+ = VXY + W(VY->W) = VXYW + Z(WX->Z) = VXYWZ = सब आ गया।
VXZ+ से Y नहीं आएगा, तो Key नहीं।
VWXY और VWXYZ Super Key हैं, Candidate नहीं क्योंकि VXY ही छोटा है।
1-Line Trick: VXY से सब आ जाता है, VXY ही Minimal Key है।