Monoidal functional dependencies

• A logic for reasoning with similarity-preserving dependencies is proposed.
• Its semantics is defined using commutative integral partially ordered monoids.
• The logic is complete and decidable.
• A closure-like algorithm for non-contracting sets of dependencies is presented.
• Two kinds of semantics are discussed: a propositional and a relational one.

We present a complete logic for reasoning with functional dependencies (FDs) with semantics defined over classes of commutative integral partially ordered monoids and complete residuated lattices. The dependencies allow us to express stronger relationships between attribute values than the ordinary FDs. In our setting, the dependencies not only express that certain values are determined by others but also express that similar values of attributes imply similar values of other attributes. We show complete axiomatization using a system of Armstrong-like rules, comment on related computational issues, and the relational vs. propositional semantics of the dependencies.