*OPTIONAL comment concerning the title, e.g., if a variant or an extended abstract of the paper has appeared elsewhere.

# Integrity Constraints Revisited: From Exact to Approximate Implication

Batya Kenig  Technion<EMAIL_ADDRESS>Dan Suciu  University of
Washington<EMAIL_ADDRESS>
###### Abstract

Integrity constraints such as functional dependencies (FD), and multi-valued
dependencies (MVD) are fundamental in database schema design. Likewise,
probabilistic conditional independences (CI) are crucial for reasoning about
multivariate probability distributions. The implication problem studies
whether a set of constraints (antecedents) implies another constraint
(consequent), and has been investigated in both the database and the AI
literature, under the assumption that all constraints hold exactly. However,
many applications today consider constraints that hold only approximately. In
this paper we define an approximate implication as a linear inequality between
the degree of satisfaction of the antecedents and consequent, and we study the
relaxation problem: when does an exact implication relax to an approximate
implication? We use information theory to define the degree of satisfaction,
and prove several results. First, we show that any implication from a set of
data dependencies (MVDs+FDs) can be relaxed to a simple linear inequality with
a factor at most quadratic in the number of variables; when the consequent is
an FD, the factor can be reduced to 1. Second, we prove that there exists an
implication between CIs that does not admit any relaxation; however, we prove
that every implication between CIs relaxes “in the limit”. Finally, we show
that the implication problem for differential constraints in market basket
analysis also admits a relaxation with a factor equal to 1. Our results
recover, and sometimes extend, several previously known results about the
implication problem: implication of MVDs can be checked by considering only
2-tuple relations, and the implication of differential constraints for
frequent item sets can be checked by considering only databases containing a
single transaction.

###### keywords:

Integrity constraints, the implication problem

##  1 Introduction

Cone | Relaxation Bounds
---|---
General | MVDs+FDs | MVDs+FDs | Disjoint MVDs+FDs
$\Rightarrow$ FD |  $\Rightarrow$ any |  $\Rightarrow$ MVD/FD
$\Gamma_{n}$ |  $(2^{n})!$ (Thm. 19) |  $1$ (Thm. 5) |  $\frac{n^{2}}{4}$ (Thm. 5) |  $1$ (Thm. 12)
$\Gamma^{*}_{n}$ |  $\infty$ (Thm. 13) |  $1$ (Thm. 5) |  $\frac{n^{2}}{4}$ (Thm. 5) |  $1$ (Thm. 12)
$\mathcal{P}_{n}$ |  $1$ (Thm. 24) |  $1\hskip 2.84544pt$(Thm. 24) |  $1$ (Thm. 24) |  $1$ (Thm. 24)
Table 1: Summary of results: relaxation bounds for the implication
$\Sigma\Rightarrow\tau$ for the sub-cones of $\Gamma_{n}$ under various
restrictions. (1) General; no restrictions to either $\Sigma$ or $\tau$ (2)
$\Sigma$ is a set of saturated CIs and conditional entropies (i.e., MVDs+FDs
in databases), and $\tau$ is a conditional entropy. (3) $\Sigma$ is a set of
saturated CIs and conditional entropies, $\tau$ is _any_ CI (4) Disjoint
integrity constraints. The terms in $\Sigma$ are both saturated and _disjoint_
(see definition 4 in Sec. 4), and $\tau$ is saturated.

Traditionally, integrity constraints are assertions about a database that are
stated by the database administrator and enforced by the system during
updates. However, in several applications of Big Data, integrity constraints
are discovered, or mined in a database instance, as opposed to being asserted
by the administrator [GR04, SBHR06, CIPY14, BBF+16, KN18]. For example, data
cleaning can be done by first learning conditional functional dependencies in
some reference data, then using them to identify inconsistencies in the test
data [IC15, CIPY14]. Causal reasoning [SGS00, PE08, SGS18] and learning sum-
of-product networks [PD11, FD16, MVM+18] repeatedly discover conditional
independencies in the data. Constraints also arise in many other domains, for
example in the _frequent itemset problem_ (FIS) [Li05, CP01], or as _measure
based constraints_ [SGG08] in applications like Dempster-Shafer theory,
possibilistic theory, and game theory (see discussion in [SGG08]). In all
these applications, quite often the constraints are learned from the data, and
are not required to hold exactly, but it suffices if they hold only to a
certain degree.

The classical _implication problem_ asks whether a set of constraints, called
the antecedents, logically imply another constraint called the consequent. In
this setting, both antecedents and consequent are required to hold exactly,
hence we refer to it as an _exact implication_ (EI). The database literature
has extensively studied the EI problem for integrity constraints and shown
that the implication problem is decidable and axiomatizable for Functional
Dependencies (FDs) and Multivalued Dependencies (MVDs) [Mai83, KLV13, AD80,
BFH77], and undecidable for Embedded Multivalued Dependencies (EMVDs) [Her06].
The AI community has studied extensively the EI problem for Conditional
Independencies (CI), which are assertions of the form $X\perp Y\mid Z$,
stating that $X$ is independent of $Y$ conditioned on $Z$, and has shown that
the implication problem is decidable and axiomatizable for saturated CIs
[GP93] (where $XYZ=$ all variables), but not finitely axiomatizable in general
[Stu90]. In the FIS problem, a constraint like $X\rightarrow Y\vee Z\vee U$
means that every basket that contains $X$ also contains at least one of
$Y,Z,U$, and the implication problem here is also decidable and axiomatizable
[SVG05].

The Relaxation Problem. In this paper we consider a new problem, called the
relaxation problem: if an exact implication holds, does an approximate
implication hold too? For example, suppose we prove that a given set of FDs
implies another FD, but the input data satisfies the antecedent FDs only to
some degree: to what degree does the consequent FD hold on the database? An
_approximate implication_ (AI) is an inequality that (numerically) bounds the
consequent by a linear combination of the antecedents. The relaxation problem
asks whether we can convert an EI into an AI. When relaxation holds, then any
inference system for proving exact implication, e.g. using a set of axioms or
some algorithm, can be used to infer an approximate implication.

In order to study the relaxation problem we need to measure the degree of
satisfaction of a constraint. In this paper we use Information Theory. This is
the natural semantics for modeling CIs of multivariate distributions, because
$X\perp Y\mid Z$ iff $I(X;Y|Z)=0$ where $I$ is the _conditional mutual
information_. FDs and MVDs are special cases of CIs [Lee87, DR00, WBW00]
(reviewed in Sec. 2.1), and thus they are naturally modeled using the
information theoretic measure $I(X;Y|Z)$ or $H(Y|X)$; in contrast, EMVDs do
not appear to have a natural interpretation using information theory, and we
will not discuss them here. Several papers have argued that information theory
is a suitable tool to express integrity constraints [Lee87, DR00, WBW00,
Mal86, GR04].

An exact implication (EI) becomes an assertion of the form
$(\sigma_{1}=0\wedge\sigma_{2}=0\wedge\ldots)\Rightarrow(\tau=0)$, while an
approximate implication (AI) is a linear inequality
$\tau\leq\lambda\cdot\left(\sum\sigma_{i}\right)$, where $\lambda\geq 0$, and
$\tau,\sigma_{1},\sigma_{2},\ldots$ are information theoretic measures. We say
that a class of constraints can be relaxed if EI implies AI; we also say that
it $\lambda$-relaxes, when we want to specify the factor $\lambda$ in the AI.
We notice an AI always implies EI.

Results We make several contributions, summarized in Table 1. We start by
showing in Sec. 4 that MVDs$+$FDs admit an $n^{2}/4$-relaxation, where $n$ is
the number of variables. When the consequent is an FD, we show that
implication admits a 1-relaxation. Thus, whenever an exact implication holds
between MVD$+$FDs, a simple linear inequality also holds between their
associated information theoretic terms. In fact, we prove a stronger result
that holds for CIs in general, which implies the result for MVDs$+$FDs. In
addition, under some mild syntactic restrictions to the antecedents, we
strengthen the result from a $n^{2}/4$-relaxation to a 1-relaxation, even when
the consequent is an MVD; we leave open the question whether 1-relaxation
exists in general.

So far, we have restricted ourselves to saturated or conditional CIs (which
correspond to MVDs or FDs). In Sec. 5 we remove any restrictions, and prove a
negative result: there exists an EI that does not relax (Eq. (19), based on an
example in [KR13]). Nevertheless, we show that every EI can be relaxed to an
AI plus an error term, which can be made arbitrarily small, at the cost of
increasing the factor $\lambda$. This result implies that every EI can be
proven from some inequality, corresponding to the AI associated to the EI,
plus an error term. In fact, the EI in Eq. (19) follows from an inequality by
Matúš [Mat07], which is precisely the associated AI plus an error term; our
result shows that every EI can be proven in this style.

Next, we consider two restrictions, which are commonly used in model theory.
First, in Sec. 6 we restrict the class of axioms used to prove implications,
to Shannon’s inequalities (monotonicity and submodularity, reviewed in Sec.
2.2). In general, Shannon’s inequalities are sound but incomplete for proving
exact and approximate implications that hold for all probability distributions
[ZY97, ZY98], but they are complete for deriving inequalities that hold for
all polymatroids [Yeu08]. We show that they are also complete for
saturated$+$conditional constraints (as we show in Sec 4), and for measure-
based constraints [SGG08] (Sec. 7). We prove that every exact implication that
holds for all polymatroids relaxes to an approximate implication, and prove an
upper bound $\lambda\leq(2^{n})!$, and a lower bound $\lambda\geq 3$; the
exact bound remains open. Second, in Sec. 7 we restrict the class of models
used to check an implication, to probability distributions with exactly 2
outcomes (tuples), each with probability 1/2; we justify this shortly. We
prove that, under this restriction, the implication problem has a
1-relaxation. Restricting the models leads to a complete but unsound method
for checking general implication, however this method is sound for
saturated$+$conditional (as we show in Sec 4) and is also sound for checking
FIS constraints (as we show in Sec. 7).

Two Consequences While our paper is focused on relaxation, our results have
two consequences for the exact implication problem. The first is a 2-tuple
model property: an exact implication, where the antecedents are saturated or
conditional CIs, can be verified on uniform probability distributions with 2
tuples. A similar result is known for MVD$+$FDs [SDPF81]. Geiger and Pearl
[GP93], building on an earlier result by Fagin [Fag82], prove that every set
of CIs has an _Armstrong model_ : a discrete probability distribution that
satisfies only the CIs and their consequences, and no other CI. The Armstrong
model is also called a _global witness_ , and, in general, can be arbitrarily
large. Our result concerns a local witness: for any EI, if it fails on some
probability distribution, then it fails on a 2-tuple uniform distribution.

The second consequence concerns the equivalence between the implication
problem of saturated$+$conditional CIs with that of MVD$+$FDs. It is easy to
check that the former implies the latter (Sec. 2). Wong et al. [WBW00] prove
the other direction, relying on the sound and complete axiomatization of MVDs
[BFH77]. Our 2-tuple model property implies the other direction immediately.

This article extends the conference publication by the authors [KS20]. We have
added in this article all the proofs and intermediate results that were
excluded from the conference paper, as well as examples illustrating the ideas
and methods introduced.

##  2 Notation and Preliminaries

We denote by $[n]=\mathord{\\{1,2,\ldots,n\\}}$. If
$\Omega=\mathord{\\{X_{1},\ldots,X_{n}\\}}$ denotes a set of variables and
$U,V\subseteq\Omega$, then we abbreviate the union $U\cup V$ with $UV$.

###  2.1 Integrity Constraints and Conditional Independence

A _relation instance_ $R$ over signature
$\Omega=\mathord{\\{X_{1},\dots,X_{n}\\}}$ is a finite set of tuples with
attributes $\Omega$. Let $X,Y,Z\subseteq\Omega$. We say that the instance $R$
satisfies the _functional dependency_ (FD) $X\rightarrow Y$, and write
$R\models X\rightarrow Y$, if forall $t_{1},t_{2}\in R$, $t_{1}[X]=t_{2}[X]$
implies $t_{1}[Y]=t_{2}[Y]$. We say that $R$ satisfies the _embedded
multivalued dependency_ (EMVD) $X\twoheadrightarrow Y\mid Z$, and write
$R\models X\twoheadrightarrow Y\mid Z$, if for all $t_{1},t_{2}\in R$,
$t_{1}[X]=t_{2}[X]$ implies $\exists t_{3}\in R$ such that
$t_{1}[XY]=t_{3}[XY]$ and $t_{2}[XZ]=t_{3}[XZ]$. One can check that
$X\twoheadrightarrow Y\mid Y$ iff $X\rightarrow Y$. When $XYZ=\Omega$, then we
call $X\twoheadrightarrow Y\mid Z$ a _multivalued dependency_ , MVD; notice
that $X,Y,Z$ are not necessarily disjoint [BFH77].

A set of constraints $\Sigma$ implies a constraint $\tau$, in notation
$\Sigma\Rightarrow\tau$, if for every instance $R$, if $R\models\Sigma$ then
$R\models\tau$. The implication problem has been extensively studied in the
literature; Beeri et al. [BFH77] gave a complete axiomatization of FDs and
MVDs, while Herrman [Her06] showed that the implication problem for EMVDs is
undecidable.

Recall that two discrete random variables $X,Y$ are called independent if
$p(X=x,Y=y)=p(X=x)\cdot p(Y=y)$ for all outcomes $x,y$. Fix
$\Omega=\mathord{\\{X_{1},\dots,X_{n}\\}}$ a set of $n$ jointly distributed
discrete random variables with finite domains
$\mathcal{D}_{1},\dots,\mathcal{D}_{n}$, respectively; let $p$ be the
probability mass. For $\alpha\subseteq[n]$, denote by $X_{\alpha}$ the joint
random variable $(X_{i}\mathrel{\mathop{\ordinarycolon}}i\in\alpha)$ with
domain
$\mathcal{D}_{\alpha}\stackrel{{\scriptstyle\text{def}}}{{=}}\prod_{i\in\alpha}D_{i}$.
We write $p\models X_{\beta}\perp X_{\gamma}|X_{\alpha}$ when
$X_{\beta},X_{\gamma}$ are conditionally independent given $X_{\alpha}$; in
the special case $\beta=\gamma$, then $p\models X_{\beta}\perp
X_{\beta}|X_{\alpha}$ iff $X_{\alpha}$ functionally determines111This means:
$\forall u\in D_{\alpha}$, if $p(X_{\alpha}=u)\neq 0$ then $\exists v\in
D_{\beta}$ s.t. $p(X_{\beta}=v|X_{\alpha}=u)=1$, and $v$ is unique.
$X_{\beta}$, and we write $p\models X_{\alpha}\rightarrow X_{\beta}$.

An assertion $Y\perp Z|X$ is called a Conditional Independence statement, or a
CI; this includes $X\rightarrow Y$ as a special case. When $XYZ=\Omega$ we
call it _saturated_ , and when $Z=\emptyset$ we call it _marginal_. A set of
CIs $\Sigma$ implies a CI $\tau$, in notation $\Sigma\Rightarrow\tau$, if
every probability distribution that satisfies $\Sigma$ also satisfies $\tau$.
This implication problem has also been extensively studied: Pearl and Paz
[PP86] gave a sound but incomplete set of graphoid axioms, Studeny [Stu90]
proved that no finite axiomatization exists, while Geiger and Pearl [GP93]
gave a complete axiomatization for saturated, and marginal CIs.

Lee [Lee87] observed the following connection between database constraints and
CIs. The _empirical distribution_ of a relation $R$ is the uniform
distribution over its tuples, in other words, $\forall t\in R$, $p(t)=1/|R|$.
Then:

######  Lemma 1.

_([Lee87])_ Forall $X,Y,Z\subset\Omega$ such that $XYZ=\Omega$.

$\displaystyle R\models$ $\displaystyle X\rightarrow Y$
$\displaystyle\Leftrightarrow$ $\displaystyle p\models X\rightarrow Y$ and
$\displaystyle R\models$ $\displaystyle X\twoheadrightarrow Y|Z$
$\displaystyle\Leftrightarrow$ $\displaystyle p\models(Y\perp Z|X)$ (1)

As can be seen in the Example of Table 2, the lemma no longer holds for EMVDs,
and for that reason we no longer consider EMVDs in this paper. The lemma
immediately implies that if $\Sigma,\tau$ are saturated and/or conditional CIs
and the implication $\Sigma\Rightarrow\tau$ holds for all probability
distributions, then the corresponding implication holds in databases, where
the CIs are interpreted as MVDs or FDs respectively. Wong [WBW00] gave a non-
trivial proof for the other direction; we will give a much shorter proof in
Corollary 7.

$X_{1}$ | $X_{2}$ | $X_{3}$
---|---|---
$a$ | $c$ | $e$
$b$ | $c$ | $e$
$a$ | $d$ | $e$
$b$ | $d$ | $e$
$b$ | $d$ | $f$
Table 2:  The relation $R[X_{1},X_{2},X_{3}]$ satisfies the EMVD
$\emptyset\twoheadrightarrow X_{1}|X_{2}$, yet for the empirical distribution,
$I_{h}(X_{1};X_{2})\neq 0$ because $X_{1},X_{2}$ are dependent:
$p(X_{1}=a)=2/5\neq p(X_{1}=a|X_{2}=c)=1/2$.

###  2.2 Background on Information Theory

We adopt required notation from the literature on information theory [Yeu08,
Cha11]. For $n>0$, we identify vectors in ${}^{2^{n}}$ with functions
$2^{{[n]}}\rightarrow$.

Polymatroids. A function222Most authors consider rather the space
${}^{2^{n}-1}$, by dropping $h(\emptyset)$ because it is always $0$.
$h\in^{2^{n}}$ is called a _polymatroid_ if $h(\emptyset)=0$ and satisfies the
following inequalities, called Shannon inequalities:

  1. 1.

Monotonicity: $h(A)\leq h(B)$ for $A\subseteq B$

  2. 2.

Submodularity: $h(A\cup B)+h(A\cap B)\leq h(A)+h(B)$ for all $A,B\subseteq[n]$

The set of polymatroids is denoted $\Gamma_{n}\subseteq^{2^{n}}$, and forms a
polyhedral cone (reviewed in Sec. 5). For any polymatroid $h$ and subsets
$A,B,C\subseteq[n]$, we define333Recall that $AB$ denotes $A\cup B$.

$\displaystyle h(B|A)\mathrel{\stackrel{{\scriptstyle\textsf{\tiny
def}}}{{=}}}$ $\displaystyle~{}h(AB)-h(A)$ (2) $\displaystyle
I_{h}(B;C|A)\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}{{=}}}$
$\displaystyle~{}h(AB)+h(AC)-h(ABC)-h(A)$ (3)

Then, $\forall h\in\Gamma_{n}$, $I_{h}(B;C|A)\geq 0$ and $h(B|A)\geq 0$. The
_chain rule_ is the identity:

$I_{h}(B;CD|A)=I_{h}(B;C|A)+I_{h}(B;D|AC)$ (4)

We call $I_{h}(B;C|A)$ _saturated_ if $ABC=[n]$, and _elemental_ if
$|B|=|C|=1$; $h(B|A)$ is a special case of $I_{h}$, because
$h(B|A)=I_{h}(B;B|A)$.

Entropic Functions. If $X$ is a random variable with a finite domain
$\mathcal{D}$ and probability mass $p$, then $H(X)$ denotes its entropy

$H(X)\mathrel{\stackrel{{\scriptstyle\textsf{\tiny
def}}}{{=}}}\sum_{x\in\mathcal{D}}p(x)\log\frac{1}{p(x)}$ (5)

For a set of jointly distributed random variables
$\Omega=\mathord{\\{X_{1},\dots,X_{n}\\}}$ we define the function
$h\mathrel{\mathop{\ordinarycolon}}2^{{[n]}}\rightarrow$ as
$h(\alpha)\mathrel{\stackrel{{\scriptstyle\textsf{\tiny
def}}}{{=}}}H(X_{\alpha})$; $h$ is called an _entropic function_ , or, with
some abuse, an _entropy_. The set of entropic functions is denoted
$\Gamma^{*}_{n}$. The quantities $h(B|A)$ and $I_{h}(B;C|A)$ are called the
_conditional entropy_ and _conditional mutual information_ respectively. The
conditional independence $p\models B\perp C\mid A$ holds iff $I_{h}(B;C|A)=0$,
and similarly $p\models A\rightarrow B$ iff $h(B|A)=0$, thus, entropy provides
us with an alternative characterization of CIs.

2-Tuple Relations and Step functions. 2-tuple relations play a key role for
the implication problem of MVDs$+$FDs: if an implication fails, then there
exists a witness consisting of only two tuples [SDPF81]. We define a _step
function_ as the entropy of the empirical distribution of a 2-tuple relation;
$R=\mathord{\\{t_{1},t_{2}\\}}$, $t_{1}\neq t_{2}$, and
$p(t_{1})=p(t_{2})=1/2$. We denote the step function by $h_{U}$, where
$U\subsetneq\Omega$ is the set of attributes where $t_{1},t_{2}$ agree. One
can check:

$\displaystyle h_{U}(W)=$ $\displaystyle\begin{cases}0&\mbox{if $W\subseteq
U$}\\\ 1&\mbox{otherwise}\end{cases}$ (6)

If we set $U=\Omega$ in (6) then $h_{\Omega}\equiv 0$. Unless otherwise
stated, in this paper we do not consider $h_{\Omega}$ to be a step function.
Thus, there are $2^{n}-1$ step functions and their set is denote
$\mathcal{S}_{n}$. We will use the following fact extensively in this paper:
$I_{h_{U}}(Y;Z|X)=1$ if $X\subseteq U$ and $Y,Z\not\subseteq U$, and
$I_{h_{U}}(Y;Z|X)=0$ otherwise.

$X_{1}$ | $X_{2}$ | $U_{1}$ | $U_{2}$ | ${\tt\mathrm{Pr}}$
---|---|---|---|---
0 | 0 | 0 | 0 | 1/2
1 | 1 | 0 | 0 | 1/2

(a)

$X$ | $Y$ | $Z$ | $\Pr$
---|---|---|---
0 | 0 | 0 | 1/4
0 | 1 | 1 | 1/4
1 | 0 | 1 | 1/4
1 | 1 | 0 | 1/4

(b)

$A$ | $B$ | $C$ | $D$ | $\Pr$
---|---|---|---|---
0 | 0 | 0 | 0 | $1/2-\varepsilon$
0 | 1 | 0 | 1 | $1/2-\varepsilon$
1 | 0 | 1 | 0 | $\varepsilon$
1 | 1 | 0 | 0 | $\varepsilon$

(c)

Figure 1: Two relations and their empirical distribution (a),(b); a
distribution from [KR13] (c).

Consider the relational instance in Fig. 1 (a). It’s entropy is the step
function $h_{U_{1}U_{2}}(W)$, which is 0 for $W\subseteq U_{1}U_{2}$ and 1
otherwise. $R\models X_{1}\rightarrow X_{2}$ because
$h(X_{2}|X_{1})=h(X_{1}X_{2})-h(X_{1})=1-1=0$, and $R\not\models
U_{1}\rightarrow X_{1}$ because $h(X_{1}|U_{1})=h(X_{1}U_{1})-h(U_{1})=1-0\neq
0$.

The relational instance $R=\\{{(x,y,z)}\mid{x+y+z\mod 2=0}\\}$ in Fig. 1 (b)
is called the parity function. It’s entropy is $h(X)=h(Y)=h(Z)=1$,
$h(XY)=h(XZ)=h(YZ)=h(XYZ)=2$. We have that $R\models Y\perp Z$ because
$I_{h}(Y;Z)=h(Y)+h(Z)-h(YZ)=1+1-2=0$, but $R\not\models Y\perp Z|X$ because
$I_{h}(Y;Z|X)=1$ 444$h(XY)+h(XZ)-h(X)-h(XYZ)=2+2-1-2=1$.

####  2.2.1 Cones

We review cones [Stu93, BV04] that are used in the proof of Theorem 14 in
Section 5. A set $C\subseteq^{N}$ is _convex_ if, for any two points
$x_{1},x_{2}\in C$ and any $\theta\in[0,1]$, $\theta x_{1}+(1-\theta)x_{2}\in
C$; and it is called a _cone_ , if for every $x\in C$ and $\theta\geq 0$ we
have that $\theta x\in C$. The _conic hull_ of $C$,
$\mathbf{conhull}\left(C\right)$, is the set of vectors of the form
$\theta_{1}x_{1}+\dots+\theta_{k}x_{k}$, where $x_{1},\ldots,x_{k}\in C$ and
$\theta_{i}\geq 0,\forall i\in[k]$.

####  2.2.2 The I-measure

The I-measure [Yeu91, Yeu08] is a theory which establishes a one-to-one
correspondence between Shannon’s information measures and set theory. We use
the I-measure to characterize the cone of step functions
$\mathcal{P}_{n}\mathrel{\stackrel{{\scriptstyle\textsf{\tiny
def}}}{{=}}}\mathbf{conhull}(\mathcal{S}_{n})$, and to prove that _any_ exact
implication in $\mathcal{P}_{n}$ admits a 1-relaxation (see Table 1). We use
this in Section 7, to show that differential constraints in market basket
analysis admit a 1-relaxation (Theorem 24). We also use the I-measure to prove
Theorem 12.

Let $h\in\Gamma_{n}$ denote a polymatroid defined over the variable set
$\mathord{\\{X_{1},\dots,X_{n}\\}}$. Every variable $X_{i}$ is associated with
a set $\mathrm{m}(X_{i})$, and it’s complement $\mathrm{m}^{c}(X_{i})$. The
universal set is $\Lambda\mathrel{\stackrel{{\scriptstyle\textsf{\tiny
def}}}{{=}}}\bigcup_{i=1}^{n}\mathrm{m}(X_{i})$, and we consider only atoms in
which at least one set appears in positive form (i.e., the atom
$\bigcap_{i=1}^{n}\mathrm{m}^{c}(X_{i})\mathrel{\stackrel{{\scriptstyle\textsf{\tiny
def}}}{{=}}}\emptyset$ is defined to be empty). Let $\mathcal{I}\subseteq[n]$.
We denote by $X_{\mathcal{I}}\mathrel{\stackrel{{\scriptstyle\textsf{\tiny
def}}}{{=}}}\mathord{\\{X_{j}\mid j\in\mathcal{I}\\}}$, and
$\mathrm{m}(X_{\mathcal{I}})\mathrel{\stackrel{{\scriptstyle\textsf{\tiny
def}}}{{=}}}\bigcup_{i\in\mathcal{I}}\mathrm{m}(X_{i})$.

The field $\mathcal{F}_{n}$ generated by sets
$\mathrm{m}(X_{1}),\dots,\mathrm{m}(X_{n})$ is the collection of sets which
can be obtained by any sequence of usual set operations (union, intersection,
complement, and difference) on $\mathrm{m}(X_{1}),\dots,\mathrm{m}(X_{n})$.

The _atoms_ of $\mathcal{F}_{n}$ are sets of the form
$\bigcap_{i=1}^{n}Y_{i}$, where $Y_{i}$ is either $\mathrm{m}(X_{i})$ or
$\mathrm{m}^{c}(X_{i})$. We denote by $\mathcal{A}$ the atoms of
$\mathcal{F}_{n}$. There are $2^{n}-1$ non-empty atoms and $2^{2^{n}-1}$ sets
in $\mathcal{F}_{n}$ expressed as the union of its atoms. A function
$\mu\mathrel{\mathop{\ordinarycolon}}\mathcal{F}_{n}\rightarrow$ is _set
additive_ if, for every pair of disjoint sets $A$ and $B$, it holds that
$\mu(A\cup B)=\mu(A){+}\mu(B)$. A real function $\mu$ defined on
$\mathcal{F}_{n}$ is called a _signed measure_ if it is set additive, and
$\mu(\emptyset)=0$.

The $I$-measure $\mu^{*}$ on $\mathcal{F}_{n}$ is defined by
$\mu^{*}(m(X_{\mathcal{I}}))=h(X_{\mathcal{I}})$ for all nonempty subsets
$\mathcal{I}\subseteq\mathord{\\{1,\dots,n\\}}$. Table 3 summarizes the
extension of this definition to the rest of the Shannon measures.

Information | $\mu^{*}$
---|---
Measures
$h(X)$ | $\mu^{*}(\mathrm{m}(X))$
$h(XY)$ | $\mu^{*}\left(\mathrm{m}(X)\cup\mathrm{m}(Y)\right)$
$h(X|Y)$ | $\mu^{*}\left(\mathrm{m}(X)\cap\mathrm{m}^{c}(Y)\right)$
$I_{h}(X;Y)$ | $\mu^{*}\left(\mathrm{m}(X)\cap\mathrm{m}(Y)\right)$
$I_{h}(X;Y|Z)$ | $\mu^{*}\left(\mathrm{m}(X)\cap\mathrm{m}(Y)\cap\mathrm{m}^{c}(Z)\right)$
Table 3: Information measures and associated I-measure

Theorem 2 [Yeu91, Yeu08] establishes the one-to-one correspondence between
Shannon’s information measures and $\mu^{*}$.

######  Theorem 2.

_([Yeu91, Yeu08])_ $\mu^{*}$ is the unique signed measure on $\mathcal{F}_{n}$
which is consistent with all Shannon’s information measures (i.e., entropies,
conditional entropies, and mutual information).

Let $\sigma=I(X;Y{|}Z)$. We denote by
$\mathrm{m}(\sigma)=\mathrm{m}(X)\cap\mathrm{m}(Y)\cap\mathrm{m}^{c}(Z)$ the
set associated with $\sigma$ (see also Table 3). For a set of mutual
information and entropy terms $\Sigma$, we let:

$\mathrm{m}(\Sigma)\mathrel{\stackrel{{\scriptstyle\textsf{\tiny
def}}}{{=}}}\bigcup_{\sigma\in\Sigma}\mathrm{m}(\sigma).$

######  Theorem 3.

_([Yeu08])_ If there is no constraint on $X_{1},\dots,X_{n}$, then $\mu^{*}$
can take any set of nonnegative values on the nonempty atoms of
$\mathcal{F}_{n}$.

The following simple Lemma will be used later on in sections 4 and 7.

######  Lemma 4.

Let $\Sigma$ denote a set of mutual information terms. If
$\Gamma_{n}\models_{EI}\Sigma\Rightarrow\tau$ then
$\mathrm{m}(\tau)\subseteq\mathrm{m}(\Sigma)$.

######  Proof 2.1.

Assume, by contradiction, that
$\mathrm{m}(\tau)\not\subseteq\mathrm{m}(\Sigma)$, and let
$b\in\mathrm{m}(\tau){\setminus}\mathrm{m}(\Sigma)$. By Theorem 3 the
$I$-measure $\mu^{*}$ can take the following non-negative values:

$\mu^{*}(a)=\begin{cases}1&\text{if }a=b\\\ 0&\text{otherwise}\end{cases}$

It is evident that $\mu^{*}(\Sigma)=0$ while $\mu^{*}(\tau)=1$, which
contradicts the implication.

###  2.3 Discussion

This paper studies exact and approximate implications, expressed as equalities
or inequalities of entropic functions $h$. For example, the augmentation axiom
for MVDs [BFH77] $A\twoheadrightarrow B|CD\Rightarrow AC\twoheadrightarrow
B|D$ is expressed as $I_{h}(B;CD|A)=0\Rightarrow I_{h}(B;D|AC)=0$, which holds
by the chain rule (4). Thus, our golden standard is to prove that
(in)equalities hold forall entropic functions, $\Gamma_{n}^{*}$. It is known
that $\Gamma^{*}_{n}$ is not topologically closed [Yeu08]; its topological
closure, $\mathbf{cl}\left(\Gamma^{*}_{n}\right)$, is called the set of almost
entropic functions. If an inequality holds for all entropic functions
$h\in\Gamma^{*}_{n}$, then, by continuity, it also holds for all almost
entropic functions $h\in\mathbf{cl}\left(\Gamma^{*}_{n}\right)$. However, this
observation does not extend to implications of (in)equalities; Kaced and
Romashchenko [KR13] gave an example of an exact implication that holds only
for entropic functions but fails for almost entropic functions. Thus, when
discussing an EI, it matters whether we assume that it holds for
$\Gamma^{*}_{n}$ or for $\mathbf{cl}\left(\Gamma^{*}_{n}\right)$. The only
result in this paper where this distinction matters are the two main theorems
in Sec. 5: the negative result Theorem 13 holds for both $\Gamma^{*}_{n}$ and
for $\mathbf{cl}\left(\Gamma^{*}_{n}\right)$, while the positive result
Theorem 14 holds only for $\mathbf{cl}\left(\Gamma^{*}_{n}\right)$. The
results in Sec. 4 apply to any set of polymatroids $K$ that contains all step
functions, i.e. $\mathcal{S}_{n}\subseteq K\subseteq\Gamma_{n}$, thus they
apply to both $\Gamma^{*}_{n}$ and $\mathbf{cl}\left(\Gamma^{*}_{n}\right)$,
while those in Sec 6 and Sec. 7 are stated only for $\Gamma_{n}$ and only for
(the conic closure of) $\mathcal{S}_{n}$ respectively.

##  3 Definition of the Relaxation Problem

We now formally define the relaxation problem. We fix a set of variables
$\Omega=\mathord{\\{X_{1},\ldots,X_{n}\\}}$, and consider formulas of the form
$\sigma=(Y;Z|X)$, where $X,Y,Z\subseteq\Omega$, which we call a _conditional
independence_ , CI; when $Y=Z$ then we write it as $X\rightarrow Y$ and call
it a _conditional_. An _implication_ is a formula $\Sigma\Rightarrow\tau$,
where $\Sigma$ is a set of CIs called _antecedents_ and $\tau$ is a CI called
_consequent_. For a CI $\sigma=(B;C|A)$, we define
$h(\sigma)\mathrel{\stackrel{{\scriptstyle\textsf{\tiny
def}}}{{=}}}I_{h}(B;C|A)$, for a set of CIs $\Sigma$, we define
$h(\Sigma)\mathrel{\stackrel{{\scriptstyle\textsf{\tiny
def}}}{{=}}}\sum_{\sigma\in\Sigma}h(\sigma)$. Fix a set $K$ s.t.
$\mathcal{S}_{n}\subseteq K\subseteq\Gamma_{n}$.

The _exact implication_ (EI) $\Sigma\Rightarrow\tau$ holds in $K$, denoted
$K\models_{EI}(\Sigma\Rightarrow\tau)$ if, forall $h\in K$, $h(\Sigma)=0$
implies $h(\tau)=0$. The _$\lambda$ -approximate implication_ ($\lambda$-AI)
holds in $K$, in notation $K\models\lambda\cdot h(\Sigma)\geq h(\tau)$, if
$\forall h\in K$, $\lambda\cdot h(\Sigma)\geq h(\tau)$. The _approximate
implication_ holds, in notation $K\models_{AI}(\Sigma\Rightarrow\tau)$, if
there exist a $\lambda\geq 0$ such that the $\lambda$-AI holds.

We will sometimes consider an equivalent definition for AI, as
$\sum_{\sigma\in\Sigma}\lambda_{\sigma}h(\sigma)\geq h(\tau)$, where
$\lambda_{\sigma}\geq 0$ are coefficients, one for each $\sigma\in\Sigma$;
these two definitions are equivalent, by taking
$\lambda=\max_{\sigma}\lambda_{\sigma}$. Notice that both EI and AI are
preserved under subsets of $K$ in the sense that $K_{1}\subseteq K_{2}$ and
$K_{2}\models_{x}(\Sigma\Rightarrow\tau)$ implies
$K_{1}\models_{x}(\Sigma\Rightarrow\tau)$, for $x\in\mathord{\\{EI,AI\\}}$.

AI always implies EI. Indeed, $h(\tau)\leq\lambda\cdot h(\Sigma)$ and
$h(\Sigma)=0$, implies $h(\tau)\leq 0$, which further implies $h(\tau)=0$,
because $h(\tau)\geq 0$ for every CI $\tau$, and every polymatroid $h$. In
this paper we study the reverse.

Let $\mathcal{I}$ be a syntactically-defined class of implication statements
$(\Sigma\Rightarrow\tau)$, and let $K\subseteq\Gamma_{n}$. We say that
$\mathcal{I}$ _admits a relaxation_ in $K$ if, every implication statement
$(\Sigma\Rightarrow\tau)$ in $\mathcal{I}$ that holds exactly, also holds
approximately: $K\models_{EI}\Sigma\Rightarrow\tau$ implies
$K\models_{AI}\Sigma\Rightarrow\tau$. We say that $\mathcal{I}$ admits a
_$\lambda$ -relaxation_ if every EI admits a $\lambda$-AI.

Let $\Sigma{=}\mathord{\\{(A;B|\emptyset),(A;C|B)\\}}$ and
$\tau{=}(A;C|\emptyset)$. Since $I_{h}(A;C|\emptyset)\leq
I_{h}(A;B|\emptyset)+I_{h}(A;C|B)$ by the chain rule (4), then the exact
implication $\Gamma_{n}\models_{EI}\Sigma\Rightarrow\tau$ admits a $1$-$AI$.

##  4 Relaxation for FDs and MVDs: Always Possible

In this section we consider the implication problem where the antecedents are
either saturated CIs, or conditionals. This is a case of special interest in
databases, because the constraints correspond to MVDs, or FDs. Recall that a
CI $(B;C|A)$ is _saturated_ if $ABC=\Omega$ (i.e., the set of all attributes).
Our main result in this section is:

######  Theorem 5.

Assume that each formula in $\Sigma$ is either saturated, or a conditional,
and let $\tau$ be an arbitrary CI. Assume
$\mathcal{S}_{n}\models_{EI}\Sigma\Rightarrow\tau$. Then:

  1. 1.

$\Gamma_{n}\models\frac{n^{2}}{4}h(\Sigma)\geq h(\tau)$.

  2. 2.

If $\tau$ is a conditional, $Z\rightarrow X$, then $\Gamma_{n}\models
h(\Sigma)\geq h(\tau)$.

Before we prove the theorem, we list two important consequences.

######  Corollary 6.

Let $\Sigma$ consist of saturated CIs and/or conditionals, and let $\tau$ be
any CI. Then $\mathcal{S}_{n}\models\Sigma\Rightarrow_{EI}\tau$ implies
$\Gamma_{n}\models\Sigma\Rightarrow_{EI}\tau$

######  Proof 4.1.

If $\mathcal{S}_{n}\models\Sigma\Rightarrow_{EI}\tau$ then $\forall
h\in\Gamma_{n}$, $h(\tau)\leq\frac{n^{2}}{4}h(\Sigma)$, thus $h(\Sigma)=0$
implies $h(\tau)=0$.

The corollary has an immediate application to the inference problem in
graphical models [GP93]. There, the problem is to check if every probability
distribution that satisfies all CIs in $\Sigma$ also satisfies the CI $\tau$;
we have seen that this is equivalent to
$\Gamma^{*}_{n}\models_{EI}\Sigma\Rightarrow\tau$. The corollary states that
it is enough that this implication holds on all of the uniform 2-tuple
distributions, i.e. $\mathcal{S}_{n}\models\Sigma\Rightarrow_{EI}\tau$,
because this implies the (even stronger!) statement
$\Gamma_{n}\models\Sigma\Rightarrow_{EI}\tau$. Decidability was already known:
Geiger and Pearl [GP93] proved that the set of graphoid axioms is sound and
complete for the case when both $\Sigma$ and $\tau$ are saturated, while
Gyssens et al. [GNG14] improve this by dropping any restrictions on $\tau$.

The second consequence is the following:

######  Corollary 7.

Let $\Sigma,\tau$ consist of saturated CIs and/or conditionals. Then the
following two statements are equivalent:

  1. 1.

The implication $\Sigma\Rightarrow\tau$ holds, where we interpret
$\Sigma,\tau$ as MVDs and/or FDs.

  2. 2.

$\Gamma_{n}\models_{EI}\Sigma\Rightarrow\tau$.

######  Proof 4.2.

We have shown right after Lemma 1 that (2) implies (1). For the opposite
direction, by Th. 5, we need only check
$\mathcal{S}_{n}\models_{EI}\Sigma\Rightarrow\tau$, which holds because on
every uniform probability distribution a saturated CI holds iff the
corresponding MVD holds, and similarly for conditionals and FDs. Since the
2-tuple relation satisfies the implication for MVDs$+$FDs, it also satisfies
the implication for CIs, proving the claim.

Wong et al. [WBW00] have proven that the implication for MVDs is equivalent to
that of the corresponding saturated CIs (called there BMVD); they did not
consider FDs. For the proof in the hard direction, they use the sound and
complete axiomatization of MVDs in [BFH77]. In contrast, our proof is
independent of any axiomatic system, and is also much shorter. Finally, we
notice that the corollary also implies that, in order to check an implication
between MVDs and/or FDs, it suffices to check it on all 2-tuple databases:
indeed, this is equivalent to checking
$\mathcal{S}_{n}\models_{EI}\Sigma\Rightarrow\tau$, because this implies Item
(2), which in turn implies item (1). This rather surprising fact was first
proven in [SDPF81].

We now turn to the proof of Theorem 5. Before proceeding, we note that we can
assume w.l.o.g. that $\Sigma$ consists only of saturated CIs. Indeed, if
$\Sigma$ contains a non-saturated term, then by assumption it is a
conditional, $X\rightarrow Y$, and we will replace it with two saturated
terms: $(Y;Z|X)$ and $XZ\rightarrow Y$, where $Z=\Omega\setminus XY$. Denoting
$\Sigma^{\prime}$ the new set of formulas, we have
$h(\Sigma)=h(\Sigma^{\prime})$, because $h(Y|X)=I_{h}(Y;Z|X)+h(Y|XZ)$. Thus,
we will assume w.l.o.g. that all formulas in $\Sigma$ are saturated.

Theorem 5 follows from the next result, which is also of independent interest.
We say that a CI $(X;Y|Z)$ is _elemental_ if $|X|=|Y|=1$. We say that $\sigma$
_covers_ $\tau$ if all variables in $\tau$ are contained in $\sigma$; for
example $\sigma=(abc;d|e)$ covers $\tau=(cd;be)$. Then:

######  Theorem 8.

Let $\tau$ be an elemental CI, and suppose each formula in $\Sigma$ covers
$\tau$. Then $\mathcal{S}_{n}\models_{EI}(\Sigma\Rightarrow\tau)$ implies
$\Gamma_{n}\models h(\tau)\leq h(\Sigma)$.

Notice that this result immediately implies Item (1) of Theorem 5, because
every $\tau=(Y;Z|X)$ can be written as a sum of $|Y|\cdot|Z|\leq n^{2}/4$
elemental terms (by the chain rule). In what follows we prove Theorem 8, then
use it to prove item (2) of Theorem 5.

Finally, we consider whether (1) of Theorem 5 can be strengthened to a
1-relaxation; we give in Th. 12 below a sufficient condition, whose proof uses
the notion of I-measure (Section 2.2.2), and leave open the question whether
1-relaxation holds in general for implications where the antecedents are
saturated CIs and conditionals.

We say that two CIs $(X;Y|Z)$ and $(A;B|C)$ are disjoint if at least one of
the following four conditions holds: (1) $X\subseteq C$, (2) $Y\subseteq C$,
(3) $A\subseteq Z$, or (4) $B\subseteq Z$. If $\tau=(X;Y|Z)$ and
$\sigma=(A;B|C)$ are disjoint, then for any step function $h_{W}$, it cannot
be the case that both $h_{W}(\tau)\neq 0$ and $h_{W}(\sigma)\neq 0$. Indeed,
if such $W$ exists, then $Z,C\subseteq W$ and, assuming (1) $X\subseteq C$
(the other three cases are similar), we have $ZX\subseteq W$ thus
$h_{W}(\tau)=0$.

###  4.1 Proof of Theorem 8

The following holds by the chain rule, and will be used later on.

######  Lemma 9.

Let $\sigma=(A;B|C)$ and $\tau=(X;Y|Z)$ be CIs such that $X\subseteq A$,
$Y\subseteq B$, $C\subseteq Z$ and $Z\subseteq ABC$. Then, $\Gamma_{n}\models
h(\tau)\leq h(\sigma)$.

######  Proof 4.3.

Since $Z\subseteq ABC$, we denote by $Z_{A}=A\cap Z$, $Z_{B}=B\cap Z$, and
$Z_{C}=C\cap Z$. Also, denote by $A^{\prime}=A\setminus(Z_{A}\cup X)$,
$B^{\prime}=B\setminus(Z_{B}\cup Y)$. So, we have that:
$I(A;B|C)=I(Z_{A}A^{\prime}X;Z_{B}B^{\prime}Y|C)$. By the chain rule, we have
that:

$\displaystyle I(Z_{A}A^{\prime}X;Z_{B}B^{\prime}Y|C)$
$\displaystyle=I(Z_{A};Z_{B}|C)+I(A^{\prime}X;Z_{B}|CZ_{A})+I(Z_{A};B^{\prime}Y|Z_{B}C)$
$\displaystyle+I(X;Y|CZ_{A}Z_{B})+I(X;B^{\prime}|CZ_{A}Z_{B}Y)+I(A^{\prime};B^{\prime}Y|CZ_{A}Z_{B}X)$

Noting that $Z=CZ_{A}Z_{B}$, we get that $I(X;Y|Z)\leq I(A;B|C)$ as required.

We now prove theorem 8. We use lower case for single variables, thus
$\tau=(x;y|Z)$ because it is elemental. We may assume w.l.o.g. $x,y\not\in Z$
(otherwise $I_{h}(x;y|Z)=0$ and the lemma holds trivially). The deficit of an
elemental CI $\tau=(x;y|Z)$ is the quantity $|\Omega-Z|$. We prove by
induction on the deficit of $\tau$ that
$\mathcal{S}_{n}\models_{EI}\Sigma\Rightarrow\tau$ implies $\Gamma_{n}\models
h(\tau)\leq h(\Sigma)$.

Assume $\mathcal{S}_{n}\models_{EI}\Sigma\Rightarrow\tau$, and consider the
step function at $Z$. Since $h_{Z}(\tau)=1$, there exists $\sigma\in\Sigma$,
$\sigma=(A;B|C)$, such that $h_{Z}(\sigma)=1$; this means that $C\subseteq Z$,
and $A,B\not\subseteq Z$. In particular $x,y\not\in C$, therefore $x,y\in AB$,
because $\sigma$ covers $\tau$. If $x\in A$ and $y\in B$ (or vice versa), then
$\Gamma_{n}\models h(\tau)\leq h(\sigma)$ by Lemma 9, proving the theorem.
Therefore, we assume w.l.o.g. that $x,y\in A$ and none is in $B$. Furthermore,
since $B\not\subseteq Z$, there exists $u\in B-Z$.

Base case: $\tau$ is saturated. Then $u\not\in xyZ$, contradicting the
assumption that $\tau$ is saturated; in other words, in the base case, it is
the case that $x\in A$ and $y\in B$.

Step: Let $Z_{A}=Z{\cap}A$, and $Z_{B}=Z{\cap}B$. Since $C\subseteq Z$, and
$\sigma=(A;B|C)$ covers $\tau$, then $Z=Z_{A}Z_{B}C$. We also write
$A=xyA^{\prime}Z_{A}$ (since $x,y\in A$) and $B=uB^{\prime}Z_{B}$. So, we have
that $\sigma=(A;B|C)=(xyA^{\prime}Z_{A};uB^{\prime}Z_{B}|C)$, and we use the
chain rule to define $\sigma_{1},\sigma_{2}$:

$\displaystyle h(\sigma)=$ $\displaystyle
I_{h}(xyA^{\prime}Z_{A};uB^{\prime}Z_{B}|C)=I_{h}(\underbrace{xyA^{\prime}Z_{A};uZ_{B}|C}_{\stackrel{{\scriptstyle\text{def}}}{{=}}\sigma_{1}})+I_{h}(\underbrace{xyA^{\prime}Z_{A};B^{\prime}|uCZ_{B}}_{\stackrel{{\scriptstyle\text{def}}}{{=}}\sigma_{2}})$

We also partition $\Sigma$ s.t. $h(\Sigma)=h(\sigma_{1})+h(\Sigma_{2})$, where
$\Sigma_{2}\stackrel{{\scriptstyle\text{def}}}{{=}}(\Sigma\setminus\mathord{\\{\sigma\\}})\cup\mathord{\\{\sigma_{2}\\}}$.

Next, define $\tau^{\prime}\stackrel{{\scriptstyle\text{def}}}{{=}}(x;uy|Z)$
and use the chain rule to define $\tau_{1},\tau_{2}$:

$h(\underbrace{x;y|Z}_{\tau})\leq
I_{h}(\underbrace{x;uy|Z}_{\tau^{\prime}})=I_{h}(\underbrace{x;u|Z}_{\stackrel{{\scriptstyle\text{def}}}{{=}}\tau_{1}})+I_{h}(\underbrace{x;y|uZ}_{\stackrel{{\scriptstyle\text{def}}}{{=}}\tau_{2}})$
(7)

By Lemma 9, $\Gamma_{n}\models h(\sigma_{1})\geq h(\tau_{1})$. We will prove:
$\mathcal{S}_{n}\models_{EI}\Sigma_{2}\Rightarrow\tau_{2}$. This implies the
theorem, because $\Sigma_{2}$ is saturated, and by the induction hypothesis
$\Gamma_{n}\models h(\Sigma_{2})\geq h(\tau_{2})$ (since the deficit of
$\tau_{2}$ is one less than that of $\tau$), and the theorem follows from
$h(\Sigma)=h(\sigma_{1})+h(\Sigma_{2})\geq
h(\tau_{1})+h(\tau_{2})=h(\tau^{\prime})\geq h(\tau)$. It remains to prove
$\mathcal{S}_{n}\models_{EI}\Sigma_{2}\Rightarrow\tau_{2}$, and we start with
a weaker claim:

$\mathcal{S}_{n}\models_{EI}\Sigma\Rightarrow\tau_{2}$.

######  Proof 4.4.

By Lemma 9 we have that
$h(\sigma)=I_{h}(xyA^{\prime}Z_{A};uB^{\prime}Z_{B}|C)\geq
I_{h}(xy;u|Z)=I_{h}(y;u|Z)+I_{h}(x;u|yZ)$. Therefore,
$\Sigma\Rightarrow(x;u|yZ)$. Since $\Sigma\Rightarrow(x;y|Z)$, then by the
chain rule we have that $\Sigma\Rightarrow(x;uy|Z)=\tau^{\prime}$, and the
claim follows from (7).

Finally, we prove $\mathcal{S}_{n}\models_{EI}\Sigma_{2}\Rightarrow\tau_{2}$.
Assume otherwise, and let $h_{W}$ be a step function such that
$h_{W}(\tau_{2})=I_{h_{W}}(x;y|uZ)=1$, and $h_{W}(\Sigma_{2})=0$. This means
that $uZ\subseteq W$. Therefore $uZ_{B}\subseteq W$, implying
$I_{h_{W}}(xyA^{\prime}Z_{A};uZ_{B}|C)=h_{W}(\sigma_{1})=0$ (because
$uZ_{B}C\subseteq uZ$). Therefore,
$h_{W}(\Sigma)=h_{W}(\sigma_{1})+h_{W}(\Sigma_{2})=0$, contradicting the fact
that $\mathcal{S}_{n}\models_{EI}\Sigma\Rightarrow\tau_{2}$.

###  4.2 Proof of Theorem 5 Item 2

######  Lemma 10.

Suppose $\mathcal{S}_{n}\models_{EI}\Sigma\Rightarrow\tau$, where
$\tau=(X;Y|Z)$. Let $\sigma\in\Sigma$ such that $\tau,\sigma$ are disjoint
(Def. 4). Then:
$\mathcal{S}_{n}\models_{EI}\left(\Sigma{\setminus}\mathord{\\{\sigma\\}}\right)\Rightarrow\tau.$

######  Proof 4.5.

Let $\Sigma^{\prime}\mathrel{\stackrel{{\scriptstyle\textsf{\tiny
def}}}{{=}}}\Sigma\setminus\mathord{\\{\sigma\\}}$. Assume by contradiction
that there exists a step function $h_{W}$ such that $h_{W}(\Sigma^{\prime})=0$
and $h_{W}(\tau)=1$. Since $\sigma,\tau$ are disjoint, $h_{W}(\sigma)=0$. Then
$h_{W}(\Sigma)=0$, contradicting the assumption
$\mathcal{S}_{n}\models_{EI}\Sigma\Rightarrow\tau$.

######  Lemma 11.

Let $\Sigma$ be a set of saturated CIs s.t.
$\mathcal{S}_{n}\models_{EI}\Sigma\Rightarrow\tau$. Suppose
$\tau=(Z\rightarrow uX)$ (which, recall, is a shorthand for $(uX;uX|Z)$), and
define $\tau_{1}=(Z\rightarrow u)$, $\tau_{2}=(uZ\rightarrow X)$; thus,
$h(\tau)=h(\tau_{1})+h(\tau_{2})$. Then there exists $\Sigma_{1}$ and
$\Sigma_{2}$ such that: (1) $h(\Sigma)=h(\Sigma_{1})+h(\Sigma_{2})$; we say
that $\Sigma_{1},\Sigma_{2}$ form a parition of $\Sigma$. (2) $\Sigma_{1}$
covers $\tau_{1}$ and
$\mathcal{S}_{n}\models_{EI}\Sigma_{1}\Rightarrow\tau_{1}$. (3) $\Sigma_{2}$
is saturated and $\mathcal{S}_{n}\models\Sigma_{2}\Rightarrow\tau_{2}$.

######  Proof 4.6.

We partition $\Sigma$ into $\Sigma_{1}$ and $\Sigma_{2}$ as follows. For every
$\sigma=(A;B|C)\in\Sigma$, if $u\in C$ then we place $\sigma$ in $\Sigma_{2}$.
Otherwise, assume w.l.o.g that $u\in A$, and we write
$A=uA_{Z}A_{X}A^{\prime}$ where $A_{Z}=A\cap Z$, $A_{X}=A\cap X$, and
$A^{\prime}=A{\setminus}\mathord{\\{uA_{Z}A_{X}\\}}$. We use the chain rule to
define $\sigma_{1},\sigma_{2}$:

$I_{h}(A;B|C)=I_{h}(uA_{Z}A_{X}A^{\prime};B|C)=I_{h}(\underbrace{uA_{Z};B|C}_{\stackrel{{\scriptstyle\text{def}}}{{=}}\sigma_{1}})+I(\underbrace{A_{X}A^{\prime};B|uA_{Z}C}_{\stackrel{{\scriptstyle\text{def}}}{{=}}\sigma_{2}})$
(8)

We place $\sigma_{1}$ in $\Sigma_{1}$, and $\sigma_{2}$ in $\Sigma_{2}$. We
observe that $\sigma_{1}$ covers $\tau_{1}$ (because
$Z=A_{Z}B_{Z}C_{Z}\subseteq A_{Z}BC$) and $\sigma_{2}$ is saturated.
Furthermore, $h(\Sigma_{1})+h(\Sigma_{2})=h(\Sigma)$. We prove
$\Sigma_{1}\models_{EI}\tau_{1}$. By assumption,
$\Sigma\models_{EI}\tau_{1}=(Z\rightarrow u)$. Let any
$\sigma_{2}=(A;B|C)\in\Sigma_{2}$; since $u\in C$, by Lemma 10 we can remove
it, obtaining $\Sigma\setminus\mathord{\\{\sigma_{2}\\}}\models_{EI}\tau_{1}$;
repeating this process proves $\Sigma_{1}\models_{EI}\tau_{1}$. Finally, we
prove $\Sigma_{2}\models_{EI}\tau_{2}$. By assumption,
$\Sigma\models_{EI}\tau_{2}=(uZ\rightarrow X)$. Let any
$\sigma_{1}=(uA_{Z};B|C)\in\Sigma_{1}$; since $uA_{Z}\subseteq uZ$, by Lemma
10 we can remove it, obtaining
$\Sigma\setminus\mathord{\\{\sigma_{1}\\}}\models_{EI}\tau_{2}$; repeating
this process proves $\Sigma_{2}\models_{EI}\tau_{2}$.

We now complete the proof of Theorem 5 item 2. Let $\tau=(Z\rightarrow X)$,
and $\Sigma$ be saturated. We show, by induction on $|X|$, that if
$\mathcal{S}_{n}\models_{EI}\Sigma\Rightarrow\tau$ then $\Gamma_{n}\models
h(\tau)\leq h(\Sigma)$. If $|X|=1$, then $X=\mathord{\\{x\\}}$,
$h(x|Z)=I(x;x|Z)$ is elemental, and the claim follows from Th. 8. Otherwise,
let $u$ be any variable in $X$, write $\tau=(Z\rightarrow uX^{\prime})$, and
apply Lemma 11 to $\tau_{1}=(Z\rightarrow u)$, $\tau_{2}=(Zu\rightarrow
X^{\prime})$, which gives us a partition of $\Sigma$ into
$\Sigma_{1},\Sigma_{2}$. On one hand,
$\mathcal{S}_{n}\models_{EI}\Sigma_{1}\Rightarrow\tau_{1}$, and from Th. 8 we
derive $h(\tau_{1})\leq h(\Sigma_{1})$ (because $\tau_{1}$ is elemental, and
covered by $\Sigma_{1}$); on the other hand
$\mathcal{S}_{n}\models_{EI}\Sigma_{2}\Rightarrow\tau_{2}$ where $\Sigma_{2}$
is saturated, which implies, by induction, $h(\tau_{2})\leq h(\Sigma_{2})$.
The result follows from $h(\tau)=h(\tau_{1})+h(\tau_{2})\leq
h(\Sigma_{1})+h(\Sigma_{2})=h(\Sigma)$, completing the proof.

###  4.3 A special case

In Theorem 12 we show that under the assumption that the set of CIs in
$\Sigma$ is disjoint (Definition 4), we also obtain a 1-relaxation. The proof
relies on the I-measure presented in Section 2.2.2, and, in particular, on
lemma 4.

######  Theorem 12.

Let $\Sigma$ be a set of saturated, pairwise disjoint CI terms (Def. 4), and
$\tau$ be a saturated mutual information. Then,
$\mathcal{S}_{n}\models_{EI}(\Sigma\Rightarrow\tau)$ implies
$\Gamma_{n}\models h(\tau)\leq h(\Sigma)$.

######  Proof 4.7.

From Theorem 6 we have that $\Gamma_{n}\models\Sigma\Rightarrow\tau$. Let
$\tau=I(A;B|C)$ be the saturated implied CI, and let
$\sigma=I(X;Y|Z)\in\Sigma$ be a saturated CI. Noting that
$\mathrm{m}(\tau)=\mathrm{m}^{c}(C)\mathrm{m}(A)\mathrm{m}(B)$ we get that:

$\mathrm{m}^{c}(\tau)=\mathrm{m}(C)\cup\mathrm{m}^{c}(C)\mathrm{m}^{c}(A)\cup\mathrm{m}^{c}(C)\mathrm{m}(A)\mathrm{m}^{c}(B)$
(9)

Furthermore, since $\sigma=I(X;Y|Z)$ is saturated, we get that
$C=C_{X}C_{Y}C_{Z}$ where $C_{X}=C\cap X$, $C_{Y}=C\cap Y$, and $C_{Z}=C\cap
Z$. From this, we get that:

$\mathrm{m}(C)=\mathrm{m}(C_{X})\cup\mathrm{m}^{c}(C_{X})\mathrm{m}(C_{Y})\cup\mathrm{m}^{c}(C_{X})\mathrm{m}^{c}(C_{Y})\mathrm{m}(C_{Z})$
(10)

Then, from (9), and the set-additivity of $\mu^{*}$, we get that:

$\displaystyle\mu^{*}\left(\mathrm{m}(\sigma)\cap\mathrm{m}^{c}(\tau)\right)$
$\displaystyle=\mu^{*}(\mathrm{m}(\sigma)\cap\mathrm{m}(C))+\mu^{*}(\mathrm{m}(\sigma)\cap\mathrm{m}^{c}(C)\mathrm{m}^{c}(A))+\mu^{*}(\mathrm{m}(\sigma)\cap\mathrm{m}^{c}(C)\mathrm{m}(A)\mathrm{m}^{c}(B))$
(11)

We consider each one of the terms in (11) separately. By (10), we have that:

$\displaystyle\mu^{*}(\mathrm{m}(\sigma)\cap\mathrm{m}(C))$
$\displaystyle=\mu^{*}(\mathrm{m}(\sigma)\mathrm{m}(C_{X}))+\mu^{*}(\mathrm{m}(\sigma)\mathrm{m}^{c}(C_{X})\mathrm{m}(C_{Y}))+\mu^{*}(\mathrm{m}(\sigma)\mathrm{m}^{c}(C_{X})\mathrm{m}^{c}(C_{Y})\mathrm{m}(C_{Z}))$
$\displaystyle=\mu^{*}(\mathrm{m}(C_{X})\mathrm{m}(Y)\mathrm{m}^{c}(Z))+\mu^{*}(\mathrm{m}(X{\setminus}C_{X})\mathrm{m}(C_{Y})\mathrm{m}^{c}(ZC_{X}))+$
$\displaystyle\mu^{*}(\mathrm{m}(X{\setminus}C_{X})\mathrm{m}(Y{\setminus}C_{Y})\mathrm{m}(C_{Z})\mathrm{m}^{c}(ZC_{X}C_{Y}))$
$\displaystyle=\mu^{*}(\mathrm{m}(C_{X})\mathrm{m}(Y)\mathrm{m}^{c}(Z))+\mu^{*}(\mathrm{m}(X{\setminus}C_{X})\mathrm{m}(C_{Y})\mathrm{m}^{c}(ZC_{X}))$
(12) $\displaystyle=I_{h}(C_{X};Y|Z)+I_{h}(X{\setminus}C_{X};C_{Y}|ZC_{X})$
(13)

where transition (12) is because $C_{Z}\subseteq Z$ and thus
$\mathrm{m}(C_{Z})\mathrm{m}^{c}(ZC_{X}C_{Y})=\emptyset$, and
$\mu^{*}(\emptyset)=0$. We now consider the second term of (11).

$\displaystyle\mu^{*}(\mathrm{m}(\sigma)\cap\mathrm{m}^{c}(C)\mathrm{m}^{c}(A))$
$\displaystyle=\mu^{*}(\mathrm{m}(X)\mathrm{m}(Y)\mathrm{m}^{c}(Z)\mathrm{m}^{c}(C)\mathrm{m}^{c}(A))$
$\displaystyle=\mu^{*}(\mathrm{m}(X)\mathrm{m}(Y)\mathrm{m}^{c}(ZCA)$
$\displaystyle=I_{h}(X;Y|ZCA)$ (14)

Finally, we consider the third term of (11). Since $I(X;Y|Z)$ is saturated, we
get that $A=A_{X}A_{Y}A_{Z}$ where $A_{X}=A\cap X$, $A_{Y}=A\cap Y$, and
$A_{Z}=A\cap Z$. Therefore:

$\mathrm{m}(A)=\mathrm{m}(A_{X})\cup\mathrm{m}^{c}(A_{X})\mathrm{m}(A_{Y})\cup\mathrm{m}^{c}(A_{X})\mathrm{m}^{c}(A_{Y})\mathrm{m}(A_{Z})$
(15)

From (15), and the set-additivity of $\mu^{*}$, we get that:

$\displaystyle\mu^{*}(\mathrm{m}(\sigma)\cap\mathrm{m}^{c}(C)\mathrm{m}(A)\mathrm{m}^{c}(B))$
$\displaystyle=\mu^{*}(\mathrm{m}(X)\mathrm{m}(Y)\mathrm{m}^{c}(Z)\mathrm{m}^{c}(C)\mathrm{m}(A)\mathrm{m}^{c}(B))$
$\displaystyle=\mu^{*}(\mathrm{m}(X)\mathrm{m}(Y)\mathrm{m}(A)\mathrm{m}^{c}(ZCB))$
$\displaystyle=\mu^{*}(\mathrm{m}(A_{X})\mathrm{m}(Y)\mathrm{m}^{c}(ZCB))+\mu^{*}(\mathrm{m}(X{\setminus}A_{X})\mathrm{m}(A_{Y})\mathrm{m}^{c}(ZCBA_{X}))$
$\displaystyle+\mu^{*}(\mathrm{m}(X{\setminus}A_{X})\mathrm{m}(Y{\setminus}A_{Y})\mathrm{m}(A_{Z})\mathrm{m}^{c}(ZCBA_{X}A_{Y}))$
$\displaystyle=\mu^{*}(\mathrm{m}(A_{X})\mathrm{m}(Y)\mathrm{m}^{c}(ZCB))+\mu^{*}(\mathrm{m}(X{\setminus}A_{X})\mathrm{m}(A_{Y})\mathrm{m}^{c}(ZCBA_{X}))$
(16)
$\displaystyle=I_{h}(A_{X};Y|ZCB)+I_{h}(X{\setminus}A_{X};A_{Y}|ZCBA_{X})$
(17)

where transition (16) is because $A_{Z}\subseteq Z$, and thus
$\mathrm{m}(A_{z})\cap\mathrm{m}^{c}(ZCBA_{X})=\emptyset$, and
$\mu^{*}(\emptyset)=0$. By (13), (14), and (17) we get that:

$\displaystyle\mu^{*}(\mathrm{m}(\sigma)\cap\mathrm{m}^{c}(\tau))$
$\displaystyle=I_{h}(C_{X};Y|Z)+I_{h}(X{\setminus}C_{X};C_{Y}|ZC_{X})$
$\displaystyle+I_{h}(X;Y|ZCA)+I_{h}(A_{X};Y|ZCB)+I_{h}(X{\setminus}A_{X};A_{Y}|ZCBA_{X})$
(18)

Therefore, by (18), we get that:
$\mu^{*}\left(\mathrm{m}(\sigma)\cap\mathrm{m}^{c}(\tau)\right)\geq 0$ for
every $\sigma\in\Sigma$. By lemma 4 we have that
$\mathrm{m}(\tau)\subseteq\mathrm{m}(\Sigma)$. And since $\Sigma$ is disjoint
then
$\mu^{*}(\mathrm{m}(\tau))=\sum_{\sigma\in\Sigma}\mu^{*}(\mathrm{m}(\tau)\cap\mathrm{m}(\sigma))$.
The result then follows from noting that due to the set-additivity of
$\mu^{*}$ then:

$h(\Sigma)=\sum_{\sigma\in\Sigma}\mu^{*}(\mathrm{m}(\sigma))=\underbrace{\sum_{\sigma\in\Sigma}\mu^{*}(\mathrm{m}(\sigma)\cap\mathrm{m}(\tau))}_{\begin{subarray}{c}=\mu^{*}(m(\tau))=h(\tau)\\\
\text{ because }\Sigma\text{ is
disjoint}\end{subarray}}+\underbrace{\sum_{\sigma\in\Sigma}\mu^{*}(\mathrm{m}(\sigma)\cap\mathrm{m}^{c}(\tau))}_{\geq
0\text{ (by~{}\eqref{eq:satdisjProof9})}}.$

##  5 Relaxation for General CIs: Sometimes Impossible

We consider the relaxation problem for arbitrary Conditional Independence
statements. Recall that our golden standard is to check (in)equalities for all
entropic functions, $h\in\Gamma^{*}_{n}$. As we saw, for MVD$+$FDs, these
(in)equalities coincide with those satisfied by $\mathcal{S}_{n}$, and with
those satisfied by $\Gamma_{n}$. In general, however, they differ. We start
with an impossibility result, then prove that relaxation with an arbitrarily
small error term always exists. Both results are for the topological closure,
$\mathbf{cl}\left(\Gamma^{*}_{n}\right)$. This makes the negative result
stronger, but the positive result weaker; it is unlikely for the positive
result to hold for $\Gamma^{*}_{n}$. We start with an example providing some
of the intuition behind this result.

###  5.1 Warmup: A Simple Example

Theorem 13 states that some EI does not relax to an AI. The example, based on
[KR13], uses 4 random variables, hence it is essentially a statement about 15,
making it difficult to visualize its underlying geometry. We give here a
simpler counterexample, in 3, albeit in a vector space unrelated to
information theory.

Let
$K\stackrel{{\scriptstyle\text{def}}}{{=}}\\{{\left(\begin{array}[]{cc}x_{1}&x_{2}\\\
x_{2}&x_{3}\end{array}\right)}\mid{x_{1}\geq 0,x_{3}\geq 0,x_{1}x_{3}\geq
x_{2}^{2}}\\}$ be the cone of semi-positive definite $2\times 2$ matrices.
This is known to be a convex cone, also called the positive semidefinite cone
[BV04]. Equivalently, we view $K$ as a cone in 3, namely
$K=\\{{(x_{1},x_{2},x_{3})}\mid{x_{1}\geq 0,x_{3}\geq 0,x_{1}x_{3}\geq
x_{2}^{2}}\\}$. Then $K$ satisfies the following Exact Implication:

$\displaystyle\forall(x_{1},x_{2},x_{3})\in
K\mathrel{\mathop{\ordinarycolon}}\ \ x_{1}\leq 0\Rightarrow x_{2}\leq 0$

because $x_{1}\leq 0$ is equivalent to $x_{1}=0$, implying $x_{2}^{2}\leq 0$
thus $x_{2}=0$. However, $K$ does not satisfy the corresponding Approximate
Implication, more precisely the following is false:

$\displaystyle\exists\lambda>0,\forall(x_{1},x_{2},x_{3})\in
K\mathrel{\mathop{\ordinarycolon}}\ \ x_{2}\leq\lambda x_{1}$ (this is false)

Indeed, for every choice of $\lambda>0$, choose $0<x_{1}<1/\lambda$, and let
$x_{2}=1$, $x_{3}=1/x_{1}$. Then $(x_{1},x_{2},x_{3})\in K$, yet
$x_{2}>\lambda x_{1}$.

Instead, Theorem 16 states that, for every $\varepsilon>0$, there exists
$\lambda>0$, and an error term ${\mathbf{e}}=(e_{1},e_{2},e_{3})$, with
$e_{1},e_{2},e_{3}<\varepsilon$, such that:

$\displaystyle\forall{\mathbf{x}}\in K\mathrel{\mathop{\ordinarycolon}}$
$\displaystyle x_{2}\leq\lambda x_{1}+e_{1}x_{1}+e_{2}x_{2}+e_{3}x_{3}$

In our simple example, this statement is easily verified. Indeed, given
$\varepsilon>0$, define
$\lambda\stackrel{{\scriptstyle\text{def}}}{{=}}1/\varepsilon$ and
${\mathbf{e}}\stackrel{{\scriptstyle\text{def}}}{{=}}(0,0,\varepsilon/4)$.
Then $\lambda
x_{1}+(e_{1}x_{1}+e_{2}x_{2}+e_{3}x_{3})=\frac{1}{\varepsilon}x_{1}+\frac{\varepsilon}{4}x_{3}\geq
2\sqrt{\frac{1}{4}x_{1}x_{3}}=\sqrt{x_{1}x_{3}}\geq|x_{2}|\geq x_{2}$ proving
the AI 555The inequaltiy we are using is $(a+b)/2\geq\sqrt{ab}$.. This simple
example explains why the error term is necessary in Theorem 16.

Geometrically, the error term is necessary whenever the cone
$\mathbf{conhull}\left(K^{*}\cup L\right)$ used in the proof of Theorem 16 is
not closed. In our example $K^{*}=K$ because the positive, semidefinite cone
is self-dual [BV04], and
$L\stackrel{{\scriptstyle\text{def}}}{{=}}\mathord{\\{(-1,0,0)\\}}$, and will
check that $\mathbf{conhull}\left(K^{*}\cup
L\right)=\mathbf{conhull}\left(K\cup L\right)$ is not closed. For that,
consider the sequence
${\mathbf{y}}_{n}\stackrel{{\scriptstyle\text{def}}}{{=}}(0,1,1/n)$. On one
hand, we have $(n,1,1/n)\in K$, therefore
${\mathbf{y}}_{n}=(0,1,1/n)=(n,1,1/n)+n(-1,0,0)\in\mathbf{conhull}\left(K\cup
L\right)$. On the other hand,
$\lim_{n\rightarrow\infty}{\mathbf{y}}_{n}=(0,1,0)\not\in\mathbf{conhull}\left(K\cup
L\right)$. To see this, it suffices to notice that every vector in
$\mathbf{conhull}\left(K\cup L\right)$ has the form
$(x_{1}-\lambda,x_{2},x_{3})$ for some $(x_{1},x_{2},x_{3})\in K$ and
$\lambda\geq 0$, and, therefore, it satisfies the EI $x_{3}=0\Rightarrow
x_{2}=0$; our limit vector $(0,1,0)$ does not satisfy this EI, hence it is not
in $\mathbf{conhull}\left(K\cup L\right)$. This proves the fact that
$\mathbf{conhull}\left(K^{*}\cup L\right)$ is not closed, and hence taking its
closure in the proof of Theorem 16 is necessary, leading to the error term.

######  Theorem 13.

There exists $\Sigma,\tau$ with four variables, such that
$\mathbf{cl}\left(\Gamma_{4}^{*}\right)\models_{EI}(\Sigma\Rightarrow\tau)$
and
$\mathbf{cl}\left(\Gamma_{4}^{*}\right)\not\models_{AI}(\Sigma\Rightarrow\tau)$.

For the proof, we adapt an example by Kaced and Romashchenko [KR13, Inequality
$(\mathcal{I}5^{\prime})$ and Claim 5], built upon an earlier example by Matúš
[Mat07]. Let $\Sigma$ and $\tau$ be the following:

$\displaystyle\Sigma=$
$\displaystyle\mathord{\\{(C;D|A),(C;D|B),(A;B),(B;C|D)\\}}$
$\displaystyle\tau=$ $\displaystyle(C;D)$ (19)

We first prove that, for any $\lambda\geq 0$, there exists an entropic
function $h$ such that:

$\displaystyle I_{h}(C;D)>$
$\displaystyle\lambda\cdot(I_{h}(C;D|A)+I_{h}(C;D|B)+I_{h}(A;B)+I_{h}(B;C|D))$
(20)

Indeed, consider the distribution shown in Fig. 1 (c) (from [KR13]). By direct
calculation, $I_{h}(C;D)=\varepsilon+O(\varepsilon^{2})=\Omega(\varepsilon)$,
while $I_{h}(C;D|A)=I_{h}(C;D|B)=I_{h}(A;B)=0$ and
$I_{h}(B;C|D)=O(\varepsilon^{2})$ and we obtain Eq.(20) by choosing
$\varepsilon$ small enough. Next, we prove
$\mathbf{cl}\left(\Gamma_{n}^{*}\right)\models_{EI}(\Sigma\Rightarrow\tau)$.
Matúš [Mat07] proved the following666Matus [Mat07] proved $I(C;D)\leq
I(C;D|A)+I(C;D|B)+I(A;B)+I(C;E|B)+\frac{1}{k}I(B;E|C)+\frac{k-1}{2}(I(B;C|D)+I(C;D|B))$.
Inequality (21) follows by setting $E=D$.  $\forall h\in\Gamma^{*}_{n}$ and
$\forall k\in{\mathbb{N}}$:

$\displaystyle I_{h}(C;D)\leq$ $\displaystyle
I_{h}(C;D|A)+\frac{k{+}3}{2}I_{h}(C;D|B)+I_{h}(A;B)+\frac{k{-}1}{2}I_{h}(B;C|D)+\frac{1}{k}I_{h}(B;D|C)$
(21)

The inequality obviously holds for $\mathbf{cl}\left(\Gamma^{*}_{n}\right)$
too. The EI follows by taking $k\rightarrow\infty$. Inequality (21) is almost
a relaxation of the implication (19): the only extra term is the last term,
which can be made arbitrarily small by increasing $k$. Our second result
generalizes this:

######  Theorem 14.

Let $\Sigma,\tau$ be arbitrary CIs, and suppose
$\mathbf{cl}\left(\Gamma_{n}^{*}\right)\models\Sigma\Rightarrow\tau$. Then,
for every $\varepsilon>0$ there exists $\lambda>0$ such that, forall
$h\in\mathbf{cl}\left(\Gamma_{n}^{*}\right)$:

$\displaystyle h(\tau)\leq$ $\displaystyle\lambda\cdot
h(\Sigma)+\varepsilon\cdot h(\Omega)$ (22)

Intuitively, the theorem shows that every EI can be relaxed in
$\mathbf{cl}\left(\Gamma_{n}^{*}\right)$, if one allows for an error term,
which can be made arbitrarily small. We notice that the converse of the
theorem always holds: if $h(\Sigma)=0$, then (22) implies
$h(\tau)\leq\varepsilon\cdot h(\Omega)$, $\forall\varepsilon>0$, which implies
$h(\tau)=0$.

Proof of Theorem 14. For the proof we need the following on cones [Stu93,
BV04]. A cone $K$ is _finitely generated_ if
$K=\mathbf{conhull}\left(L\right)$ for some finite set $L\subset^{N}$, and is
_polyhedral_ if there exists $u_{1},\dots,u_{r}\in^{N}$ s.t.
$K=\\{{x}\mid{u_{i}{\cdot}x\geq 0,i\in[r]}\\}$; a cone is finitely generated
iff it is polyhedral. For any $K\subseteq^{N}$, the _dual_ is the set
$K^{*}\subseteq^{N}$ defined as:

$K^{*}\stackrel{{\scriptstyle\text{def}}}{{=}}\mathord{\\{y\mid\forall x\in
K,x{\cdot}y\geq 0\\}}$ (23)

$K^{*}$ represents the linear inequalities that hold for all $x\in K$, and is
always a closed, convex cone (it is the intersection of closed half-spaces).
We warn that the $*$ in $\Gamma^{*}_{n}$ does not represent the dual; the
notation $\Gamma^{*}_{n}$ for entropic functions is by now well established,
and we adopt it here too, despite it’s clash with the standard notation for
the dual cone. The following are known properties of cones (reviewed and
proved below):

  1. [(A)]

  2. 1.

For any set $K$,
$\mathbf{cl}\left(\mathbf{conhull}\left(K\right)\right)=K^{**}$.

  3. 2.

If $L$ is a finite set, then $\mathbf{conhull}\left(L\right)$ is closed.

  4. 3.

If $K_{1}$ and $K_{2}$ are closed, convex cones then: $(K_{1}\cap
K_{2})^{*}=\left(\mathbf{cl}\left(\mathbf{conhull}\left(K_{1}^{*}\cup
K_{2}^{*}\right)\right)\right)$.

######  Theorem 15.

Let $K,K_{1},K_{2}\subseteq^{n}$. The following holds.

  1. 1.

$K_{1}\subseteq K_{2}\Rightarrow K_{2}^{*}\subseteq K_{1}^{*}$

  2. 2.

If $K\neq\emptyset$ then
$\mathbf{cl}\left(\mathbf{conhull}\left(K\right)\right)=K^{**}$.

  3. 3.

If $K_{1}$ and $K_{2}$ are closed, convex cones then: $(K_{1}\cap
K_{2})^{*}=\left(\mathbf{cl}\left(\mathbf{conhull}\left(K_{1}^{*}\cup
K_{2}^{*}\right)\right)\right)$.

  4. 4.

A cone $K$ is finitely generated iff $K^{*}$ is finitely generated.

######  Proof 5.1.

Proof of (1). Let $x\in K_{2}^{*}$, and let $y\in K_{1}$. Since $x\cdot z\geq
0$ for every vector $z\in K_{2}$, and since $K_{2}\supseteq K_{1}$ then
$x\cdot y\geq 0$ as well. Therefore, $x\in K_{1}^{*}$.

##### Proof of (2)

This is shown in Fact 6 of [Stu93].

##### Proof of (3)

By definition of union we have that:
$K_{i}^{*}\subseteq\mathbf{cl}\left(\mathbf{conhull}\left(K_{1}^{*}\cup
K_{2}^{*}\right)\right)$ for $i\in\mathord{\\{1,2\\}}$. By item (1) we have
that
$K_{i}^{**}\supseteq\left(\mathbf{cl}\left(\mathbf{conhull}\left(K_{1}^{*}\cup
K_{2}^{*}\right)\right)\right)^{*}$ for $i\in\mathord{\\{1,2\\}}$. Since
$K_{1}$ and $K_{2}$ are closed convex cones then by item (2) it holds that
$K_{1}^{**}=K_{1}$ and $K_{2}^{**}=K_{2}$. Therefore, for
$i\in\mathord{\\{1,2\\}}$ we have that
$K_{i}\supseteq\left(\mathbf{cl}\left(\mathbf{conhull}\left(K_{1}^{*}\cup
K_{2}^{*}\right)\right)\right)^{*}$. From the above we get that $K_{1}\cap
K_{2}\supseteq\left(\mathbf{cl}\left(\mathbf{conhull}\left(K_{1}^{*}\cup
K_{2}^{*}\right)\right)\right)^{*}$. By property (1) we get that:
$(K_{1}\cap
K_{2})^{*}\subseteq\left(\mathbf{cl}\left(\mathbf{conhull}\left(K_{1}^{*}\cup
K_{2}^{*}\right)\right)\right)^{**}$. By property (2) we have that

$\left(\mathbf{cl}\left(\mathbf{conhull}\left(K_{1}^{*}\cup
K_{2}^{*}\right)\right)\right)^{**}=\mathbf{cl}\left(\mathbf{conhull}\left(K_{1}^{*}\cup
K_{2}^{*}\right)\right).$

Overall, we get that $(K_{1}\cap
K_{2})^{*}\subseteq\mathbf{cl}\left(\mathbf{conhull}\left(K_{1}^{*}\cup
K_{2}^{*}\right)\right)$.

##### Proof of (4)

Suppose $K$ is finitely generated,
$K=\mathbf{conhull}(\mathord{\\{x_{1},\ldots,x_{n}\\}})$. Then
$K^{*}=\\{{y}\mid{x_{1}\cdot y\geq 0,\ldots,x_{n}\cdot y\geq 0}\\}$, hence it
is polyhedral by definition.

Theorem 14 follows from a more general statement about cones:

######  Theorem 16.

Let $K\subseteq{\mathbb{R}}^{N}$ be a closed, convex cone, and let
$y_{1},\dots,y_{m},y$ be $m+1$ vectors in N. The following are equivalent:

  1. [(a)]

  2. 1.

For every $x\in K$, if $x\cdot y_{1}\leq 0,\dots,x\cdot y_{m}\leq 0$ then
$x\cdot y\leq 0$.

  3. 2.

For every $\varepsilon>0$ there exists $\theta_{1},\ldots,\theta_{m}\geq 0$
and an error vector $e\in^{N}$ such that $||e||_{\infty}<\varepsilon$ and, for
every $x\in K$, $x\cdot y\leq\theta_{1}x\cdot y_{1}+\cdots+\theta_{m}x\cdot
y_{m}+x\cdot e$.

######  Proof 5.2.

Let
$L\stackrel{{\scriptstyle\text{def}}}{{=}}\mathord{\\{-y_{1},-y_{2},\ldots,-y_{m}\\}}$.
Statement (a) is equivalent to ${-}y\in(K\cap L^{*})^{*}$. Consider statement
(b). It asserts $\forall\varepsilon>0,\exists||e||_{\infty}<\varepsilon$ such
that

$\displaystyle\exists\theta_{1}\geq 0,\ldots,\exists\theta_{k}\geq 0,$
$\displaystyle\underbrace{\forall x\in K,x\cdot y\leq
x\cdot(\sum\theta_{i}y_{i}+e)}_{-y+\sum\theta_{i}y_{i}+e\in K^{*}}$

In other words, $-y+e\in\mathbf{conhull}\left(K^{*}\cup L\right)$ and, since
this must hold for arbitrarily small $||e||_{\infty}$, statement (b) is
equivalent to ${-}y\in\mathbf{cl}\left(\mathbf{conhull}\left(K^{*}\cup
L\right)\right)$. We prove equivalence of (a) and (b):

$\displaystyle(K\cap L^{*})^{*}=$
$\displaystyle\mathbf{cl}\left(\mathbf{conhull}\left(K^{*}\cup
L^{**}\right)\right)$ Item (3) $\displaystyle=$
$\displaystyle\mathbf{cl}\left(\mathbf{conhull}\left(K^{*}\cup\mathbf{cl}\left(\mathbf{conhull}\left(L\right)\right)\right)\right)$
Item (1) $\displaystyle=$
$\displaystyle\mathbf{cl}\left(\mathbf{conhull}\left(K^{*}\cup\mathbf{conhull}\left(L\right)\right)\right)$
Item (2) $\displaystyle=$
$\displaystyle\mathbf{cl}\left(\mathbf{conhull}\left(K^{*}\cup
L\right)\right)$ Def. of $\mathbf{conhull}\left(-\right)$

We now prove Theorem 14, using the fact that
$K\stackrel{{\scriptstyle\text{def}}}{{=}}\mathbf{cl}\left(\Gamma_{n}^{*}\right)$
is a closed cone [Yeu08]. Let
$\Sigma=\mathord{\\{\sigma_{1},\ldots,\sigma_{m}\\}}$. Associate to each term
$\sigma_{i}=(B_{i};C_{i}|A_{i})$ the vector $y_{i}\in^{2^{n}}$ such that,
forall $h\in^{2^{n}}$, $h\cdot
y_{i}=I_{h}(B_{i};C_{i}|A_{i})=h(A_{i}B_{i})+h(A_{i}C_{i})-h(A_{i}B_{i}C_{i})-h(C_{i})$
(i.e. $y_{i}$ has two coordinates equal to $+1$, and two equal to $-1$), for
$i=1,m$. Denote by $y$ the similar vector associated to $\tau$. To prove
Theorem 14, let $\varepsilon>0$. By assumption,
$\mathbf{cl}\left(\Gamma_{n}^{*}\right)\models\Sigma\Rightarrow\tau$, thus
condition (a) of Th. 16 holds, and this implies condition (b), where we choose
$e$ such that $||e||_{\infty}<\varepsilon/2^{n}$. Then, condition (b) becomes:

$\displaystyle h(\tau)=h\cdot y\leq$ $\displaystyle\sum_{i}\theta_{i}h\cdot
y_{i}+h\cdot
e=\sum_{i}\theta_{i}h(\sigma_{i})+\sum_{W\subseteq[n]}|e_{W}|h(W)\leq\lambda
h(\Sigma)+\varepsilon h(\Omega)$

where $\lambda=\max_{i}\theta_{i}$. This completes the proof of Theorem 14.

##  6 Restricted Axioms

The characterization of the entropic cone
$\mathbf{cl}\left(\Gamma^{*}_{n}\right)$ is currently an open problem [Yeu08].
In other words, there is no known decision procedure capable of deciding
whether an exact or approximate implication holds for all entropic functions.
In this section, we consider implications that can be inferred using only the
Shannon inequalities (e.g., (2), and (3)), and thus hold for all polymatroids
$h\in\Gamma_{n}$. Several tools exists (e.g. ITIP or XITIP [Yeu97]) for
checking such inequalities.

This study is important for several reasons. First, by restricting to Shannon
inequalities we obtain a sound, but in general incomplete method for deciding
implications. All axioms for reasoning about MVD, FD, or semi-graphoid
axioms777Semi-graphoid axioms restricted to “strictly positive” distributions,
which fail $\Gamma^{*}_{n}$. [BFH77, PP86, GP93] are, in fact, based on
Shannon inequalities. Second, under some syntactic restrictions, they are also
complete; as we saw, they are complete for MVD and/or FDs, for saturated
constraints and/or conditionals, and also for marginal constraints [GP93].
Third, Shannon inequalities are complete for reasoning for a different class
of constraints, called _measure-based constraints_ , which were introduced by
Sayrafi et al. [SGG08] (where $\Gamma_{n}$ is denoted by
${\mathcal{M}}_{\texttt{SI}}$) and shown to have a variety of applications.

We start by showing that every exact implication of CIs can be relaxed over
$\Gamma_{n}$. This result was known, e.g. [KR13]; we re-state and prove it
here for completeness.

######  Theorem 17.

Let $\Sigma,\tau$ be arbitrary CIs. If
$\Gamma_{n}\models_{EI}\Sigma\Rightarrow\tau$, then there exist $\lambda\geq
0$, s.t. $\Gamma_{n}\models h(\tau)\leq\lambda\cdot h(\Sigma)$. In other
words, CIs admit relaxation over $\Gamma_{n}$.

######  Proof 6.1.

(Sketch) We set $K=\Gamma_{n}$ in Th. 16. Then $K$ is polyhedral, hence
$K^{*}$ is finitely generated. Therefore, in the proof of Th. 16, the set
$K^{*}\cup L$ is finitely generated, hence $\mathbf{conhull}\left(K^{*}\cup
L\right)$ is closed, therefore there is no need for an error vector $e$ in
Statement (b) of Th. 16, and, hence, no need for $\varepsilon$ in AI (22)

It follows that Shannon inequalities are incomplete for proving the
implication $\Sigma\Rightarrow\tau$, where $\Sigma,\tau$ are given by Eq.
(19). This is a “non-Shannon” exact implication, i.e. it holds only in
$\mathbf{cl}\left(\Gamma^{*}_{n}\right)$, but fails in $\Gamma_{n}$, otherwise
it would admit a relaxation. The explanation is that Matus’ inequality (21) is
a non-Shannon inequality. (The first example of a non-Shannon inequality is
due to Yeung and Zhang [ZY98].) Next, we turn our attention to the size of the
factor $\lambda$. We prove a lower bound of 3:

######  Theorem 18 ([DFZ09]).

The following inequality holds for all polymatroids $h\in\Gamma_{n}$:

$\displaystyle h(Z)\leq
I_{h}(A;B|C)+I_{h}(A;B|D)+I_{h}(C;D|E)+I_{h}(A;E)+3h(Z|A)+2h(Z|B)$ (24)

but the inequality fails if any of the coefficients $3,2$ are replaced by
smaller values. In particular, denoting $\tau,\Sigma$ the terms on the two
sides of Eq.(24), the exact implication
$\Gamma_{n}\models_{EI}\Sigma\Rightarrow\tau$ holds, and does not have a
1-relaxation.

We have checked the two claims in the theorem using the ITIP888http://user-
www.ie.cuhk.edu.hk/ ITIP/ tool. For the positive result, we also provide
direct (manual) proof in the full version of this paper [KS18]. Since some EIs
relax only with $\lambda\geq 3$, the next question is, how large does
$\lambda$ need to be? We prove this upper bound in [KS18]:

######  Theorem 19.

If $\Gamma_{n}\models\Sigma\Rightarrow\tau$ then
$\Gamma_{n}\models\tau\leq(2^{n})!\cdot h(\Sigma)$. In other words, every
implication of CIs admits a $(2^{n})!$-relaxation over $\Gamma_{n}$.

##  7 Restricted Models

In this section we restrict ourselves to models of uniform 2-tuple
distributions. Recall that their entropic functions are the step functions,
$\mathcal{S}_{n}$. Denoting their conic hull by
$\mathcal{P}_{n}\stackrel{{\scriptstyle\text{def}}}{{=}}\mathbf{conhull}\left(\mathcal{S}_{n}\right)$,
we prove here that all EI’s admit a 1-relaxation on $\mathcal{P}_{n}$. This
study has two motivations. First, it leads to a complete, but unsound
procedure for implication. A model checking system may verify an EI or AI by
checking it on all 2-tuple distributions. As we saw in Sec. 4 this procedure
is sound and complete for saturated or conditional CI’s, but it may be unsound
in general, for example the inequality $I_{h}(X;Y|Z)\leq I_{h}(X;Y)$ holds for
all step functions, but fails on the “parity function” in Fig. 1 (b). Second,
this model checking procedure is sound and complete in an important
application, namely for checking _differential constraints_ in market basket
analysis [SVG05]. Differential constraints are more general than the CIs we
discussed so far, yet we prove here that they, too, admit a 1-relaxation in
$\mathcal{P}_{n}$. Thus, our relaxation result has immediate application to
market basket constraints.

###  7.1 Exact implications in the cone $\mathcal{P}_{n}$ admit a 1-relaxation

We recall the signed measure $\mu^{*}$ (Theorem 2) defined over the field
$\mathcal{F}_{n}$ (Definition 2.2.2) whose atoms we denote by $\mathcal{A}$.
In particular, $\mu^{*}$ can be negative. If $\mu^{*}(a)\geq 0$ for all atoms
$a\in\mathcal{A}$ then it is called a _positive measure_. A polymatroid is
said to be positive if its I-measure is positive, and we denote by
$\Delta_{n}$ the cone of positive polymatroids.

Theorem 3 states that any I-measure assigning a non-negative value to its
atoms is a polymatroid. As a corollary, we get, in Lemma 4, a set-theoretic
characterization of exact implication in the polymatroid cone. This result,
combined with the assumption of a non-negative measure, gives us a
1-relaxation in the cone of positive polymatroids $\Delta_{n}$ (Theorem 20).
Then, in Theorem 21 we prove that the conic-hull of step functions
$\mathcal{P}_{n}=\mathbf{conhull}(\mathcal{S}_{n})$ coincides with the cone of
positive polymatroids $\Delta_{n}$ (i.e., $\mathcal{P}_{n}=\Delta_{n}$). In
particular, since $\mathcal{P}_{n}\subseteq\Delta_{n}$, we get a 1-relaxation
in $\mathcal{P}_{n}$.

######  Theorem 20.

Exact implication in the cone of positive polymatroids admits a 1-relaxation.

$\text{If }\Delta_{n}\models_{EI}\Sigma\Rightarrow\tau\text{ then
}\Delta_{n}\models_{AI}h(\Sigma)\geq h(\tau).$

######  Proof 7.1.

By Lemma 4 we have that $\mathrm{m}(\tau)\subseteq\mathrm{m}(\Sigma)$. This
means that
$\mathrm{m}(\tau)=\cup_{\sigma\in\Sigma}\left(\mathrm{m}(\tau)\cap\mathrm{m}(\sigma)\right)$.
By the assumption that the I-measure $\mu^{*}$ is nonnegative, we get that:

$\mu^{*}(\mathrm{m}(\tau))=\mu^{*}\left(\cup_{\sigma\in\Sigma}\left(\mathrm{m}(\tau)\cap\mathrm{m}(\sigma)\right)\right)\leq\sum_{\sigma\in\Sigma}\mu^{*}((\mathrm{m}(\tau)\cap\mathrm{m}(\sigma))$
(25)

By the set-additivity of $\mu^{*}$ we get that:

$h(\Sigma)\mathrel{\stackrel{{\scriptstyle\textsf{\tiny
def}}}{{=}}}\sum_{\sigma\in\Sigma}\mu^{*}(\mathrm{m}(\sigma))=\sum_{\sigma\in\Sigma}\mu^{*}(\mathrm{m}(\sigma)\cap\mathrm{m}(\tau))+\sum_{\sigma\in\Sigma}\mu^{*}(\mathrm{m}(\sigma)\cap\mathrm{m}^{c}(\tau))$
(26)

From (26), (25), and non-negativity of $\mu^{*}$ we get that:

$\displaystyle\mu^{*}(\mathrm{m}(\tau))$
$\displaystyle\leq\sum_{\sigma\in\Sigma}\mu^{*}(\mathrm{m}(\sigma))-\sum_{\sigma\in\Sigma}\mu^{*}(\mathrm{m}(\sigma)\cap\mathrm{m}^{c}(\tau))$
$\displaystyle\leq\sum_{\sigma\in\Sigma}\mu^{*}(\mathrm{m}(\sigma)).$

Since, by Theorem 2, $\mu^{*}$ is the unique signed measure consistent with
all Shannon information measures, the result follows.

#####  $\mathcal{P}_{n}$ coincides with the cone of step functions

We describe the structure of the I-measure of a step function, and prove that
the conic hull of step functions
$\mathcal{P}_{n}=\mathbf{conhull}\left(\mathcal{S}_{n}\right)$ and positive
polymatroids $\Delta_{n}\subseteq\Gamma_{n}$ coincide. That is,
$\Delta_{n}=\mathcal{P}_{n}$. We let $U\subseteq[n]$, and let $s_{U}$ denote
the step function at $U$. In the rest of this section we prove Theorem 21.

######  Theorem 21.

It holds that $\Delta_{n}=\mathcal{P}_{n}$.

######  Lemma 22.

Let $s_{U}$ be the step function at $U\subseteq[n]$, and $R=[n]\setminus U$.
The unique I-measure for any step function $s_{U}$ is:

$\mu^{*}(a)=\begin{cases}1&\text{if }a=\left(\cap_{X\in
R}\mathrm{m}(X)\right)\cap\left(\cap_{X\in U}\mathrm{m}^{c}(X)\right)\\\
0&\text{otherwise}\end{cases}$ (27)

######  Proof 7.2.

We define the atom $a^{*}$ by:

$a^{*}\mathrel{\stackrel{{\scriptstyle\textsf{\tiny
def}}}{{=}}}\left(\cap_{X\in R}\mathrm{m}(X)\right)\cap\left(\cap_{X\in
U}\mathrm{m}^{c}(X)\right)$

Let $S\subseteq U$. We show that $h(S)=\mu^{*}(\mathrm{m}(S))=0$. By
definition, $\mathrm{m}(S)=\cup_{Y\in S}\mathrm{m}(Y)$. Therefore, every atom
$a\in\mathrm{m}(S)$ has at least one set $\mathrm{m}(Y)$, where $Y\in S$, that
appears in positive form. In particular, $a^{*}\notin\mathrm{m}(S)$.
Therefore, by (27), we have that $h(S)=\mu^{*}(\mathrm{m}(S))=0$ as required.

Now, let $T{\not\subseteq}U$, and let $X{\in}T{\setminus}U$. Since
$\mathrm{m}(X)$ appears in positive form in $a^{*}$, and since
$\mathrm{m}(X){\subseteq}\mathrm{m}(T)$, then we have that $h(T){=}1$.
Therefore, $\mu^{*}$ as defined in (27) is the I-measure for $s_{U}$. By
Theorem 2, the I-measure $\mu^{*}$ is _unique_ , and is therefore the only
I-measure for $s_{U}$.

By Lemma 22, every step function has a nonnegative I-measure. As a
consequence, any conic combination of step functions has a positive I-measure,
proving that $\mathcal{P}_{n}\subseteq\Delta_{n}$.

Now, let $\mu^{*}$ denote any nonnegative I-measure. For every atom $a$, we
let $\mathbf{neg}(a)$ denote the set of variables whose sets appear in negated
form (e.g., if $a=\left(\cap_{X\in R}\mathrm{m}(X)\right)\cap\left(\cap_{X\in
U}\mathrm{m}^{c}(X)\right)$, then $\mathbf{neg}(a)=U$). Let $\mathcal{A}$
denote the atoms of $\mathcal{F}_{n}$. We define the mapping
$f\mathrel{\mathop{\ordinarycolon}}\mathcal{A}\mapsto\mathcal{P}_{n}$ as
follows.

$f(a)\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}{{=}}}\mu^{*}(a)\cdot
s_{\mathbf{neg}(a)}$

where $s_{\mathbf{neg}(a)}$ is the step function at $\mathbf{neg}(a)$. Since,
by Lemma 22, the I-measure of $s_{\mathbf{neg}(a)}$ is $1$ at atom $a$ and $0$
everywhere else we get that:

$\mu^{*}=\sum_{a\in\mathcal{A}}f(a)=\sum_{a\in\mathcal{A}}\mu^{*}(a)\cdot
s_{\mathbf{neg}(a)}$

proving that $\mu^{*}\in\mathcal{P}_{n}$, and that
$\Delta_{n}\subseteq\mathcal{P}_{n}$.

###  7.2 Exact Implication of Differential Constraints in Market Basket
Analysis admit a 1-Relaxation

Consider a set of items $\Omega=\mathord{\\{X_{1},\dots,X_{n}\\}}$, and a set
of baskets $\mathcal{B}=\mathord{\\{b_{1},\ldots,b_{N}\\}}$ where every basket
is a subset $b_{i}\subseteq\Omega$. The _support function_
$f\mathrel{\mathop{\ordinarycolon}}2^{\Omega}\rightarrow\mathbb{N}$ assigns to
every subset $W\subseteq\mathcal{B}$ the number of baskets in $\mathcal{B}$
that contain the set $W$: $f(W)=|\\{{i}\mid{i\in[N],W\subseteq
b_{i}\in\mathcal{B}}\\}|$. A constraint $f(W)=f(WX)$ asserts that every basket
that contains $W$ also contains $X$. Sayrafi and Van Gucht [SVG05] define the
_density_ of a function
$f\mathrel{\mathop{\ordinarycolon}}2^{\Omega}\rightarrow\mathbb{N}$ as
$d_{f}(W)\stackrel{{\scriptstyle\text{def}}}{{=}}\sum_{Z\mathrel{\mathop{\ordinarycolon}}W\subseteq
Z}(-1)^{|Z-W|}f(Z)$; we show below this equals the number of baskets
$b_{i}\in\mathcal{B}$ s.t. $W=b_{i}$. Then, they define a _differential
constraint_ to be a statement of the form $d_{f}(W)=0$, for some
$W\subseteq\Omega$, and study the implication problem of differential
constraints.

We now explain the connection to step functions $\mathcal{S}_{n}$; for the
purpose of this discussion we consider $h_{\Omega}$ to be a step function,
which is $h_{\Omega}\equiv 0$ (Sec 2.2). Fix $i\in[N]$ and consider the single
basket $b_{i}\in\mathcal{B}$. Define $f_{b_{i}}$ to be the support function
for the singleton set $\mathord{\\{b_{i}\\}}$, that is $f_{b_{i}}(W)=1$ if
$W\subseteq b_{i}$ and 0 otherwise. It follows that
$h_{b_{i}}(W)\stackrel{{\scriptstyle\text{def}}}{{=}}1-f_{b_{i}}(W)$ is
precisely the step function at $b_{i}$. The support function for
$\mathcal{B}=\mathord{\\{b_{1},\ldots,b_{N}\\}}$ is
$f=\sum_{i\in[N]}f_{b_{i}}=N-h$, where
$h\stackrel{{\scriptstyle\text{def}}}{{=}}\sum_{i\in[N]}h_{b_{i}}\in\mathcal{P}_{n}$.
Thus, any support function $f$ gives rise to a polymatroid
$h\stackrel{{\scriptstyle\text{def}}}{{=}}N-f\in\mathcal{P}_{n}$. By
linearity, their densities are related by $d_{f}=d_{N}-d_{h}$, where $d_{N}$
is the density of the constant function $N$:
$d_{N}(W)=N\cdot\sum_{Z\mathrel{\mathop{\ordinarycolon}}W\subseteq
Z\subseteq\Omega}(-1)^{|Z-W|}$, thus $d_{N}(\Omega)=N$ and $d_{N}(W)=0$ for
$W\subsetneq\Omega$; in particular, $d_{f}(W)=-d_{h}(W)$ for
$W\subsetneq\Omega$. Conversely, any
$h=\sum_{U\subsetneq\Omega}c_{U}h_{U}\in\mathcal{P}_{n}$, where $c_{U}\geq 0$,
and any $N\geq\sum_{U}c_{U}$ gives rise to a set of baskets $\mathcal{B}$ of
size $N$, where each set $U\subsetneq\Omega$ occurs exactly $c_{U}$ times and
$\Omega$ occurs exactly $N-\sum_{U}c_{U}$ times, such that the support
function of $\mathcal{B}$ is $f=|\mathcal{B}|-h$. Therefore, the implication
problem of differential constraints studied in [SVG05] is equivalent to the
implication problem for $\mathcal{P}_{n}$. Since, by Theorem 21 we have that
$\mathcal{P}_{n}\subseteq\Delta_{n}$, and since, by Theorem 20, every exact
implication in $\Delta_{n}$ admits a 1-relaxation, then the result follows.
Below we give an alternative proof that does not rely on the I-measure. We
start with a lemma:

######  Lemma 23.

Fix a function
$h\mathrel{\mathop{\ordinarycolon}}2^{\Omega}\rightarrow{\mathbb{R}}$ s.t.
$h(\emptyset)=0$. Then $h=\sum_{Z\subsetneq\Omega}(-d_{h}(Z))\cdot h_{Z}$. In
other words, the step functions $h_{Z}$ form a basis for the vector space
$\\{{h\in R^{2^{n}}}\mid{h(\emptyset)=0}\\}$.

######  Proof 7.3.

Recall that $h(\Omega|Z)=h(\Omega)-h(Z)$. Define $\delta_{h}(W)$ to be the
Möbius inverse of $h(\Omega|W)$, in other words:

$\displaystyle\forall W\mathrel{\mathop{\ordinarycolon}}\delta_{h}(W)=$
$\displaystyle\sum_{Z\mathrel{\mathop{\ordinarycolon}}W\subseteq
Z}(-1)^{|Z-W|}h(\Omega|Z)$ $\displaystyle\forall
W\mathrel{\mathop{\ordinarycolon}}h(\Omega|W)=$
$\displaystyle\sum_{Z\mathrel{\mathop{\ordinarycolon}}W\subseteq
Z}\delta_{h}(Z)$ (28)

We claim that, for $W\subsetneq\Omega$, $\delta_{h}(W)=-d_{h}(W)$. Indeed,
$\delta_{h}(W)=\sum_{Z\mathrel{\mathop{\ordinarycolon}}W\subseteq
Z}(-1)^{|Z-W|}h(\Omega|Z)=h(\Omega)\sum_{Z\mathrel{\mathop{\ordinarycolon}}W\subseteq
Z\subseteq\Omega}(-1)^{|Z-W|}-d_{h}(W)$ and the claim follows from
$\sum_{Z\mathrel{\mathop{\ordinarycolon}}W\subseteq
Z\subseteq\Omega}(-1)^{|Z-W|}=0$ when $W\subsetneq\Omega$. We prove that
$h=\sum_{Z\subsetneq\Omega}\delta_{h}(Z)\cdot h_{Z}$, by using the right part
of Eq.(28):

$\displaystyle h(W)=$ $\displaystyle
h(\Omega|\emptyset)-h(\Omega|W)=\sum_{Z}\delta_{h}(Z)-\sum_{Z\mathrel{\mathop{\ordinarycolon}}W\subseteq
Z}\delta_{h}(Z)=\sum_{Z\mathrel{\mathop{\ordinarycolon}}W\not\subseteq
Z}\delta_{h}(W)=\sum_{Z}\delta_{h}(Z)\cdot h_{Z}(W)$

because $h_{Z}(W)=1$ iff $W\not\subseteq Z$, and $h(W)=0$ otherwise. This
proves that the $2^{n}-1$ step functions span the vector space $\\{{h\in
R^{2^{n}}}\mid{h(\emptyset)=0}\\}$; since the latter has dimension $2^{n}-1$,
it follows that the step functions form a basis.

Fix a step function, $h=h_{W}$. By the Lemma, $h_{W}$ admits a unique
decomposition $h_{W}=\sum_{Z\subsetneq\Omega}(-d_{h_{W}}(Z))h_{Z}$; it follows
that $d_{h_{W}}(Z)=-1$ when $Z=W$ and $d_{h_{W}}(Z)=0$ otherwise. In
particular, $d_{h}\leq 0$ forall $h\in\mathcal{P}_{n}$. Fix a set of baskets
$\mathcal{B}=\mathord{\\{b_{1},\ldots,b_{N}\\}}$, and let $f$ be its support
function. We prove that $d_{f}(Z)$ is equal to the number of baskets $b_{i}$
s.t. $Z=b_{i}$; in particular $d_{f}\geq 0$. Indeed, for $Z=\Omega$ this
follows from the definition of the differential $d_{f}$, while for
$Z\subsetneq\Omega$ we use the fact that $f=N-\sum_{i}h_{b_{i}}$ and
$d_{f}(Z)=-\sum_{i}d_{h_{b_{i}}}(Z)$.

The quantity
$I_{h}(y_{1};y_{2};\cdots;y_{m}|W)\stackrel{{\scriptstyle\text{def}}}{{=}}-\sum_{Z\mathrel{\mathop{\ordinarycolon}}W\subseteq
Z\subseteq\mathord{\\{y_{1},\ldots,y_{m}\\}}}(-1)^{|Z-W|}h(Z)$ is called the
_conditional multivariate mutual information_ , thus, $-d_{h}(W)$ is a
saturated conditional multivariate mutual information. We show in the full
paper [KS18] that $-d_{h}(W)$ is precisely the I-measure of an atom in
I-measure theory [Yeu08].

Once we have motivated the critical role of the negated densities $-d_{h}(W)$,
we define an I-measure constraint to be an arbitrary sum
$\sigma=-\sum_{i}d_{h}(W_{i})$; the exact constraint is the assertion
$\sigma=0$, while an approximate constraint asserts some bound, $\sigma\leq
c$. The differential constraints [SVG05] are special cases of I-measure
constraints. Any CI constraint is also a special case of an I-measure, for
example $h(Y|X)=-\sum_{W\mathrel{\mathop{\ordinarycolon}}X\subseteq
W,Y\not\subseteq W}d_{h}(W)$, and
$I_{h}(Y;Z|X)=-\sum_{W\mathrel{\mathop{\ordinarycolon}}X\subseteq
W,X\not\subseteq W,Y\not\subseteq W}d_{h}(W)$. Since $d_{h}\leq 0$ for
$h\in\mathcal{P}_{n}$, it follows that all I-measure constraints are $\geq 0$.
We prove:

######  Theorem 24.

Exact implications of I-measure constraints admit a 1-relaxation in
$\mathcal{P}_{n}$.

######  Proof 7.4.

Consider an implication $\Sigma\Rightarrow\tau$ where all constraints in
$\Sigma,\tau$ are I-measure constraints. Let $\tau=-\sum_{i}d_{h}(W_{i})$.
Then, for every $i$, there exists some constraint
$\sigma=-\sum_{j}d_{h}(W_{j})\in\Sigma$ such that $W_{i}=W_{j}$ for some $j$,
proving the theorem. If not, then for the step function
$h\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}{{=}}}h_{W_{i}}$ we have
$h(\sigma)=0$ forall $\sigma\in\Sigma$, yet $h(\tau)=1$, contradicting the
assumption $P_{n}\models\Sigma\Rightarrow\sigma$.

Consider Example 4.3 in [SVG05]: $d_{1}=f(A)+f(ABCD)-f(ABC)-f(ACD)$,
$d_{2}=f(C)-f(CD)$, and $d=f(AB)-f(ABD)$. Sayrafi and Van Gucht prove
$d_{1}=d_{2}=0$ implies $d=0$ for all support functions $f$. The quantity
$d_{1}$ represents the number of baskets that contain $A$, but do not contain
$BC$ nor $CD$, while $d_{2}$ is the number of baskets that contain $C$ but not
$D$. Our theorem converts the exact implication into an inequality as follows.
Denote by
$\sigma_{1}\stackrel{{\scriptstyle\text{def}}}{{=}}I_{h}(BC;CD|A),\sigma_{2}\stackrel{{\scriptstyle\text{def}}}{{=}}h(D|C),\tau\stackrel{{\scriptstyle\text{def}}}{{=}}h(D|AB)$,
$P_{n}\models(\sigma_{1}=\sigma_{2}=0\Rightarrow\tau=0)$ relaxes to
$P_{n}\models\sigma_{1}+\sigma_{2}\geq\tau$, which translates into
$d_{1}+d_{2}\leq d$ forall support functions $f$.

##  8 Discussion and Future Work

Number of Repairs A natural way to measure the degree of a constraint in a
relation instance $R$ is by the number of repairs needed to enforce the
constraint on $R$. In the case of a key constraint, $X\rightarrow Y$, where
$XY=\Omega$, our information-theoretic measure is naturally related to the
number of repairs, as follows. If $h(Y|X)=c$, where $h$ is the entropy of the
empirical distribution on $R$, then one can check $|R|/|\Pi_{X}(R)|\leq
2^{c}$. Thus, the number of repairs $|R|-|\Pi_{X}(R)|$ is at most
$(2^{c}-1)|\Pi_{X}(R)|$. We leave for future work an exploration of the
connections between number of repairs and information theoretic measures.

Small Model Property. We have proven in Sec. 4 that several classes of
implications (including saturated CIs, FDs, and MVDs) have a “small model”
property: if the implication holds for all uniform, 2-tuple distributions,
then it holds in general. In other words, it suffices to check the implication
on the step functions $\mathcal{S}_{n}$. One question is whether this small
model property continues to hold for other tractable classes of implications
in the literature. For example, Geiger and Pearl [GP93] give an axiomatization
(and, hence, a decision procedure) for _marginal_ CIs. However, marginal CIs
do not have the same small model property. Indeed, the implication $(X\perp
Y)\&(X\perp Z)\Rightarrow(X\perp YZ)$ holds for all uniform 2-tuple
distributions (because $I_{h}(X;YZ)\leq I_{h}(X;Y)+I_{h}(X;Z)$ holds for all
step functions), however it fails for the “parity distribution” in Fig.1(b).
We leave for future work an investigation of the small model property for
other classes of constraints.

Bounds on the factor $\lambda$. In the early stages of this work we
conjectured that all CIs in $\Gamma_{n}$ admit 1-relaxation, until we
discovered the counterexample in Th. 18, where $\lambda=3$. On the other hand,
the only general upper bound is $(2^{n})!$. None of them is likely to be
tight. We leave for future work the task of finding tighter bounds for
$\lambda$.

## References

  * [AD80] William Ward Armstrong and Claude Delobel.  Decomposition and functional dependencies in relations.  ACM Trans. Database Syst., 5(4):404–430, 1980.
  * [BBF+16] Tobias Bleifuß, Susanne Bülow, Johannes Frohnhofen, Julian Risch, Georg Wiese, Sebastian Kruse, Thorsten Papenbrock, and Felix Naumann.  Approximate discovery of functional dependencies for large datasets.  In Proceedings of the 25th ACM International Conference on Information and Knowledge Management, CIKM 2016, Indianapolis, IN, USA, October 24-28, 2016, pages 1803–1812, 2016.
  * [BFH77] Catriel Beeri, Ronald Fagin, and John H. Howard.  A complete axiomatization for functional and multivalued dependencies in database relations.  In Proceedings of the 1977 ACM SIGMOD International Conference on Management of Data, Toronto, Canada, August 3-5, 1977., pages 47–61, 1977.
  * [BV04] Stephen Boyd and Lieven Vandenberghe.  Convex Optimization.  Cambridge University Press, 2004.
  * [Cha11] Terence Chan.  Recent progresses in characterising information inequalities.  Entropy, 13(2):379–401, 2011.
  * [CIPY14] Xu Chu, Ihab F. Ilyas, Paolo Papotti, and Yin Ye.  Ruleminer: Data quality rules discovery.  In IEEE 30th International Conference on Data Engineering, Chicago, ICDE 2014, IL, USA, March 31 - April 4, 2014, pages 1222–1225, 2014\.
  * [CP01] Toon Calders and Jan Paredaens.  Axiomatization of frequent sets.  In Jan Van den Bussche and Victor Vianu, editors, Database Theory — ICDT 2001, pages 204–218, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg.
  * [DFZ09] Randall Dougherty, Christopher F. Freiling, and Kenneth Zeger.  Linear rank inequalities on five or more variables.  CoRR, abs/0910.0284, 2009.
  * [DR00] Mehmet M. Dalkilic and Edward L. Roberston.  Information dependencies.  In Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS ’00, pages 245–253, New York, NY, USA, 2000. ACM.
  * [Fag82] Ronald Fagin.  Horn clauses and database dependencies.  J. ACM, 29(4):952–985, 1982.
  * [FD16] Abram Friesen and Pedro Domingos.  The sum-product theorem: A foundation for learning tractable models.  In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 1909–1918, New York, New York, USA, 20–22 Jun 2016. PMLR.
  * [GNG14] Marc Gyssens, Mathias Niepert, and Dirk Van Gucht.  On the completeness of the semigraphoid axioms for deriving arbitrary from saturated conditional independence statements.  Inf. Process. Lett., 114(11):628–633, 2014.
  * [GP93] Dan Geiger and Judea Pearl.  Logical and algorithmic properties of conditional independence and graphical models.  The Annals of Statistics, 21(4):2001–2021, 1993.
  * [GR04] Chris Giannella and Edward L. Robertson.  On approximation measures for functional dependencies.  Inf. Syst., 29(6):483–507, 2004.
  * [Her06] Christian Herrmann.  Corrigendum to ”on the undecidability of implications between embedded multivalued database dependencies” [inform. and comput. 122(1995) 221-235].  Inf. Comput., 204(12):1847–1851, 2006.
  * [IC15] Ihab F. Ilyas and Xu Chu.  Trends in cleaning relational data: Consistency and deduplication.  Foundations and Trends in Databases, 5(4):281–393, 2015.
  * [KLV13] Juha Kontinen, Sebastian Link, and Jouko Väänänen.  Independence in database relations.  In Leonid Libkin, Ulrich Kohlenbach, and Ruy de Queiroz, editors, Logic, Language, Information, and Computation, pages 179–193, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
  * [KN18] Sebastian Kruse and Felix Naumann.  Efficient discovery of approximate dependencies.  PVLDB, 11(7):759–772, 2018.
  * [KR13] Tarik Kaced and Andrei E. Romashchenko.  Conditional information inequalities for entropic and almost entropic points.  IEEE Trans. Information Theory, 59(11):7149–7167, 2013.
  * [KS18] Batya Kenig and Dan Suciu.  Integrity constraints revisited: From exact to approximate implication.  CoRR, abs/1812.09987, 2018.
  * [KS20] Batya Kenig and Dan Suciu.  Integrity constraints revisited: From exact to approximate implication.  In Carsten Lutz and Jean Christoph Jung, editors, 23rd International Conference on Database Theory, ICDT 2020, March 30-April 2, 2020, Copenhagen, Denmark, volume 155 of LIPIcs, pages 18:1–18:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [Lee87] Tony T. Lee.  An information-theoretic analysis of relational databases - part I: data dependencies and information metric.  IEEE Trans. Software Eng., 13(10):1049–1061, 1987.
  * [Li05] Chen Li, editor.  Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 13-15, 2005, Baltimore, Maryland, USA. ACM, 2005.
  * [Mai83] David Maier.  Theory of Relational Databases.  Computer Science Pr, 1983.
  * [Mal86] Francesco M. Malvestuto.  Statistical treatment of the information content of a database.  Inf. Syst., 11(3):211–223, 1986.
  * [Mat07] F. Matúš.  Infinitely many information inequalities.  In 2007 IEEE International Symposium on Information Theory, pages 41–44, June 2007.
  * [MVM+18] Alejandro Molina, Antonio Vergari, Nicola Di Mauro, Sriraam Natarajan, Floriana Esposito, and Kristian Kersting.  Mixed sum-product networks: A deep architecture for hybrid domains.  In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 3828–3835, 2018.
  * [PD11] Hoifung Poon and Pedro M. Domingos.  Sum-product networks: A new deep architecture.  In UAI 2011, Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence, Barcelona, Spain, July 14-17, 2011, pages 337–346, 2011.
  * [PE08] Jean-Philippe Pellet and André Elisseeff.  Using markov blankets for causal structure learning.  Journal of Machine Learning Research, 9:1295–1342, 2008.
  * [PP86] Judea Pearl and Azaria Paz.  Graphoids: Graph-based logic for reasoning about relevance relations or when would x tell you more about y if you already know z?  In ECAI, pages 357–363, 1986.
  * [SBHR06] Yannis Sismanis, Paul Brown, Peter J. Haas, and Berthold Reinwald.  GORDIAN: efficient and scalable discovery of composite keys.  In Proceedings of the 32nd International Conference on Very Large Data Bases, Seoul, Korea, September 12-15, 2006, pages 691–702, 2006.
  * [SDPF81] Yehoshua Sagiv, Claude Delobel, D. Scott Parker, Jr., and Ronald Fagin.  An equivalence between relational database dependencies and a fragment of propositional logic.  J. ACM, 28(3):435–453, July 1981.
  * [SGG08] Bassem Sayrafi, Dirk Van Gucht, and Marc Gyssens.  The implication problem for measure-based constraints.  Inf. Syst., 33(2):221–239, 2008.
  * [SGS00] Peter Spirtes, Clark N Glymour, and Richard Scheines.  Causation, prediction, and search.  MIT press, 2000.
  * [SGS18] Babak Salimi, Johannes Gehrke, and Dan Suciu.  Bias in OLAP queries: Detection, explanation, and removal.  In Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018, pages 1021–1035, 2018.
  * [Stu90] Milan Studený.  Conditional independence relations have no finite complete characterization.  In 11th Prague Conf. Information Theory, Statistical Decision Foundation and Random Processes, pages 377–396. Norwell, MA, 1990.
  * [Stu93] Milan Studený.  Convex cones in finite-dimensional real vector spaces.  Kybernetika, 29(2):180–200, 1993.
  * [SVG05] Bassem Sayrafi and Dirk Van Gucht.  Differential constraints.  In Proceedings of the Twenty-fourth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS ’05, pages 348–357, New York, NY, USA, 2005. ACM.
  * [WBW00] S. K. Michael Wong, Cory J. Butz, and Dan Wu.  On the implication problem for probabilistic conditional independency.  IEEE Trans. Systems, Man, and Cybernetics, Part A, 30(6):785–805, 2000.
  * [Yeu91] Raymond W. Yeung.  A new outlook of shannon’s information measures.  IEEE Trans. Information Theory, 37(3):466–474, 1991.
  * [Yeu97] Raymond W. Yeung.  A framework for linear information inequalities.  IEEE Trans. Information Theory, 43(6):1924–1934, 1997.
  * [Yeu08] Raymond W. Yeung.  Information Theory and Network Coding.  Springer Publishing Company, Incorporated, 1 edition, 2008.
  * [ZY97] Zhen Zhang and Raymond W. Yeung.  A non-shannon-type conditional inequality of information quantities.  IEEE Trans. Information Theory, 43(6):1982–1986, 1997.
  * [ZY98] Zhen Zhang and Raymond W. Yeung.  On characterization of entropy function via information inequalities.  IEEE Trans. Information Theory, 44(4):1440–1452, 1998.