Unit4 - Subjective Questions

Data Integrity Rules ensure the accuracy, consistency, and reliability of data in a database throughout its lifecycle.

1. Entity Integrity Rule:

• Definition: This rule states that the primary key of a relation cannot be null.
• Reasoning: Since the primary key uniquely identifies each row in a table, a null value would mean the entity cannot be uniquely identified.
• Example: In a STUDENT(StudentID, Name, Age) table where StudentID is the primary key, no student record can have a NULL StudentID.

2. Referential Integrity Rule:

• Definition: This rule applies to foreign keys. It states that if a foreign key exists in a relation, either the foreign key value must match a candidate key value of some tuple in its home relation, or the foreign key value must be wholly null.
• Example: Consider EMPLOYEE(EmpID, Name, DeptID) and DEPARTMENT(DeptID, DeptName). The DeptID in EMPLOYEE is a foreign key. An employee can only be assigned a DeptID that actually exists in the DEPARTMENT table, or it can be NULL (if they are not yet assigned a department).

Functional Dependency (FD) is a relationship that exists between two attributes or sets of attributes in a relational database.

• Definition: If and are subsets of attributes of a relation , then is functionally dependent on , denoted as , if for every valid instance of , each value is associated with precisely one value.
• Determinant and Dependent: In , is the determinant and is the dependent.

Significance in Database Design:

• Identifies Keys: FDs help in identifying primary and candidate keys. If and determines all attributes of the relation, is a superkey.
• Guides Normalization: FDs are the core building blocks of normalization (1NF, 2NF, 3NF, BCNF). They help identify partial and transitive dependencies that cause anomalies.
• Maintains Data Quality: They act as constraints on the database, preventing invalid data from being inserted.

Normalization is the process of organizing data in a database to reduce redundancy and improve data integrity.

Need for Normalization:

• To eliminate redundant data (storing the same data in multiple places).
• To ensure data dependencies make sense (storing related data together).
• To prevent database anomalies during data operations.

Anomalies in Unnormalized Databases:

• Insertion Anomaly: Occurs when certain attributes cannot be inserted into the database without the presence of other attributes. Example: If a table stores Student, Course, and Professor, we might not be able to add a new Professor who hasn't been assigned a Course yet, unless we use NULLs.
• Update Anomaly: Occurs when duplicate data is not updated correctly in all places, leading to inconsistent data. Example: If a student's address is stored multiple times for each course they take, changing their address requires updating multiple rows. Missing one row leads to an inconsistency.
• Deletion Anomaly: Occurs when deleting a record inadvertently causes the loss of other required data. Example: If a student drops their only course, deleting that record might also delete all information about the student themselves.

First Normal Form (1NF) dictates that a relation must not contain any repeating groups or multi-valued attributes. Every attribute must be atomic (indivisible).

Rules for 1NF:

• Each table cell must contain a single value.
• Each record needs to be unique (typically ensured by a primary key).

Example of Unnormalized Table (Not in 1NF):
Consider STUDENT_COURSES(StudentID, Name, Courses)
Row 1: (1, 'Alice', 'Math, Physics')
Row 2: (2, 'Bob', 'Chemistry')
Here, the Courses attribute contains multiple values for Alice.

Conversion to 1NF:
We create a new row for each value in the multi-valued attribute.
STUDENT_COURSES_1NF(StudentID, Name, Course)
Row 1: (1, 'Alice', 'Math')
Row 2: (1, 'Alice', 'Physics')
Row 3: (2, 'Bob', 'Chemistry')
Now, every cell holds a single, atomic value.

Partial Dependency occurs when a non-prime attribute (an attribute not part of any candidate key) is functionally dependent on only a part of a composite primary key, rather than the entire key.

Second Normal Form (2NF):
A relation is in 2NF if:

1. It is already in 1NF.
2. It has no partial dependencies.

Resolution Process:

• Identify the Primary Key: Let's say a relation has a composite primary key .
• Identify Dependencies: Suppose the functional dependencies are and . Here, is partially dependent on the key because it depends only on , not the full key .
• Decompose the Table: To convert to 2NF, split the table into two:
  • Table 1: Contains the full key and attributes fully dependent on it:
  • Table 2: Contains the part of the key causing the partial dependency and the attributes dependent on it: .
    This eliminates the partial dependency while preserving data.

Transitive Dependency occurs when a non-prime attribute depends on another non-prime attribute rather than directly on the primary key. Mathematically, if and , then is a transitive dependency (assuming is not a candidate key).

Example:
Consider EMPLOYEE(EmpID, EmpName, DeptID, DeptName) with Primary Key EmpID.

• (Employee belongs to a department)
• (Department ID determines Department Name)
  Here, DeptName depends on EmpID transitively through DeptID.

Third Normal Form (3NF):
A relation is in 3NF if:

1. It is in 2NF.
2. It contains no transitive dependencies (i.e., every non-prime attribute is non-transitively dependent on every candidate key).

Resolution:
To achieve 3NF, the relation is decomposed:

• EMP(EmpID, EmpName, DeptID)
• DEPT(DeptID, DeptName)
  This eliminates the transitive dependency and prevents update anomalies related to department names.

Boyce-Codd Normal Form (BCNF) is an extension or stronger version of 3NF.

3NF Definition:
For every non-trivial functional dependency , at least one is true:

1. is a superkey.
2. is a prime attribute (part of some candidate key).

BCNF Definition:
For every non-trivial functional dependency , MUST be a superkey. There is no exception for being a prime attribute.

Why BCNF is stronger:
BCNF is stricter because it handles situations where a prime attribute depends on a non-prime attribute (overlapping candidate keys). 3NF allows this anomaly as long as the dependent attribute is part of a key. BCNF forbids this completely. Therefore, every relation in BCNF is automatically in 3NF, but a relation in 3NF is not necessarily in BCNF.

Multivalued Dependency (MVD) occurs when the presence of one or more rows in a table implies the presence of one or more other rows in that same table. It exists when an attribute determines a set of values for another attribute, completely independent of a third attribute.

• Notation: (A multidetermines B).
• Condition: For a relation , exists if, for any two tuples that agree on , we can swap their values and the resulting tuples must also exist in .

Example:
Consider COURSE(Course, Instructor, Textbook).
Suppose a course (e.g., 'Physics') has multiple instructors (e.g., 'Dr. Smith', 'Dr. Jones') and multiple textbooks (e.g., 'Text A', 'Text B'). Instructors and Textbooks are independent of each other.

To represent this without losing information, the table must contain all combinations:

• (Physics, Dr. Smith, Text A)
• (Physics, Dr. Smith, Text B)
• (Physics, Dr. Jones, Text A)
• (Physics, Dr. Jones, Text B)

Problem: This causes massive data redundancy and update anomalies. If a new textbook is added, multiple rows must be inserted for every instructor.

Fourth Normal Form (4NF) deals specifically with eliminating unwanted multivalued dependencies (MVDs).

Definition:
A relation schema is in 4NF with respect to a set of dependencies (FDs and MVDs) if, for every non-trivial multivalued dependency , is a superkey for .

• An MVD is trivial if or equals the entire set of attributes of .

Resolution (Decomposition into 4NF):
If a table has an MVD and is not in 4NF (because is not a superkey), we decompose the table into two tables to eliminate the redundancy:

2. (where Z represents the remaining attributes)

Example Solution:
Using the COURSE(Course, Instructor, Textbook) example with and , we split it into:

• COURSE_INSTRUCTOR(Course, Instructor)
• COURSE_TEXTBOOK(Course, Textbook)
  This eliminates the redundancy of storing every combination of instructor and textbook.

Functional dependencies () can be categorized as trivial or non-trivial based on the relationship between the determinant () and the dependent ().

1. Trivial Functional Dependency:

• Definition: A dependency is trivial if is a subset of (). It means an attribute always determines itself or a subset of itself. This is always true by default.
• Example: In a table with attributes and , the dependency is trivial because is a subset of . Similarly, is trivial.

2. Non-Trivial Functional Dependency:

• Definition: A dependency is non-trivial if is NOT a subset of (). This represents a genuine constraint on the data.
• Example: In a STUDENT(StudentID, Name) table, is a non-trivial dependency because Name is not a subset of StudentID.

(Note: A dependency is completely non-trivial if , meaning they have no attributes in common)..

Armstrong's Axioms are a set of sound and complete inference rules used to derive all functional dependencies logically implied by a given set of functional dependencies ().

Primary Rules (Axioms):

1. Reflexivity Rule: If is a subset of (), then . (This defines trivial dependencies).
2. Augmentation Rule: If , then for any set of attributes , . (Adding the same attributes to both sides maintains the dependency).
3. Transitivity Rule: If and , then .

Additional (Derived) Rules:

4. Union Rule: If and , then .
5. Decomposition Rule: If , then and .
6. Pseudotransitivity Rule: If and , then .

These axioms are called "sound" because they do not generate incorrect dependencies, and "complete" because they can generate all true implied dependencies.

Closure of a set of Functional Dependencies ():
The closure of a set of FDs, denoted by , is the set of all functional dependencies that can be logically derived from using Armstrong's Axioms.

Closure of an Attribute Set ():
The closure of an attribute set under a set of FDs , denoted as , is the set of all attributes that are functionally determined by .

Algorithm to compute :

1. Initialize the result set to : Closure = X
2. Repeat the following until Closure stops changing:
   • For each functional dependency in :
   • If , then Closure = Closure \cup B (Add B to the Closure)
3. Return Closure.

Significance: Computing is widely used to determine if an attribute set is a superkey (if contains all attributes of the relation) and to check if a specific dependency holds (it holds if ).

Lossless-Join Decomposition is a property of decomposition in relational database design which ensures that no information is lost when a relation is broken down into smaller relations.

Definition:
A decomposition of relation into and is lossless if the natural join of and exactly yields the original relation .
Mathematically:

Condition for Lossless Join:
Let be decomposed into and . The decomposition is lossless if at least one of the following holds true:

1. (The common attributes form a superkey for )
2. (The common attributes form a superkey for )

Why it is necessary:
If a decomposition is "lossy" (not lossless), joining the tables back together will produce spurious tuples (fake rows that did not exist in the original table). This ruins data integrity because the system can no longer distinguish between the original correct data and the false generated data.

Dependency Preserving Decomposition is a property where all functional dependencies present in the original relation can still be enforced after the relation has been decomposed, without needing to join the decomposed relations.

Definition:
Let be a relation with functional dependencies . is decomposed into . Let be the set of dependencies in that only involve attributes in . The decomposition is dependency preserving if the union of all 's () logically implies all dependencies in the original . Mathematically, .

Example:
Let with .
Suppose we decompose into and .

• can enforce .
• can enforce .
  Since both original dependencies can be checked locally within the new tables, the decomposition is dependency preserving.
  (Note: Checking transitive dependencies like is implicitly covered if and are preserved)..

Step 1: Find the Candidate Key

• Calculate the closure of attributes.
• (Since , , ).
• Since contains all attributes, is a Candidate Key (and the only one, as no other attribute determines ).
• Prime attribute: . Non-prime attributes: .

Step 2: Check for 2NF

• 2NF requires no partial dependencies. A partial dependency exists if a proper subset of a candidate key determines a non-prime attribute.
• Since the candidate key is a single attribute, there can be no proper subset of the key.
• Therefore, there are no partial dependencies. is in 2NF.

Step 3: Check for 3NF

• 3NF requires no transitive dependencies. A transitive dependency exists if a non-prime attribute determines another non-prime attribute.
• Look at : is non-prime, is non-prime. This is a transitive dependency.
• Look at : is non-prime, is non-prime. This is a transitive dependency.
• Because of these transitive dependencies, is not in 3NF.

Conclusion:
The highest normal form of relation is 2NF.

1. Domain Integrity:

• Definition: Domain integrity dictates that all columns in a relational database must be declared upon a defined domain. A domain is a set of valid values for an attribute.
• Purpose: It ensures that data entered into a column falls within legal constraints (data type, format, length, and range).
• Example: A Salary column must be a numeric data type and greater than zero. An Age column might be restricted to integers between 18 and 65. Constraints like CHECK, DEFAULT, and NOT NULL are often used to enforce domain integrity.

2. User-Defined Integrity:

• Definition: User-defined integrity encompasses specific business rules and constraints that do not fall under entity, referential, or domain integrity categories.
• Purpose: It allows database designers to enforce custom business logic directly within the database system.
• Example: A bank database might have a rule: "A customer's total withdrawal in a day cannot exceed their current balance plus a 500 overdraft limit." This is enforced via custom triggers or complex table-level CHECK constraints.

To compute the closure of under the given FDs:

Given FDs:

Step-by-step computation:

1. Initialization: Start with the given set of attributes.
   
2. Iteration 1: Check all FDs against the current .
   • Using : Since , add . Now, .
   • Using : Since , add . Now, .
   • Using : Since , add . Now, .
3. Iteration 2: The now contains all attributes of the relation. No further additions are possible.

Result:
.
Since the closure of contains all attributes of the relation , is a superkey (and candidate key) for .

Denormalization is the process of intentionally introducing redundancy into a database by combining tables that were previously separated during normalization.

Reasons for Denormalization:

• Performance Optimization: The primary reason is to speed up complex SELECT queries. Normalization spreads data across many tables, requiring expensive JOIN operations to retrieve combined data. Denormalizing reduces the number of joins needed.
• Reporting/OLAP: Data warehouses often use denormalized structures (like Star or Snowflake schemas) because they prioritize fast data retrieval over insert/update efficiency.

Trade-offs (Disadvantages):

• Data Redundancy: More storage space is required since data is duplicated.
• Update Anomalies: Updating a piece of duplicated information requires updating multiple rows, increasing the risk of data inconsistency.
• Slower DML Operations: While SELECT queries become faster, INSERT, UPDATE, and DELETE operations become slower because the database must maintain the redundant data.
• Complex Code: Application code or database triggers must be written to ensure that the redundant data remains synchronized.

Equivalence of Functional Dependencies:
Two sets of functional dependencies, and , are considered equivalent (denoted as ) if they logically imply exactly the same set of functional dependencies.

In other words, and are equivalent if the closure of is equal to the closure of :

How to prove equivalence:
To prove that , we must show two conditions:

1. covers (): This means every functional dependency in can be derived from . To test this, for every FD in , we calculate using the rules of , and check if .
2. covers (): This means every functional dependency in can be derived from . We test this by taking every FD in , calculating using the rules of , and checking if .

If both conditions hold true, the two sets of FDs are equivalent.

A relation is in 3NF but not in BCNF if there is a non-trivial functional dependency where is not a superkey, but is a prime attribute (part of a candidate key). This usually happens when a table has multiple overlapping composite candidate keys.

Scenario Example:
Consider STUDENT_ADVISOR(Student, Subject, Advisor).
Rules:

1. A student can take many subjects, but has only one advisor per subject:
2. An advisor advises in only one subject:
3. A student cannot have the same advisor multiple times.

Candidate Keys:

• [from rule 1]
• [since Advisor determines Subject]
  Prime attributes: Student, Subject, Advisor. Non-prime: None.

Normal Form Analysis:

• 3NF: The FD has (not a superkey) determining (a prime attribute). Since the dependent is prime, it passes 3NF.
• BCNF: BCNF requires the determinant of every non-trivial FD to be a superkey. In , is NOT a superkey. Therefore, it violates BCNF.

Decomposition into BCNF:
We split the table based on the violating FD ():

1. (Stores which advisor teaches which subject. Key: Advisor)
2. (Stores which student is assigned to which advisor. Key: Student, Advisor)
   Now, both tables are in BCNF.