Consider the algorithm in figure to compute ?+. Show that this algorithm is more efficient than the one presented in Figure (Section 7.3.3) and that it computes ?+ correctly.

Transcribed Image Text:

result := 0; /* fdcount is an array whose ith element contains the numb of attributes on the left side of the ith FD that are not yet known to be in at */ for i := 1 to |F| do begin let 3 fdcount [i] = 13; - y denote the ith FD; end /* appears is an array with one entry for each attribute. The entry for attribute A is a list of integers. Each integer i on the list indicates that A appears on the left side of the ith FD*/ for each attribute A do begin appears (A] := NIL; for i := 1 to |F| do begin let 3 - y denote the ith FD; if A € B then add i to appears (A]; end end addin (a); return (result); procedure addin (a); for each attribute A in a do begin if A ¢ result then begin result := result U {A}; for each element i of appears[A] do begin fdcount [i] := fdcount [i] - 1; if fdcount [i] = 0 then begin let 3 - y denote the ith FD; addin (y); end end end end