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

ABSTRACT

According to the definition of satisfaction of Boolean dependencies, Theorem 15 is not true for Boolean dependencies with negation. (A 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 r a set &agr;(r) of truth assignments, as follows. For each pair of distinct tuples of r, the set &agr;(r) contains the truth assignment that maps an attribute A to true if the two tuples are equal on A, and to false if the two tuples have different values for A. A Boolean dependency &sgr; is satisfied by a relation r if &sgr; (i.e., the corresponding Boolean formula) satisfies every truth assignment of &agr;(r). The original definition given in the paper is equivalent to having &agr;(r) also include the truth assignment that is generated by pairs in which both tuples are really the same tuple of r, that is, to having &agr;(r) also always include the truth assignment &tgr; 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

REFERENCES

• 1: BI~RMAN, J., AND BLOK, W.J. Positive Boolean dependencies. Report. Department of Mathematics, Statistics, and Computer Science, Univ. of Illinois, Chicago, Ill. 1985.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Algorithms, Theory