Proposition for modification of Bernstein’s Algorithm for Vertical Normalization by Synthesis

U radu su analizirane mogućnosti algoritma za vertikalnu normalizaciju sintezom. I Bernsteinov (1976) i Yangov (1983) algoritam za vertikalnu normalizaciju sintezom polaze od pretpostavke da će svođenje ukupnog broja atributa u lijevim i desnim stranama svih zavisnosti u skupu funkcijskih zavisnost, imati za posljedicu minimalan broj kopija atributa u normaliziranom modelu baze podataka. Uz ovu pretpostavku vezana su dva problema. U prvom redu nije poznat algoritam za pronalaženje pokrivača zadanog skupa s minimalnim brojem atributa (tzv. optimalni pokrivač). Pored toga, iako će smanjivanje ukupnog broja atributa općenito smanjiti i ukupan broj kopija u modelu baze, nije sigurno da ćemo, polazeći od optimalnog pokrivača pomoću Bernsteinovog algoritma dobiti model baze s minimalnim brojem kopija. U radu se predlaže modifikacija Bernsteinovog algoritma, koja eliminira tzv. suvišne atribute (ako postoje), koje Bernsteinov algoritam ne eliminira. U slučaju postojanja suvišnih vrhova, predloženim modificiranim algoritmom, dobiva se komplet relacijskih shema u trećoj normalnoj formi s ukupno manjim brojem atributa, nego što se dobije Bernsteinovim algoritmom.