Accession Number : ADA135303

Title :   Notions of Dependency Satisfaction.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Graham,M H ; Mendelzon,A O ; Vardi,M Y

PDF Url : ADA135303

Report Date : Aug 1983

Pagination or Media Count : 38

Abstract : Two notions of dependency satisfaction, consistency and completeness, are introduced. Consistency is the natural generalization of weak-instance satisfaction and seems appropriate when only equality-generating dependencies are given, but disagrees with the standard notion in the presence of tuple-generating dependencies. Completeness is based on the intuitive semantics of tuple-generating dependencies but differs from the standard notion for equality-generating dependencies. It is argued that neither approach is the correct one, but rather that they correspond to different policies on constraint enforcement, and each one is appropriate in different circumstances. Consistency and completeness of a state are characterized in terms of the tableau associated with the state and in terms of logical properties of a set of first-order sentences associated with the state. A close relation between the problems of testing for consistency and completeness and of testing implication of dependencies is established, leading to lower and upper bounds for the complexity of consistency and completeness. The possibility of formalizing dependency satisfaction without using a universal relation scheme is examined. (Author)

Descriptors :   *Data bases, Test and evaluation, Consistency, Theorems, Test methods, Embedding, Programming languages

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE