Abstract
This paper explores the logic of functional dependencies (FDs) in systems that exhibit local consistency but lack a single global state. Such scenarios are common in quantum mechanics (contextuality), distributed databases, and Bayesian statistics. The authors demonstrate that classical inference rules, specifically transitivity, fail in this setting. To address this, they introduce novel axioms—the cycle and contextual chain rules—and provide a graph-theoretic framework to determine when local structures can be realized as valid probability distributions or multisets.
Introduction
In many scientific and engineering domains, we encounter data through overlapping, partial views. Relational databases partition data across tables; Bayesian networks utilize marginal distributions; quantum physics measures subsets of variables. Traditionally, it is assumed these views can be synthesized into a globally consistent whole. However, systems can be locally consistent (agreeing on overlaps) yet globally inconsistent (no single distribution can produce all views). This paper investigates how logical inference, particularly FDs like $A \to B$, operates when the global consistency assumption is discarded.
Theoretical Framework
The authors employ $K$-relations as a unifying abstraction. A $K$-relation is a database table where rows are annotated with values from a monoid $K$. By varying $K$, this framework can represent boolean logic, multisets (counts), or probability distributions. To model sets of relations that are locally consistent, the authors define "contextual $K$-families" and evaluate Armstrong’s classical axioms (Reflexivity, Augmentation, and Transitivity) within this environment.
The Failure of Transitivity
A central finding is that classical transitivity ($A \to B$ and $B \to C \implies A \to C$) fails in locally consistent systems. Consider a medical database where one table maps Patient to Diagnosis and another maps Diagnosis to a standard Treatment. While these tables might be locally consistent, a third table recording actual Patient to Treatment mappings might show deviations from the standard protocol. In this case, Patient no longer strictly determines Treatment globally, even if the local dependencies hold.
New Axioms and Realizability
To replace failed transitivity, the authors introduce Context Dependencies (CDs)—declarations that certain variables are measured together. They propose the Cycle Rule (if $x_1 \to x_2 \to \dots \to x_k \to x_1$, then $x_1 \to x_k$) and the Contextual Chain Rule for ternary contexts.
Furthermore, they address the "realizability" problem: when can a locally consistent boolean framework be translated into a valid probability distribution? They prove that for specific "hole" context sequences, a system is $K$-realizable if and only if its "overlap projection graph" is edge-cyclic. Notably, realizability with probabilities (non-negative reals) is equivalent to realizability with counts (natural numbers).
Complexity and Completeness
The paper provides a rigorous analysis of the complexity and completeness of the proposed proof systems. For unary FDs with binary contexts, Reflexivity combined with the Cycle Rule is shown to be sound and complete.
As shown in the summary table above, the complexity of determining entailment for unary FDs with binary CDs is NL-complete, while the contextual chain rule allows for efficient PTIME computation.
Conclusion and Future Work
This work establishes a foundation for reasoning about dependencies in contextual systems. While currently focused on unary FDs, it opens significant avenues for future research, including the search for finite axiom sets for general FDs and the generalization of graph-theoretic realizability to arbitrary context sets. The authors also suggest exploring whether the full (non-unary) entailment problem is even finitely axiomatizable or decidable.
Summary updated