$\mathbb{K}$. The monoid $\mathbb{N}[X]_{1}$ will feature prominently in
Section 5.5. Note that the elements in $\mathbb{N}[X]_{1}$ can be identified
with the finite support maps $c:X\to Z^{\geq 0}$ that assign a non-negative
integer to each indeterminate.

For all these examples, if $\mathbb{K}$ has the transportation property, so do
the various monoids of polynomials $\mathbb{K}[x]$, $\mathbb{K}[X]$,
$\mathbb{K}[X]_{m}$, etc., by Proposition 7. Similarly, if the inner
consistency property holds for $\mathbb{K}$-relations with sparse witnesses,
then the sparsity of witnesses is inherited for $\mathbb{K}[X]$-relations
annotated by polynomials with few non-zero coefficients, by Proposition 8.
$\dashv$

Example 11. Powersets revisited. An example of a different flavour is the
powerset monoid $\mathbb{P}(A)=(\mathscr{P}(A),\cup,\emptyset)$ of a finite
set $A$. This monoid is isomorphic to the product $\mathbb{B}^{A}$, where
$\mathbb{B}=(\\{0,1\\},\vee,0)$ is the Boolean monoid, and $A$ is viewed as a
finite index set. Note that it in this case it makes no difference whether we
consider $\mathbb{B}^{A}$ or $\mathbb{B}^{A}_{\mathrm{fin}}$ because the index
set is finite and, therefore, any indexed sequence has finite support.

Similarly, the monoid
$\mathbb{P}_{\mathrm{fin}}(A)=(\mathscr{P}_{\mathrm{fin}}(A),\cup,\emptyset)$
of finite subsets of a countably infinite set $A$ is isomorphic to
$\mathbb{B}^{A}_{\mathrm{fin}}$. It is also isomorphic to the monoid
$\mathbb{B}[X]$ of formal multivariate polynomials with coefficients in
$\mathbb{B}$ from the previous paragraph. $\dashv$

Example 12. Additive monoids of provenance semirings. The semiring
$\mathbb{N}[X]$ of formal multivariate polynomials with coefficients in
$\mathbb{N}$ is the _most informative_ member of a well-studied hierarchy of
_provenance semirings_ in database theory - see Figure 1.

$\begin{array}[]{ccccc}&&\mathbb{N}[X]&&\\\ &\swarrow&&\searrow&\\\
\mathbb{B}[X]&&&&\mathrm{Trio}[X]\\\ &\searrow&&\swarrow&\\\
&&\mathrm{Why}[X]&&\\\ &\swarrow&&\searrow&\\\
\mathrm{Lin}[X]&&&&\mathrm{PosBool}[X]\\\ &\searrow&&\swarrow&\\\
&&\mathbb{B}&&\end{array}$ Figure 1: The provenance semirings from [GKT07]. In
this diagram, an arrow $\mathbb{K}_{1}\rightarrow\mathbb{K}_{2}$ means that
there is a surjective semiring homomorphism from $\mathbb{K}_{1}$ to
$\mathbb{K}_{2}$.

The $\mathrm{Trio}[X]$ semiring has a technical definition (see [Gre11]) but
it is easily seen to be equivalently defined as $\mathbb{N}[X]_{\mathrm{m}}$,
the semiring of multilinear multivariate polynomials with coefficients in
$\mathbb{N}$. The $\mathrm{Why}[X]$ semiring is equivalently defined as
$\mathbb{B}[X]_{\mathrm{m}}$, the semiring of multilinear multivariate
polynomials with coefficients in $\mathbb{B}$. The $\mathrm{Lin}[X]$ semiring
is defined to have $P_{\mathrm{fin}}(X)\cup\\{\bot\\}$ as its base set, where
$P_{\mathrm{fin}}(X)$ denotes the collection of finite subsets of $X$ and
$\bot$ is a fresh element, with addition and multiplication both defined as
the union of sets, except for $\bot$ which is treated as the neutral element
of addition and as the absorptive element of multiplication. Finally, the
$\mathrm{PosBool}[X]$ semiring has as base set the collection of positive
Boolean formulas with variables in $X$ and constants $1$ and $0$ for true and
false, identified up to logical equivalence. Its operations are the standard
disjunction and conjunction of formulas for addition and multiplication,
respectively.

For the questions of interest in this paper, only the additive monoid
structure of these semirings matters. It should be clear that $\mathbb{N}[X]$
and $\mathrm{Trio}[X]$ have the additive structure of
$\mathbb{N}^{I}_{\mathrm{fin}}$ for an appropriate index set $I$, and,
likewise, $\mathbb{B}[X]$ and $\mathrm{Why}[X]$ have the additive structure of
$\mathbb{B}^{I}_{\mathrm{fin}}$ again for appropriate index set $I$. Thus, the
additive monoids of these four cases are covered by Proposition 7, which means
that these monoids have the transportation property. The additive structure of
$\mathrm{Lin}[X]$ is somewhat peculiar, but it is not hard to check that if it
is alternatively expanded with the intersection of sets for its multiplicative
structure, viewing $\bot$ as a second copy of the empty set, then we get an
additively absorptive and multiplicatively idempotent semiring, which is then
covered by Proposition 2. Similarly, $\mathrm{PosBool}[X]$ is covered in the
same way and therefore the additive monoids of these two semirings also have
the transportation property. Finally, we argued already that the Boolean
semiring $\mathbb{B}$ has the transportation property, which completes all
cases in the diagram of Figure 1. $\dashv$

###  5.5 The Free Commutative Monoid

For this section, recall the basic definitions of universal algebra concerning
homomorphisms, subalgebras, products and varieties of monoids as they were
presented in Section 2. An important result of universal algebra states that
varieties have _universal objects_ , referred to as _free algebras_. We state
this in the special case of monoids, but first we need two definitions.

Let $\mathcal{C}$ be a class of monoids. Note that so far we do not require
$\mathcal{C}$ to be a variety. Let $\mathbb{K}(X)=(K,+,0)$ be a monoid which
is generated by a finite or infinite set $X\subseteq K$ of generators; this
means that each $a\in K$ can be written in the form $t(a_{1},\ldots,a_{n})$
for some $n\geq 0$ and $a_{1},\ldots,a_{n}\in X$, where
$t(a_{1},\ldots,a_{n})$ denotes the result of evaluating an expression formed
by composing the constants $0$ and $a_{1},\ldots,a_{n}$ with the binary
operation $+$. We say that $\mathbb{K}(X)$ has the _universal mapping property
for $\mathcal{C}$ over $X$_ if for every $\mathbb{M}=(M,+,0)$ in $\mathcal{C}$
and every map $g:X\to M$ there is a homomorphism $h:K\to M$ which extends $g$
(see Definition 10.5 in [BS81]).

With these definitions, now we can state the result that we need from
universal algebra. The general theorem is due to Birkhoff and here we state
only its specialization to varieties of monoids: For every finite or infinite
set $X$ of _indeterminates_ (also called _variables_ or _free generators_),
and for every variety $\mathcal{C}$ of monoids, there is a monoid
$\mathbb{F}_{\mathcal{C}}(X)$ in $\mathcal{C}$ that is generated by $X$ and
has the universal mapping property for $\mathcal{C}$ over $X$ (see Theorems
10.10 and 10.12 in [BS81]). Furthermore, $\mathbb{F}_{\mathcal{C}}(X)$ is, up
to isomorphism, the unique monoid $\mathbb{K}(Y)$ in $\mathcal{C}$ that is
generated by a set $Y$ of generators of cardinality $|Y|=|X|$ and has the
universal mapping property for $\mathcal{C}$ over $Y$ (see Exercise 6 in
Chapter II.10 in [BS81]). Since we care only for commutative monoids, which
form a variety of monoids, we write $\mathbb{F}(X)$ for
$\mathbb{F}_{\mathcal{C}}(X)$, when $\mathcal{C}$ is the variety of
commutative monoids, and we refer to it as _the free commutative monoid
generated by $X$_.

It turns out that, as we argue below, the free commutative monoid generated by
$X$ has an explicit description: it is precisely the monoid that we called
$\mathbb{N}[X]_{1}$ in Section 5.4, i.e., the monoid of linear forms on the
indeterminates $X$ with non-negative integer coefficients. One consequence of
this is that the free commutative monoid $\mathbb{F}(X)$ is always positive.
Another consequence is that it has the transportation property. A third
consequence that is inherited from this is that any two
$\mathbb{F}(X)$-relations that are inner consistent have a sparse witness of
consistency, when the set $X$ of generators is finite. We collect the first
two properties in the following proposition.

######  Proposition 9.

For every set $X$ of indeterminates, the free commutative monoid generated by
$X$ is isomorphic to $\mathbb{N}[X]_{1}$, i.e.,
$\mathbb{F}(X)\cong\mathbb{N}[X]_{1}$, and is a positive commutative monoid
that has the transportation property.

###### Proof.

Since $\mathbb{N}[X]_{1}$ is positive and has the transportation property by
Example 8, it suffices to show that $\mathbb{F}(X)\cong\mathbb{N}[X]_{1}$. For
this proof, let $\mathcal{C}$ denote the variety of commutative monoids, so
that $\mathbb{F}_{\mathcal{C}}(X)=\mathbb{F}(X)$. Since $\mathbb{N}[X]_{1}$ is
generated by $X$, by the uniqueness of $\mathbb{F}_{\mathcal{C}}(X)$ it
suffices to show that $\mathbb{N}[X]_{1}$ has the universal mapping property
for $\mathcal{C}$ over $X$. Before we do this, let us recall from Example 8
that every element in $\mathbb{N}[X]_{1}$ is identified with a finite-support
map $c:X\to Z^{\geq 0}$, with each indeterminate $x\in X$ being identified
with the finite-support map $c_{x}:X\to Z^{\geq 0}$ defined by $c_{x}(x)=1$
and $c_{x}(y)=0$ for all $y\in X\setminus\\{x\\}$.

Now, to prove the universal mapping property for $\mathbb{N}[X]_{1}$, fix a
commutative monoid $\mathbb{M}=(M,+,0)$ and let $g:X\to M$ be any map. Define
the required homomorphism $h$ as the _evaluation map_

$c\mapsto\sum_{\genfrac{}{}{0.0pt}{2}{x\in X:}{c(x)\not=0}}c(x)g(x),$ (36)

where $c$ is an element in $\mathbb{N}[X]_{1}$ identified with a finite-
support map $c:X\to Z^{\geq 0}$. The external sum on the right-hand side of
Equation (36) is in $\mathbb{M}$, and the notation $na$ for a positive integer
$n$ and an element $a\in M$ stands for the sum $a+\cdots+a$ in $\mathbb{M}$
with $n$ occurrences of $a$ in the sum if $n\geq 1$, and the neutral element
$0$ of $M$ if $n=0$. Note that the summation sign in (36) has finite extension
because $c$ has finite support. Using the choice of $c_{x}$ for $x\in X$
defined above, it is straightforward to prove that $h$ is a homomorphism from
$\mathbb{N}[X]_{1}$ to $\mathbb{M}$ that extends $g$. ∎

The additional claim we made that any two $\mathbb{F}(X)$-relations that are
inner consistency have a sparse witness of consistency when the set $X$ of
generators is finite follows from combining the fact that
$\mathbb{F}(X)\cong\mathbb{N}[X]_{1}$ with the correspondence
$\mathbb{N}[X]_{1}\cong\mathbb{N}^{X}_{\mathrm{fin}}$ discussed in Example 8,
together with Example 6, Proposition 5, Proposition 6, and Proposition 8.

###  5.6 Some Important Non-Examples

As we have seen, many important positive commutative monoids have the
transportation property. Unfortunately there are positive commutative monoids
of different character that fail to have the transportation property. Here we
present a few examples of such monoids.

Example 13. Natural numbers with addition truncated to $2$. Recall the
positive commutative monoid $\mathbb{N}_{2}$ from Section 3.2: the natural
numbers $\\{0,1,2\\}$ with addition truncated to $2$. In that section we
showed that the path-of-length-$3$ hypergraph $P_{3}$ does not have the local-
to-global consistency property for ${\mathbb{N}}_{2}$-relations. From the
implications (1) $\Longrightarrow$ (3) and (2) $\Longrightarrow$ (3) in
Theorem 3, it follows that $\mathbb{N}_{2}$ does not have the transportation
property and, furthermore, the inner consistency property for
${\mathbb{N}}_{2}$-relations fails. Here, we give a simple example showing
that the inner consistency property for ${\mathbb{N}}_{2}$-relations fails.
Combined with Theorem 3, this gives a different proof that ${\mathbb{N}}_{2}$
does not have the transportation property.

Let $R(AC)$ and $S(BC)$ be the $\mathbb{N}_{2}$-relations given by
$R(a_{1},c)=R(a_{2},c)=S(b_{1},c)=1$ and $S(b_{2},c)=2$, and no other tuples
in their support. These two $\mathbb{N}_{2}$-relations are inner consistent
because $R(c)=S(c)=2$. However, they are not consistent. To prove this and
towards a contradiction, assume that $W(ABC)$ is an $\mathbb{N}_{2}$-relation
such that $W[AB]=R$ and $W[BC]=S$. Let us say $W(a_{i},b_{j},c)=x_{ij}$ for
$i=1,2,3$ and $j=1,2$, where each $x_{ij}$ is a value in $\\{0,1,2\\}$. This
assumption gives rise to a system of five equations:

$x_{i1}\oplus x_{i2}$ | $=1$ |  | for $i=1,2,3$
---|---|---|---
$x_{1j}\oplus x_{2j}\oplus x_{3j}$ | $=2$ |  | for $j=1,2$.

We reach a contradiction by double-counting the number of $x_{ij}$’s that are
assigned the value $1$. The first type of equation implies that, for all
$i=1,2,3$, either $x_{i1}=0$ and $x_{i2}=1$, or $x_{i1}=1$ and $x_{i2}=0$. In
particular, exactly three among all $x_{ij}$ with $i=1,2,3$ and $j=1,2$ are
assigned the value $1$ and the rest are assigned the value $0$. Therefore, for
at least one among $j=1,2$ there is at most one among $i=1,2,3$ such that
$x_{ij}$ is assigned the value $1$ and the rest are assigned the value $0$,
which is against the second type of equation for this $j$. $\dashv$

Example 14. Non-negative real numbers with addition and a gap. Let
$\mathbb{R}_{1}=(\\{0\\}\cup[1,+\infty),+,0)$ be the structure with $0$ and
all real numbers bigger or equal than $1$ as its universe, and with the
standard addition as its operation. It is obvious that $\mathbb{R}_{1}$ is a
positive commutative monoid. We show that the inner consistency property for
$\mathbb{R}_{1}$ fails, hence $\mathbb{R}_{1}$ does not have the
transportation property.

Let $R(AC)$ and $S(BC)$ be the $\mathbb{R}_{1}$-relations given by
$R(a_{i},c)=1$ for $i=1,2,3$ and $S(b_{j},c)=1.5$ for $j=1,2$, and no other
tuples in their supports. These two $\mathbb{R}_{1}$-relations are inner
consistent, since $R(c)=S(c)=3$. We claim that they are not consistent.
Indeed, assume that there is an $\mathbb{R}_{1}$-relation $W(ABC)$ witnessing
the consistency of $R(AB)$ and $S(BC)$. Let us say that
$W(a_{i},b_{j},c)=x_{ij}$ for $i=1,2,3$ and $j=1,2$, where each $x_{ij}$ is a
value in $\\{0\\}\cup[1,+\infty)$. This assumption gives rise to a system of
five equations:

$x_{i1}+x_{i2}$ | $=1$ |  | for $i=1,2,3$
---|---|---|---
$x_{1j}+x_{2j}+x_{3j}$ | $=1.5$ |  | for $j=1,2$.

The first type of equation with $i=1$ implies that either $x_{11}=0$ and
$x_{12}=1$, or that $x_{11}=1$ and $x_{12}=0$. If $x_{11}=0$, then the second
type of equation with $j=1$ implies that $x_{21}+x_{31}=0.5$, which is
impossible. If $x_{12}=0$, then the second type of equation with $j=2$ implies
that $x_{22}+x_{32}=0.5$, which is impossible. Since the system has no
solution in $\mathbb{R}_{1}$, we conclude that the relations $R(AC)$ and
$S(BC)$ are not consistent. Note that in this proof we used only three of the
six equations. However, the other two are forced by the inner consistency
condition (i.e., there is no choice but to have $x_{21}+x_{22}=1$ and
$x_{31}+x_{32}=1$). $\dashv$

Example 15. Truncated powersets. For each natural number $k$, let
$\mathbb{P}_{k}=(\\{0,\ldots,k+1\\},+,0)$ be the monoid with neutral element
$0$, absorbing element $k+1$, and such that $i+i=i$ for all $i\in[k]$, and
$i+j=k+1$ for all $i,j\in[k]$ with $i\not=j$. An alternative presentation of
$\mathbb{P}_{k}$ is as the substructure of the powerset monoid
$\mathbb{P}([k+1])=(\mathcal{P}([k+1]),\cup,\emptyset)$ induced by the empty
set $\emptyset$, the full set $[k+1]$, and the $(k-1)$-element subsets
$[k]\setminus\\{i\\}$ for $i=1,\ldots,k$. This explains the name _truncated
powersets_. For example, this alternative presentation of $\mathbb{P}_{3}$ is
the structure
$(\\{\emptyset,\\{1,2\\},\\{1,3\\},\\{2,3\\},\\{1,2,3\\}\\},\cup,\emptyset)$.

Clearly each $\mathbb{P}_{k}$ is positive and commutative. We show that
$\mathbb{P}_{k}$ does not have the transportation property unless $k=0$ or
$k=1$ or $k=2$. For $k=0$ we have that $\mathbb{P}_{k}$ is isomorphic to
Boolean monoid $\mathbb{B}=(\\{0,1\\},\vee,0)$. For $k=1$ we have that
$\mathbb{P}_{k}$ is isomorphic to $(\\{0,1,2\\},\max,0)$. For $k=2$ we have
that $\mathbb{P}_{k}$ is isomorphic to
$(\mathcal{P}(\\{1,2\\}),\cup,\emptyset)$. These three cases are covered by
the lattice case in Example 2 and have then the transportation property. For
$k\geq 3$ we show that $\mathbb{P}_{k}$ does not have the transportation
property.

Let $k\geq 3$, and let $R(AC)$ and $S(BC)$ be the $\mathbb{P}_{k}$-relations
with $R(a_{1},c)=1$ and $R(a_{2},c)=3$ and $S(b_{1},c)=2$ and $S(b_{2},c)=3$,
and no other tuples in their supports. These are inner consistent since, in
the structure $\mathbb{P}_{k}$ with $k\geq 3$, we have
$R[C](c)=1+3=k+1=2+3=S[C](c)$. We show that $R$ and $S$ are not consistent.
Indeed, assume that there is a $\mathbb{P}_{k}$-relation $W(ABC)$ witnessing
the consistency of $R(AB)$ and $S(BC)$. Let us say that
$W(a_{i},b_{j},c)=x_{ij}$ for $i=1,2$ and $j=1,2$, where each $x_{ij}$ is a
value in $\\{0,\ldots,k+1\\}$. This assumption gives rise to a system of four
equations:

$x_{11}+x_{12}=1$
---
$x_{21}+x_{22}=3$
$x_{11}+x_{21}=2$
$x_{12}+x_{22}=3$.

The first equation interpreted in $\mathbb{P}_{k}$ implies that $x_{11}=1$ or
$x_{12}=1$. If $x_{11}=1$, then the third equation cannot be satisfied since
there is no $j$ such that $1+j=2$ in $\mathbb{P}_{k}$, while if $x_{12}=1$,
then the fourth equation cannot be satisfied since there is no $j$ such that
$1+j=3$ in $\mathbb{P}_{k}$. $\dashv$

Our last example involves a natural positive commutative monoid for which the
failure of the transportation property is conceptually significant as it
corresponds to the deep fact of quantum mechanics that there exist pairs of
binary observables that cannot be jointly measured. This is a manifestation of
the celebrated _Heisenberg uncertainty principle_ for positive-operator-valued
measures [MI08]; we do not elaborate on this here and refer the interested
reader to the introduction of the cited article for an extensive survey of
related literature.

Example 16. Positive semidefinite matrices under addition. Let $n\geq 1$ be a
positive integer and let $\mathbb{PSD}_{n}$ be the set of positive
semidefinite matrices in $\mathbb{R}^{n\times n}$, i.e., the $n\times n$
symmetric real matrices $A$ for which $z^{\mathrm{T}}Az\geq 0$ holds for all
$z\in\mathbb{R}^{n}$. Equivalently, $A$ is positive semidefinite if and only
if it is symmetric and all its eigenvalues are non-negative. This is a
commutative monoid under componentwise addition; commutativity is obvious and
the sum of positive semidefinite matrices is positive semidefinite since
$z^{\mathrm{T}}(A+B)z=z^{\mathrm{T}}Az+z^{\mathrm{T}}Bz\geq 0$ for all
$z\in\mathbb{R}^{n}$, where the inequality follows from the positive
semidefiniteness of $A$ and $B$. The monoid is also positive. To see this,
first note that if $A+B=0$, then
$z^{\mathrm{T}}Az+z^{\mathrm{T}}Bz=z^{\mathrm{T}}(A+B)z=0$, so
$z^{\mathrm{T}}Az=z^{\mathrm{T}}Bz=0$ for all vectors $z\in\mathbb{R}^{n}$ by
the positive semidefiniteness of $A$ and $B$. By applying this to the standard
basis vectors $e_{i}=(0,\ldots,0,1,0,\ldots,0)\in\mathbb{R}^{n}$ with
$i=1,\ldots,n$ we see that the diagonals of $A$ and $B$ vanish, so the traces
of $A$ and $B$ vanish, which means that the sums of their eigenvalues vanish,
so all their eigenvalues vanish since positive semidefinite matrices have non-
negative eigenvalues. From this it follows that $A$ and $B$ are the zero
matrix by considering their spectral decompositions $A=PDP^{\mathrm{T}}$ and
$B=QEQ^{\mathrm{T}}$, where $D$ and $E$ are the diagonal matrices that collect
their eigenvalues.

Next we show that $\mathbb{PSD}_{n}$ does not have the transportation
property, provided $n>1$. For $n=1$, we have that $\mathbb{PSD}_{n}$ is
isomorphic to the monoid $\mathbb{R}^{\geq 0}$ of the non-negative reals with
addition, and this has been shown to have the transportation property in
Example 5. Next we argue that $\mathbb{PSD}_{2}$ does not have the
transportation property. From this, the claim follows for $\mathbb{PSD}_{n}$
with $n>2$ by padding the matrices with zeros. Our proof for $n=2$ is an
adaptation of a more general statement that can be found in [KHF14].

Consider the classical Pauli matrices:

$X=\left({\begin{array}[]{cc}0&1\\\
1&0\end{array}}\right)\;\;\;\;\;Y=\left({\begin{array}[]{cc}0&-i\\\
i&0\end{array}}\right)\;\;\;\;\;Z=\left({\begin{array}[]{cc}1&0\\\
0&-1\end{array}}\right).$

Observe that $Y$ has complex entries, but $X$ and $Z$ are $2\times 2$ real
matrices. Consider the instance of the transportation problem given by the
four matrices

$\begin{array}[]{ccccccc}B_{1}&=&(\mathrm{I}+X)/2&&B_{2}&=&(\mathrm{I}-X)/2\\\
C_{1}&=&(\mathrm{I}+Z)/2&&C_{2}&=&(\mathrm{I}-Z)/2,\end{array}$

where $\mathrm{I}$ is the $2\times 2$ identity matrix. These are positive
semidefinite matrices since their eigenvalues are in $\\{0,1\\}$, and the
vectors $(B_{1},B_{2})$ and $(C_{1},C_{2})$ form a balanced instance of the
transportation problem since $B_{1}+B_{2}=C_{1}+C_{2}=\mathrm{I}$. This gives
rise to a system of four matrix equations

$\displaystyle X_{11}+X_{12}=B_{1}$ $\displaystyle X_{21}+X_{22}=B_{2}$
$\displaystyle X_{11}+X_{21}=C_{1}$ $\displaystyle X_{12}+X_{22}=C_{2}$

We claim that this system is infeasible in $2\times 2$ positive semidefinite
matrices. Suppose otherwise. Left-multiply the first equation by $X$, the
second equation by $-X$, the third equation by $Z$, the fourth equation by
$-Z$, and add up everything. Using the fact that $X^{2}=Z^{2}=\mathrm{I}$ and
hence $XB_{1}-XB_{2}=ZC_{1}-ZC_{2}=\mathrm{I}$, this gives the identity

$A_{11}X_{11}+A_{12}X_{12}+A_{21}X_{21}+A_{22}X_{22}=2\mathrm{I}$ (37)

where

$\begin{array}[]{ccccccccc}A_{11}&=&X+Z&&A_{12}&=&X-Z\\\
A_{21}&=&-X+Z&&A_{22}&=&-X-Z.\end{array}$

The trace of the matrix on the right-hand side in (37) is $4$. In contrast, by
Hölder’s inequality for the Schatten norm with $p=1$ and $q=\infty$, the trace
of the matrix on the left-hand side in (37) is bounded by

$\|A_{11}\|\mathrm{tr}(X_{11})+\|A_{12}\|\mathrm{tr}(X_{12})+\|A_{21}\|\mathrm{tr}(X_{21})+\|A_{22}\|\mathrm{tr}(X_{22}),$
(38)

where $\|A\|$ denotes the spectral norm of $A$, i.e., the largest eigenvalue
of the matrix $A$, in absolute value. It can be checked by direct computation
that each of the matrices $A_{ij}$ has eigenvalues $\pm\sqrt{2}$, so their
spectral norm is $\sqrt{2}$. Furthermore, each $X_{ij}$ is a positive
semidefinite matrix by assumption; hence its trace, which is the sum of the
eigenvalues, which are non-negative for positive semidefinite matrices, is
non-negative. It follows that (38) is bounded by

$(\mathrm{tr}(X_{11})+\mathrm{tr}(X_{12})+\mathrm{tr}(X_{21})+\mathrm{tr}(X_{22}))\sqrt{2}=\mathrm{tr}(X_{11}+X_{12}+X_{21}+X_{22})\sqrt{2}=2\sqrt{2},$
(39)

where the first equality follows from the linearity of the trace, and the
second follows from the fact that the sum of the $X_{ij}$ is
$B_{1}+B_{2}=C_{1}+C_{2}=\mathrm{I}$, which has trace $2$. The conclusion is
that the trace of the left-hand side in (37) is at most $2\sqrt{2}<4$, which
is against the fact that the trace of the right-hand side in (37) is $4$.
$\dashv$

##  6 Local Consistency up to a Cover

In the previous sections, we characterized the class of positive commutative
monoids $\mathbb{K}$ for which the standard local consistency of
$\mathbb{K}$-relations agrees with their global consistency for precisely the
acyclic hypergraphs. The goal of this section is to investigate whether there
is a suitably modified notion of local consistency of $\mathbb{K}$-relations
that has the same effect of capturing the global consistency of
$\mathbb{K}$-relations for precisely the acyclic hypergraphs, but that applies
to _every_ positive commutative monoid.

We achieve this by strengthening the requirement of locality: in addition to
requiring that the relations are pairwise consistent as
$\mathbb{K}$-relations, we will also require that they are pairwise consistent
when they are appropriately viewed as $\mathbb{F}(X)$-relations, where
$\mathbb{F}(X)$ is the free commutative monoid with a large enough set $X$ of
generators. We refer to this new notion of local consistency of
$\mathbb{K}$-relations as _pairwise consistency up to the free cover_ of
$\mathbb{K}$. Surprisingly, we show that this abstract notion of local
consistency of $\mathbb{K}$-relations characterizes global consistency of
$\mathbb{K}$-relations for precisely the acyclic hypergraphs, and for _every_
positive commutative monoid $\mathbb{K}$.

###  6.1 Consistency up to a Cover

Let $\mathbb{K}$ be a positive commutative monoid. A _cover of $\mathbb{K}$_
is a positive commutative monoid $\mathbb{K}^{*}$ such that there is a
surjective homomorphism $h$ from ${\mathbb{K}}^{*}$ onto $\mathbb{K}$. The
_identity cover_ is the cover where $\mathbb{K}^{*}$ is $\mathbb{K}$ itself
and $h$ is the identity map. A cover of $\mathbb{K}$ is given by the pair
$(\mathbb{K}^{*},h)$ of both objects; we use the notation
$h:\mathbb{K}^{*}\stackrel{{\scriptstyle\scriptscriptstyle{s}}}{{\rightarrow}}\mathbb{K}$
to say that the pair $(\mathbb{K}^{*},h)$ is a cover of $\mathbb{K}$. For the
definitions of the next paragraph, fix such a cover.

For a $\mathbb{K}$-relation $R(Y)$, an _$h$ -lift of $R$_ is a
$\mathbb{K}^{*}$-relation $R^{*}(Y)$ such that $h(R^{*}(t))=R(t)$ holds for
every $Y$-tuple $t$, i.e., $h\circ R^{*}=R$ holds. In most of the cases that
follow, the cover will be clear from the context, and we simply say that
$R^{*}$ is a lift of $R$, without any reference to $h$. Note that, since the
homomorphism $h$ is surjective onto $\mathbb{K}$, every $\mathbb{K}$-relation
$R$ has at least one $h$-lift $R^{*}$. Consider the special case where
$h:\mathbb{K}^{*}\stackrel{{\scriptstyle\scriptscriptstyle{s}}}{{\rightarrow}}\mathbb{K}$
is a _retraction_ , meaning that $K\subseteq K^{*}$ and $h$ is the identity on
$K$, where $K$ and $K^{*}$ are the universes of $\mathbb{K}$ and
$\mathbb{K}^{*}$, respectively; in this case, the _direct $h$-lift of $R$_ is
the $\mathbb{K^{*}}$-relation $R^{*}$ defined by $R^{*}(t)=R(t)$, for every
$Y$-tuple $t$.

######  Definition 6.

Let $\mathbb{K}$ be a positive commutative monoid, let
$h:\mathbb{K}^{*}\stackrel{{\scriptstyle\scriptscriptstyle{s}}}{{\rightarrow}}\mathbb{K}$
be a cover of $\mathbb{K}$, let $X_{1},\ldots,X_{m}$ be a schema, let
$R_{1}(X_{1}),\ldots,R_{m}(X_{m})$ be a collection of $\mathbb{K}$-relations
over the schema $X_{1},\ldots,X_{m}$, and let $k$ be a positive integer. We
say that the collection $R_{1},\ldots,R_{m}$ is  _$k$ -wise consistent up to
the cover
$h:\mathbb{K}^{*}\stackrel{{\scriptstyle\scriptscriptstyle{s}}}{{\rightarrow}}\mathbb{K}$_
if there exists a collection $R^{*}_{1},\ldots,R^{*}_{m}$ of $h$-lifts of
$R_{1},\ldots,R_{m}$ that is $k$-wise consistent (as a collection of
$\mathbb{K}^{*}$-relations). If $k=2$, then we say that the collection
$R_{1},\ldots,R_{m}$ is _pairwise consistent up to the cover_. If $k=m$, then
we say that the collection $R_{1},\ldots,R_{m}$ is _globally consistent up to
the cover_. When $k=m=2$ we just say that $R_{1}$ and $R_{2}$ are _consistent
up to the cover_.

Before we go on, it is important to point out that in the definition of
consistency up to a cover, not only the choice of the cover
$h:\mathbb{K}^{*}\stackrel{{\scriptstyle\scriptscriptstyle{s}}}{{\rightarrow}}\mathbb{K}$
potentially matters, but also the choice of $h$-lifts
$R_{1}^{*},\ldots,R_{m}^{*}$ matters. We illustrate this with an example.

Example 17. Consider the $\mathbb{N}_{2}$-relations $R_{2}(BC)$ and
$R_{3}(CD)$ in Proposition 1. Consider the cover
$h:\mathbb{F}(x,y)\stackrel{{\scriptstyle\scriptscriptstyle{s}}}{{\rightarrow}}\mathbb{N}_{2}$
given by the canonical homomorphism $h$ from the free commutative monoid
$\mathbb{F}(x,y)$ with two generators $x$ and $y$ for the non-zero elements
$1$ and $2$ of $\mathbb{N}_{2}$, which is of course a surjective homomorphism.
As shown in Proposition 1, the $\mathbb{N}_{2}$-relations $R_{2}(BC)$ and
$R_{3}(CD)$ are consistent as $\mathbb{N}_{2}$-relations. However, when viewed
as $\mathbb{F}(x,y)$-relations $R_{2}^{*}$ and $R_{3}^{*}$ through the direct
$h$-lift with the retraction that identifies $x$ with $1$ and $y$ with $2$,
the two $\mathbb{F}(x,y)$-relations $R^{*}_{2}$ and $R^{*}_{3}$ are $h$-lifts
of $R_{2}$ and $R_{3}$ that are not consistent because they are not even inner
consistent, since we have that
$R^{*}_{2}[C](c_{1})=y\not=x+x+x=R^{*}_{3}[C](c_{1})$. Nonetheless, if we take
the $\mathbb{N}_{2}$-relation $R_{23}(BCD)$ that witnesses the consistency of
$R_{2}$ and $R_{3}$ as $\mathbb{N}_{2}$-relations, then we can view $R_{23}$
as an $\mathbb{F}(x,y)$-relation $W^{*}$ that is an $h$-lift of $R_{23}$, and
we can now take $R_{2}^{*}:=W^{*}[BC]$ and $R_{3}^{*}=W^{*}[CD]$, and these
are obviously both consistent $\mathbb{F}(x,y)$-relations and $h$-lifts of
$R_{2}$ and $R_{3}$, though not direct $h$-lifts. $\dashv$

#### Global Consistency up to Covers and its Absoluteness

The first technical result of this section is the following simple but
important observation stating that, as regards to global consistency, the
choice of the cover does not really matter. While this independence of the
cover will not be shared by the notion of pairwise consistency up to a cover
that we will introduce later on, the fact that it holds for global consistency
is key for our purposes.

######  Proposition 10 (Absoluteness of Global Consistency).

Let $\mathbb{K}$ be a positive commutative monoid and let $R_{1},\ldots,R_{m}$
be a collection of $\mathbb{K}$-relations. The following statements are
equivalent:

  1. 1.

the collection $R_{1},\ldots,R_{m}$ is globally consistent,

  2. 2.

the collection $R_{1},\ldots,R_{m}$ is globally consistent up to every cover
of $\mathbb{K}$,

  3. 3.

the collection $R_{1},\ldots,R_{m}$ is globally consistent up to some cover of
$\mathbb{K}$.

###### Proof.

Let $Y_{i}$ be the set of attributes of $R_{i}$ for $i=1,\ldots,m$.

(1) $\Longrightarrow$ (2): Let $W$ be a $\mathbb{K}$-relation such that
$W[Y_{i}]=R_{i}$ holds for all $i\in[m]$. Fix an arbitrary cover
$h:\mathbb{K}^{*}\stackrel{{\scriptstyle\scriptscriptstyle{s}}}{{\rightarrow}}\mathbb{K}$
and let $W^{*}$ be any $h$-lift of $W$. Such a lift exists because $h$ is
surjective onto $\mathbb{K}$. For each $i\in[m]$, choose
$R_{i}^{*}:=W^{*}[Y_{i}]$. We claim that $R_{1}^{*},\ldots,R_{m}^{*}$ are
lifts of $R_{1},\ldots,R_{m}$, and also that $W^{*}$ witnesses their global
consistency. Indeed, for each $i\in[m]$ and each $Y_{i}$-tuple $t$ we have

$\displaystyle h(R^{*}_{i}(t))$
$\displaystyle=h(W^{*}[Y_{i}](t))=h\Big{(}{\sum_{r:r[Y_{i}]=t}W^{*}(r)}\Big{)}=$
(40)
$\displaystyle={\sum_{r:r[Y_{i}]=t}h(W^{*}(r))}={\sum_{r:r[Y_{i}]=t}W(r)}=W[Y_{i}](t)=R_{i}(t),$
(41)

where the first equality follows from the choice of $R^{*}_{i}$, the second
follows from the definition of marginal, the third follows from the fact that
$h$ is a homomorphism, the fourth follows from the fact that $W^{*}$ is a lift
of $W$, the fifth follows from the definition of marginal, and the sixth
follows from $W[Y_{i}]=R_{i}$. This shows that $h\circ R_{i}^{*}=R_{i}$, so
$R_{1}^{*},\ldots,R_{m}^{*}$ are lifts of $R_{1},\ldots,R_{m}$. Finally, the
fact that $W^{*}$ witnesses the global consistency of
$R_{1}^{*},\ldots,R_{m}^{*}$ is obvious by construction.

(2) $\Longrightarrow$ (3): This is obvious by choosing the identity cover.

(3) $\Longrightarrow$ (1): Let
$h:\mathbb{K}^{*}\stackrel{{\scriptstyle\scriptscriptstyle{s}}}{{\rightarrow}}\mathbb{K}$
be a cover up to which the collection $R_{1},\ldots,R_{m}$ is globally
consistent. Let then $R_{1}^{*},\ldots,R_{m}^{*}$ be a collection of lifts of
$R_{1},\ldots,R_{m}$ that is globally consistent. Let $W^{*}$ be the
$\mathbb{K}^{*}$-relation that witnesses its global consistency and define
$W:=h\circ W^{*}$. We claim that $W$ witnesses the global consistency of
$R_{1},\ldots,R_{m}$. Indeed, for each $i\in[m]$ and each $Y_{i}$-tuple $t$ it
holds that

$\displaystyle W[Y_{i}](t)$
$\displaystyle={\sum_{r:r[Y_{i}]=t}W(r)}={\sum_{r:r[Y_{i}]=t}h(W^{*}(r))}=$
(42)
$\displaystyle=h\Big{(}{\sum_{r:r[Y_{i}]=t}W^{*}(r)}\Big{)}=h(W^{*}[Y_{i}](t))=h(R^{*}_{i}(t))=R_{i}(t),$
(43)

where the first equality follows from the definition of marginal, the second
follows from the choice of $W$, the third follows from the fact that $h$ is a
homomorphism, the fourth follows from the definition of marginal, the fifth
follows from the fact that $W^{*}[Y_{i}]=R^{*}_{i}$, and the sixth follows
from the fact that $R^{*}_{i}$ is an $h$-lift of $R_{i}$. This shows that
$W[Y_{i}]=R_{i}$, hence the collection $R_{1},\ldots,R_{m}$ is globally
consistent. ∎

In view of Proposition 10, we say that the notion of global consistency up to
covers is _absolute_ as if it holds for some cover, then it holds for all
covers. Next we localize this notion. Unlike the global notion, the local
notion will _not_ be absolute in the sense that a collection of
$\mathbb{K}$-relations may be locally consistent up to some cover but not up
to every cover.

#### Local Consistency up to Covers

We show that, up to covers, two thirds of Proposition 10 descend from global
consistency to local consistency. Concretely, we show in Proposition 11 below
that a collection is $k$-wise consistent in the standard sense if and only if
it is $k$-wise consistent up to some cover of $\mathbb{K}$. In contrast, we
also show in Example 11 below that a third statement quantifying over all
covers of $\mathbb{K}$ would not be equivalent. This state of affairs
notwithstanding, two additional refined notions of local consistency up to a
cover make sense and those are indeed equivalent to the one we defined. While
these refined notions will not play a role in later sections, we spell them
out next to clarify the choices that were involved in the original definition
of local consistency up to a cover.

We say that the collection $R_{1},\ldots,R_{m}$ is _weakly $k$-wise consistent
up to the cover
$h:\mathbb{K}^{*}\stackrel{{\scriptstyle\scriptscriptstyle{s}}}{{\rightarrow}}\mathbb{K}$_
if for every $t\in[k]$, every $i_{1},\ldots,i_{t}\in[m]$, and every $j\in[t]$,
there exists an $h$-lift $R_{i_{j}}^{*}$ of $R_{i_{j}}$ such that the
collection $R_{i_{1}}^{*},\ldots,R_{i_{t}}^{*}$ is globally consistent.
Finally, we say that the collection $R_{1},\ldots,R_{m}$ is _very weakly
$k$-wise consistent up to some covers of $\mathbb{K}$_ if for every $t\in[k]$
and every $i_{1},\ldots,i_{t}\in[m]$ there exists a cover
$h:\mathbb{K}^{*}_{t}\stackrel{{\scriptstyle\scriptscriptstyle{s}}}{{\rightarrow}}\mathbb{K}$
such that for and every $j\in[t]$, there exist an $h$-lift $R^{*}_{i_{j}}$ of
$R_{i_{j}}$ such that the collection $R_{i_{1}}^{*},\ldots,R_{i_{t}}^{*}$ is
globally consistent. Note the difference with the earlier definition: in the
_weak_ case, the choices of lifts for each $R_{i}$ may depend on the
subcollection, and in the _very weak_ case even the cover up to which
consistency is defined may depend on the subcollection.

######  Proposition 11.

Let $\mathbb{K}$ be a positive commutative monoid, let $R_{1},\ldots,R_{m}$ be
a collection of $\mathbb{K}$-relations, and let $k$ be a positive integer. The
following statements are equivalent:

  1. (1)

the collection $R_{1},\ldots,R_{m}$ is $k$-wise consistent,

  2. (2)

the collection $R_{1},\ldots,R_{m}$ is $k$-wise consistent up to some cover of
$\mathbb{K}$,

  3. (3)

the collection $R_{1},\ldots,R_{m}$ is weakly $k$-wise consistent up to some
cover of $\mathbb{K}$,

  4. (4)

the collection $R_{1},\ldots,R_{m}$ is very weakly $k$-wise consistent up to
some covers of $\mathbb{K}$.

###### Proof.

Let $Y_{i}$ be the set of attributes in $R_{i}$ for $i=1,\ldots,m$.

(1) $\Longrightarrow$ (2): This is obvious by choosing the identity cover.

(2) $\Longrightarrow$ (3): This is obvious by choosing the same lifts.

(3) $\Longrightarrow$ (4): This is obvious by choosing the same cover and the
same lifts.

(4) $\Longrightarrow$ (1): Fix $t\in[k]$ and $i_{1},\ldots,i_{t}\in[m]$, and
let
$h:\mathbb{K}^{*}\stackrel{{\scriptstyle\scriptscriptstyle{s}}}{{\rightarrow}}\mathbb{K}$
and $R^{*}_{i_{1}},\ldots,R^{*}_{i_{t}}$ be as given by the definition of very
weakly $k$-wise consistency up to some covers for this $t$ and these
$i_{1},\ldots,i_{t}$. In particular the collection
$R^{*}_{i_{1}},\ldots,R^{*}_{i_{t}}$ is globally consistent. Therefore, the
subcollection $R_{i_{1}},\ldots,R_{i_{t}}$ of the original
$\mathbb{K}$-relations is globally consistent up to some cover, i.e., namely
$h:\mathbb{K}^{*}\to\mathbb{K}$, and hence globally consistent by Proposition
10. ∎

It should be pointed out that the equivalence of the items in Proposition 11
would not go through if the same cover of $\mathbb{K}$ were fixed at the
outset for all items. This will follow from the fact that, as we argue below,
absoluteness fails for local consistency. For the main result of this section,
what really matters from Proposition 11 is the equivalence between items (1)
and (2), which states that local consistency up to a cover is a conservative
generalization of the classical notion of local consistency.

Finally we give the promised example showing that, in general, $k$-wise
consistency up to a cover is not absolute in the sense of Proposition 10.
Concretely, the example will show that for the positive commutative monoid
$\mathbb{N}_{2}$ in Proposition 1 and for the values $k=2$ and $m=3$, one
cannot add to Proposition 11 a condition analogous to the second condition in
Proposition 10 stating that the collection $R_{1},\ldots,R_{m}$ is $k$-wise
consistent up to every cover of $\mathbb{N}_{2}$. In other words, there are
collections of $\mathbb{N}_{2}$-relations that are pairwise consistent but are
not pairwise consistent up to every cover of $\mathbb{N}_{2}$.

Example 18. Consider the collection $R(AB),S(BC),T(CD)$ of the three
$\mathbb{N}_{2}$-relations from Proposition 1. These relations are pairwise
consistent but are not globally consistent as $\mathbb{N}_{2}$-relations.
Consider the cover
$h:\mathbb{N}\stackrel{{\scriptstyle\scriptscriptstyle{s}}}{{\rightarrow}}\mathbb{N}_{2}$,
where $\mathbb{N}$ is the bag monoid and $h$ maps $n$ to $n$ if $n=0$ or
$n=1$, and maps $n$ to $2$ if $n\geq 2$, i.e., $h$ truncates addition to $2$.
We claim that the collection $R,S,T$ cannot be lifted to a collection of
pairwise consistent $\mathbb{N}$-relations $R^{*},S^{*},T^{*}$. For, if they
could, then $R^{*},S^{*},T^{*}$ would be a collection of pairwise consistent
bags, hence they would also be globally consistent by the local-to-global
consistency property for bags on acyclic schemas, since the schema $AB,BC,CD$
is acyclic. But then $R(AB),S(BC),T(CD)$ would be also globally consistent as
$\mathbb{N}_{2}$-relations by truncating to $2$ every natural number bigger
than $2$ in the bag $W^{*}$ that witnesses the global consistency of
$R^{*},S^{*},T^{*}$. This contradicts Proposition 1 and completes the example.
$\dashv$

###  6.2 Local-to-Global Consistency up to Covers

The local-to-global consistency property up to a cover is defined to
generalize Definition 2 as follows:

######  Definition 7.

Let $\mathbb{K}$ be a positive commutative monoid, let
$h:\mathbb{K}^{*}\stackrel{{\scriptstyle\scriptscriptstyle{s}}}{{\rightarrow}}\mathbb{K}$
be a cover of $\mathbb{K}$, and let $X_{1},\ldots,X_{m}$ be a listing of all
the hyperedges of a hypergraph $H$. We say that $H$ has the _local-to-global
consistency property for $\mathbb{K}$-relations up to the cover
$h:\mathbb{K}^{*}\stackrel{{\scriptstyle\scriptscriptstyle{s}}}{{\rightarrow}}\mathbb{K}$_
if every collection $R_{1}(X_{1}),\ldots,R(X_{m})$ of $\mathbb{K}$-relations
that is pairwise consistent up to the cover is globally consistent.

Recall from Section 5.5 the definition of the free commutative monoid
$\mathbb{F}(X)$ for a finite or finite set of indeterminates $X$. In the
statement of the following theorem, let $\mathbb{F}(K^{+})$ denote the free
commutative monoid generated by the set $K^{+}$ of non-zero elements in $K$
seen as indeterminates. Note that $\mathbb{F}(K^{+})$ is positive by
Proposition 9. The _free cover of $\mathbb{K}$_ refers to the cover
$h:\mathbb{F}(K^{+})\stackrel{{\scriptstyle\scriptscriptstyle{s}}}{{\rightarrow}}\mathbb{K}$
provided by the homomorphism $h$ from $\mathbb{F}(K^{+})$ to $\mathbb{K}$
given by the universal mapping property of $\mathbb{F}(K^{+})$ applied to the
identity map $g:K^{+}\to K^{+}$ defined by $g(x)=x$ for all $x\in K^{+}$.
Clearly, $h$ is surjective onto $K$ as it extends $g$ and any homomorphism
between monoids maps the neutral element of the first monoid to the neural
element of the second. Hence,
$h:\mathbb{F}(K^{+})\stackrel{{\scriptstyle\scriptscriptstyle{s}}}{{\rightarrow}}\mathbb{K}$
is indeed a cover.

######  Theorem 4.

Let $\mathbb{K}$ be a positive commutative monoid and let $H$ be a hypergraph.
Then, the following statements are equivalent:

  1. 1.

$H$ is acyclic,

  2. 2.

$H$ has the local-to-global consistency property up to the free cover of
$\mathbb{K}$,

  3. 3.

$H$ has the local-to-global consistency property up to some cover of
$\mathbb{K}$.

###### Proof.

Let $Y_{1},\ldots,Y_{m}$ be a listing of the hyperedges of $H$.

(1) $\Longrightarrow$ (2). We need to show that if $H$ is acyclic, then
pairwise consistency up to the free cover of $\mathbb{K}$ is a sufficient
condition for global consistency. This proof uses as a black box the
previously established fact that, for any non-empty set $X$ of indeterminates,
the free commutative monoid $\mathbb{F}(X)$ has the transportation property,
hence every acyclic hypergraph has the (standard) local-to-global consistency
property for $\mathbb{F}(X)$-relations - see Proposition 9 in Section 5.5, and
Theorem 3 in Section 4.

Let $R_{1}(Y_{1}),\ldots,R_{m}(Y_{m})$ be a collection of
$\mathbb{K}$-relations and assume that it is pairwise consistent up to the
free cover
$h:\mathbb{F}(K^{+})\stackrel{{\scriptstyle\scriptscriptstyle{s}}}{{\rightarrow}}\mathbb{K}$.
Accordingly, let $R^{*}_{1},\ldots,R^{*}_{m}$ be a collection of
$\mathbb{F}(K^{+})$-relations that are $h$-lifts of $R_{1},\ldots,R_{m}$,
respectively, and assume that the collection $R^{*}_{1},\ldots,R^{*}_{m}$ is
pairwise consistent. Since $H$ is acyclic, it has the local-to-global
consistency property for $\mathbb{F}(K^{+})$-relations, so the collection
$R^{*}_{1},\ldots,R^{*}_{m}$ of $\mathbb{F}(K^{+})$-relations is globally
consistent as $\mathbb{F}(K^{+})$-relations. But, then, the collection
$R_{1},\ldots,R_{m}$ of $\mathbb{K}$-relations itself is globally consistent
up to the free cover of $\mathbb{K}$, so it is globally consistent by the
absoluteness property stated in Proposition 10.

(2) $\Longrightarrow$ (3). This is obvious because the free cover of
$\mathbb{K}$ is a cover of $\mathbb{K}$.

(3) $\Longrightarrow$ (1). First we adapt the proof of Lemma 2 to show that
there is no cover up to which the minimal non-acyclic hypergraphs $C_{n}$ and
$H_{n}$ with $n\geq 3$ have the local-to-global consistency property. As in
Lemma 2, we prove this more generally for any non-trivial uniform and regular
hypergraph in Lemma 5 below. After this is proved, we show that the reduction
that transfers the local-to-global consistency property from any non-acyclic
hypergraph to the minimal cases also works up to covers. This is done by
adapting Lemma 4 to the new context in Lemma 6 below. ∎

The statement of the following lemma is almost identical to its predecessor
Lemma 2, the only difference being that the pairwise consistency of the
collection of $\mathbb{K}$-relations is claimed up to every cover. We prove it
by indicating how the original arguments need to be adjusted.

######  Lemma 5.

Let $\mathbb{K}$ be a positive commutative monoid and let $X_{1},\ldots,X_{m}$
be a schema that is $k$-uniform and $d$-regular with $k\geq 1$ and $d\geq 2$.
Then, there exists a collection of $\mathbb{K}$-relations of schema
$X_{1},\ldots,X_{m}$ that is pairwise consistent up to every cover of
$\mathbb{K}$ but not globally consistent.

###### Proof.

The construction of the $\mathbb{K}$-relations $R_{1},\ldots,R_{m}$ proceeds
exactly as in Lemma 2 until the point where it is argued that it is pairwise
consistent. Here we need to show that it is pairwise consistent up to every
cover of $\mathbb{K}$. Fix such a cover $h:\mathbb{K}^{*}\to\mathbb{K}$ and
argue as follows.

By the surjectivity of $h$, there exists an element $c^{*}$ of
$\mathbb{K}^{*}$ such that $h(c^{*})=c$. Since $h$ is a homomorphism and
$c\not=0$ in $\mathbb{K}$, we have that also $c^{*}\not=0$ in
$\mathbb{K}^{*}$. Let $a^{*}:=c^{*}+\cdots+c^{*}$ with $c^{*}$ appearing
$d^{k}$ times in the sum, which is computed in $\mathbb{K}^{*}$. Using the
notation $nx$ for $x+\cdots+x$ with $x$ appearing $n\geq 1$ times in the sum,
which is computed in $\mathbb{K}$ or $\mathbb{K}^{*}$ depending on whether $x$
is an element of $\mathbb{K}$ or of $\mathbb{K}^{*}$, we have

$h(a^{*})=h(d^{k}c^{*})=d^{k}h(c^{*})=d^{k}c=a,$ (44)

and $a^{*}\not=0$ in $\mathbb{K}^{*}$, again because $h$ is a homomorphism and
$a\not=0$ in $\mathbb{K}$. Next we define a collection
$R^{*}_{1},\ldots,R^{*}_{m}$ of $h$-lifts of $R_{1},\ldots,R_{m}$ by setting
$R^{*}_{i}(t)=a^{*}$ for every $X_{i}$-tuple $t$ such that $t\in
R_{i}^{\prime}$, and $R^{*}_{i}(t)=0$ for every other $X_{i}$-tuple. By (44)
we have $h\circ R^{*}_{i}=R_{i}$, so $R^{*}_{i}$ is an $h$-lift of $R_{i}$.
The proof that the collection $R^{*}_{1},\ldots,R^{*}_{m}$ is pairwise
consistent as a collection $\mathbb{K}^{*}$-relations is identical to that in
Lemma 2 for $R_{1},\ldots,R_{m}$ but arguing with $c^{*}$ and $a^{*}$ in
$\mathbb{K}^{*}$ instead of arguing with $c$ and $a$ in $\mathbb{K}$.

The proof that the collection $R_{1},\ldots,R_{m}$ of $\mathbb{K}$-relations
is not globally consistent stays the same, which completes the proof. ∎

Next we argue that the two operations that transform an arbitrary non-acyclic
hypergraph to a minimal one of the form $C_{n}$ with $n\geq 3$, or $H_{n}$
with $n\geq 4$, preserve the same levels of consistency up to a cover. The
statement of the following lemma is almost identical to that of Lemma 4. To
prove it we will only indicate the differences in the arguments.

######  Lemma 6.

Let $\mathbb{K}$ be a positive commutative monoid and let
$h:\mathbb{K}^{*}\stackrel{{\scriptstyle\scriptscriptstyle{s}}}{{\rightarrow}}\mathbb{K}$
be a cover of $\mathbb{K}$. Let $H_{0}$ and $H_{1}$ be hypergraphs such that
$H_{0}$ is obtained from $H_{1}$ by a sequence of safe-deletion operations.
For every collection $D_{0}$ of $\mathbb{K}$-relations over $H_{0}$, there
exists a collection $D_{1}$ of $\mathbb{K}$-relations over $H_{1}$ such that,
for every positive integer $k$, it holds that $D_{0}$ is $k$-wise consistent
up to the cover if and only if $D_{1}$ is $k$-wise consistent up to the cover.

###### Proof.

The construction is the same as in Lemma 4 just that besides the
$\mathbb{K}$-relations $R_{i}$ we also need to construct their $h$-lifts
$R^{*}_{i}$ from the $h$-lifts $S^{*}_{i}$ of the $S_{i}$. Concretely, the
argument is as follows. In an edge-deletion operation with the notation as in
the proof of Lemma 4, the lift $R^{*}_{i}$ associated to an $R_{i}$ with
$X_{i}\not=X$ is taken as $R^{*}_{i}:=S^{*}_{i}$, and that associated to the
$R_{i}$ with $X_{i}=X$ is taken as $R^{*}_{i}:=S^{*}_{j}[X]$. In a vertex-
deletion operation with the notation as in the proof of Lemma 4, the lift
$R^{*}_{i}$ associated to an $R_{i}$ with $A\not\in X_{i}$ is taken as
$R^{*}_{i}:=S^{*}_{i}$, and that associated to an $R_{i}$ with $A\in X_{i}$ is
defined by $R^{*}_{i}(t):=S^{*}_{i}(t[X_{i}])$ if $t(A)=u_{0}$ and
$R^{*}_{i}(t):=0$ if $t(A)\not=u_{0}$. Observe that, in both cases, since
$h\circ S^{*}_{i}=S_{i}$ holds for all indices $i\in[m]$ for which $S_{i}$ and
$S^{*}_{i}$ exist, also $h\circ R^{*}_{i}=R_{i}$ holds for all $i\in[m]$, so
$R^{*}_{1},\ldots,R^{*}_{m}$ are $h$-lifts of $R_{1},\ldots,R_{m}$.

With these definitions, the proof follows from Claims 1 and 2 applied to the
positive commutative monoid $\mathbb{K}^{*}$ instead of $\mathbb{K}$, and to
the collections of $\mathbb{K}^{*}$-relations $R^{*}_{i}$ and $S^{*}_{i}$
instead of the collections of $\mathbb{K}$-relations $R_{i}$ and $S_{i}$. ∎

##  7 Concluding Remarks

In this paper, we carried out a systematic investigation of the interplay
between local consistency and global consistency for $\mathbb{K}$-relations,
where ${\mathbb{K}}$ is a positive commutative monoid. In particular, we
characterized the positive commutative monoids $\mathbb{K}$ for which a schema
$H$ is acyclic if and only if $H$ has the local-to-global consistency property
for $\mathbb{K}$-relations; this characterization was in terms of the inner
consistency property, which is a semantic notion, and also in terms of the
transportation property, which is a combinatorial notion. Furthermore, we
showed that, by strengthening the notion of pairwise consistency to pairwise
consistency up to the free cover of $\mathbb{K}$, we can characterize the
local-to-global consistency property for collections of $\mathbb{K}$-relations
on acyclic schemas for arbitrary positive commutative monoids.

We conclude by describing a few open problems motivated by the work reported
here.

As seen earlier, there are finite positive commutative monoids that have the
transportation property (e.g., $\mathbb{B}$) and others that do not (e.g.,
${\mathbb{N}}_{2}$). How difficult is it to decide whether or not a given
finite positive commutative monoid $\mathbb{K}$ has the transportation
property? Is this problem decidable or undecidable? The same question can be
asked when the given monoid is _finitely presentable_. Note that the
transportation property is defined using an infinite set of first-order axioms
in the language of monoids. Thus, a related question is whether or not the
transportation property is finitely axiomatizable.

We exhibited several classes of monoids that have the transportation property.
In each case, we gave an explicit construction or a procedure for finding a
witness to the consistency of two consistent $\mathbb{K}$-relations. In some
cases (e.g., when the monoid has an expansion to a semifield), there is a
suitable join operation that yields a _canonical_ such witness. However, in
some other cases (e.g., when the northwest corner method is used), no
_canonical_ such witness seems to exist. Is there a way to compare the
different witnesses to consistency and classify them according to some
desirable property, such as maximizing some carefully chosen objective
function?

Beeri et al. [BFMY83] showed that hypergraph acyclicity is also equivalent to
semantic conditions other than the local-to-global consistency property for
ordinary relations, such as the existence of a _full reducer_ , which is a
sequence of _semi-join_ operations for computing a witness to global
consistency. Does an analogous result hold for positive commutative monoids
$\mathbb{K}$ that have the transportation property? The main difficulty is
that it is not clear if a suitable semi-join operation on
$\mathbb{K}$-relations can be defined for such monoids.

Finally, the work presented here expands the study of relations with
annotations over semirings to relations with annotations over monoids. As
explained in the Introduction, consistency notions only require the use of an
addition operation (and not a multiplication operation). What other
fundamental problems in databases can be studied in this broader framework of
relations with annotations over monoids?

## Acknowledgments

The research of Albert Atserias was partially supported by grants
PID2019-109137GB-C22 (PROOFS) and PID2022-138506NB-C22 (PROOFS BEYOND), and
Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence
in R&D (CEX2020-001084-M) of the AEI. The research of Phokion Kolaitis was
partially supported by NSF Grant IIS-1814152.

## References

  * [ABU79] Alfred V. Aho, Catriel Beeri, and Jeffrey D. Ullman.  The theory of joins in relational databases.  ACM Trans. Database Syst., 4(3):297–314, 1979.
  * [AK21] Albert Atserias and Phokion G. Kolaitis.  Structure and complexity of bag consistency.  In Leonid Libkin, Reinhard Pichler, and Paolo Guagliardo, editors, PODS’21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Virtual Event, China, June 20-25, 2021, pages 247–259. ACM, 2021.
  * [AK23] Albert Atserias and Phokion G. Kolaitis.  Acyclicity, consistency, and positive semirings.  In Alessandra Palmigiano and Mehrnoosh Sadrzadeh, editors, Samson Abramsky on Logic and Structure in Computer Science and Beyond, Outstanding Contributions to Logic, pages 623–668. Springer, 2023.
  * [Bel64] John S Bell.  On the Einstein-Podolsky-Rosen paradox.  Physics Physique Fizika, 1(3):195, 1964.
  * [Ber89] Claude Berge.  Hypergraphs - combinatorics of finite sets, volume 45 of North-Holland mathematical library.  North-Holland, 1989.
  * [BFMY83] Catriel Beeri, Ronald Fagin, David Maier, and Mihalis Yannakakis.  On the desirability of acyclic database schemes.  J. ACM, 30(3):479–513, July 1983.
  * [Bir35] Garrett Birkhoff.  On the structure of abstract algebras.  In Mathematical proceedings of the Cambridge philosophical society, volume 31(4), pages 433–454. Cambridge University Press, 1935.
  * [Bra16] Johann Brault-Baron.  Hypergraph acyclicity revisited.  ACM Comput. Surv., 49(3):54:1–54:26, 2016.
  * [BS81] Stanley Burris and Hanamantagouda P. Sankappanavar.  A course in universal algebra, volume 78 of Graduate texts in mathematics.  Springer, 1981.
  * [GKT07] Todd J. Green, Gregory Karvounarakis, and Val Tannen.  Provenance semirings.  In Leonid Libkin, editor, Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 11-13, 2007, Beijing, China, pages 31–40. ACM, 2007.
  * [Gre11] Todd J. Green.  Containment of conjunctive queries on annotated relations.  Theory Comput. Syst., 49(2):429–459, 2011.
  * [HLY80] Peter Honeyman, Richard E. Ladner, and Mihalis Yannakakis.  Testing the universal instance assumption.  Inf. Process. Lett., 10(1):14–19, 1980.
  * [KHF14] Ravi Kunjwal, Chris Heunen, and Tobias Fritz.  Quantum realization of arbitrary joint measurability structures.  Phys. Rev. A, 89:052126, May 2014.
  * [KRS14] Egor V. Kostylev, Juan L. Reutter, and András Z. Salamon.  Classification of annotation semirings over containment of conjunctive queries.  ACM Trans. Database Syst., 39(1):1:1–1:39, 2014.
  * [MI08] Takayuki Miyadera and Hideki Imai.  Heisenberg’s uncertainty principle for simultaneous measurement of positive-operator-valued measures.  Phys. Rev. A, 78:052119, Nov 2008.
  * [RTL76] Donald J. Rose, Robert Endre Tarjan, and George S. Lueker.  Algorithmic aspects of vertex elimination on graphs.  SIAM J. Comput., 5(2):266–283, 1976.
  * [Sch86] Alexander Schrijver.  Theory of Linear and Integer Programming.  John Wiley & Sons, Inc., USA, 1986.
  * [Tse68] G. S. Tseitin.  On the complexity of derivation in propositional calculus.  Structures in Constructive Mathematics and Mathematical Logic, pages 115–125, 1968.
  * [Ull82] Jeffrey D. Ullman.  The u. r. strikes back.  In Jeffrey D. Ullman and Alfred V. Aho, editors, Proceedings of the ACM Symposium on Principles of Database Systems, March 29-31, 1982, Los Angeles, California, USA, pages 10–22. ACM, 1982.
  * [Vor62] Nikolai Nikolaevich Vorob’ev.  Consistent families of measures and their extensions.  Theory of Probability & Its Applications, 7(2):147–163, 1962.