<p>Suppose we have a Boolean formula <span class="math-container">$\phi(X,Y)$</span> over the sets of Boolean variables <span class="math-container">$X$</span> and <span class="math-container">$Y$</span>, representing a binary relation. There are in general many tuples in this relation.</p>
<p>Is there a way to augment the formula to a <span class="math-container">$\phi'(X,Y,Z)$</span> such that the extra variables from <span class="math-container">$Z$</span> act as a primary key? More precisely, we want that any satisfying assignment <span class="math-container">$\nu$</span> for <span class="math-container">$\phi'$</span> also satisfies <span class="math-container">$\phi$</span> when restricted to the original variables, and for any two assignments <span class="math-container">$\nu$</span> and <span class="math-container">$\nu'$</span> for <span class="math-container">$\phi'$</span>, <span class="math-container">$\nu(Z)=\nu'(Z)$</span> implies that <span class="math-container">$\nu(X,Y)=\nu'(X,Y)$</span> (with some notation abuse, forgive me).</p>
<p>The obvious way would be to enumerate all the assignments. For example, for a formula <span class="math-container">$x\lor y$</span>, which has 3 assignments, one may end up with:</p>
<p><span class="math-container">\begin{equation}
(z_1\lor z_0) \land 
(z_1\land z_0 \to x \land y) 
\land (z_1 \land \neg z_0 \to x \land \neg y) 
\land (\neg z_1 \land z_0 \to \neg x\land y)
\end{equation}</span></p>
<p>But this is of course exponential and useless. Is there any hope to do better? Am I missing something obvious?</p>

CC BY-SA 4.0
2022-11-01T23:56:36.520Z
What about $\phi(X,Y)\wedge (Z_0=X)\wedge (Z_1=Y)$?
Wei Zhan
CC BY-SA 4.0
2022-11-02T06:08:11.087Z
When you write "any assignment $\nu$ for $\phi'$", do you actually mean "any assignment $\nu$ that satisfies $\phi'$"?
D.W.
CC BY-SA 4.0
2022-11-02T10:01:20.613Z
Hi, yes, of course. I've edited the question.
Nicola Gigante
<lo.logic><db.databases><boolean-formulas>
Making primary keys explicit in a Boolean relation
Nicola Gigante
# Making primary keys explicit in a Boolean relation

(Asked by: username_0 on 2022-11-01)

Suppose we have a Boolean formula $\phi(X,Y)$ over the sets of Boolean variables $X$ and $Y$, representing a binary relation. There are in general many tuples in this relation.

Is there a way to augment the formula to a $\phi'(X,Y,Z)$ such that the extra variables from $Z$ act as a primary key? More precisely, we want that any satisfying assignment $\nu$ for $\phi'$ also satisfies $\phi$ when restricted to the original variables, and for any two assignments $\nu$ and $\nu'$ for $\phi'$, $\nu(Z)=\nu'(Z)$ implies that $\nu(X,Y)=\nu'(X,Y)$ (with some notation abuse, forgive me).

The obvious way would be to enumerate all the assignments. For example, for a formula $x\lor y$, which has 3 assignments, one may end up with:

\begin{equation}
(z\_1\lor z\_0) \land
(z\_1\land z\_0 \to x \land y)
\land (z\_1 \land \neg z\_0 \to x \land \neg y)
\land (\neg z\_1 \land z\_0 \to \neg x\land y)
\end{equation}

But this is of course exponential and useless. Is there any hope to do better? Am I missing something obvious?

**Tags:** lo.logic, db.databases, boolean-formulas
> **Comments:**
> **username_1**: What about $\phi(X,Y)\wedge (Z_0=X)\wedge (Z_1=Y)$?  
> **username_2**: When you write "any assignment $\nu$ for $\phi'$", do you actually mean "any assignment $\nu$ that satisfies $\phi'$"?  
> **username_0**: Hi, yes, of course. I've edited the question.  

---

## 0 answers

