Access Restriction

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

   Open content in new tab
Source: ACM Digital Library