Relational Database Design Functional Dependency – definition, trivial and non-trivial FD, Armstrong's Axioms/Inference Rules

Functional Dependency – definition, trivial and non-trivial FD, Armstrong's Axioms/Inference Rules

1. Database Management System Bhoomika Patel , Assistant Professor Computer Science & Engineering

2. Relational Databse Design CHAPTER-5

3. Contents Functional Dependency – definition, trivial and non-trivial FD Armstrong's Axioms/Inference Rules Closure of FD Closure of Attributes Candidate Key Finding a Candidate Key Decomposition (Lossy & Lossless) Database Anomalies normalization – 1Nf, 2NF, 3NF, BCNF, 4NF, 5NF

4. Functional Dependency: Brief overview of databases and the importance of data integrity. Introduction to Functional Dependencies (FD) as a concept ensuring data consistency. Functional Dependency (FD) is a constraint between two sets of attributes in a relation from a database. Notation: X→YX \rightarrow YX→Y Meaning: Attribute Y is functionally dependent on attribute X if each value of X is associated with precisely one value of Y. Example: Table with attributes: StudentID, StudentName, CourseID, CourseName Example FD: StudentID→StudentNameStudentID \rightarrow StudentNameStudentID→StudentName, CourseID→CourseNameCourseID \rightarrow CourseNameCourseID→CourseName Explanation of the relationship between the attributes.

5. Trivial Functional Dependency: Definition: A functional dependency X→YX \rightarrow YX→Y is trivial if YYY is a subset of XXX. Example: If X={A,B}X = \{A, B\}X={A,B}, then A→AA \rightarrow AA→A and {A,B}→A\{A, B\} \rightarrow A{A,B}→A are trivial FDs. Explanation: These dependencies hold true by default.

6. Non-Trivial Functional Dependency: Definition: A functional dependency X→YX \rightarrow YX→Y is non-trivial if YYY is not a subset of XXX. Example: If X={A}X = \{A\}X={A} and Y={B}Y = \{B\}Y={B}, then A→BA \rightarrow BA→B is non-trivial. Explanation: These dependencies provide meaningful constraints in database design.

7. Candidatekey: A candidate key is a minimal set of attributes that can uniquely identify a tuple in a relation. Every relation can have one or more candidate keys. Finding candidate key: Given a relation and a set of functional dependencies: Relation R(A, B, C, D) FDs: {A → B, C → D} Step-by-step process to identify candidate keys.

8. Decomposition: Decomposition is the process of breaking down a relation into two or more sub-relations. Purpose: To eliminate redundancy, prevent anomalies, and ensure data integrity. Types: Lossy Decomposition Lossless Decomposition

9. Lossy Decomposition: Definition: Decomposition where the original relation cannot be perfectly reconstructed from the decomposed sub-relations. Example: Illustrative example showing data loss after decomposition. Consequences: Data anomalies, potential loss of information. Given relation R(A, B, C). Decomposed into R1(A, B) and R2(B, C). Loss of information due to redundancy in B. Illustration of how original relation cannot be accurately reconstructed.

10. Lossless Decomposition: Definition: Decomposition where the original relation can be perfectly reconstructed from the decomposed sub-relations. Conditions: Dependency preservation and ensuring common attributes form a super key. Importance: Ensures data integrity and prevents anomalies. Given relation R(A, B, C). Decomposed into R1(A, B) and R2(A, C). Reconstruction: Natural join of R1 and R2 restores the original relation. Illustration of how the original relation is accurately reconstructed.

11. Database Anomalies: Definition: Inconsistencies or errors in a database due to improper database design. Causes: Typically caused by redundancy and lack of normalization.

12. First Normal Form (1NF) Definition: A relation is in 1NF if it contains only atomic (indivisible) values. Rules: No repeating groups, no multi-valued attributes. Example: Converting a table with repeating groups to 1NF. Example: First Normal Form (1NF) Initial table with repeating groups. Conversion to 1NF by eliminating repeating groups and ensuring atomic values.

13. Second Normal Form (2NF) Definition: A relation is in 2NF if it is in 1NF and all non-key attributes are fully dependent on the primary key. Rule: Eliminate partial dependencies. Example: Converting a table from 1NF to 2NF. example: Second Normal Form (2NF) Initial table in 1NF with partial dependencies. Conversion to 2NF by removing partial dependencies and creating separate tables.

14. Third Normal Form (3NF): Definition: A relation is in 3NF if it is in 2NF and all the attributes are functionally dependent only on the primary key. Rule: Eliminate transitive dependencies. Example: Converting a table from 2NF to 3NF. Example: Third Normal Form (3NF) Initial table in 2NF with transitive dependencies. Conversion to 3NF by removing transitive dependencies and creating separate tables.

15. Boyce-Codd Normal Form (BCNF) Definition: A relation is in BCNF if it is in 3NF and every determinant is a candidate key. Rule: Handle situations where 3NF is insufficient. Example: Converting a table from 3NF to BCNF. Example: Boyce-Codd Normal Form (BCNF) Initial table in 3NF with anomalies. Conversion to BCNF by ensuring every determinant is a candidate key.

16. Fourth Normal Form (4NF) Definition: A relation is in 4NF if it is in BCNF and has no multi-valued dependencies. Rule: Eliminate multi-valued dependencies. Example: Converting a table from BCNF to 4NF. Example: Fourth Normal Form (4NF) Initial table in BCNF with multi-valued dependencies. Conversion to 4NF by removing multi-valued dependencies and creating separate tables.

17. Fifth Normal Form (5NF) Definition: A relation is in 5NF if it is in 4NF and has no join dependencies. Rule: Eliminate join dependencies. Example: Converting a table from 4NF to 5NF. Example: Fifth Normal Form (5NF) Initial table in 4NF with join dependencies. Conversion to 5NF by removing join dependencies and ensuring that the table can be decomposed into smaller tables without loss of information.

18. www.paruluniversity.ac.in