Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
In the context of database theory, what does semantic closure mean (linguistically speaking, i.e. not the mathematical definition)
If X is the set of attributes of $F$, then the semantic closure $F^+$ of $F$ is defined as follows:
$F^+=\{$ Y $\rightarrow$ Z $\ |\ $ Y $\cup$ Z $\subseteq$ X $\wedge\ F \models$ Y $\rightarrow$ Z $\}$
$F \models $ Y $\rightarrow$ Z means that any database instance that satisfies every functional dependency of $F$ also satisfies Y $\rightarrow$ Z
Generally speaking, the term closure is used when you have sets of items and some kind of operation that, given one or more items, can produce more such items. The closure of a set of items with respect to the operation is the set obtained by applying the operation on items in the set in whichever way possible, adding the resulting items to the set, and repeating this until no more items can be added (which may be infinitely often). The resulting set is the smallest set that includes the original set and is closed under the operation (in the sense that all possible applications of the operation on items in the set produce items that are also in the set).
Examples:
In this context, $F^+ = \{ X \rightarrow Y \mid F \models X \rightarrow Y \}$ is the set of all the dependencies that semantically (logically) follow from $F$ as you wrote. You also have a syntactic closure, defined as $F^\star = \{ X \rightarrow Y \mid F \vdash X \rightarrow Y \}$ where $F \vdash X \rightarrow Y$ means that $X \rightarrow Y$ can be deduced from $F$ according to an inference system, in this case, Armstrong's axioms.
Armstrong's system is both sound and complete so $F^+ = F^\star$, but the concepts are different. To illustrate the difference, let $\Sigma = \{A \rightarrow B, BC \rightarrow D\}$ and prove the following:
$AC \rightarrow D \in \Sigma^+$ (semantic proof). Let $r$ an instance such that $r \models A \rightarrow B$ and $r \models BC \rightarrow D$. Assume $t_1, t_2 \in r$ with $t_1[AC] = t_2[AC]$ this implies $t_1[A] = t_2[A]$ which implies $t_1[B] = t_2[B]$ because $r \models A \rightarrow B$. Thus we have $t_1[BC] = t_2[BC]$ and we can conclude $t_1[D] = t_2[D]$ because $r \models BC \rightarrow D$. Thus $t_1[AC] = t_2[AC]$ implies $t_1[D] = t_2[D]$ for arbitrary tuples $t_1$ and $t_2$ so $r \models AC \rightarrow D$. We have shown an arbitrary instance model of $\Sigma$ is a model of $AC \rightarrow D$ too, so $\Sigma \models AC \rightarrow D$.
$AC \rightarrow D \in \Sigma^\star$ (axiomatic proof). From $A \rightarrow B$ we obtain $AC \rightarrow BC$ by augmentation. Now using $BC \rightarrow D$ we obtain $AC \rightarrow D$ by transitivity.
