  In several different settings, one comes across situations in which the
objects of study are locally consistent but globally inconsistent. Earlier work
about probability distributions by Vorob'ev (1962) and about database relations
by Beeri, Fagin, Maier, Yannakakis (1983) produced characterizations of when
local consistency always implies global consistency. Towards a common
generalization of these results, we consider K-relations, that is, relations
over a set of attributes such that each tuple in the relation is associated
with an element from an arbitrary, but fixed, positive semiring K. We introduce
the notions of projection of a K-relation, consistency of two K-relations, and
global consistency of a collection of K-relations; these notions are natural
extensions of the corresponding notions about probability distributions and
database relations. We then show that a collection of sets of attributes has
the property that every pairwise consistent collection of K-relations over
those attributes is globally consistent if and only if the sets of attributes
form an acyclic hypergraph. This generalizes the aforementioned results by
Vorob'ev and by Beeri et al., and demonstrates that K-relations over positive
semirings constitute a natural framework for the study of the interplay between
local and global consistency. In the course of the proof, we introduce a notion
of join of two K-relations and argue that it is the "right" generalization of
the join of two database relations. Furthermore, to show that non-acyclic
hypergraphs yield pairwise consistent K-relations that are globally
inconsistent, we generalize a construction by Tseitin (1968) in his study of
hard-to-prove tautologies in propositional logic.
