2
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ But seriously, perhaps this will help: blackwellreference.com/public/… $\endgroup$ Apr 3, 2013 at 21:34
  • 1
    $\begingroup$ What means "linguistically speaking"? $\endgroup$
    – frafl
    Apr 4, 2013 at 20:14
  • $\begingroup$ In the Alice databases book (available online from the authors) the motivation is: given a set of functional dependencies, one wants to know if any other functional dependencies are necessarily satisfied by an instance that satisfies the original set. One can then add all these additional dependencies to the set to form the closure. $\endgroup$ Apr 10, 2013 at 22:25

2 Answers 2

1
$\begingroup$

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:

  • the closure of {1} with respect to the operation add 2 is the set of odd natural numbers
  • the closure of {1,3,5} with respect to the operation multiply is $\{3^n5^m \mid n, m \in I\!\!N\}$
  • the transitive closure of the relation {(1,2), (2,4), (4,5)} is {(1,2), (1,4), (1,5), (2,4), (2,5), (4,5)} (the smallest transitive set that includes the original set)
$\endgroup$
3
  • $\begingroup$ This answer explains closure, but not semantic, as Romuald's answer does. $\endgroup$ Jun 27, 2013 at 8:12
  • $\begingroup$ Does $\mathbb N$ containg $0$ ? --- In the third transitive closure, shouldn't you add (1,4) and (2,5)? $\endgroup$
    – babou
    Aug 5, 2015 at 11:08
  • $\begingroup$ 1) I've never seen an $I\!N$ that didn't (although I've heard of it). 1) Yes, thanks, I've added them.. $\endgroup$ Aug 5, 2015 at 16:58
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ may you plz provide argument for the downvote? $\endgroup$
    – Romuald
    Apr 16, 2013 at 11:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.