Chapter 18, Problem 1PE

Explanation of Solution

Proof:

Consider the set of attributes be $\text{α}$ .

F is considered to be the set of functional dependencies (FDs).

The set of attributes is considered to be functionally determined by $\text{α}$ under F and is defined to be close of $\text{α}$ under $\text{F}\left({\text{α}}^{+}\right)$.

Using the Figure 7.19 and Figure 7.8:

The algorithm provided in the figure 7.19 will correctly compute the $\left({\text{α}}^{+}\right)$ as shown below:

• Computing what will happen after adding A to result.
• Proving $\text{α}\to \text{A}$
• Since $\text{α}\to \text{α}$ is trivially which means $\text{α}$ is considered to be a part of the result.
• Now, after adding $\text{A}\notin \text{α}$ to the resultant there should be existence of functional dependency that is $\text{β}\to \text{γ}$ where $\text{A}\in \text{γ}$ and where $\text{β}\subseteq \text{result}$.
• Or else the value of the “fdcount” will not become zero, then the related of condition of the algorithm will not change to be the value “false”.
• When $\text{A}\in {\text{α}}^{\text{+}}$, then it will added to the result for sure.
• Proving this by induction by utilizing the Armstrong’s axiom on the length of proof on $\text{α}\to \text{A}$ are shown below:
• The add- in procedure gets called with the argument say “c”, then all the attribute present in the “C” gets added to the result.
• Similarly in addition to it when the functional dependency “fdcount” value is zero, then all the attributes of its tail is surely added to the resultant too.
• Utilizing the induction to the base case that is when $\text{A}\in \text{α}$ then $\text{A}\in {\text{α}}^{+}$ is considered to be true because the very first call that is made to the add-in procedure is made with the argument $\text{α}$.
• Assume that $\text{α}\to \text{A}$ and it can be proved in “n” steps or lesser than “n” steps and then it is also $\text{A}\in \text{result}$.
• Now proving $\text{α}\to \text{A}$ in n+1 steps;
• The last step of proof can be obtained by applying one of the Armstrong axioms.
  • The below are three Armstrong’s axiom and they are
    • Reflexivity
      • A is considered to be set of attributes
      • $\text{B}\subseteq \text{C and B}\subseteq \text{A then A}\to \text{B}$
    • Augmentation
      • A is considered to be set of attributes
      • $\text{B}\to \text{C, then AB}\to \text{AC}$ will also hold
    • Transitivity
      • $\text{ A}\to \text{B and B}\to \text{A}$, then $\text{A}\to \text{C}$ can also be hold.
• This indicates that the A was already present in the result and also in the nth step itself.
• Or else by induction we can obtain that $\text{c}\subseteq \text{result}$

Comparison:

The algorithm present in the figure 7.19 is comparatively more efficient when compared with that of the figure 7.8 as shown below:

• Each and every functional dependency gets scanned only one in the main program.
• The resultant array size that appears is proportional to the size of the functional dependencies.
• The recursive call that is made to the procedure add-in is also considered to be linear to the size that it appears.
• Therefore, the time taken for the overall algorithm is linear to the size of the functional dependencies.
• The algorithm presented in the figure 7.8 requires quadratic time because
  • The loop gets performed based the times of functional dependencies(FD’s)
  • Also for each loop the FD gets scanned again and again.