Chapter 7, Problem 8PE

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{α}$