### Correction to “An equivalence between relational database dependencies and a fragment of propositional logic”Correction to “An equivalence between relational database dependencies and a fragment of propositional logic”

Access Restriction
Subscribed

 Author Sagiv, Y. ♦ Delobel, C. ♦ Parker, D. S. ♦ Fagin, Ronald Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1987 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract According to the definition of satisfaction of Boolean dependencies, Theorem 15 is not true for Boolean dependencies with negation. (A $\textit{positive}$ Boolean dependency is built using the Boolean connectives ⋏, ⋎, and ↛; a general Boolean dependency (with negation) may use also the Boolean connective ¬.) Actually, the definition of satisfaction is not meaningful for Boolean dependencies with negation, since many are never satisfied. We show how the definition of satisfaction should be changed in order to make Boolean dependencies with negation meaningful and correct the error.We associate with each relation $\textit{r}$ a set $α(\textit{r})$ of truth assignments, as follows. For each pair of distinct tuples of $\textit{r},$ the set $α(\textit{r})$ contains the truth assignment that maps an attribute $\textit{A}$ to true if the two tuples are equal on $\textit{A},$ and to false if the two tuples have different values for $\textit{A}.$ A Boolean dependency &sgr; is satisfied by a relation $\textit{r}$ if &sgr; (i.e., the corresponding Boolean formula) satisfies every truth assignment of $α(\textit{r}).The$ original definition given in the paper is equivalent to having $α(\textit{r})$ also include the truth assignment that is generated by pairs in which both tuples are really the same tuple of $\textit{r},$ that is, to having $α(\textit{r})$ also always include the truth assignment τ mapping all attributes to true. Under that definition, however, many Boolean dependencies with negation are never satisfied and, hence, are meaningless. More precisely, according to the original definition, a Boolean dependency is satisfied by ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Publisher Date 1987-10-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 34 Issue Number 4 Page Count 3 Starting Page 1016 Ending Page 1018

#### Open content in new tab

Source: ACM Digital Library