Unit 4 - Practice Quiz

The Entity Integrity rule states that no primary key value can be NULL. This is because the primary key is used to uniquely identify individual records in a table.

Referential integrity preserves the defined relationship between tables when records are entered or deleted. It ensures that a foreign key always points to a valid, existing record in the referenced table.

The notation is used to represent that attribute A functionally determines attribute B. This means for any given value of A, there is exactly one corresponding value of B.

The functional dependency StudentID StudentName means that the StudentID uniquely determines the StudentName. You can look up a student's name using their ID.

A functional dependency is trivial if the attributes in Y are already contained within the attributes of X. For example, (StudentID, StudentName) StudentName is a trivial dependency.

Normalization is a systematic process of organizing columns and tables in a relational database to minimize data redundancy and avoid anomalies like insertion, update, and deletion anomalies.

A deletion anomaly occurs when the deletion of certain data leads to the unintended loss of other unrelated data. Normalization helps prevent this by separating related data into different tables.

The fundamental rule of 1NF is that every cell in a table must hold a single, atomic value. It cannot hold multiple values or repeating groups.

This violates 1NF because the 'PhoneNumbers' attribute is not atomic; it contains a list of multiple phone numbers in a single field. To be in 1NF, each phone number should be in a separate row or column.

A relation is in 2NF if it is in 1NF and every non-prime attribute is fully functionally dependent on the entire primary key. This means there are no partial dependencies where a non-key attribute depends only on a part of the composite primary key.

A partial dependency occurs when a non-prime attribute is functionally dependent on only a part of a composite primary key. If the primary key is simple (a single attribute), a partial dependency cannot exist by definition.

A relation is in 3NF if it is in 2NF and it eliminates transitive dependencies. A transitive dependency is when a non-prime attribute depends on another non-prime attribute, rather than directly on the primary key.

This is a classic example of a transitive dependency. The non-key attribute C depends on another non-key attribute B, which in turn depends on the primary key A. 3NF aims to remove such dependencies.

BCNF (Boyce-Codd Normal Form) is a stricter version of 3NF. Therefore, any relation that satisfies the BCNF condition automatically satisfies the 3NF condition. However, a relation in 3NF is not necessarily in BCNF.

The definition of BCNF states that for any non-trivial functional dependency , the determinant X must be a superkey of the relation. This is a stricter condition than that of 3NF.

The double arrow notation, , is used to represent a multivalued dependency, which means that for a single value of A, there can be a set of corresponding values for B, and this set is independent of any other attributes.

A multivalued dependency means that for a given value of X, the set of Y values is independent of the values of any other attributes in the relation. This independence is what distinguishes it from a functional dependency.

The definition of 4NF builds upon BCNF. A relation is in 4NF if it is in BCNF and it does not contain any non-trivial multivalued dependencies.

4NF is specifically designed to handle and eliminate data redundancy and anomalies that arise from multivalued dependencies, which are not addressed by normal forms up to BCNF.

The normal forms follow a strict hierarchy. A relation in 4NF must, by definition, also satisfy the conditions for all the lower normal forms: BCNF, 3NF, 2NF, and 1NF.

The closure of {A, C} is calculated as follows:

1. Start with the initial set: Result = {A, C}.
2. From A -> B, since A is in Result, we add B. Result becomes {A, B, C}.
3. From BC -> D, since B and C are now in Result, we add D. Result becomes {A, B, C, D}.
   No more attributes can be added, so .

A relation is in 2NF if it is in 1NF and every non-prime attribute is fully functionally dependent on the primary key. Here, the primary key is {A, B}. The attribute C is a non-prime attribute. The dependency A -> C shows that C is dependent on only a part of the primary key (A), which is a partial dependency. This violates the condition for 2NF.

The relation is in 1NF. The primary key is StudentID. There are no partial dependencies since the key is a single attribute, so it is in 2NF. However, there is a transitive dependency: StudentID -> Zip and Zip -> City. This means a non-key attribute (City) is determined by another non-key attribute (Zip), violating the conditions for 3NF.

The candidate keys are {A, B} and {A, C}. The attributes A, B, and C are all prime attributes. The relation is in 2NF because there are no partial dependencies. The relation is in 3NF because for every dependency , either is a prime attribute or is a superkey. For AB -> C, AB is a superkey. For C -> B, B is a prime attribute. So it is in 3NF. However, it is not in BCNF because for the dependency C -> B, the determinant C is not a superkey.

Referential integrity ensures that a foreign key value in one table must match a primary key value in another table, or be null. It prevents actions that would create 'orphan' records. In this case, deleting a student from the STUDENT table while corresponding enrollment records exist would violate referential integrity, as the StudentID in ENROLLMENT would no longer refer to a valid student.

This scenario describes multivalued dependencies (MVDs). For a given EmployeeID, there is a set of associated Project values and a set of associated Skill values. Crucially, the set of projects is not related to the set of skills. This independence is the hallmark of MVDs, represented as EmployeeID ->> Project and EmployeeID ->> Skill.

The definition of Fourth Normal Form (4NF) builds directly on BCNF. A relation is in 4NF if and only if it is in BCNF and for every non-trivial multivalued dependency , is a superkey. The core purpose of 4NF is to eliminate data redundancy caused by independent multivalued facts about the same entity.

An update anomaly occurs when redundant data requires the same piece of information to be changed in multiple places. In this schema, EmpName is repeated for every ProjectID the employee is on. Changing the name requires updating all these records, and failing to do so leads to data inconsistency. Normalization would solve this by placing EmpID and EmpName in a separate EMPLOYEE table.

First Normal Form (1NF) requires that all attributes in a relation must be atomic, meaning they hold a single value. A Prerequisites attribute containing a comma-separated list of values is a repeating group or a multi-valued attribute, which violates 1NF. To be in 1NF, this should be modeled with a separate PREREQUISITE table.

Armstrong's Augmentation Rule states that if holds, then also holds. A simpler form is that if holds, then also holds. Given (A, B) -> C, we can augment the left side with any attribute set, such as {D}. This gives us (A, B, D) -> C. The other options are incorrect inferences.

The candidate key is {X, Y}. The relation is in 2NF because there are no partial dependencies (the key has multiple attributes, but no non-prime attribute is dependent on a part of it). It is in 3NF because for the dependency Z -> Y, the attribute Y is a prime attribute (part of a candidate key). However, it is not in BCNF. The BCNF rule states that for any non-trivial FD , must be a superkey. The dependency Z -> Y violates this, as Z is not a superkey.

The relation is not in 3NF because of the transitive dependency A -> B -> C. A non-key attribute C is dependent on another non-key attribute B. To normalize to 3NF, we must remove this transitive dependency. We decompose the relation by taking out the problematic dependency B -> C into its own table R2(B, C). The original table becomes R1(A, B, D), retaining the determinant B as a foreign key.

Entity Integrity is a rule that states that every table must have a primary key, and the column or columns chosen to be the primary key must be unique and not null. This ensures that each row (entity) can be uniquely identified.

The primary key is {OrderID, ItemID}. For a relation to be in 2NF, all non-prime attributes must be fully dependent on the entire primary key. Here, ItemPrice is a non-prime attribute. The dependency ItemID -> ItemPrice shows that ItemPrice is dependent only on a part of the primary key (ItemID), not the whole key. This is a partial dependency, which violates 2NF.

An insertion anomaly occurs when you are unable to insert a record for one entity without also having information for another entity. In this case, you cannot record the existence of a new department (DeptID, DeptName) because a FacultyID is required as part of the primary key or cannot be null, but no faculty has been assigned yet. Normalization would separate DEPARTMENT information into its own table.

To find the candidate key, we first identify attributes that are not on the right side of any FD; these must be part of the key. Here, A and B are never on the RHS. Let's find the closure of {A, B}.

2. Using AB -> C, we get
3. Using C -> D, we get
4. Using D -> E, we get
   Since the closure of {A, B} contains all attributes of the relation, {A, B} is a candidate key. Since A and B are essential, it is the only candidate key.

The definition of 4NF states that for a relation to be in 4NF, it must be in BCNF and for every non-trivial multivalued dependency that holds, must be a superkey for the relation. Therefore, for the MVD A ->> B not to violate 4NF, the determinant A must be a superkey.

The BCNF rule is strict: for any non-trivial FD , must be a superkey. The 3NF rule is slightly more relaxed: for any non-trivial FD , either is a superkey OR is a prime attribute (part of a candidate key). The second condition (Y is a prime attribute) is an allowance that 3NF makes but BCNF does not, which is why a 3NF relation may not be in BCNF.

The MVD transitivity rule is more complex than standard transitivity. It states: if and , then . The simple transitivity A ->> C does not generally hold for MVDs, making this statement false. The other statements are true: FD is a special case of MVD, the complementation rule is a key property, and MVDs are the target of 4NF normalization, which goes beyond BCNF.

The relation has a transitive dependency A -> B -> D, where A is the key, B is a non-key attribute, and D is a non-key attribute dependent on B. This violates 3NF. To resolve this, the dependency causing the violation (B -> D) is moved to a new relation R2(B, D). The determinant B is kept in the original relation, which becomes R1(A, B, C). This decomposition preserves dependencies and eliminates the transitive dependency.

To find the candidate key, we must compute the attribute closure for each potential key.

1. (since , then , then , then ). So, A is a candidate key.
2. . We cannot determine anything else.
3. .
4. (since , then , then ). So, E is a candidate key.
   Let's use . Let's find candidate keys.
   • . So CE is a candidate key.
   • . So BE is a candidate key.
   • . So DE is a candidate key.
     Let's try a better F. . Find candidate keys.
   • . So AC is a key.
   • . So CD is a key.
   • . So BC is a key.
     The original question had a flaw. Let's correct the question and explanation based on a solid FD set.
     Original FD: .
   • . A is a candidate key.
   • . E is a candidate key.
   • . CD is a candidate key.
   • . BC is a candidate key.
     None of the options A, B, C, E are unique minimal superkeys. A and E are candidate keys. This makes a bad MCQ.
     Let's fix the question:
     Given schema and . Which set of attributes is a candidate key?
   • . ACD is a superkey. Is it minimal? . . . So ACD is minimal. ACD is a candidate key.
     Let's try to make a question where a single attribute is the key.
     , . Candidate keys?
   • . Is AB minimal? . Yes. AB is a CK.
   • . Is BC minimal? . Yes. BC is a CK.
   • . Is BD minimal? . Yes. BD is a CK.
     Question: Consider and the set of FDs . What is the closure of (i.e., )?
     Options:
     A)
     B)
     C)
     D)
     Correct Option: B
     Explanation:
5. Start with .
6. Using , we can add V and Z. Now, .
7. Using , we can add W. Now, .
8. The closure is now , which contains all attributes of the relation. This also implies that XY is a candidate key. The question asks for the closure, not just the key. This tests the process. This is a good hard question.

The candidate keys of R are . The dependency is a BCNF violation because L is not a superkey. The decomposition into and is the standard BCNF decomposition. It is lossless because the intersection of attributes is a superkey of . Both (key L) and (key JL) are in BCNF. However, the original dependency cannot be checked on either or alone. Its attributes are spread across both relations, and checking it requires a join. Therefore, the decomposition is not dependency preserving.

The problem states that courses and clubs are independent for a given student. This means for a student S1 taking courses C1, C2 and in clubs CL1, CL2, the database must store tuples (S1,C1,CL1), (S1,C1,CL2), (S1,C2,CL1), (S1,C2,CL2) to maintain consistency. This is the classic sign of a multivalued dependency (MVD). The MVD is . Because CourseID and ClubID are independent for a StudentID, this can also be written as the non-trivial MVD . A relation is in 4NF if for every non-trivial MVD , X is a superkey. Here, the key for the Enrollment relation is . Since is not a superkey, the relation is not in 4NF.

1. Check 2NF: A relation is in 2NF if it's in 1NF and has no partial dependencies. The only candidate key is . A partial dependency would be if a proper subset of (i.e., A or B) determines a non-prime attribute. The FDs are and . There are no FDs like or where X is a non-prime attribute. Therefore, there are no partial dependencies, and the relation is in 2NF.
2. Check 3NF: A relation is in 3NF if it's in 2NF and has no transitive dependencies. A transitive dependency exists when a non-key attribute determines another non-key attribute. Here, the key is , and the non-key attributes are . We have the dependency chain (from ) and . Since (a key) determines (a non-key attribute), and determines (another non-key attribute), this is a transitive dependency. Thus, the relation is not in 3NF.

The process is as follows:

1. A DELETE statement is issued for a row in the Departments table.
2. The database checks for foreign key constraints referencing this DeptID. The Employees table has such a constraint with the rule ON DELETE SET NULL.
3. For the 5 employees in that department, their DeptID column is updated to NULL. The employee records themselves are not deleted.
4. Since no employee records were deleted from the Employees table, the ON DELETE CASCADE rule on the Projects table is not triggered.
5. Therefore, the Projects table remains completely unaffected. The final state is: the department is gone, the 5 employees now have a NULL department, and the projects are unchanged.

• . So BCD is a candidate key.
• Are there other candidate keys? Let's check subsets of BCD. BC, CD, BD are not keys.
  Let's assume there's a typo and the FDs are . Key is AB. Then and are partial dependencies. This is too simple.
  Let's stick to the original FDs: .
• Let's find keys. . So BCD is a key.
• determines A. determines C. determines E.
• Let's check . So ABD is also a key.
• Let's check . So BCD is also a key.
  This is getting too complex. Let's make a cleaner example.
  New Question: A relation has FDs and the candidate key is . Which Normal Form does R satisfy?
  Correct Answer: R is in 1NF but not 2NF.
  Explanation: The candidate key is . The non-prime attributes are and . The dependency is a partial dependency because its determinant, , is a proper subset of the candidate key , and it determines a non-prime attribute . The existence of this partial dependency means the relation is not in 2NF.

To find the minimal cover, we follow three steps:

1. Singleton Right-Hand Side: Decompose F into . Removing duplicates gives .
2. Remove Extraneous LHS Attributes: There are no FDs with composite attributes on the left, so this step is skipped.
3. Remove Redundant FDs:
   • Is redundant? To check, we see if can be derived from the rest: . The closure of A under this set is just . It does not include B. So is not redundant.
   • Is redundant? To check, we see if can be derived from . The closure of B is just . So is not redundant.
   • Is redundant? To check, we see if can be derived from . The closure of A is . It includes C. So is redundant because of transitivity.
     Removing the redundant gives the minimal cover: .

1. Find Candidate Keys:
   • . So AB is a candidate key.
   • . So AC is a candidate key.
   • The prime attributes are A, B, and C.
2. Check BCNF: A relation is in BCNF if for every non-trivial FD , X is a superkey. Let's check our FDs:
   • : AB is a superkey (it's a candidate key). This is fine.
   • : Is C a superkey? No. . It does not determine all attributes. Thus, is not in BCNF.
   • : AB is a superkey. This satisfies 3NF.
   • : C is not a superkey, so we check condition (b). Is Y (which is B) a prime attribute? Yes, B is part of the candidate key AB. Therefore, this dependency also satisfies the condition for 3NF.
     Since all dependencies satisfy the 3NF condition, the relation is in 3NF. However, it is not in BCNF.

This question tests the interaction between MVDs and FDs. There is a specific inference rule called the mixed transitivity rule (sometimes called pseudo-transitivity for MVDs). The rule states: If and hold, then holds. A simpler corollary is that if and hold, then also holds if Z is a subset of Y. That is not the case here. The correct rule is the multivalued transitivity rule: if and , then holds. That's not applicable either. The key is that a functional dependency is a special case of a multivalued dependency. If , then it implies . Now we can use the multivalued transitivity rule: Since and , it follows that . Since C is not in B, this simplifies to . This is a subtle but important derivation. (an FD) does not necessarily hold.

The design is in 1NF but not 2NF due to partial dependencies (ProjID -> ProjName and EmpID -> {EmpName, HourlyRate}). The intent of putting everything in one table is often a naive attempt to simplify queries. This structure suffers from all three anomalies. However, the question asks for the most critical failure.

• Update Anomaly: If an employee's name changes, it must be updated in every row for every project they are on. This is a significant issue.
• Insertion Anomaly: You cannot add a new employee to the system if they have not yet been assigned to a project. This is a critical failure because it prevents storing core entity information (an employee) independently.
• Deletion Anomaly: If an employee is removed from their last project, their entire record (including their name and hourly rate) is deleted from the database.
  Comparing the failures, the inability to add a fundamental entity (an employee) without a related entity (a project) is arguably the most critical structural flaw related to insertion. The design attempts to capture assignments (solving an 'update' problem of tracking who is where), but the structure itself prevents the insertion of independent entities.

1. Dependency Preservation: An FD is preserved if all attributes in appear in one of the decomposed relations.
   • : Attributes A, B are in . Preserved.
   • : Attributes B, C are in . Preserved.
   • : Attributes C, D are in . Preserved.
     Since all original FDs are preserved, the decomposition is dependency preserving.
2. Lossless Join: A decomposition of R into and is lossless if the intersection of their attributes is a superkey for at least one of them. We can apply this test pairwise.
   • Join and . The intersection is . Is B a superkey of or ? In , the FD holds, and B is the key of . So, the join of and is lossless, resulting in a relation .
   • Join and . The intersection is . Is C a superkey of or ? In , the FD holds, and C is the key of . So, the join is lossless.
     Since the pairwise joins are lossless, the entire decomposition is lossless.

Codd's original definition of First Normal Form (1NF) states that the domain of an attribute must include only atomic (indivisible) values and that the value of any attribute in a tuple must be a single value from the domain of that attribute. A JSON object is inherently structured and contains multiple values (e.g., 'dark', 'email', 'sms'). From a pure relational theory perspective, this is a repeating group or a nested relation within a column, which is a clear violation of the atomicity rule of 1NF. While modern database systems can handle and query JSON types, this practice deviates from the classical definition of 1NF. Option B describes the practical implementation but ignores the theoretical definition, which the question refers to.

A relation is in 4NF if, for every non-trivial MVD , X is a superkey. A relation is in BCNF if, for every non-trivial FD , X is a superkey. The key distinction is that a relation can be in BCNF (having no FD violations) but still have a non-trivial MVD where the determinant is not a superkey. For example, the Enrollment(StudentID, CourseID, ClubID) example (where the only key is all three attributes) is in BCNF because there are no non-trivial FDs. However, it contains the MVD , and StudentID is not a superkey, so it violates 4NF. Therefore, a BCNF relation is not in 4NF if it has a non-trivial MVD that isn't caused by an FD, and whose determinant is not a superkey.

Let's prove the Pseudotransitivity Rule:

1. Given: (Premise)
2. Given: (Premise)
3. From (1), by Augmentation Rule (augmenting with W): . This step uses Augmentation.
4. From (3) and (2), we have and . By the Transitivity Rule, we can conclude .

Referential integrity requires that a foreign key must reference a complete primary key or a unique key of the referenced table. In this case, the primary key of the Tasks table is (ProjectID, TaskNumber). A TaskNumber alone does not uniquely identify a task across all projects. By creating a foreign key (DependsOnTask) that only references TaskNumber, the database cannot enforce the rule that the dependency must be within the same project. A task in Project 1 could incorrectly reference a task number that exists only in Project 2. The correct design would be to have a composite foreign key (DependsOnProjectID, DependsOnTaskNumber) that references (ProjectID, TaskNumber) to enforce the integrity constraint properly.

First, we identify the prime and non-prime attributes. The candidate keys are AB and BC. The set of prime attributes is {A, B, C}. The only non-prime attribute is D.
Second, we check for 2NF. A relation is not in 2NF if there is a partial dependency, which is when a proper subset of any candidate key determines a non-prime attribute.

• Consider the candidate key AB. A proper subset is {A} or {B}. We have the FD . Here, a proper subset of key AB (i.e., B) determines a non-prime attribute (D). This is a partial dependency.
• Consider the candidate key BC. A proper subset is {B} or {C}. The same FD shows that a proper subset of key BC (i.e., B) determines a non-prime attribute (D).
  Because of the partial dependency , the relation is not in 2NF.

A multivalued dependency on a relation R with attribute set U is defined as trivial under two conditions:

1. : This means the attributes on the right are already part of the attributes on the left. This provides no new information, similar to a trivial functional dependency like .
2. : This means that the attributes on the left and right combined make up all the attributes of the relation. Let . If , then Z is empty. The MVD definition requires that for each value of X, the associated Y values are independent of the Z values. If Z is empty, this condition is vacuously true.
   Any MVD that does not meet one of these two conditions is non-trivial and may indicate a need for decomposition to 4NF.

The original relation is not in 3NF due to transitive dependencies. The candidate key is A.

1. : This is a transitive dependency because B is not a superkey and C is a non-prime attribute.
2. : This is a transitive dependency because D is not a superkey and E is a non-prime attribute.
   To achieve 3NF, we decompose based on these violating FDs while ensuring the original key is preserved in one relation.
   • The FD leads to a relation .
   • The FD leads to a relation .
   • We must remove the transitively determined attributes (C and E) from the main relation and keep the determinants (B and D) along with the original key (A). This gives us .
     This set of relations is in 3NF, is dependency preserving, and the decomposition is lossless.

1. Find Candidate Key: We compute the closure of A: . So, A is the candidate key.
2. Check BCNF: For every non-trivial FD , X must be a superkey.
   • : A is a superkey. OK.
   • : A is a superkey. OK.
   • : Is C a superkey? No, . This dependency violates BCNF.
3. Check 3NF: For every non-trivial FD , either X is a superkey or Y is a prime attribute. The only prime attribute is A.
   • : X (A) is a superkey. OK.
   • : X (A) is a superkey. OK.
   • : X(C) is not superkey. Y(D) is not prime. So it violates 3NF.
     Okay, let me re-craft the question for a 3NF but not BCNF case. The classic example is with . The question above is for 2NF not 3NF.
     New Question: with FDs . What is the highest normal form of R?
     Explanation: Keys are {ST, TV, UV}. The dependencies and violate BCNF because U and V are not superkeys. To check 3NF, we use the rule: for an FD , either X is a superkey or Y is a prime attribute. Prime attributes are S, T, U, V. In , V is prime. In , S is prime. So both dependencies satisfy the 3NF condition. The relation is in 3NF but not BCNF.