Backend Processor

Role:

For a set of functional dependencies (FDs)...

• Generate all appropriate candidate keys (CKs)
• Generate the canonical cover
• Decompose a relation into 2NF, 3NF & BCNF

TODO:

• Create CK generation script
  • Add sufficient # of test cases
  • Deploy
• Create canonical cover generation script
  • Add sufficient # of test cases
  • Deploy
• Decompose a relation into 2NF
  • Add sufficient # of test cases
  • Deploy
• Decompose a relation into 3NF
  • Add sufficient # of test cases
  • Deploy
• Decompose a relation into BCNF
  • Add sufficient # of test cases
  • Deploy

Candidate Key Generation

1. Determining mandatory attributes intuition:
   
   R(α₁, α₂, ..., α_n)
   Where R is our relation.
   
   β₁ ⇒ μ₁
   β₂ ⇒ μ₂
   β₃ ⇒ μ₃
   .
   .
   β_n ⇒ μ_n
   
   Where β_i, μ_i ∈ ∑* {α₁, α₂, ..., α_n}
   for i ≤ n
   
   Α = [ R- [(μ₁ ∪ μ₂ ∪ μ₃ ∪ ... ∪ μ_n) ∩ R] ]
   Where Α represents the attributes of the relation that are NOT included within the derivation portion (right side), of the FD.
   
   Α is the set of attributes that must be included within the candidate key
   
   

   Α is filtered on both the LHS and RHS of the FD to ensure that trivial redundancy is eliminated.

2. Adding accessory attributes onto the necessary minimal attributes (intuition above):

   • In this context, an accessory attribute is one that is not part of our set of necessary minimal attributes, but exists within the relational schema
     
     A heuristic approach is taken, where accessory attributes are added onto a working candidate key, and a heuristic based on the amount of unmatched FDs is taken. The accessory attribute that is associated with the smallest heuristic value, is added onto the working CK attribute, and the process repeats until we've reached a minimal heuristic value of 0.