---
abstract: 'We present a complete finite axiomatization of the unrestricted implication problem for inclusion and conditional independence atoms in the context of dependence logic. For databases, our result implies a finite axiomatization of the unrestricted implication problem for inclusion, functional, and embedded multivalued dependencies in the unirelational case.'
author:
- 'Miika Hannula [^1]'
- 'Juha Kontinen[^2]'
bibliography:
- 'biblio.bib'
title: 'A finite axiomatization of conditional independence and inclusion dependencies[^3]'
---

Introduction
============

We formulate a finite axiomatization of the implication problem for inclusion and conditional independence atoms (dependencies) in the dependence logic context. The input of this problem is given by a finite set $\Sigma\cup \{\phi\}$ consisting of conditional independence atoms and inclusion atoms, and the question to decide is whether the following logical consequence holds $$\label{AX}
\Sigma \models \phi.$$ Independence logic [@gradel10] and inclusion logic [@galliani12] are recent variants of dependence logic the semantics of which are defined over sets of assigments (teams) rather than a single assignment as in first-order logic. By viewing a team $X$ with domain $\{x_1,\ldots,x_k\}$ as a relation schema $X[\{x_1,\ldots,x_k\}]$, our results provide a finite axiomatization for the unrestricted implication problem of inclusion, functional, and embedded multivalued database dependencies over $X[\{x_1,\ldots,x_k\}]$.

Dependence logic [@vaananen07] extends first-order logic by dependence atomic formulas $$\label{da}\dep(x_1,\ldots,x_n)$$ the meaning of which is that the value of $x_n$ is functionally determined by the values of $x_1,\ldots, x_{n-1}$. Independence logic replaces the dependence atoms by independence atoms $$\vec{y}\bot_{\vec{x}} \vec{z},$$ the intuitive meaning of which is that, with respect to any fixed value of $ \vec x$, the variables $\vec y$ are totally independent of the variables $\vec z$. Furthermore, inclusion logic is based on inclusion atoms of the form $$\vec{x}\subseteq \vec{y},$$ with the meaning that all the values of $\vec{x}$ appear also as values for $\vec{y}$. By viewing a team $X$ of assignments with domain $\{x_1,\ldots,x_k\}$ as a relation schema $X[\{x_1,\ldots,x_k\}]$, the atoms $\dep(\vec{x})$, $\vec{x}\subseteq \vec{y}$, and $\vec{y}\bot_{\vec{x}} \vec{z}$ correspond to functional, inclusion, and embedded multivalued database dependencies. Furthermore, the atom $\dep(x_1,\ldots,x_n)$ can be alternatively expressed as $$x_n\bot_{x_1\ldots x_{n-1}} x_n,$$ hence our results for independence atoms cover also the case where dependence atoms are present.

The team semantics of dependence logic is a very flexible logical framework in which various notions of dependence and independence can be formalized. Dependence logic and its variants have turned out to be applicable in various areas. For example, Väänänen and Abramsky have recently axiomatized and formally proved Arrow’s Theorem from social choice theory and, certain No-Go theorems from the foundations of quantum mechanics in the context of independence logic [@AV]. Also, the pure independence atom $\vec{y}\bot \vec{z}$ and its axioms has various concrete interpretations such as independence $X\ci Y$ between two sets of random variables [@geiger91], and independence in vector spaces and algebraically closed fields [@GP].

Dependence logic is equi-expressive with existential second-order logic (ESO). Furthermore, the set of valid formulas of dependence logic has the same complexity as that of full second-order logic, hence it is not possible to give a complete axiomatization of dependence logic [@vaananen07]. However, by restricting attention to syntactic fragments [@FYJV; @hannula13; @kontinenv11] or by modifying the semantics [@btxdoc] complete axiomatizations have recently been obtained. The axiomatization presented in this article is based on the classical characterization of logical implication between dependencies in terms of the *Chase* procedure [@Maier:1979:TID:320107.320115]. The novelty in our approach is the use of the so-called *Lax* team semantics of independence logic to simulate the chase on the logical level using only inclusion and independence atoms and existential quantification.

In database theory, the implication problems of various types of database dependencies have been extensively studied starting from Armstrong’s axiomatization for functional dependencies [@armstrong74]. Inclusion dependencies were axiomatized in [@casanova83], and an axiomatization for pure independence atoms is also known (see [@DBLP:journals/jcss/Paredaens80; @geiger91; @DBLP:conf/wollic/KontinenLV13]). On the other hand, the implication problem of embedded multivalued dependencies, and of inclusion dependencies and functional dependencies together, are known to be undecidable [@Herrmann1995221; @Herrmann2006; @chandra85], hence simple axiomatization (that would yield a decision procedure) is deemed impossible. On the other hand, the unrestricted implication problem of inclusion and functional dependencies has been finitely axiomatized in [@mitchell83] using a so-called *Attribute Introduction Rule* that allows new attribute names representing derived attributes to be introduced into deductions. These new attributes can be thought of as implicitly existentially quantified. Our *Inclusion Introduction Rule* is essentially equivalent to the Attribute Introduction Rule of [@mitchell83]. It is also worth noting that the chase procedure has been used to axiomatize the unrestricted implication problem of various classes of dependencies, e.g., *Template Dependencies* [@DBLP:journals/jacm/SadriU82], and *Typed Dependencies* [@DBLP:journals/siamcomp/BeeriV84]. Finally we note that the role of inclusion atom in our axiomatization has some similarities to the axiomatization of the class of *Algebraic Dependencies* [@DBLP:journals/jcss/YannakakisP82].

Preliminaries
=============

In this section we define team semantics and introduce dependence, independence and inclusion atoms. The version of team semantics presented here is the Lax one, originally introduced in [@galliani12], which will turn out to be valuable for our purposes due to its interpretation of existential quantification.

Team semantics
--------------

The semantics is formulated using sets of assignments called teams instead of single assignments. Let ${\mathcal{M}}$ be a model with domain $M$. An *assignment* $s$ of ${\mathcal{M}}$ is a finite mapping from a set of variables into $M$. A *team* $X$ over ${\mathcal{M}}$ with domain ${\textrm{Dom}}(X) = V$ is a set of assignments from $V$ to $M$. For a subset $W$ of $V$, we write $X \upharpoonright W$ for the team obtained by restricting all the assignments of $X$ to the variables in $W$.

If $s$ is an assignment, $x$ a variable, and $a \in A$, then $s[a/x]$ denotes the assignment (with domain ${\textrm{Dom}}(s) \cup \{x\}$) that agrees with $s$ everywhere except that it maps $x$ to $a$. For an assignment $s$, and a tuple of variables $\vec{x} = (x_1,...,x_n)$, we sometimes denote the tuple $(s(x_1), . . . , s(x_n))$ by $s(\vec{x})$. For a formula $\phi$, ${\textrm{Var}}(\phi)$ and ${\textrm{Fr}}(\phi)$ denote the sets of variables that appear in $\phi$ and appear free in $\phi$, respectively. For a finite set of formulas ${\Sigma}= \{\phi_1, \ldots ,\phi_n\}$, we write ${\textrm{Var}}({\Sigma})$ for ${\textrm{Var}}(\phi_1) \cup \ldots \cup {\textrm{Var}}(\phi_n)$, and define ${\textrm{Fr}}({\Sigma})$ analogously. When using set operations $\vec{x} \cup \vec{y}$ and $\vec{x}\setminus \vec{y} $ for sequences of variables $\vec{x}$ and $\vec{y}$, then these sequences are interpreted as the sets of elements of these sequences.

Team semantics is defined for first-order logic formulas as follows:

\[team\] Let ${\mathcal{M}}$ be a model and let $X$ be any team over it. Then

-   If $\phi$ is a first-order atomic or negated atomic formula, then ${\mathcal{M}}\models_X \phi$ if and only if for all $s \in X$, ${\mathcal{M}}\models_s \phi$ (in Tarski semantics).

-   ${\mathcal{M}}\models_X \psi \vee \theta$ if and only if there are $Y$ and $Z$ such that $X = Y \cup Z$ and ${\mathcal{M}}\models_Y \psi$ and ${\mathcal{M}}\models_Z \theta$.

-   ${\mathcal{M}}\models_X \psi \wedge \theta$ if and only if ${\mathcal{M}}\models_X \psi$ and ${\mathcal{M}}\models_X \theta$.

-   ${\mathcal{M}}\models_X \exists v \psi$ if and only if there is a function $F : X \rightarrow \mathcal P(M) \backslash \{\emptyset\}$ such that ${\mathcal{M}}\models_{X[F/v]} \psi$, where $X[F/v] = \{s[m/v] : s \in X, m \in F(s)\}$.

-   ${\mathcal{M}}\models_X \forall v \psi$ if and only if ${\mathcal{M}}\models_{X[M/v]} \psi$, where $X[M/v] = \{s[m/v] : s \in X, m \in M\}$.

The following lemma is an immediate consequence of Definition \[team\].

\[ketjulemma\] Let ${\mathcal{M}}$ be a model, $X$ a team and ${\exists}x_1 \ldots {\exists}x_n \phi$ a formula in team semantics setting where $x_1, \ldots ,x_n$ is a sequence of variables. Then $${\mathcal{M}}\models_X {\exists}x_1 \ldots {\exists}x_n \phi\textrm{ iff for some function }F:X\rightarrow {\mathcal{P}}(M^n)\setminus\{\emptyset\}\textrm{, }{\mathcal{M}}\models_{X[F/x_1\ldots x_n]} \phi$$ where $X[F/x_1\ldots x_n]:= \{s[a_1/x_1]\ldots[a_n/x_n] \mid (a_1, \ldots ,a_n) \in F(s)\}$.

If ${\mathcal{M}}\models_X \phi$, then we say that $X$ *satisfies* $\phi$ in ${\mathcal{M}}$. If $\phi$ is a sentence (i.e. a formula with no free variables), then we say that $\phi$ is *true* in ${\mathcal{M}}$, and write ${\mathcal{M}}\models \phi$, if ${\mathcal{M}}\models_{\{\emptyset\}} \phi$ where $\{\emptyset\}$ is the team consisting of the empty assignment. Note that $\{\emptyset\}$ is different from the *empty team* $\emptyset$ containing no assignments.

In the team semantics setting, formula $\psi$ is a *logical consequence* of $\phi$, written $\phi\Rightarrow \psi$, if for all models ${\mathcal{M}}$ and teams $X$, with ${\textrm{Fr}}(\phi)\cup {\textrm{Fr}}(\psi)\subseteq {\textrm{Dom}}(X)$, $${\mathcal{M}}\models_X\phi \Rightarrow   {\mathcal{M}}\models_X\psi.$$ Formulas $\phi$ and $\psi$ are said to be *logically equivalent* if $\phi \Rightarrow \psi$ and $\psi \Rightarrow \phi$. Logics $\mathcal{L}$ and $\mathcal{L}'$ are said to be equivalent, $\mathcal{L}=\mathcal{L}'$, if every $\mathcal{L}$-sentence $\phi$ is equivalent to some $\mathcal{L}'$-sentence $\psi$, and vice versa.

Dependencies in team semantics
------------------------------

Dependence, independence and inclusion atoms are given the following semantics.

Let ${\vec{x}}$ be a tuple of variables and $y$ a variable. Then $\dep({\vec{x}} ,y)$ is a *dependence atom* with the semantic rule

-   ${\mathcal{M}}\models_X \dep({\vec{x}} ,y)$ if and only if for any $s, s' \in X$ with $s(\vec{x})=s'(\vec{x})$, $s(y)=s'(y)$.

Let ${\vec{x}}$, ${\vec{y}}$ and ${\vec{z}}$ be tuples of variables. Then ${{\vec{y}} ~\bot_{{\vec{x}}}~ {\vec{z}}}$ is a *conditional independence atom* with the semantic rule

-   ${\mathcal{M}}\models_X {{\vec{y}} ~\bot_{{\vec{x}}}~ {\vec{z}}}$ if and only if for any $s, s' \in X$ with $s(\vec{x})=s'(\vec{x})$ there is a $s'' \in X$ such that $s''(\vec{x})=s(\vec{x})$, $s''(\vec{y})=s(\vec{y})$ and $s''(\vec{z})=s'(\vec{z})$.

Furthermore, we will write ${{\vec{x}} ~\bot~ {\vec{y}}}$ as a shorthand for ${{\vec{x}} ~\bot_{\emptyset}~ {\vec{y}}}$, and call it a *pure independence atom*.

Let ${\vec{x}}$ and ${\vec{y}}$ be two tuples of variables of the same length. Then ${\vec{x}} \subseteq {\vec{y}}$ is an *inclusion atom* with the semantic rule

-   ${\mathcal{M}}\models_X {\vec{x}} \subseteq {\vec{y}}$ if and only if for any $s \in X$ there is a $s'\in X$ such that $s(\vec{x})=s'(\vec{y})$.

Note that in the definition of an inclusion atom ${\vec{x}} \subseteq {\vec{y}}$, the tuples ${\vec{x}}$ and ${\vec{y}}$ may both have repetitions. Also in the definition of a conditional independence atom ${{\vec{y}} ~\bot_{{\vec{x}}}~ {\vec{z}}}$, the tuples ${\vec{x}}$, ${\vec{y}}$ and ${\vec{z}}$ are not necessarily pairwise disjoint. Thus any dependence atom $\dep(\vec{x},y)$ can be expressed as a conditional independence atom ${y ~\bot_{\vec{x}}~ y}$. Also any independence atom ${\vec{y} ~\bot_{\vec{x}}~ \vec{z}}$ can be expressed as a conjunction of dependendence atoms and an independence atom ${\vec{y}^* ~\bot_{\vec{x}}~ \vec{z}^*}$ where $\vec{x}$, $\vec{y}^*$ and $\vec{z}^*$ are pairwise disjoint. For disjoint tuples ${\vec{x}}$, ${\vec{y}}$ and ${\vec{z}}$, independence atom ${\vec{y} ~\bot_{\vec{x}}~ \vec{z}}$ corresponds to the embedded multivalued dependency $\vec{x} \twoheadrightarrow \vec{y} |\vec{z}$. Hence the class of conditional independence atoms corresponds to the class of functional dependencies and embedded multivalued dependencies in database theory.

Let ${\vec{y} ~\bot_{\vec{x}}~ \vec{z}}$ be a conditional independence atom where $\vec{x}$, $\vec{y}$ and $\vec{z}$ are tuples of variables. If $\vec{y}^*$ lists the variables in $\vec{y} - \vec{x}\cup\vec{z}$, $\vec{z}^*$ lists the variables in $\vec{z}-\vec{x}\cup\vec{y}$, and $\vec{u}$ lists the variables in $\vec{y} \cap \vec{z}-\vec{x}$, then $${\mathcal{M}}\models_X {\vec{y} ~\bot_{\vec{x}}~ \vec{z}} \Leftrightarrow {\mathcal{M}}\models_X {\vec{y}^* ~\bot_{\vec{x}}~ \vec{z}^*} {\wedge}\bigwedge_{u\in \vec{u}} \dep(\vec{x},u).$$

The extension of first-order logic by dependence atoms, conditional independence atoms and inclusion atoms is called *dependence logic* (${{{\rm FO}}(\dep(\ldots ))}$), *independence logic* (${{{\rm FO}}(\bot_{\rm c})}$) and *inclusion logic* (${{{\rm FO}}(\subseteq)}$), respectively. The fragment of independence logic containing only pure independence atoms is called *pure independence logic*, written ${{{\rm FO}}(\bot)}$. For a collection of atoms $\mathcal C \subseteq \{=\!\!(\ldots), \bot_{\rm c}, \subseteq\}$, we will write ${{\rm FO}}(\mathcal C)$ (omitting the set parenthesis of $\mathcal{C}$) for first-order logic with these atoms.

We end this section with a list of properties of these logics.

\[PROP\] For $\mathcal C = \{=\!\!(\ldots), \bot_{\rm c}, \subseteq\}$, the following hold.

1.  (Empty Team Property)\[thm:etp\] For all models ${\mathcal{M}}$ and formulas $\phi \in {{\rm FO}}(\mathcal C)$ $${\mathcal{M}}\models_\emptyset \phi.$$

2.  (Locality [@galliani12])\[thm:loc\] If $\phi \in {{\rm FO}}(\mathcal C)$ is such that ${\textrm{Fr}}(\phi){\subseteq}V$, then for all models ${\mathcal{M}}$ and teams $X$, $${\mathcal{M}}\models_X \phi \Leftrightarrow {\mathcal{M}}\models_{X\upharpoonright V} \phi.$$

3.  \[thm:inc\_ind\][@galliani12] An inclusion atom ${\vec{x}} \subseteq {\vec{y}}$ is logically equivalent to the pure independence logic formula $$\forall v_1 v_2 {\vec{z}} (({\vec{z}} \not = {\vec{x}} \wedge {\vec{z}} \not = {\vec{x}}) \vee (v_1 \not = v_2 \wedge {\vec{z}} \not = {\vec{y}}) \vee ((v_1 = v_2 \vee {\vec{z}} = {\vec{y}}) \wedge {{\vec{z}} ~\bot~ v_1 v_2}))$$ where $v_1$, $v_2$ and ${\vec{z}}$ are new variables.

4.  [@vaananen13] Any independence logic formula is logically equivalent to some pure independence logic formula.

5.  [@vaananen07; @gradel10] Any dependence (or independence) logic sentence $\phi$ is logically equivalent to some existential second-order sentence $\phi^*$, and vice versa.

6.  \[thm:ILGFP\][@gallhella13] Any inclusion logic sentence $\phi$ is logically equivalent to some positive greatest fixpoint logic sentence $\phi^*$, and vice versa.

Deduction system
================

In this section we present a sound and complete axiomatization for the implication problem of inclusion and independence atoms. The implication problem is given by a finite set ${\Sigma}\cup \{\phi\}$ consisting of conditional independence and inclusion atoms, and the question is to decide whether ${\Sigma}\models \phi.$

\[axioms\] In addition to the usual introduction and elimination rules for conjunction, we adopt the following rules for conditional independence and inclusion atoms.

1.  Reflexivity: $$\vec{x} \subseteq \vec{x}.$$

2.  Projection and Permutation: $$\textrm{if }x_1 \ldots x_n \subseteq y_1 \ldots y_n  \textrm{, then } x_{i_1} \ldots x_{i_k} \subseteq y_{i_1} \ldots y_{i_k},$$ for each sequence $i_1 , \ldots ,i_k$ of integers from $\{1, \ldots ,n\}$.

3.  Transitivity: $$\textrm{if }\vec{x} \subseteq \vec{y}{\wedge}\vec{y} \subseteq \vec{z} \textrm{, then }\vec{x} \subseteq \vec{y}.$$

4.  Identity Rule: $$\textrm{if }ab{\subseteq}cc {\wedge}\phi \textrm{, then } \phi',$$ where $\phi'$ is obtained from $\phi$ by replacing any number of occurrences of $a$ by $b$.

5.  Inclusion Introduction: $$\textrm{if }\vec{a} \subseteq \vec{b} \textrm{, then } \vec{a}x \subseteq \vec{b} c,$$ where $x$ is a *new* variable.

6.  Start Axiom: $$\vec{a} \vec{c} \subseteq \vec{a} \vec{x} {\wedge}{\vec{b} ~\bot_{\vec{a}}~ \vec{x}} {\wedge}\vec{a} \vec{x} \subseteq \vec{a} \vec{c}$$ where $\vec{x}$ is a sequence of pairwise distinct *new* variables.

7.  Chase Rule: $$\textrm{if }{\vec{y} ~\bot_{\vec{x}}~ \vec{z}} {\wedge}\vec{a}\vec{b} \subseteq \vec{x}\vec{y} {\wedge}\vec{a}\vec{c} \subseteq \vec{x}\vec{z}  \textrm{, then } \vec{a}\vec{b}\vec{c} \subseteq \vec{x}\vec{y}\vec{z}.$$

8.  Final Rule: $$\textrm{if }\vec{a} \vec{c} \subseteq \vec{a} \vec{x}{\wedge}{\vec{b} ~\bot_{\vec{a}}~ \vec{x}} {\wedge}\vec{a}\vec{b} \vec{x} \subseteq \vec{a}\vec{b} \vec{c}  \textrm{, then } {\vec{b} ~\bot_{\vec{a}}~ \vec{c}}.$$

In an application of Inclusion Introduction, the variable $x$ is called the new variable of the deduction step. Similarly, in an application of Start Axiom, the variables of $\vec{x}$ are called the new variables of the deduction step. A deduction from ${\Sigma}$ is a sequence of formulas $(\phi_1, \ldots ,\phi_n)$ such that:

1.  Each $\phi_i$ is either an element of ${\Sigma}$, an instance of Reflexivity or Start Axiom, or follows from one or more formulas of ${\Sigma}\cup \{\phi_1, \ldots ,\phi_{i-1}\}$ by one of the rules presented above.

2.  If $\phi_i$ is an instance of Start Axiom (or follows from ${\Sigma}\cup \{\phi_1, \ldots ,\phi_{i-1}\}$ by Inclusion Introduction), then the new variables of $\vec{x}$ (or the new variable $x$) must not appear in ${\Sigma}\cup \{\phi_1,\ldots ,\phi_{i-1}\}$.

We say that $\phi$ is provable from ${\Sigma}$, written ${\Sigma}\vdash \phi$, if there is a deduction $(\phi_1, \ldots ,\phi_n)$ from ${\Sigma}$ with $\phi=\phi_n$ and such that no variables in $\phi$ are new in $\phi_1, \ldots ,\phi_n$.

Soundness
=========

First we prove the soundness of these axioms. Identity Rule and Start Axiom are sound if we interpret all the new variables as existentially quantified.

\[fakesound\] Let $(\phi_1, \ldots ,\phi_n)$ be a deduction from ${\Sigma}$, and let $\vec{y}$ list all the new variables of the deduction steps. Let ${\mathcal{M}}$ and $X$ be such that ${\mathcal{M}}\models_X {\Sigma}$ and ${\textrm{Var}}({\Sigma}_n) \setminus\vec{y} {\subseteq}{\textrm{Dom}}(X)$ where ${\Sigma}_n := {\Sigma}\cup\{\phi_1, \ldots ,\phi_{n}\}$. Then $${\mathcal{M}}\models_X {\exists}\vec{y} \bigwedge {\Sigma}_n.$$

We show the claim by induction on $n$. So assume that the claim holds for any deduction of length $n$. We prove that the claim holds for deductions of lenght $n+1$ also. Let $(\phi_1, \ldots ,\phi_{n+1})$ be a deduction from ${\Sigma}$, and let $\vec{y}$ and $\vec{z}$ list all the new variables of the deduction steps $\phi_1, \ldots ,\phi_n$ and $\phi_{n+1}$, respectively. Note that $\phi_{n+1}$ might not contain any new variables in which case $\vec{z}$ is empty. Assume that ${\mathcal{M}}\models_X {\Sigma}$ for some ${\mathcal{M}}$ and $X$, where ${\textrm{Var}}({\Sigma}_{n+1}) \setminus\vec{y}\vec{z} {\subseteq}{\textrm{Dom}}(X)$. By Proposition \[PROP\].\[thm:loc\] we may assume that ${\textrm{Var}}({\Sigma}_{n+1}) \setminus\vec{y}\vec{z} = {\textrm{Dom}}(X)$. We need to show that $${\mathcal{M}}\models_X {\exists}\vec{y}{\exists}\vec{z} \bigwedge\Sigma_{n+1}.$$ By the induction assumption, $${\mathcal{M}}\models_X {\exists}\vec{y} \bigwedge\Sigma_n$$ when by Lemma \[ketjulemma\] there is a function $F:X \rightarrow {\mathcal{P}}(M^{|\vec{y}|})\setminus\{\emptyset\}$ such that $$\label{heipähei}
{\mathcal{M}}\models_{X'} \bigwedge \Sigma_n$$ where $X':= X[F/\vec{y}]$. It suffices to show that $${\mathcal{M}}\models_{X'} {\exists}\vec{z} \bigwedge \Sigma_{n+1}.$$ If $\phi_{n+1}$ is an instance of Start Axiom, or follows from ${\Sigma}_n$ by Inclusion Introduction, then by Lemma \[ketjulemma\] it suffices to find a $G: X' \rightarrow {\mathcal{P}}(M^{|\vec{z}|})\setminus\{\emptyset\}$, such that ${\mathcal{M}}\models_{X'[G/\vec{z}]} \phi_{n+1}$. For this note that no variable of $\vec{z}$ is in ${\textrm{Var}}({\Sigma}_n)$, and hence by Proposition \[PROP\].\[thm:loc\] ${\mathcal{M}}\models_{X'[G/\vec{z}]} {\Sigma}_n$ follows from . Otherwise, if $\vec{z}$ is empty, then it suffices to show that ${\mathcal{M}}\models_{X'} \phi_{n+1}$.

The cases where $\phi_{n+1}$ is an instance of Reflexivity, or follows from ${\Sigma}_n$ by a conjunction rule, Projection and Permutation, Transitivity or Identity are straightforward. We prove the claim in the cases where one of the last four rules is applied.

-   Inclusion Introduction: Then $\phi_{n+1}$ is of the form $\vec{a}x \subseteq \vec{b} c$ where $\vec{a} \subseteq \vec{b}$ is in ${\Sigma}_n$. Let $s \in X'$. Since ${\mathcal{M}}\models_{X'} \vec{a} \subseteq \vec{b}$ there is a $s'\in X'$ such that $s(\vec{a})=s'(\vec{b})$. We let $G(s)=\{s'(c)\}$. Since $x \not\in {\textrm{Dom}}(X')$ we conclude that $ {\mathcal{M}}\models_{X'[G/x]} \vec{a}x \subseteq \vec{b} c$.

-   Start Axiom: Then $\phi_{n+1}$ is of the form $\vec{a} \vec{c} \subseteq \vec{a} \vec{x} {\wedge}{\vec{b} ~\bot_{\vec{a}}~ \vec{x}} {\wedge}\vec{a} \vec{x} \subseteq \vec{a} \vec{c}$. We define $G: X' \rightarrow {\mathcal{P}}(M^{|\vec{x}|})\setminus\{\emptyset\}$ as follows: $$G(s) = \{s'(\vec{c}) \mid s'\in X', s'(\vec{a})=s(\vec{a})\}.$$ Again, since $\vec{x}$ does not list any of the variables in ${\textrm{Dom}}(X')$, it is straightforward to show that $${\mathcal{M}}\models_{X'[G/\vec{x}]}  \vec{a} \vec{c} \subseteq \vec{a} \vec{x} {\wedge}{\vec{b} ~\bot_{\vec{a}}~ \vec{x}} {\wedge}\vec{a} \vec{x} \subseteq \vec{a} \vec{c}.$$

-   Chase Rule: Then $\phi_{n+1}$ is of the form $\vec{a}\vec{b}\vec{c} \subseteq \vec{x}\vec{y}\vec{z}$ where $${\vec{y} ~\bot_{\vec{x}}~ \vec{z}}{\wedge}\vec{a}\vec{b}\subseteq \vec{x}\vec{y}{\wedge}\vec{a}\vec{c}\subseteq \vec{x}\vec{z} \in {\Sigma}_n.$$ Let $s \in X'$. Since ${\mathcal{M}}\models_{X'}  \vec{a}\vec{b} \subseteq \vec{x}\vec{y} {\wedge}\vec{a}\vec{c} \subseteq \vec{x}\vec{z}$ there are $s',s''\in X'$ such that $s'(\vec{x}\vec{y})=s(\vec{a}\vec{b})$ and $s''(\vec{x}\vec{z} )=s(\vec{a}\vec{c})$. Since $s'(\vec{x})=s''(\vec{x})$ and ${\mathcal{M}}\models_{X'} {\vec{y} ~\bot_{\vec{x}}~ \vec{z}}$, there is a $s_0\in X'$ such that $s_0(\vec{x}\vec{y}\vec{z})=s(\vec{a}\vec{b}\vec{c})$ which shows the claim.

-   Final Rule: Then $\phi_{n+1}$ is of the form ${\vec{b} ~\bot_{\vec{a}}~ \vec{c}}$ where $$\vec{a} \vec{c} \subseteq \vec{a} \vec{x}{\wedge}{\vec{b} ~\bot_{\vec{a}}~ \vec{x}}{\wedge}\vec{a}\vec{b} \vec{x} \subseteq \vec{a}\vec{b} \vec{c}  \in {\Sigma}_n.$$ Let $s,s' \in X'$ be such that $s(\vec{a})=s'(\vec{a})$. Since ${\mathcal{M}}\models_{X'} \vec{a} \vec{c} \subseteq \vec{a} \vec{x}$ there is a $s_0 \in X'$ such that $s'(\vec{a}\vec{c})=s_0(\vec{a}\vec{x})$. Since ${\mathcal{M}}\models_{X'} {\vec{b} ~\bot_{\vec{a}}~ \vec{x}}$ and $s(\vec{a})=s_0(\vec{a})$ there is a $s_1\in X'$ such that $s_1(\vec{a}\vec{b}\vec{x})=s(\vec{a}\vec{b})s_0(\vec{x})$. And since ${\mathcal{M}}\models_{X'} \vec{a}\vec{b} \vec{x} \subseteq \vec{a}\vec{b} \vec{c}$ there is a $s''\in X'$ such that $s''(\vec{a}\vec{b}\vec{c})=s_1(\vec{a}\vec{b}\vec{x})$. Then $s''(\vec{a}\vec{b}\vec{c})=s(\vec{a}\vec{b})s'(\vec{c})$ which shows the claim and concludes the proof.

This gives us the following soundness theorem.

\[sound\] Let ${\Sigma}\cup \{\phi\}$ be a finite set of conditional independence and inclusion atoms. Then ${\Sigma}\models \phi$ if ${\Sigma}\vdash \phi$.

Assume that ${\Sigma}\vdash \phi$. Then there is a deduction $(\phi_1, \ldots ,\phi_n)$ from ${\Sigma}$ such that $\phi = \phi_n$ and no variables in $\phi$ are new in $\phi_1, \ldots ,\phi_n$. Let ${\mathcal{M}}$ and $X$ be such that ${\textrm{Var}}({\Sigma}\cup \{\phi\}) {\subseteq}{\textrm{Dom}}(X)$ and ${\mathcal{M}}\models_X {\Sigma}$. We need to show that ${\mathcal{M}}\models_X \phi$. Let $\vec{y}$ list all the new variables in $\phi_1, \ldots ,\phi_n$, and let $\vec{z}$ list all the variables in ${\textrm{Var}}({\Sigma}_n)\setminus \vec{y}$ which are not in ${\textrm{Dom}}(X)$. We first let $X':=X[\vec{0}/\vec{z}]$ for some dummy sequence $\vec{0}$ when by Theorem \[PROP\].\[thm:loc\], ${\mathcal{M}}\models_{X'} {\Sigma}$. Then by Theorem \[fakesound\], ${\mathcal{M}}\models_{X'} {\exists}\vec{y} \bigwedge {\Sigma}_n$ implying there exists a $F: X' \rightarrow {\mathcal{P}}(M^{|\vec{y}|})\setminus\{\emptyset\}$ such that ${\mathcal{M}}\models_{X''} \phi$, for $X'':=X'[F/\vec{y}]$. Since $X''= X[\vec{0}/\vec{z}][F/\vec{y}]$ and no variables of $\vec{y}$ or $\vec{z}$ appear in $\phi$, we conclude by Theorem \[PROP\].\[thm:loc\] that ${\mathcal{M}}\models_X \phi$.

Completeness
============

In this section we will prove that the set of axioms and rules presented in Definition \[axioms\] is complete with respect to the implication problem for conditional independence and inclusion atoms. For this purpose we introduce a graph characterization for the implication problem in subsection \[graphchar\]. This characterization is based on the classical characterization of the implication problem for various database dependencies using the chase procedure [@Maier:1979:TID:320107.320115]. The completeness proof is presented in subsection \[comp.proof\].

Graph characterization {#graphchar}
----------------------

We will consider graphs consisting of vertices and edges labeled by (possibly multiple) pairs of variables. The informal meaning is that a vertice will correspond to an assignment of a team, and an edge between $s$ and $s'$, labeled by $uw$, will express that $s(u)=s'(w)$. The graphical representation of the chase procedure is adapted from [@naumovre].

\[verkko\] Let $G=(V,E)$ be a graph where $E$ consists of non-directed labeled edges $(u,w)_{ab}$ where $ab$ is a pair of variables, and for every pair $(u,w)$ of vertices there can be several $ab$ such that $(u,w)_{ab} \in E$. Then we say that $u$ and $w$ are $ab$-connected, written $u \sim_{ab} w$, if $u=w$ and $a=b$, or if there are vertices $v_0, \ldots ,v_n$ and variables $x_0, \ldots ,x_{n}$ such that $$(u,v_0)_{ax_0},(v_0,v_1)_{x_0x_1}, \ldots ,(v_{n-1},v_n)_{x_{n-1}x_n},(v_n,w)_{x_nb} \in E.$$

Next we define a graph $G_{{\Sigma},\phi}$ in the style of Definition \[verkko\] for a set ${\Sigma}\cup \{\phi\}$ of conditional independence and inclusion atoms.

Let ${\Sigma}\cup\{\phi\}$ be a finite set of conditional independence and inclusion atoms. We let $G_{{\Sigma},\phi}:=(\bigcup_{n\in{\mathbb{N}}} V_n,\bigcup_{n\in{\mathbb{N}}} E_n)$ where $G_n=(V_n,E_n)$ is defined as follows:

-   If $\phi$ is ${\vec{b} ~\bot_{\vec{a}}~ \vec{c}}$, then $V_0:=\{v^+,v^-\}$ and $E_0:=\{(v^+,v^-)_{aa} \mid a \in \vec{a}\}$. If $\phi$ is $\vec{a} \subseteq \vec{b}$, then $V_0:= \{v\}$ and $E_0:= \emptyset$.

-   Assume that $G_n$ is defined. Then for every $v \in V_n$ and $x_1 \ldots x_k \subseteq y_1 \ldots y_k \in {\Sigma}$ we introduce a new vertex $v_{\rm new}$ and new edges $(v,v_{\rm new})_{x_iy_i}$, for $1 \leq i \leq k$. Also for every $u,w \in V_n$, $u\neq w$, and ${\vec{y} ~\bot_{\vec{x}}~ \vec{z}} \in {\Sigma}$ where $u \sim_{xx} w$, for $x \in \vec{x}$, we introduce a new vertex $v_{\rm new}$ and new edges $(u,v_{\rm new})_{yy}$, $(w,v_{\rm new})_{zz}$, for $y \in \vec{x}\vec{y}$ and $z \in \vec{x}\vec{z}$. We let $V_{n+1}$ and $E_{n+1}$ be obtained by adding these new vertices and edges to the sets $V_n$ and $E_n$.

Note that $G_{{\Sigma},\phi}= G_0$ if ${\Sigma}= \emptyset$.

This gives us a characterization of the following form. Instead of writing ${\mathcal{M}}\models_X \phi$ we will now write $X \models \phi$, since the satisfaction of an atom depends only on the team $X$.

\[char\] Let ${\Sigma}\cup\{\phi\}$ be a finite set of conditional independence and inclusion atoms.

1.  If $\phi$ is $a_1 \ldots a_k \subseteq b_1 \ldots b_k$, then ${\Sigma}\models \phi \Leftrightarrow {\exists}w \in V_{{\Sigma},\phi}(v \sim_{a_ib_i}w \textrm{ for all }1 \leq i \leq k$).

2.  If $\phi$ is ${\vec{b} ~\bot_{\vec{a}}~ \vec{c}}$, then ${\Sigma}\models \phi \Leftrightarrow {\exists}v \in V_{{\Sigma},\phi}(v^+ \sim_{bb} v  \textrm{ and } v^- \sim_{cc} v\textrm{ for all }b\in\vec{a}\vec{b} \textrm{ and }c\in\vec{a}\vec{c})$.

We deal with cases $1$ and $2$ simultaneously. First we will show the direction from right to left. So assume that the right-hand side assumption holds. We show that ${\Sigma}\models \phi$. Let $X$ be a team such that $X \models {\Sigma}$. We show that $X \models \phi$. For this, let $s,s'\in X$ be such that $s(\vec{a})=s'(\vec{a})$. If $\phi$ is ${\vec{b} ~\bot_{\vec{a}}~ \vec{c}}$, then we need to find a $s''$ such that $s''(\vec{a}\vec{b}\vec{c})=s(\vec{a}\vec{b})s'(\vec{c})$. If $\phi$ is $a_1 \ldots a_k \subseteq b_1 \ldots b_k$, then we need to find a $s''$ such that $s(a_1\ldots a_k)=s''(b_1\ldots b_k)$. We will now define inductively, for each natural number $n$, a function $f_n: V_n \rightarrow X$ such that $f_n(u)(x)=f_n(w)(y)$ if $(u,w)_{xy}\in E_n$. This will suffice for the claim as we will later show.

-   Assume that $n=0$.

    1.  \[caseone\] If $\phi$ is $a_1 \ldots a_k \subseteq b_1 \ldots b_k$, then $V_0= \{v\}$ and $E_0= \emptyset$, and we let $f_0(v):=s$.

    2.  \[casetwo\] If $\phi$ is ${\vec{b} ~\bot_{\vec{a}}~ \vec{c}}$, then $V_0=\{v^+,v^-\}$ and $E_0=\{(v^+,v^-)_{aa} \mid a \in \vec{a}\}$. We let $f_0(v^+):=s$ and $f_0(v^-):=s'$. Then $f(v^+)(a)=f(v^-)(a)$, for $a \in \vec{a}$, as wanted.

-   Assume that $n=m+1$, and that $f_m$ is defined so that $f_m(u)(x)=f_m(w)(y)$ if $(u, w)_{xy} \in E_m$. We let $f_{m+1}(u)=f_m(u)$, for $u\in V_m$. Assume that $v_{\rm new}\in V_{m+1}\setminus V_m$ and that there are $u \in V_m$ and $x_1 \ldots x_l\subseteq y_1\ldots y_l \in {\Sigma}$ such that $(u,v_{\rm new})_{x_iy_i}\in E_{m+1}\setminus E_m$, for $1 \leq i \leq l$. Since $X \models x_1 \ldots x_l\subseteq y_1\ldots y_l $, there is a $s_0\in X$ such that $f_{m+1}(u)(x_i)=s_0(y_i)$, for $1 \leq i \leq l$. We let $f_{m+1}(v_{\rm new}):=s_0$ when $f_{m+1}(u)(x_i)=f_{m+1}(v_{\rm new})(y_i)$, for $1 \leq i \leq l$, as wanted.

    Assume then that $v_{\rm new}\in V_{m+1}\setminus V_m$ and that there are $u,w \in V_m$, $u \neq w$, and ${\vec{y} ~\bot_{\vec{x}}~ \vec{z}} \in {\Sigma}$ such that $(u,v_{\rm new})_{yy},(w,v_{\rm new})_{zz}\in E_{m+1}\setminus E_m$, for $y\in \vec{x}\vec{y}$ and $z\in\vec{x}\vec{z}$. Then $u \sim_{xx} w$ in $G_m$, for $x \in \vec{x}$. This means that there are vertices $v_0, \ldots ,v_n$ and variables $x_0, \ldots ,x_{n}$, for $x \in \vec{x}$, such that $$(u,v_0)_{xx_0},(v_0,v_1)_{x_0x_1}, \ldots ,(v_{n-1},v_n)_{x_{n-1}x_n},(v_n,w)_{x_nx} \in E_m.$$ By the induction assumption then $$f_m(u)(x)=f_m(v_0)(x_0)=\ldots =f_m(v_n)(x_n)=f_m(w)(x).$$ Hence, since $X\models {\vec{y} ~\bot_{\vec{x}}~ \vec{z}} $, there is a $s_0$ such that $s_0(\vec{x}\vec{y}\vec{z})=f_m(u)(\vec{x}\vec{y})f_m(w)(\vec{z})$. We let $f_{m+1}(v_{\rm new}):=s_0$ and conclude that $f_{m+1}(u)(y)=f_{m+1}(v_{\rm new})(y)$ and $f_{m+1}(w)(z)=f_{m+1}(v_{\rm new})(z)$, for $y\in \vec{x}\vec{y}$ and $z\in\vec{x}\vec{z}$. This concludes the construction.

Now, in case \[caseone\] there is a $v \in V_{{\Sigma},\phi}$ such that $v^+ \sim_{bb} v $ and $v^- \sim_{cc} v$ for all $b\in\vec{a}\vec{b}$ and $c\in\vec{a}\vec{c}$. Let $n$ be such that each path witnessing this is in $G_n$. We want to show that choosing $s''$ as $f_n(v)$, $s''(\vec{a}\vec{b}\vec{c})=s(\vec{a}\vec{b})s'(\vec{c})$. Recall that $s=f_n(v^+)$ and $s'=f_n(v^-)$. First, let $b \in \vec{a}\vec{b}$. The case where $v=v^+$ is trivial, so assume that $v \neq v^+$ in which case there are vertices $v_0, \ldots ,v_n$ and variables $x_0, \ldots ,x_{n}$ such that $$(v^+,v_0)_{bx_0},(v_0,v_1)_{x_0x_1}, \ldots ,(v_{n-1},v_n)_{x_{n-1}x_n},(v_n,v)_{x_nb} \in E_n$$ when by the construction, $f_n(v^+)(b)=f_n(v)(b)$. Analogously $f_n(v^-)(c)=f_n(v)(c)$, for $c \in \vec{c}$, which concludes this case.

In case \[casetwo\], $s''$ is found analogously. This concludes the proof of the direction from right to left.

For the other direction, assume that the right-hand side assumption fails in $G_{{\Sigma},\phi}$. Again, we deal with both cases simultaneously. We will now construct a team $X$ such that $X \models {\Sigma}$ and $X \not\models \phi$. We let $X:=\{s_u \mid u \in V_{{\Sigma}, \phi}\}$ where each $s_u:{\textrm{Var}}({\Sigma}\cup \{\phi\}) \rightarrow {\mathcal{P}}(V_{{\Sigma},\phi})^{|{\textrm{Var}}({\Sigma}\cup \{\phi\})|}$ is defined as follows: $$s_u(x) := \prod_{y \in {\textrm{Var}}({\Sigma}\cup \{\phi\})} \{w \in V_{{\Sigma},\phi} \mid u\sim_{xy}  w\}.$$ We claim that $s_u(x) = s_w(y) \Leftrightarrow u \sim_{xy} w$. Indeed, assume that $u \sim_{xy} w$. If now $v$ is in the set with the index $z$ of the product $s_u(x)$, then $u\sim_{xz} v$. Since $w \sim_{yx} u$, we have that $w \sim_{yz} v$. Thus $v$ is in the set with the index $z$ of the product $s_w(y)$. Hence by symmetry we conclude that $s_u(x)=s_w(y)$. For the other direction assume that $s_u(x) =s_w(y)$. Then consider the set with the index $y$ of the product $s_w(y)$. Since $w \sim_{yy} w$ by the definition, the vertex $w$ is in this set, and thus by the assumption it is in the set with the index $y$ of the product $s_u(x)$. It follows by the definition that $u \sim_{xy} w$ which shows the claim.

Next we will show that $X \models {\Sigma}$. So assume that ${\vec{y} ~\bot_{\vec{x}}~ \vec{z}}\in {\Sigma}$ and that $s_u,s_w \in X$ are such that $s_u(\vec{x})=s_w(\vec{x})$. We need to find a $s_v \in X$ such that $s_v(\vec{x}\vec{y}\vec{z})=s_u(\vec{x}\vec{y})s_w(\vec{z})$. Since $u \sim_{xx} w$, for $x \in \vec{x}$, there is a $v\in G_{{\Sigma},\phi}$ such that $(u,v)_{yy},(w,v)_{zz}\in E_{{\Sigma},\phi}$, for $y\in \vec{x}\vec{y}$ and $z\in \vec{x}\vec{z}$. Then $s_u(\vec{x}\vec{y})=s_v(\vec{x}\vec{y})$ and $s_w(\vec{x}\vec{z})=s_v(\vec{x}\vec{z})$, as wanted. In case $x_1 \ldots x_l {\subseteq}y_1 \ldots y_l \in {\Sigma}$, $X\models x_1 \ldots x_l {\subseteq}y_1 \ldots y_l$ is shown analogously.

It suffices to show that $X \not\models \phi$. Assume first that $\phi$ is ${\vec{b} ~\bot_{\vec{a}}~ \vec{c}}$. Then $s_{v^+}(\vec{a})=s_{v^-}(\vec{a})$, but by the assumption there is no $ v \in V_{{\Sigma},\phi}$ such that $v^+ \sim_{bb} v $ and $ v^- \sim_{cc} v$ for all $b\in\vec{a}\vec{b} $ and $c\in\vec{a}\vec{c}$. Hence there is no $s_v \in X$ such that $s_{v}(\vec{a}\vec{b})=s_{v^+}(\vec{a}\vec{b})$ and $s_{v}(\vec{a}\vec{c})=s_{v^-}(\vec{a}\vec{c})$ when $X \not\models {\vec{b} ~\bot_{\vec{a}}~ \vec{c}}$. In case $\phi$ is $a_1 \ldots a_k \subseteq b_1 \ldots b_k$, $X \not\models\phi$ is shown analogously.

Completeness proof {#comp.proof}
------------------

We are now ready to prove the completeness. Let us first define some notation needed in the proof. We will write $x = y$ for syntactical identity, $x \equiv y$ for an atom of the form $xy\subseteq zz$ implying the identity of $x$ and $y$, and $\vec{x}\equiv\vec{y}$ for an conjunction the form $\bigwedge_{i \leq |\vec{x}|} {\textrm{pr}}_i(\vec{x})\equiv {\textrm{pr}}_i (\vec{y})$. Let $\vec{x}=(x_1, \ldots ,x_n)$ be a sequence listing ${\textrm{Var}}({\Sigma}\cup \{\phi\})$. If $\vec{x}_v$ is a vector of length $|\vec{x}|$ (representing vertex $v$ of the graph $G_{{\Sigma},\phi}$), and $\vec{p}=(x_{i_1}, \ldots ,x_{i_l})$ is a sequence of variables from $\vec{x}$, then we write $\vec{p}_v$ for $$({\textrm{pr}}_{i_1} ( \vec{x}_v ), \ldots ,{\textrm{pr}}_{i_l}(\vec{x}_v)).$$

\[complete\] Let ${\Sigma}\cup \{\phi\}$ be a finite set of conditional independence and inclusion atoms. Then ${\Sigma}\vdash \phi$ if ${\Sigma}\models \phi$.

Let ${\Sigma}$ and $\phi$ be such that ${\Sigma}\models \phi$. We will show that ${\Sigma}\vdash \phi$. We have two cases: either

1.  $\phi$ is $x_{i_1}\ldots x_{i_m} {\subseteq}x_{j_1}\ldots x_{j_m}$ and, by Theorem \[char\], there is a $ w \in V_{{\Sigma},\phi}$ such that $v\sim_{x_{i_k}x_{j_k}} w$ for all $1 \leq k \leq m$, or

2.  $\phi$ is ${\vec{b} ~\bot_{\vec{a}}~ \vec{c}}$ and, by Theorem \[char\], there is a $ v \in V_{{\Sigma},\phi}$ such that $v^+\sim_{x_ix_i} v$ and $v^-\sim_{x_jx_j} v $ for all $x_i\in\vec{a}\vec{b} $ and $x_j\in\vec{a}\vec{c}$.

Using this we will show how to create a deduction of $\phi$ from ${\Sigma}$. We write ${\Sigma}{\vdash^*}\psi$ if $\psi$ appears as a step in the deduction. Recall that the new variables introduced in the deduction steps previously must not appear in $\phi$ but may appear in $\psi$. We will introduce for each $u\in V_{{\Sigma},\phi}$ a sequence $\vec{x}_u$ of length $n$ (and possibly with repetitions) such that ${\Sigma}{\vdash^*}\vec{x}_u \subseteq \vec{x} $. For each $(u,w)_{x_ix_j}\in E_{{\Sigma},\phi}$ we will also show that ${\Sigma}{\vdash^*}{\textrm{pr}}_i(\vec{x}_u) \equiv {\textrm{pr}}_j(\vec{x}_w)$. We do this inductively for $V_n$ and $E_n$ as follows:

-   Assume that $n=0$. Then we have two cases:

    1.  Assume that $\phi$ is $x_{i_1}\ldots x_{i_m} {\subseteq}x_{j_1}\ldots x_{j_m}$ when $V_0:=\{v\}$ and $E_0:=\emptyset$. Then we let $\vec{x}_{v}:=\vec{x}$ in which case we can derive $\vec{x}_v{\subseteq}\vec{x}$ by Reflexivity.

    2.  Assume that $\phi$ is ${\vec{b} ~\bot_{\vec{a}}~ \vec{c}}$ when $V_0:=\{v^+,v^-\}$ and $E_0:=\{(v^+,v^-)_{x_ix_i} \mid x_i \in \vec{a}\}$. First we use Start Axiom to obtain $$\vec{a} \vec{c} \subseteq \vec{a} \vec{c}^* {\wedge}{\vec{b} ~\bot_{\vec{a}}~ \vec{c}^*} {\wedge}\vec{a} \vec{c}^* \subseteq \vec{a} \vec{c}$$ where $\vec{c}^*$ is a sequence of pairwise distinct new variables. Then using Inclusion Introduction and Projection and Permutation we may deduce $$\label{inkl5}\vec{a}\vec{b}^*\vec{c}^*\vec{d}^*{\subseteq}\vec{a}\vec{b}\vec{c}\vec{d}$$ from $\vec{a}\vec{c}^* {\subseteq}\vec{a}\vec{c}$ where $\vec{d}$ lists $\vec{x} \setminus \vec{a}\vec{b}\vec{c}$ and $\vec{b}^*\vec{c}^*\vec{d}^*$ is a sequence of pairwise distinct new variables. By Projection and Permutation and Identity Rule we may assume that $\vec{a}\vec{b}^*\vec{c}^*\vec{d}^*$ has repetitions exactly where $\vec{a}\vec{b}\vec{c}\vec{d}$ has. Therefore we can list the variables of $\vec{a}\vec{b}^*\vec{c}^*\vec{d}^*$ in a sequence $\vec{x}_{v^-}$ of length $|\vec{x}|$ where $$\vec{a}\vec{b}^*\vec{c}^*\vec{d}^*= ({\textrm{pr}}_{i_1}(\vec{x}_{v^-}), \ldots ,{\textrm{pr}}_{i_l}(\vec{x}_{v^-})),$$ for $\vec{a}\vec{b}\vec{c}\vec{d}=(x_{i_1}, \ldots ,x_{i_l})$. Then $\vec{a}_{v^-}\vec{b}_{v^-}\vec{c}_{v^-}\vec{d}_{v^-}= \vec{a}\vec{b}^*\vec{c}^*\vec{d}^*$, and we can derive $ \vec{x}_{v^-} {\subseteq}\vec{x}$ from by Projection and Permutation. We also let $\vec{x}_{v^+}:=\vec{x}$ when $\vec{a}_{v^+}\vec{b}_{v^+}\vec{c}_{v^+}\vec{d}_{v^+}= \vec{a}\vec{b}\vec{c}\vec{d}$. Then $\vec{a}_{v^+}\equiv \vec{a}_{v^-}$ and $\vec{x}_{v^+} {\subseteq}\vec{x}$ are derivable by Reflexivity which concludes the case $n=0$.

-   Assume that $n=m+1$ and for each $u \in V_{m}$ there is a sequence $\vec{x}_u$ such that ${{\Sigma}{\vdash^*}}\vec{x}_u \subseteq \vec{x}$ and for each $(u,w)_{x_ix_j}\in E_{m}$ also ${{\Sigma}{\vdash^*}}{\textrm{pr}}_i(\vec{x}_u) \equiv {\textrm{pr}}_j(\vec{x}_w)$. Assume that $v_{\rm new}\in V_{m+1}\setminus V_m$ is such that there are $u \in V_m$ and $x_{i_1} \ldots x_{i_l} \subseteq x_{j_i} \ldots x_{j_l}   \in{\Sigma}$ for which we have added new edges $(u,v_{\rm new})_{x_{i_k}x_{j_k}}$ to $V_{m+1}$, for $1 \leq k \leq l$. We will introduce a sequence $\vec{x}_{v_{\rm new}}$ such that ${{\Sigma}{\vdash^*}}\vec{x}_{v_{\rm new}}{\subseteq}\vec{x}$ and ${{\Sigma}{\vdash^*}}{\textrm{pr}}_{i_k}(\vec{x}_{u})\equiv {\textrm{pr}}_{j_k}(x_{v_{\rm new}})$, for $1 \leq k \leq l$.

    By Projection and Permutation we deduce first $$\label{eka}{\textrm{pr}}_{i_1}(\vec{x}_u) \ldots {\textrm{pr}}_{i_l}(\vec{x}_u)   {\subseteq}x_{i_1} \ldots x_{i_l}$$ from $\vec{x}_u {\subseteq}\vec{x}$. Then we obtain $$\label{blah}{\textrm{pr}}_{i_1}(\vec{x}_u) \ldots {\textrm{pr}}_{i_l}(\vec{x}_u)  \subseteq x_{j_i} \ldots x_{j_l}$$ from and $x_{i_1} \ldots x_{i_l} \subseteq x_{j_i} \ldots x_{j_l}$ by Transitivity.

    Then by Reflexivity we may deduce $ {\textrm{pr}}_{i_1}(\vec{x}_u)    {\subseteq}{\textrm{pr}}_{i_1}(\vec{x}_u)$ from which we derive by Inclusion Introduction $$\label{plöh} {\textrm{pr}}_{i_1}(\vec{x}_u)y_1    {\subseteq}{\textrm{pr}}_{i_1}(\vec{x}_u){\textrm{pr}}_{i_1}(\vec{x}_u)$$ where $y_1$ is a new variable. Then from and we derive by Identity Rule $$\label{tähänkin_numero_tasa-arvon_nimissä} y_1 {\textrm{pr}}_{i_2}(\vec{x}_{u})\ldots {\textrm{pr}}_{i_l}(\vec{x}_u)  {\subseteq}x_{j_1} \ldots x_{j_l}.$$ Iterating this procedure $l$ times leads us to a formula $$\label{joo}\bigwedge_{1 \leq k \leq l} {\textrm{pr}}_{i_k}(\vec{x}_u) \equiv y_k {\wedge}y_1 \ldots y_l {\subseteq}x_{j_1} \ldots x_{j_l}$$ where $y_1, \ldots ,y_l$ are pairwise distinct new variables. Let $x_{j_{l+1}}, \ldots ,x_{j_{l'}}$ list $\vec{x} \setminus \{x_{j_1}, \ldots ,x_{j_l}\}$. Repeating Inclusion Introduction for the inclusion atom in gives us a formula $$\label{plaah} y_1 \ldots y_{l'} {\subseteq}x_{j_1} \ldots x_{j_{l'}}$$ where $y_{l+1}, \ldots ,y_{l'}$ are pairwise distinct new variables. Let $\vec{y}$ now denote the sequence $y_1 \ldots y_{l'}$ when $$\label{jepjep}\bigwedge_{1 \leq k \leq l} {\textrm{pr}}_{i_k}(\vec{x}_u) \equiv {\textrm{pr}}_k(\vec{y}) {\wedge}\vec{y} {\subseteq}x_{j_1} \ldots x_{j_{l'}}$$ is the formula obtained from by replacing its inclusion atom with . By Projection and Permutation and Identity Rule we may assume that ${\textrm{pr}}_{k}(\vec{y}) = {\textrm{pr}}_{k'}(\vec{y})$ if and only if $j_k = j_{k'}$, for $1 \leq k \leq l'$. Analogously to the case $n=0$, we can then order the variables of $\vec{y}$ as a sequence $\vec{x}_{v_{\rm new}}$ of length $|\vec{x}|$ such that ${\textrm{pr}}_{j_k}(\vec{x}_{v_{\rm new}})={\textrm{pr}}_k(\vec{y})$, for $1 \leq k \leq l'$. Then $$\label{jepulis}\bigwedge_{1 \leq k \leq l} {\textrm{pr}}_{i_k}(\vec{x}_u) \equiv {\textrm{pr}}_{j_k}(\vec{x}_{v_{\rm new}}) {\wedge}{\textrm{pr}}_{j_1}(\vec{x}_{v_{\rm new}}) \ldots {\textrm{pr}}_{j_{l'}}(\vec{x}_{v_{\rm new}}) {\subseteq}x_{j_1} \ldots x_{j_{l'}}$$ is the formula . By Projection and Permutation we can now deduce $\vec{x}_{v_{\rm new}} {\subseteq}\vec{x}$ from the inclusion atom in . Hence $\vec{x}_{v_{\rm new}}$ is such that ${{\Sigma}{\vdash^*}}\vec{x}_{v_{\rm new}} {\subseteq}\vec{x}$ and ${{\Sigma}{\vdash^*}}{\textrm{pr}}_{i_k}(\vec{x}_u) \equiv {\textrm{pr}}_{j_k}(\vec{x}_{v_{\rm new}}) $, for $1 \leq k \leq l$. This concludes the case for inclusion.

    Assume then that $v_{\rm new}\in V_{m+1}\setminus V_m$ is such that there are $u,w \in V_m$, $u \neq w$, and ${\vec{q} ~\bot_{\vec{p}}~ \vec{r}}  \in{\Sigma}$ for which we have added new edges $(u,v_{\rm new})_{x_ix_i}, (w,v_{\rm new})_{x_jx_j}$ to $V_{m+1}$, for $x_i \in \vec{p}\vec{q}$ and $x_j \in \vec{p}\vec{r}$. We will introduce a sequence $\vec{x}_{v_{\rm new}}$ such that ${{\Sigma}{\vdash^*}}\vec{x}_{v_{\rm new}}{\subseteq}\vec{x}$, and ${{\Sigma}{\vdash^*}}{\textrm{pr}}_{i}(\vec{x}_{u})\equiv {\textrm{pr}}_{i}(x_{v_{\rm new}})$ and ${{\Sigma}{\vdash^*}}{\textrm{pr}}_{j}(\vec{x}_{w})\equiv {\textrm{pr}}_{j}(x_{v_{\rm new}})$, for $x_i \in \vec{p}\vec{q}$ and $x_j \in \vec{p}\vec{r}$. The latter means that $${{\Sigma}{\vdash^*}}\vec{p}_u\vec{q}_u\equiv \vec{p}_{v_{\rm new}}\vec{q}_{v_{\rm new}}{\wedge}\vec{p}_w\vec{r}_w\equiv \vec{p}_{v_{\rm new}}\vec{r}_{v_{\rm new}}.$$

    First of all, we know that $u \sim_{x_kx_k} w$ in $G_m$ for all $x_k \in \vec{p}$. Thus there are vertices $v_0, \ldots ,v_n\in V_m$ and variables $x_{i_0}, \ldots ,x_{i_{n}}$ such that $$(u,v_0)_{x_kx_{i_0}} , (v_0,v_1)_{x_{i_0}x_{i_1}}, \ldots ,(v_{n-1},v_n)_{x_{i_{n-1}}x_{i_n}},\\(v_n,w)_{x_{i_n}x_k} \in E_m.$$ Hence by the induction assumption and Identity Rule, there are $\vec{x}_u$ and $\vec{x}_w$ such that ${{\Sigma}{\vdash^*}}\vec{x}_u {\subseteq}\vec{x}$ and ${{\Sigma}{\vdash^*}}\vec{x}_w {\subseteq}\vec{x}$, and ${{\Sigma}{\vdash^*}}{\textrm{pr}}_k(\vec{x}_u)\equiv {\textrm{pr}}_k(\vec{x}_w)$, for $x_k \in \vec{p}$. In other words, $$\label{tästä}{{\Sigma}{\vdash^*}}\vec{p}_u\equiv \vec{p}_w.$$

    By Projection and Permutation we first derive $$\label{label}\vec{p}_u\vec{q}_u {\subseteq}\vec{p}\vec{q}$$ and $$\label{labello} \vec{p}_w\vec{r}_w{\subseteq}\vec{p}\vec{r}$$ from $\vec{x}_u {\subseteq}\vec{x}$ and $\vec{x}_w {\subseteq}\vec{x}$, respectively. Then we derive $$\label{labelliino}\vec{p}_u\vec{r}_w{\subseteq}\vec{p}\vec{r}$$ from $\vec{p}_u\equiv \vec{p}_w$ and by Identity Rule. By Chase Rule we then derive $$\label{huh}\vec{p}_u\vec{q}_u\vec{r}_w{\subseteq}\vec{p}\vec{q}\vec{r}$$ from ${\vec{q} ~\bot_{\vec{p}}~ \vec{r}}$, and . Now it can be the case that $x_i\in \vec{p}\vec{q}$ and $x_i \in \vec{r}$, but ${\textrm{pr}}_i(\vec{x}_u)\neq{\textrm{pr}}_i(\vec{x}_w)$. Then we can derive $$\label{heh}{\textrm{pr}}_i(\vec{x}_u){\textrm{pr}}_i(\vec{x}_w) {\subseteq}x_ix_i$$ from by Projection and Permutation, and $$\vec{p}_u\vec{q}_u\vec{r}_w({\textrm{pr}}_i(\vec{x}_u)/{\textrm{pr}}_i(\vec{x}_w)){\subseteq}\vec{p}\vec{q}\vec{r}$$ from and by Identity Rule. Let now $\vec{r}^*$ be obtained from $\vec{r}_w$ by replacing, for each $x_i\in \vec{p}\vec{q} \cap \vec{r}$, the variable ${\textrm{pr}}_i(\vec{x}_w)$ with ${\textrm{pr}}_i(\vec{x}_u)$. Iterating the previous derivation gives us then $$\label{numero}\vec{r}^* \equiv \vec{r}_w {\wedge}\vec{p}_u\vec{q}_u\vec{r}^*{\subseteq}\vec{p}\vec{q}\vec{r}.$$ Let $\vec{s}$ list the variables in $\vec{x}\setminus \vec{p}\vec{q}\vec{r}$. From the inclusion atom in we derive by Inclusion Introduction $$\label{joh}\vec{p}_u\vec{q}_u\vec{r}^*\vec{s}^* {\subseteq}\vec{p}\vec{q}\vec{r}\vec{s}$$ where $\vec{s}^*$ is a sequence of pairwise distinct new variables. Then $\vec{p}_u\vec{q}_u\vec{r}^*\vec{s}^*$ has repetitions at least where $\vec{p}\vec{q}\vec{r}\vec{s}$ has, and hence we can define $\vec{x}_{v_{\rm{new}}}$ as the sequence of length $|\vec{x}|$ where $$\vec{p}_u\vec{q}_u\vec{r}^*\vec{s}^*= ({\textrm{pr}}_{i_1}(\vec{x}_{v_{\rm{new}}}), \ldots ,{\textrm{pr}}_{i_l}(\vec{x}_{v_{\rm{new}}})),$$ for $\vec{p}\vec{q}\vec{r}\vec{s}=(x_{i_1}, \ldots ,x_{i_l})$. Then $\vec{p}_{v_{\rm new}}\vec{q}_{v_{\rm new}}\vec{r}_{v_{\rm new}}\vec{s}_{v_{\rm new}}=\vec{p}_u\vec{q}_u\vec{r}^*\vec{s}^*$, and we can thus derive $$\vec{x}_{v_{\rm new}} {\subseteq}\vec{x}$$ from by Projection and Permutation. Moreover, $$\vec{p}_{v_{\rm new}}\vec{q}_{v_{\rm new}} \equiv \vec{p}_u\vec{q}_u$$ can be derived by Reflexivity, and $$\label{tää}\vec{p}_{v_{\rm new}}\vec{r}_{v_{\rm new}}  \equiv \vec{p}_w\vec{r}_w$$ is derivable since is the conjunction of $\vec{p}_u \equiv \vec{p}_w$ in and $\vec{r}^* \equiv \vec{r}_w$ in . Hence $\vec{x}_{v_{\rm new}}$ is such that $${{\Sigma}{\vdash^*}}\vec{x}_{v_{\rm new}} {\subseteq}\vec{x} {\wedge}\vec{p}_{v_{\rm new}}\vec{q}_{v_{\rm new}} \equiv \vec{p}_u\vec{q}_u {\wedge}\vec{p}_{v_{\rm new}}\vec{r}_{v_{\rm new}}  \equiv \vec{p}_w\vec{r}_w.$$ This concludes the case $n=m+1$ and the construction.

Assume now first that $\phi$ is $\vec{a} \subseteq \vec{b}$ where $\vec{a}:=x_{i_1}\ldots x_{i_m}$ and $\vec{b}:=x_{j_1}\ldots x_{j_m}$. Then there is a $ w \in V_{{\Sigma},\phi}$ such that $v\sim_{x_{i_k}x_{j_k}} w$, for $1 \leq k \leq m$. Let $n$ be such that all the witnessing paths are in $G_n$, and let $1 \leq k \leq m$. We first show that $$\label{sama}{{\Sigma}{\vdash^*}}{\textrm{pr}}_{i_k}(\vec{x}_{v})\equiv {\textrm{pr}}_{j_k}(\vec{x}_{w}).$$ If $w = v $ and $i_k =j_k$, then holds by Reflexivity. If $w \neq v $ or $i_k \neq j_k$, then there are vertices $v_0, \ldots ,v_p\in V_n$ and variables $x_{l_0}, \ldots ,x_{l_{p}}$ such that $$(v,v_0)_{x_{i_k}x_{l_0}} , (v_0,v_1)_{x_{l_0}x_{l_1}}, \ldots ,(v_{p-1},v_p)_{x_{l_{p-1}}x_{l_p}},(v_p,w)_{x_{l_p}x_{j_k}} \in E_n.$$ Then by the previous construction, $${{\Sigma}{\vdash^*}}{\textrm{pr}}_{i_k}(\vec{x}_{v})\equiv {\textrm{pr}}_{l_0}(\vec{x}_{v_0}){\wedge}\ldots {\wedge}{\textrm{pr}}_{l_p}(\vec{x}_{v_p})\equiv {\textrm{pr}}_{j_k}(\vec{x}_{w})$$ when ${{\Sigma}{\vdash^*}}{\textrm{pr}}_{i_k}(\vec{x}_{v})\equiv {\textrm{pr}}_{j_k}(\vec{x}_{w})$ by Identity Rule. Therefore we conclude that $$\label{inkl1}{{\Sigma}{\vdash^*}}\vec{a}_v \equiv \vec{b}_w.$$ Since ${{\Sigma}{\vdash^*}}\vec{x}_w {\subseteq}\vec{x}$ by the construction, then by Permutation and Projection $$\label{inkl2}{{\Sigma}{\vdash^*}}\vec{b}_w {\subseteq}\vec{b}.$$ Now $\vec{x}_v = \vec{x}$ as defined in case $1$ of step $n=0$, and therefore $\vec{a}_v=\vec{a}$. Thus we get $\vec{a} {\subseteq}\vec{b}$ from and using repeatedly Identity Rule. Since no new variables appear in $\vec{a} {\subseteq}\vec{b}$, we conclude that ${\Sigma}\vdash  \vec{a} {\subseteq}\vec{b}$.

Assume then that $\phi$ is ${\vec{b} ~\bot_{\vec{a}}~ \vec{c}}$ when there is a $ v \in V_{{\Sigma},\phi}$ such that $v^+\sim_{x_ix_i} v$ and $v^-\sim_{x_jx_j} v $ for all $x_i\in\vec{a}\vec{b} $ and $x_j\in\vec{a}\vec{c}$. Analogously to the previous case, we can now find a sequence $\vec{x}_v$ such that $$\label{inkl3}
 {{\Sigma}{\vdash^*}}\vec{x}_v {\subseteq}\vec{x}$$ and $$\label{iden1}
{{\Sigma}{\vdash^*}}\vec{a}_v\vec{b}_v\equiv\vec{a}_{v^+}\vec{b}_{v^+}{\wedge}\vec{a}_v\vec{c}_v \equiv\vec{a}_{v^-}\vec{c}_{v^-}.$$ By Projection and Permutation we may deduce $$\label{inkl4}
\vec{a}_v\vec{b}_v\vec{c}_v {\subseteq}\vec{a}\vec{b}\vec{c}$$ from , and using repeatedly Projection and Permutation and Identity Rule we get $$\vec{a}_{v^+}\vec{b}_{v^+}\vec{c}_{v^-}{\subseteq}\vec{a}\vec{b}\vec{c}$$ from and . Note that $\vec{a}_{v^+}\vec{b}_{v^+}\vec{c}_{v^-} = \vec{a}\vec{b}\vec{c}^*$ and that we have already derived $\vec{a} \vec{c} \subseteq \vec{a} \vec{c}^*$ and ${\vec{b} ~\bot_{\vec{a}}~ \vec{c}^*}$ with Start Axiom (see case $2$ of step $n=0$). Therefore we can derive ${\vec{b} ~\bot_{\vec{a}}~ \vec{c}}$ with one application of Final Rule. Since no new variables appear in ${\vec{b} ~\bot_{\vec{a}}~ \vec{c}}$, we conclude that ${\Sigma}\vdash {\vec{b} ~\bot_{\vec{a}}~ \vec{c}}$.

By Theorem \[sound\] and Theorem \[complete\] we now have the following.

Let ${\Sigma}\cup \{\phi\}$ be a finite set of conditional independence and inclusion atoms. Then ${\Sigma}\vdash \phi$ if and only if ${\Sigma}\models \phi$.

The following example shows how to deduce ${b ~\bot_{a}~ c} \vdash{c ~\bot_{a}~ b}$ and ${b ~\bot_{a}~ cd} \vdash {b ~\bot_{a}~ c}$.

-   ${b ~\bot_{a}~ c} \vdash{c ~\bot_{a}~ b}$:

    1.  $ab {\subseteq}ab' {\wedge}{c ~\bot_{a}~ b'}{\wedge}ab' {\subseteq}ab $ (Start Axiom)

    2.  $ac {\subseteq}ac$ (Reflexivity)

    3.  ${b ~\bot_{a}~ c}{\wedge}ab' {\subseteq}ab {\wedge}ac {\subseteq}ac   \vdash ab'c {\subseteq}abc$ (Chase Rule)

    4.  $ab'c {\subseteq}abc \vdash acb' {\subseteq}acb$ (Projection and Permutation)

    5.  $ab {\subseteq}ab' {\wedge}{c ~\bot_{a}~ b'} {\wedge}acb' {\subseteq}acb \vdash{c ~\bot_{a}~ b}$ (Final Rule)

-   ${b ~\bot_{a}~ cd} \vdash {b ~\bot_{a}~ c}$:

    1.  $ac{\subseteq}ac' {\wedge}{b ~\bot_{a}~ c'} {\wedge}ac' {\subseteq}ac$ (Start Axiom)

    2.  $ac'd' {\subseteq}acd$ (Inclusion Introduction)

    3.  $ab {\subseteq}ab$ (Reflexivity)

    4.  $ {b ~\bot_{a}~ cd}{\wedge}ab {\subseteq}ab {\wedge}ac'd' {\subseteq}acd  \vdash abc'd' {\subseteq}abcd$ (Chase Rule)

    5.  $abc' {\subseteq}abc$ (Projection and Permutation)

    6.  $ac{\subseteq}ac' {\wedge}{b ~\bot_{a}~ c'} {\wedge}abc' {\subseteq}abc \vdash {b ~\bot_{a}~ c}$ (Final Rule)

Our results shows that for any consequence ${\vec{b} ~\bot_{\vec{a}}~ \vec{c}}$ of ${\Sigma}$ there is a deduction starting with an application of Start Axiom and ending with an application of Final Rule.

[^1]: Department of Mathematics and Statistics, University of Helsinki, Finland. `miika.hannula@helsinki.fi`

[^2]: Department of Mathematics and Statistics, University of Helsinki, Finland. `juha.kontinen@helsinki.fi`

[^3]: The authors were supported by grant 264917 of the Academy of Finland.
