  This paper examines attribute dependencies in data that involve grades, such
as a grade to which an object is red or a grade to which two objects are
similar. We thus extend the classical agenda by allowing graded, or fuzzy,
attributes instead of Boolean attributes in case of attribute implications, and
allowing approximate match based on degrees of similarity instead of exact
match in case of functional dependencies. In a sense, we move from bivalence,
inherently present in the now-available theories of dependencies, to a more
flexible setting that involves grades. Such a shift has far-reaching
consequences. We argue that a reasonable theory of dependencies may be
developed by making use of mathematical fuzzy logic. Namely, the theory of
dependencies is then based on a solid logic calculus the same way the classical
dependencies are based on classical logic. For instance, rather than handling
degrees of similarity in an ad hoc manner, we consistently treat them as truth
values, the same way as true (match) and false (mismatch) are treated in
classical theories. In addition, several notions intuitively embraced in the
presence of grades, such as a degree of validity of a particular dependence or
a degree of entailment, naturally emerge and receive a conceptually clean
treatment in the presented approach. In the paper, we discuss motivations,
provide basic notions of syntax and semantics, and develop basic results which
include entailment of dependencies, associated closure structures, a logic of
dependencies with two versions of completeness theorem, results and algorithms
regarding complete non-redundant sets of dependencies, relationship to and a
possible reductionist interface to classical dependencies, and relationship to
functional dependencies over domains with similarity.
