Horn Formulas and the Production Retrieval Problem

Prove that every set of Horn formulas has a model, that is, an interpretation in which all of them are true.

Prove that if a CNF, in each elementary conjunction, contains exactly one variable without negation, then it is equivalent to a conjunction of Horn formulas.

Let $J_{i}, i=1, \ldots , n$ be interpretations. Call their intersection the interpretation $K=J_{1} \ldots J_{n}$ such that for any variable $x$, $K(x)=1$ if and only if $J_{i}(x)=1$ for all $i=1, \ldots , n$. Prove that if a Horn formula has models $J_{i}, i=1, \ldots , n$, then their intersection $K=J_{1} \ldots J_{n}$ is also a model of it.

Prove that a formula $\Phi$ is equivalent to a conjunction of Horn formulas if and only if its abridged CNF contains, in each elementary disjunction, exactly one variable without negation.

Prove that the sequence of processes $\tau_{i}$ in the proof of theorem 37 on p. 121 is correctly defined, that is, all the input products of each process in this sequence are available before it is started.

Recall the construction from that proof. Suppose $F \Rightarrow \left(\varphi_{X} \rightarrow y\right)$. The sequence $\tau$, together with sets of products $X_{i}$ obtainable from $X$ using $\tau_{i}$, is built step by step:

• Step $0$: $\tau_{0}=\varnothing$, $X_{0}=X$.

• Step $1$: $\tau_{1}=\left\{ t \in F : L_{t} \subseteq X_{0}\right\}$, $X_{1}=X_{0} \cup \left\{ b_{t} : t \in \tau_{1}\right\}$.

• Step $i+1$: given $\tau_{i}$ and $X_{i}$, let $\tau_{i+1}^{\prime }=\left\{ t \in \left(F \backslash \tau_{i}\right) : L_{t} \subseteq X_{i}\right\}$, $X_{i+1}=X_{i} \cup \left\{ b_{t} : t \in \tau_{i+1}^{\prime }\right\}$, and $\tau_{i+1}=\left(\tau_{i}, \tau_{i+1}^{\prime }\right)$ (processes within $\tau_{i+1}^{\prime }$ taken in an arbitrary order). The procedure stops, setting $\tau =\tau_{i+1}$, once $y \in X_{i+1}$ or $X_{i}=X_{i+1}$.

Prove theorem 38 on p. 124.

Theorem 38: The algorithm Closure$(X, F)$ returns the set $\operatorname {cl}(X, F)$, and the algorithm ForwardWave$(X, y, F)$ returns "yes" if and only if $F \Rightarrow \left(\varphi_{X} \rightarrow y\right)$.

Hint. Let $N_{k}$ be the value of $N$ after $k$ iterations of the main loop of the algorithm Closure in lines $7-14$. Show that for every product $z \in \operatorname {cl}(X, F)$ that can be obtained from $X$ by a chain of processes of length $k$ or less, $z$ belongs to $N_{k}$.

The algorithm ForwardWave $(X, y, F)$ allows answering the question of whether it is possible to produce $y$ from the input products $X$ using the processes $F$, but it does not build a chain of processes leading to $y$. Modify the algorithm Closure $(X, F)$ so that from its result, for any product $a \in \operatorname {cl}(X, F)$, a chain of processes leading to $a$ can be constructed.

Call a process $t$ a compound technological process if, from a set of input products $L_{t}$, it simultaneously produces some set of products $B_{t}$ (rather than a single product $b_{t}$). Prove that a compound technological process corresponds to a conjunction of Horn formulas.

Generalize the algorithm Closure $(X, F)$ so that it constructs the closure of $X$ with respect to a system of compound technological processes $F$.

Determine which chain of processes in example 25 on the preceding page leads to obtaining $a$.

Example 25: $A=\left\{ a, b, c, d, e, f, g, h\right\}$, $X=\left\{ b, f\right\}$, and the set of processes $F$ consists of the following six processes:

Using the algorithm Closure, compute the closure for the set of input products $X=\left\{ c, d\right\}$ and the system of technological processes $F$:

Determine which chain of processes leads to obtaining $e$.

Prove theorem 39 on p. 127.

Theorem 39: The algorithm OptClosure$(X, F)$ constructs the closure $\operatorname {cl}(X, F)$.

Hint. Let $N_{k}$ be the value of $N, A_{k}$ the value of $A$, and $C_{k}$ the value of $C$ after $k$ iterations of the main loop of the algorithm OptClosure in lines $17-29$. Show that

Modify the algorithm OptClosure so that from its result, for any product $a \in \operatorname {cl}(X, F)$, a chain of processes leading to $a$ can be constructed.

Using the algorithm OptClosure, compute the closure for the set of input attributes $X=\left\{ a, f\right\}$ and the following system of dependencies $F$:

Determine which chain of processes leads to obtaining $h$.