Algorithme de Bernstein

• X, Y, ... et A, B, C ensembles d'attributs.
• Données : R=(A₁, A₂, ... A_n) un schéma de relation et F un ensemble de df sur R.
• Résultat : une décomposition de R muni de F en schémas de relations 3NF SPI SPD
• Algorithme :
  1. On remplace F par sa couverture minimale. On cherche les clés minimales de R et on teste si R est en 3NF. Si oui on s'arrete sinon on continue.
  2. On regroupe les df X→A_i (1<=i<=p) ayant un même membre gauche. Pour chaque membre gauche X, on définit un schéma de relation contenant tous les attributs des df, soit R_X=(X, A₁, A₂, ... A_p). Le schéma R_X est muni de l'ensemble de df X→A_i
  3. Si aucun des schémas R_X définis à l'étape 2 ne contient de clé de R, alors on ajoute un schéma R_K=(K), où K est une clé minimale muni d'aucune df.
• Tous les R_i obtenus en (2.) sont bien en 3NF
• Le schéma R_K assure une décomposition SPI
• La décomposition est trivialement SPD car la réunion des df des nouveaux schémas est F