††thanks: These two authors contributed equally.††thanks: These two authors
contributed equally.

# Uncovering Emergent Spacetime Supersymmetry with Rydberg Atom Arrays

Chengshu Li  Institute for Advanced Study, Tsinghua University, Beijing,
100084, China  Shang Liu  Kavli Institute for Theoretical Physics, University
of California, Santa Barbara, California 93106, USA  Hanteng Wang  Institute
for Advanced Study, Tsinghua University, Beijing, 100084, China  Wenjun Zhang
Department of Physics and State Key Laboratory of Low Dimensional Quantum
Physics, Tsinghua University, Beijing, 100084, China  Zi-Xiang Li  Beijing
National Laboratory for Condensed Matter Physics and Institute of Physics,
Chinese Academy of Sciences, Beijing 100190, China  University of Chinese
Academy of Sciences, Beijing 100049, China  Hui Zhai  Institute for Advanced
Study, Tsinghua University, Beijing, 100084, China  Hefei National Laboratory,
Hefei 230088, China  Yingfei Gu<EMAIL_ADDRESS>Institute for
Advanced Study, Tsinghua University, Beijing, 100084, China

(July 21, 2024)

###### Abstract

In the zoo of emergent symmetries in quantum many-body physics, the previously
unrealized emergent spacetime supersymmetry (SUSY) is particularly intriguing.
Although it was known that spacetime SUSY could emerge at the (1+1)d
tricritical Ising transition, an experimental realization is still absent. In
this letter, we propose to realize the tricritical Ising transition with
Rydberg atom arrays, taking advantage of the reconfigurability of these
systems. In such systems, the spacetime SUSY manifests itself in the
respective correlation functions of a bosonic mode and its fermionic partner.
However, the correlation function of the fermionic mode inevitably involves a
string operator, making direct measurement challenging in the conventional
setting. Here, we utilize the analog–digital hybrid nature of the Rydberg atom
arrays, which can simulate a physical Hamiltonian and perform a digital
quantum circuit on the same platform, to measure the correlation function of
the fermionic mode. This hybridized protocol provides an experimentally
feasible way to reveal the hidden structure of the spacetime SUSY that emerges
at the tricritical Ising transition.

Introduction. Spacetime supersymmetry (SUSY) was proposed in the ’70s as a new
type of symmetry of spacetime and fundamental particles [1, 2]. It exchanges
bosons and fermions and provides appealing solutions to long-standing problems
in particle physics, such as the hierarchy problem [3]. However, the
experimental evidence of SUSY has not been observed up to the highest energy
we can reach in particle accelerators so far. An opposite strategy is to
realize SUSY as an emergent symmetry at low energy in quantum many-body
systems – a fascinating phenomenon where the low-energy states possess larger
symmetries than the physical Hamiltonian. This phenomenon often occurs when
the system is fine-tuned to a quantum critical point [4].

Early in the ’80s, it was known that spacetime SUSY could emerge at (1+1)
dimensional tricritical Ising transition [5, 6]. From the Landau–Ginzburg
perspective, the conventional second-order Ising transition is described by
the sign change of the quadratic term in a $\phi^{4}$ theory, where $\phi$ is
the order parameter. For a more general free energy functional
$\alpha\phi^{2}+\beta\phi^{4}+\phi^{6}$, a first-order transition could occur
at a critical line with $\alpha>0$ and $\beta<0$. The aforementioned
tricritical point refers to the meeting point of the above two transitions,
i.e. $\alpha=\beta=0$.

Continuous efforts have been made to realize the tricritical Ising transition
[7, 8, 9, 10, 11, 12, 13, 14, 15] (or other form of SUSY theories [16, 17, 18,
19, 20]). However, an experimental identification of spacetime SUSY is still
missing. In addition to the challenges in fine-tuning the model to the
tricritical point where the SUSY could emerge, there is another fundamental
difficulty in the characterization: the fermionic modes that emerge from the
underlying bosonic physical degrees of freedom inevitably involve non-local
string operators, whose detection often requires unconventional measurement
schemes [21, 22, 23, 24].

In the present letter, we propose to overcome these challenges with the
Rydberg atom array that has shown to be powerful in simulating quantum phases
of matter [25, 26, 27, 28, 29, 30, 31] and quantum information processing [32,
33, 34, 35, 36, 37, 38]. We demonstrate that the geometric reconfigurability
of the Rydberg atom array facilitates the realization of a tricritical Ising
point. Furthermore, we point out that the analog–digital hybrid nature [34] of
the platform is ideal for revealing the hidden structure of the emergent
spacetime SUSY. To be clearer, the hybrid nature here refers to the ability to
run analog quantum simulation and digital quantum circuits on the same
platform. More explicitly, the analog mode is based on the pseudo-spin doublet
consisting of one of the hyperfine levels in the electronic ground state
manifold and one Rydberg state. The tricritical Ising transition will be
realized in this mode. While in the digital mode, the data qubit is encoded
into two hyperfine levels, with the Rydberg state only used to mediate the
entangling gates [32]. This hybrid mode allows us to efficiently generate the
desired quantum many-body wave function via analog mode and coherently extract
the quantum correlation in the complex wave function with a digital quantum
circuit. In particular, we show that this hybrid protocol can be used to
measure non-local fermionic correlations to verify emergent SUSY.

Model. We consider a two-leg ladder geometry of atom arrays as shown in Fig.
1(a) where the horizontal and vertical separations between atoms are denoted
by $r_{1}$ and $r_{2}$ respectively. The two colors denote the two sets ($A$
and $B$) of atoms subjected to different Rydberg excitation lasers. This
scheme is readily realized in dual-species atom arrays [39, 40, 41, 42], where
the resonance frequencies of different Rydberg states are largely separated so
that crosstalk between different excitations is negligible. For simplicity,
although not necessary, we assume that two Rydberg excitations share equal
coupling strength $\Omega$ and equal detuning $\Delta$. In the following, we
set the Rabi frequency $\Omega=1$ as the energy unit. The interaction between
two Rydberg atoms is the van der Waals interaction given by $C_{XY}/r^{6}$
($X,Y=A$ or $B$). Here, we set $C_{AA}>0$, and we define a length unit $r_{0}$
by $C_{AA}/r_{0}^{6}=\Omega$.

Figure 1: (a) Layout of our model. Two colors denote two sets of atoms
subjected to different Rydberg excitation lasers. $r_{1}$ and $r_{2}$ denote
the nearest separation of atoms along the horizontal and vertical directions.
(b) The phase diagram computed for two-leg ladder geometry with $2\times 40$
sites. The solid line denotes a second-order transition, and the dashed line
denotes a first-order transition, with “TCI” denoting the tricritical point.
“Ferro” and “Disordered” denote the symmetry-breaking phase and the symmetric
phase. Here, the $\mathbb{Z}_{2}$ symmetry is the exchanging symmetry between
the upper and the lower legs. $\Delta$ is in unit of $\Omega$ and $r_{1}$ is
in unit of $r_{0}$ defined in the main text. Dots with a circle denote atoms
in the Rydberg state. (c) The central charge $c$ obtained from the
entanglement entropy at different given values of $r_{1}$. $c=7/10$ is the
central charge for the tricritical Ising point. The inset shows the fitting of
the subsystem entanglement entropy $S(j)$ as a function of the subsystem size
$j$ using the Calabrese–Cardy formula. The phase diagram is obtained by the
DMRG calculation with bond dimension $200$.

The Hamiltonian of this two-leg ladder two-sets Rydberg array is given by

$\hat{H}=\sum_{i}\left(\frac{\Omega}{2}\hat{\sigma}^{x}_{i}-\Delta\hat{n}_{i}\right)+\sum_{ij}\frac{C_{XY}}{r_{ij}^{6}}\hat{n}_{i}\hat{n}_{j}.$
(1)

It acts on the pseudo-spin states $|\\!\\!\downarrow\rangle_{i}$ and
$|\\!\\!\uparrow\rangle_{i}$ corresponding to the ground state $|g\rangle$ and
the Rydberg state $|r\rangle$ of atom $i$.
$\hat{n}_{i}=(1+\hat{\sigma}^{z}_{i})/2$ is the number of Rydberg excitations
on site $i$. The index $i=(i_{x},i_{y})$ labels the position of each atom with
$i_{y}=1$ or $2$ denoting the upper or lower leg, respectively. For $i_{x}$
being odd or even, the atoms belong to $A$ or $B$ subsets. Depending on
different quantum numbers of Rydberg states, the van der Waals interaction
between them can be either repulsive or attractive.

Phase Diagram. This two-leg ladder system has a $\mathbb{Z}_{2}$ symmetry as
the exchanging symmetry between the upper and the lower legs. Correspondingly,
the ground state of this system could exhibit two phases distinguished by
whether the $\mathbb{Z}_{2}$ symmetry is broken, with a first and/or second-
order transition between them. If both transitions are present, the
intersection of the two transition lines will be the desired tricritical Ising
point we aim for.

To show that the above conception can be realized in our model with realistic
experimental parameters, we set $C_{BB}=1.6C_{AA}$ and
$C_{AB}=C_{BA}=-0.97C_{AA}$ as an illustrating example 111These coefficients
are based on the existing dual-species platform, e.g. the Rydberg states of
$A$ and $B$ can be the ${}^{70}S_{1/2}$ and ${}^{73}S_{1/2}$ states of 85Rb
and 87Rb respectively [60]. Similar phase diagrams can be obtained for other
choices of atoms, for instance, the Rb–Cs mixture. and and obtain the phase
diagram shown in Fig. 1(b). In the computation, we have also fixed the spacing
between the upper and lower legs to be $r_{2}=0.5r_{0}$ so that the repulsive
interaction between two Rydberg states with the same $i_{x}$ is much larger
than $\Omega$ and therefore blockades the double occupancy of Rydberg states
in the same column. The left-over tuning parameters are detuning $\Delta$ and
horizontal spacing $r_{1}$, both are accurately accessible in the
reconfigurable atom array platform.

In the phase diagram, the $\mathbb{Z}_{2}$ symmetry-breaking phase (dubbed
“ferromagnetic”) occurs in the large $\Delta$ and small $r_{1}$ regime: the
larger $\Delta$ induces more Rydberg excitation, while the smaller $r_{1}$
leads to a stronger attractive interaction between horizontal neighbors (note
that $C_{AB}<0$), which favors the configuration that all Rydberg excitations
stay in the same row, resulting in the $\mathbb{Z}_{2}$ symmetry breaking
phase. Now, starting from the symmetry breaking phase, there are two ways to
restore symmetry: (1) shifting toward a more negative value for detuning
$\Delta$, which suppresses the Rydberg excitations and ultimately arrives at a
symmetric state without Rydberg excitation; (2) shifting towards larger
horizontal separation $r_{1}$, which reduces the attractive interaction and
therefore unlocks the correlating effects between different columns. Along
this direction, the ground state approximates the product of a symmetric
superposition of one Rydberg excitation on the upper row and one on the lower
row. It turns out that the transition along path 1 tends to be first order
while path 2 tends to be second order. Therefore, the turning point of these
two phase boundaries realizes a tricritical Ising transition point on the
$(r_{1},\Delta)$ parameter space.

Regarding the methodology, the phase diagram Fig. 1(b) is determined by a
combination of the order parameter and the subsystem entanglement entropy,
both extracted from the ground state wavefunction numerically calculated by
the density-matrix renormalization group (DMRG) method 222 The codes for our
numerical calculations are available at
https://github.com/chengshul/RydbergSUSY. Here the order parameter we choose
is the “magnetization” $n^{-}=n_{1}-n_{2}$, where
$n_{i_{y}}=L^{-1}\sum_{i_{x}=1}^{L}n_{i}$ with $i=(i_{x},i_{y})$ and $i_{y}=1$
or $2$. $n_{1}-n_{2}\neq 0$ indicates the $\mathbb{Z}_{2}$ symmetry breaking.
The first-order transition is signaled by an abrupt drop in the order
parameter. Therefore its location can be precisely determined. In contrast,
across the second-order transition, the order parameter vanishes continuously
and therefore does not trigger a sharp signal in numerics. To precisely
determine the location of the second-order phase transition, we compute the
central charge by fitting the entanglement entropy of the subsystem $S(j)$ to
the Calabrese–Cardy formula [45]
$S(j,L)=\frac{c}{3}\ln\left[\frac{L}{\pi}\sin\left(\frac{\pi
j}{L}\right)\right]+S_{0}$ with $j$ denoting the subsystem size and $L$ the
total size. A typical example is shown in the inset of Fig. 1(c). The central
charge $c$ obtained from the fitting exhibits a maximum at the second-order
phase boundary. Fig. 1(c) shows the central charge $c$ along the transition
line. One can see that $c$ approaches $1/2$ at the Ising transition line,
consistent with the prediction of Ising conformal field theory (CFT), and $c$
drops toward zero at the first-order transition. In between, $c$ peaked at the
tricritical point with the value $0.7$, consistent with the prediction of
supersymmetric CFT.

Figure 2: $\eta_{\varepsilon}$ and $\eta_{\psi}$ (see text for definition)
along the second-order transition line is plotted for different $r_{1}$. The
inset plots the spatial correlation functions
$\langle\varepsilon_{i}\varepsilon_{j}\rangle$ and
$-\left(\langle\gamma^{\prime}_{i}\gamma_{j}\rangle+\langle\gamma_{i}\gamma^{\prime}_{j}\rangle\right)$
as a function of $|r_{i}-r_{j}|$, which is a linear function under the log–log
plot. The slope of these two linear functions defines $\eta_{\varepsilon}$ and
$\eta_{\psi}$. The dashed line indicates that these two numbers differ by unit
at the ending point of the second-order transition at $r_{1}\approx 0.884$.

SUSY Manifestation. A key physical consequence of the emergent SUSY at the
critical point is that the scaling dimensions of a low-lying bosonic mode and
its fermionic superpartner differ by $1/2$. For a motivating and simplest
example, let us consider a $D$ dimensional (spacetime dimension)
supersymmetric theory of a free massless scalar paired with a massless free
fermion, with Lagrangian $\mathcal{L}_{\rm
SUSY}=\mathcal{L}_{B}[\phi]+\mathcal{L}_{F}[\psi]$. From the bosonic part
$\mathcal{L}_{B}=\int d^{D}{\bf r}(\partial\phi)^{2}$, we get the dimension of
$[\phi]$ from equation $2[\phi]=D-2$. Therefore, by dimensional analysis
$\langle\phi({\bf r}_{i})\phi({\bf r}_{j})\rangle\sim{1}/{|{\bf r}_{i}-{\bf
r}_{j}|^{D-2}}$. In parallel, the fermionic partner $\psi$ with
$\mathcal{L}_{F}=\int d^{D}{\bf r}\bar{\psi}i\not{\partial}\psi$ satisfies
$2[\psi]=D-1$ and, consequently, $\langle\psi({\bf r}_{i})\psi({\bf
r}_{j})\rangle\sim{1}/{|{\bf r}_{i}-{\bf r}_{j}|^{D-1}}$. The point is that
the exponents of these two decayed spatial correction functions of power law
differ by $1$, which is a measurable consequence of the SUSY we will
investigate in the following.

In contrast to the aforementioned free theory example, where SUSY is inherent,
our microscopic model (1) is constructed based on pseudo-spin degrees of
freedom, with SUSY emerging only at the tricritical point. In such a scenario,
it is generally challenging to identify the SUSY pair of fields that result
from a non-trivial renormalization group flow [46]. In this letter, we exploit
the aforementioned $\mathbb{Z}_{2}$ symmetry to identify the SUSY pair in our
model. In the field-theoretic description of the tricritical Ising transition,
there is a $\mathbb{Z}_{2}$-even real bosonic field $\varepsilon$ representing
the “energy”, and a natural candidate in our microscopic model is the sum of
Rydberg excitation numbers on each rung, by an abuse of notation let us denote
$\varepsilon_{i}=\hat{n}^{+}_{i}=\hat{n}_{(i,1)}+\hat{n}_{(i,2)}$. Under SUSY,
this $\mathbb{Z}_{2}$-even operator should be related to a pair of
$\mathbb{Z}_{2}$-odd real fermion operators. A simple $\mathbb{Z}_{2}$-odd
lattice operator is $\hat{n}^{-}_{i}=\hat{n}_{(i,1)}-\hat{n}_{(i,2)}$.
However, $\hat{n}^{-}_{i}$ itself is not yet a fermionic operator. To finish
the construction, we need to attach a Jordan–Wigner string so that distant
fermion operators anticommute. This gives two natural candidates:

$\hat{\gamma}_{i}=\bigg{(}\prod\limits_{j=1}^{i-1}\operatorname{SWAP}_{j}\bigg{)}\hat{n}^{-}_{i},\quad\hat{\gamma}^{\prime}_{i}=\bigg{(}\prod\limits_{j=1}^{i}\operatorname{SWAP}_{j}\bigg{)}\hat{n}^{-}_{i},$
(2)

where the swap operator $\operatorname{SWAP}_{j}$ applies an exchange between
the upper and the lower legs at site-$j$ onto the quantum state. Their linear
combination corresponds to the time reversal pair of fermion fields in the
continuum field theory, i.e. $\psi=\hat{\gamma}-i\hat{\gamma}^{\prime}$ and
$\bar{\psi}=\hat{\gamma}+i\hat{\gamma}^{\prime}$ with abuse of notation.

Now, to establish the SUSY relation, we need to check the exponents of the
decayed spatial correlation function of the bosonic $\varepsilon$ and
fermionic $\psi$ (or $\bar{\psi}$, as they have the same scaling dimension).
For the former, we need to measure the correlation function of the local
operator $\varepsilon_{i}=\hat{n}_{(i,1)}+\hat{n}_{(i,2)}$, that is,

$\langle\varepsilon_{i}\varepsilon_{j}\rangle\sim{1}/{|{\bf r}_{i}-{\bf
r}_{j}|^{\eta_{\varepsilon}}},$ (3)

and extract the exponent $\eta_{\varepsilon}$. For the fermionic operator
$\psi$, we need to extract the exponent $\eta_{\psi}$ from the following
correlation function

$\langle\psi_{i}\psi_{j}\rangle=-i\left(\langle\gamma^{\prime}_{i}\gamma_{j}\rangle+\langle\gamma_{i}\gamma^{\prime}_{j}\rangle\right)\sim{1}/{|{\bf
r}_{i}-{\bf r}_{j}|^{\eta_{\psi}}},$ (4)

where in the first step we have used the property that
$\langle\gamma_{i}\gamma_{j}\rangle=\langle\gamma^{\prime}_{i}\gamma^{\prime}_{j}\rangle=0$
enforced by the time-reversal symmetry. Note the correlation function
$\langle\gamma^{\prime}_{i}\gamma_{j}\rangle$ or
$\langle\gamma_{i}\gamma^{\prime}_{j}\rangle$ involves a non-local string
operator, for instance

$-\langle\gamma^{\prime}_{i}\gamma_{j}\rangle=\langle\hat{n}^{-}_{i}\bigg{(}\prod\limits_{k=i+1}^{j-1}\operatorname{SWAP}_{k}\bigg{)}\hat{n}^{-}_{j}\rangle$
(5)

The SUSY in our model manifests itself as $\eta_{\psi}-\eta_{\varepsilon}=1$.

We show in Fig. 2 the numerical results for the equal-time correlation
functions $\langle\varepsilon_{i}\varepsilon_{j}\rangle$ and
$-\left(\langle\gamma^{\prime}_{i}\gamma_{j}\rangle+\langle\gamma_{i}\gamma^{\prime}_{j}\rangle\right)$.
The inset confirms the power-law behavior of the two correlation functions at
the tricritical point. From the slope of the log–log plot, we can extract the
exponent as shown in Fig. 2. It verifies clearly that at the end point of the
second-order transition line, these two powers $\eta_{\varepsilon}$ and
$\eta_{\psi}$ differ by $1$, which is direct evidence of the emergent SUSY.
Away from the tricritical point, the relation fails.

Measuring fermionic correlation on Rydberg atom array. Measuring the non-local
string operator in (5) with a set of SWAP is generally difficult. The
situation is similar to the measurement of the second Renyi entropy where a
many-body interference between two identical copies of quantum states is
performed [47, 48]. Here, we need to interfere with two subsets of our single
quantum state. To accomplish the measurement, we can utilize the hybrid nature
of the Rydberg atom array platform to perform a quantum version of the
“analog-to-digital converter” and then process the quantum data via a
measurement circuit consisting of entangling gates between the upper and lower
chains.

Figure 3: (a) $\ket{0}$ and $\ket{1}$ are two hyperfine levels of the
electronic ground state, and $\ket{r}$ is a Rydberg state. $\ket{0}=|g\rangle$
and $\ket{r}$ are used for quantum simulation and $\ket{0}$ and $\ket{1}$ form
a basis for digital quantum computation. The blue line denotes the Rydberg
coupling $\Omega$ in the many-body Hamiltonian (1), and the orange line
represents the qADC coupling that transfers a many-body wave function into the
quantum computation basis. (b) Schematic of the time sequence of turning off
the Rydberg coupling and the AtoD pulse. (c) After the qADC, we use the
quantum circuit shown in the box to process the quantum many-body wave
function to measure the fermionic correlation function (4). The tables in the
last raw summarize the correspondence between the measurement outcome and the
eigenvalue of $\operatorname{SWAP}$ and $n^{-}$.

A quantum Analog-to-Digital Converter (qADC) and its partner quantum Digitial-
to-Analog Converter (qDAC) map between the “analog basis”
$\\{|g\rangle,|r\rangle\\}$ (“ground state” and “Rydberg state”) and the
“digital basis” $\\{|0\rangle,|1\rangle\\}$. In the Rydberg atom, these two
Hilbert spaces are embedded in the rich atomic levels. For instance, in the
87Rb atom, the digital basis can be chosen as the two hyperfine spin levels of
the ground state, and one of them, say $|0\rangle$ can be used for the ground
state $|g\rangle$ in the analog basis as well. For this three-level system,
the qADC can be realized by stimulated Raman adiabatic passage (STIRAP) [49]
where an additional laser is applied to coherently transfer the Rydberg state
$|r\rangle$ to the hyperfine $|1\rangle$ state, while keeping the
$|g\rangle=|0\rangle$ state invariant. In this protocol, an optimization
between the qADC pulse and the Rydberg laser in the analog mode is expected to
mitigate the dephasing error caused by the turning off of the Rydberg laser
that couples the analog basis. Alternatively, one can also realize the qADC
via a two-step process, named the coherent mapping protocol in Ref. [34],
where the ground state $|g\rangle$ (identified as $|1\rangle$ in this
protocol) is transferred to digital $|0\rangle$ and then $|r\rangle$ is
transferred to $|1\rangle$.

Following the qADC, we can utilize the quantum computation architecture to
process the many-body wavefunction in the digital basis where $|0\rangle$
represents the empty states and $|1\rangle$ represents the states with Rydberg
excitation. For each rung in the ladder, we have three allowed states
$|00\rangle$, $\frac{1}{\sqrt{2}}(|01\rangle+|10\rangle)$,
$\frac{1}{\sqrt{2}}(|01\rangle-|10\rangle)$ with eigenvalue $1$,$1$,$-1$ under
SWAP respectively. To single out the last state, we run a measurement circuit
shown as Fig. 3 (c) and collect the instance with measurement outcome
$|11\rangle$ in the computation basis. Then the fermionic correlator (4) is
obtained as

$\langle(-1)^{{\rm\\#|11\rangle~{}pairs~{}between}~{}(i,j)}~{}\hat{n}^{-}_{i}\hat{n}^{-}_{j}\rangle.$
(6)

Namely, the measurement of $\langle\psi_{i}\psi_{j}\rangle$ amounts to
averaging the measurements of two local operators $\hat{n}^{-}_{i}$
$\hat{n}^{-}_{j}$, with an additional phase $-1$ assigned to all the instances
with odd number of $|11\rangle$ between site $i$ and $j$.

Summary and Outlook. In this work, we show that a two-leg ladder Rydberg array
structure with two sets of Rydberg excitations is sufficient to realize the
tricritical Ising transition where the spacetime SUSY emerges. This proposed
setup is especially suitable for the dual-species Rydberg atom platforms where
the two Rydberg excitations can be implemented without cross-talk. We would
like to remark that unlike the single chain model discussed in literature [50,
25, 51] where the Ising symmetry is realized as a translation by one lattice
spacing, here the Ising $\mathbb{Z}_{2}$ symmetry is realized as the
exchanging between two rails of the ladder. Combining this geometric
realization of the internal symmetry with the reconfigurability of the atom
array, one can further study how various boundary conditions can be realized
geometrically [52]. We would also like to mention that a quick diagnosis of
the tricritical point without resorting to correlation measurements can be
carried out with a Kibble–Zurek ramping [53, 54, 55], with the universal
exponent $\mu=5/14$.

To manifest the emergent SUSY encoded in the many-body wavefunction, we
leverage the analog–digital hybrid nature of the Rydberg atom platform. This
involves directly loading the “experimental data” prepared by the analog mode
to the “quantum computer” in the digital mode via a quantum Analog-to-Digital
converter (qADC). By processing the data through quantum circuits, we can
access the information that is difficult to retrieve in conventional
experiments where the data are processed classically [56, 57, 58].

Additionally, we envision that a quantum Digital-to-Analog Converter (qDAC)
holds potential in the quantum simulation of many-body physics. Using the
quantum circuit module, more interesting initial states can be prepared and
sent to the quantum simulator, opening new possibilities for exploring many-
body quantum dynamics.

Acknowledgments. We thank Wenlan Chen, Xun Gao, Jiazhong Hu, Xiaodong He,
Xiao-Liang Qi, Kunpeng Wang, Peng Xu and Tao Zhang for discussions. We
acknowledge financial support from the Innovation Program for Quantum Science
and Technology 2021ZD0302005, the NSFC Grant No. 12042505 and U23A6004, the
National Key R&D Program of China 2023YFA1406702, and the Tsinghua University
Dushi Program. S.L. is supported by the Gordon and Betty Moore Foundation
under Grant No. GBMF8690 and the National Science Foundation under Grant No.
NSF PHY-1748958. Z.X.L. is supported by the NSFC under Grant No. 12347107.
H.Z. acknowledges support from the XPLORER Prize. Y.G. acknowledges support
from the DAMO Academy Young Fellow program. The DMRG calculations are
performed using the ITensor library (v0.3) [59].

## References

  * Gervais and Sakita [1971] J.-L. Gervais and B. Sakita, Field Theory Interpretation of Supergauges in Dual Models, Nucl. Phys. B 34, 632 (1971).
  * Wess and Zumino [1974] J. Wess and B. Zumino, Supergauge Transformations in Four-Dimensions, Nucl. Phys. B 70, 39 (1974).
  * Dimopoulos and Georgi [1981] S. Dimopoulos and H. Georgi, Softly Broken Supersymmetry and SU(5), Nucl. Phys. B 193, 150 (1981).
  * Sachdev [2011] S. Sachdev,  _Quantum Phase Transitions_ , 2nd ed. (Cambridge University Press, 2011).
  * Friedan  _et al._ [1985] D. Friedan, Z. Qiu, and S. Shenker, Superconformal invariance in two dimensions and the tricritical Ising model, Phys. Lett. B 151, 37 (1985).
  * Zamolodchikov [1986] A. B. Zamolodchikov, Conformal symmetry and multicritical points in two-dimensional quantum field theory, Sov. J. Nucl. Phys. 44, 529 (1986).
  * Blume [1966] M. Blume, Theory of the First-Order Magnetic Phase Change in U${\mathrm{O}}_{2}$, Phys. Rev. 141, 517 (1966).
  * Capel [1966] H. Capel, On the possibility of first-order phase transitions in Ising systems of triplet ions with zero-field splitting, Physica 32, 966 (1966).
  * Alcaraz  _et al._ [1985] F. C. Alcaraz, J. R. Drugowich de Felício, R. Köberle, and J. F. Stilck, Hamiltonian studies of the Blume-Emery-Griffiths model, Phys. Rev. B 32, 7469 (1985).
  * Grover  _et al._ [2014] T. Grover, D. N. Sheng, and A. Vishwanath, Emergent Space-Time Supersymmetry at the Boundary of a Topological Phase, Science 344, 280 (2014).
  * Rahmani  _et al._ [2015] A. Rahmani, X. Zhu, M. Franz, and I. Affleck, Emergent Supersymmetry from Strongly Interacting Majorana Zero Modes, Phys. Rev. Lett. 115, 166401 (2015).
  * Li  _et al._ [2017] Z.-X. Li, Y.-F. Jiang, and H. Yao, Edge Quantum Criticality and Emergent Supersymmetry in Topological Phases, Phys. Rev. Lett. 119, 107202 (2017).
  * O’Brien and Fendley [2018] E. O’Brien and P. Fendley, Lattice Supersymmetry and Order-Disorder Coexistence in the Tricritical Ising Model, Phys. Rev. Lett. 120, 206403 (2018).
  * Li  _et al._ [2020] C. Li, H. Ebisu, S. Sahoo, Y. Oreg, and M. Franz, Coupled wire construction of a topological phase with chiral tricritical Ising edge modes, Phys. Rev. B 102, 165123 (2020).
  * Maffi  _et al._ [2024] L. Maffi, N. Tausendpfund, M. Rizzi, and M. Burrello, Quantum Simulation of the Tricritical Ising Model in Tunable Josephson Junction Ladders, Phys. Rev. Lett. 132, 226502 (2024).
  * Lee [2007] S.-S. Lee, Emergence of supersymmetry at a critical point of a lattice model, Phys. Rev. B 76, 075103 (2007).
  * Yu and Yang [2010] Y. Yu and K. Yang, Simulating the Wess-Zumino Supersymmetry Model in Optical Lattices, Phys. Rev. Lett. 105, 150605 (2010).
  * Jian  _et al._ [2015] S.-K. Jian, Y.-F. Jiang, and H. Yao, Emergent Spacetime Supersymmetry in 3D Weyl Semimetals and 2D Dirac Semimetals, Phys. Rev. Lett. 114, 237001 (2015).
  * Jian  _et al._ [2017] S.-K. Jian, C.-H. Lin, J. Maciejko, and H. Yao, Emergence of Supersymmetric Quantum Electrodynamics, Phys. Rev. Lett. 118, 166802 (2017).
  * Li  _et al._ [2018] Z.-X. Li, A. Vaezi, C. B. Mendl, and H. Yao, Numerical observation of emergent spacetime supersymmetry at quantum criticality, Sci. Adv. 4, eaau1463 (2018).
  * Endres  _et al._ [2011] M. Endres, M. Cheneau, T. Fukuhara, C. Weitenberg, P. Schauß, C. Gross, L. Mazza, M. C. Bañuls, L. Pollet, I. Bloch, and S. Kuhr, Observation of Correlated Particle-Hole Pairs and String Order in Low-Dimensional Mott Insulators, Science 334, 200 (2011).
  * Hilker  _et al._ [2017] T. A. Hilker, G. Salomon, F. Grusdt, A. Omran, M. Boll, E. Demler, I. Bloch, and C. Gross, Revealing hidden antiferromagnetic correlations in doped Hubbard chains via string correlators, Science 357, 484 (2017).
  * Chiu  _et al._ [2019] C. S. Chiu, G. Ji, A. Bohrdt, M. Xu, M. Knap, E. Demler, F. Grusdt, M. Greiner, and D. Greif, String patterns in the doped Hubbard model, Science 365, 251 (2019).
  * de Léséleuc  _et al._ [2019] S. de Léséleuc, V. Lienhard, P. Scholl, D. Barredo, S. Weber, N. Lang, H. P. Büchler, T. Lahaye, and A. Browaeys, Observation of a symmetry-protected topological phase of interacting bosons with Rydberg atoms, Science 365, 775 (2019).
  * Bernien  _et al._ [2017] H. Bernien, S. Schwartz, A. Keesling, H. Levine, A. Omran, H. Pichler, S. Choi, A. S. Zibrov, M. Endres, M. Greiner, V. Vuletić, and M. D. Lukin, Probing many-body dynamics on a 51-atom quantum simulator, Nature 551, 579 (2017).
  * Browaeys and Lahaye [2020] A. Browaeys and T. Lahaye, Many-body physics with individually controlled Rydberg atoms, Nat. Phys. 16, 132 (2020).
  * Ebadi  _et al._ [2021] S. Ebadi, T. T. Wang, H. Levine, A. Keesling, G. Semeghini, A. Omran, D. Bluvstein, R. Samajdar, H. Pichler, W. W. Ho, S. Choi, S. Sachdev, M. Greiner, V. Vuletić, and M. D. Lukin, Quantum phases of matter on a 256-atom programmable quantum simulator, Nature 595, 227 (2021).
  * Scholl  _et al._ [2021] P. Scholl, M. Schuler, H. J. Williams, A. A. Eberharter, D. Barredo, K.-N. Schymik, V. Lienhard, L.-P. Henry, T. C. Lang, T. Lahaye, A. M. Läuchli, and A. Browaeys, Quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms, Nature 595, 233 (2021).
  * Semeghini  _et al._ [2021] G. Semeghini, H. Levine, A. Keesling, S. Ebadi, T. T. Wang, D. Bluvstein, R. Verresen, H. Pichler, M. Kalinowski, R. Samajdar, A. Omran, S. Sachdev, A. Vishwanath, M. Greiner, V. Vuletić, and M. D. Lukin, Probing topological spin liquids on a programmable quantum simulator, Science 374, 1242 (2021).
  * Fang  _et al._ [2024] F. Fang, K. Wang, V. S. Liu, Y. Wang, R. Cimmino, J. Wei, M. Bintz, A. Parr, J. Kemp, K.-K. Ni, and N. Y. Yao, Probing critical phenomena in open quantum systems using atom arrays (2024), arXiv:2402.15376 [quant-ph] .
  * Cheng and Zhai [2024] Y. Cheng and H. Zhai, Emergent Gauge Theory in Rydberg Atom Arrays (2024), arXiv:2401.07708 [cond-mat.quant-gas] .
  * Saffman  _et al._ [2010] M. Saffman, T. G. Walker, and K. Mølmer, Quantum information with Rydberg atoms, Rev. Mod. Phys. 82, 2313 (2010).
  * Morgado and Whitlock [2021] M. Morgado and S. Whitlock, Quantum simulation and computing with Rydberg-interacting qubits, AVS Quantum Sci. 3, 023501 (2021).
  * Bluvstein  _et al._ [2022] D. Bluvstein, H. Levine, G. Semeghini, T. T. Wang, S. Ebadi, M. Kalinowski, A. Keesling, N. Maskara, H. Pichler, M. Greiner, V. Vuletić, and M. D. Lukin, A quantum processor based on coherent transport of entangled atom arrays, Nature 604, 451 (2022).
  * Ma  _et al._ [2023] S. Ma, G. Liu, P. Peng, B. Zhang, S. Jandura, J. Claes, A. P. Burgers, G. Pupillo, S. Puri, and J. D. Thompson, High-fidelity gates and mid-circuit erasure conversion in an atomic qubit, Nature 622, 279 (2023).
  * Scholl  _et al._ [2023] P. Scholl, A. L. Shaw, R. B.-S. Tsai, R. Finkelstein, J. Choi, and M. Endres, Erasure conversion in a high-fidelity Rydberg quantum simulator, Nature 622, 273 (2023).
  * Singh  _et al._ [2023] K. Singh, C. E. Bradley, S. Anand, V. Ramesh, R. White, and H. Bernien, Mid-circuit correction of correlated phase errors using an array of spectator qubits, Science 380, 1265 (2023).
  * Bluvstein  _et al._ [2024] D. Bluvstein, S. J. Evered, A. A. Geim, S. H. Li, H. Zhou, T. Manovitz, S. Ebadi, M. Cain, M. Kalinowski, D. Hangleiter, J. P. Bonilla Ataides, N. Maskara, I. Cong, X. Gao, P. Sales Rodriguez, T. Karolyshyn, G. Semeghini, M. J. Gullans, M. Greiner, V. Vuletić, and M. D. Lukin, Logical quantum processor based on reconfigurable atom arrays, Nature 626, 58 (2024).
  * Zeng  _et al._ [2017] Y. Zeng, P. Xu, X. He, Y. Liu, M. Liu, J. Wang, D. J. Papoular, G. V. Shlyapnikov, and M. Zhan, Entangling Two Individual Atoms of Different Isotopes via Rydberg Blockade, Phys. Rev. Lett. 119, 160502 (2017).
  * Sheng  _et al._ [2022] C. Sheng, J. Hou, X. He, K. Wang, R. Guo, J. Zhuang, B. Mamat, P. Xu, M. Liu, J. Wang, and M. Zhan, Defect-Free Arbitrary-Geometry Assembly of Mixed-Species Atom Arrays, Phys. Rev. Lett. 128, 083202 (2022).
  * Singh  _et al._ [2022] K. Singh, S. Anand, A. Pocklington, J. T. Kemp, and H. Bernien, Dual-Element, Two-Dimensional Atom Array with Continuous-Mode Operation, Phys. Rev. X 12, 011040 (2022).
  * Anand  _et al._ [2024] S. Anand, C. E. Bradley, R. White, V. Ramesh, K. Singh, and H. Bernien, A dual-species Rydberg array (2024), arXiv:2401.10325 [quant-ph] .
  * Note [1] These coefficients are based on the existing dual-species platform, e.g. the Rydberg states of $A$ and $B$ can be the ${}^{70}S_{1/2}$ and ${}^{73}S_{1/2}$ states of 85Rb and 87Rb respectively [60]. Similar phase diagrams can be obtained for other choices of atoms, for instance, the Rb–Cs mixture.
  * Note [2] The codes for our numerical calculations are available at https://github.com/chengshul/RydbergSUSY.
  * Calabrese and Cardy [2004] P. Calabrese and J. Cardy, Entanglement entropy and quantum field theory, J. Stat. Mech.: Theory Exp. 2004 (06), P06002.
  * Zou and Vidal [2020] Y. Zou and G. Vidal, Emergence of conformal symmetry in quantum spin chains: Antiperiodic boundary conditions and supersymmetry, Phys. Rev. B 101, 045132 (2020).
  * Daley  _et al._ [2012] A. J. Daley, H. Pichler, J. Schachenmayer, and P. Zoller, Measuring entanglement growth in quench dynamics of bosons in an optical lattice, Phys. Rev. Lett. 109, 020505 (2012).
  * Islam  _et al._ [2015] R. Islam, R. Ma, P. M. Preiss, M. Eric Tai, A. Lukin, M. Rispoli, and M. Greiner, Measuring entanglement entropy in a quantum many-body system, Nature 528, 77 (2015).
  * Vitanov  _et al._ [2017] N. V. Vitanov, A. A. Rangelov, B. W. Shore, and K. Bergmann, Stimulated Raman adiabatic passage in physics, chemistry, and beyond, Rev. Mod. Phys. 89, 015006 (2017).
  * Fendley  _et al._ [2004] P. Fendley, K. Sengupta, and S. Sachdev, Competing density-wave orders in a one-dimensional hard-boson model, Phys. Rev. B 69, 075106 (2004).
  * Slagle  _et al._ [2021] K. Slagle, D. Aasen, H. Pichler, R. S. K. Mong, P. Fendley, X. Chen, M. Endres, and J. Alicea, Microscopic characterization of Ising conformal field theory in Rydberg chains, Phys. Rev. B 104, 235109 (2021).
  * [52] C. Li _et al._ , Geometric Realization of Boundary Conditions in Reconfigurable Rydberg Arrays, to appear.
  * Kibble [1976] T. W. B. Kibble, Topology of cosmic domains and strings, J. Phys. A: Math. Gen. 9, 1387 (1976).
  * Zurek [1985] W. H. Zurek, Cosmological experiments in superfluid helium?, Nature 317, 505 (1985).
  * Keesling  _et al._ [2019] A. Keesling, A. Omran, H. Levine, H. Bernien, H. Pichler, S. Choi, R. Samajdar, S. Schwartz, P. Silvi, S. Sachdev, P. Zoller, M. Endres, M. Greiner, V. Vuletić, and M. D. Lukin, Quantum Kibble–Zurek mechanism and critical dynamics on a programmable Rydberg simulator, Nature 568, 207 (2019).
  * Aharonov  _et al._ [2022] D. Aharonov, J. Cotler, and X.-L. Qi, Quantum algorithmic measurement, Nat. Commun. 13, 887 (2022).
  * Huang  _et al._ [2022] H.-Y. Huang, M. Broughton, J. Cotler, S. Chen, J. Li, M. Mohseni, H. Neven, R. Babbush, R. Kueng, J. Preskill, and J. R. McClean, Quantum advantage in learning from experiments, Science 376, 1182 (2022).
  * Lu  _et al._ [2024] J. Z. Lu, L. Jiao, K. Wolinski, M. Kornjača, H.-Y. Hu, S. Cantu, F. Liu, S. F. Yelin, and S.-T. Wang, Digital-analog quantum learning on Rydberg atom arrays (2024), arXiv:2401.02940 [quant-ph] .
  * Fishman  _et al._ [2022] M. Fishman, S. R. White, and E. M. Stoudenmire, The ITensor Software Library for Tensor Network Calculations, SciPost Phys. Codebases , 4 (2022).
  * Šibalić  _et al._ [2017] N. Šibalić, J. Pritchard, C. Adams, and K. Weatherill, ARC: An open-source library for calculating properties of alkali Rydberg atoms, Comput. Phys. Commun. 220, 319 (2017).


and ${\llbracket{\theta_{2}}\rrbracket}_{D,\eta}={\textbf{t}}\text{ if and
only if
}{\llbracket{\theta_{2}}\rrbracket}^{{\scriptscriptstyle\boldsymbol{\textsc{2VL}}}}_{D,\eta}={\textbf{t}}$.
Thus,
${\llbracket{\theta_{1}\wedge\theta_{2}}\rrbracket}_{D,\eta}={\textbf{t}}\text{
if and only if
}{\llbracket{\theta_{1}\wedge\theta_{2}}\rrbracket}^{{\scriptscriptstyle\boldsymbol{\textsc{2VL}}}}_{D,\eta}={\textbf{t}}$.

##  Appendix E Appendix for Section 6

$\displaystyle\\!\\!\\!\\!\begin{array}[]{lr}\text{\small\color[rgb]{0,0,0}
SELECT}\\!\\!\\!&\alpha\\\ \text{\small\color[rgb]{0,0,0} FROM}&R\\\
\text{\small\color[rgb]{0,0,0} WHERE}&\theta\\\
\end{array}=\left(\\!\\!\begin{array}[]{lr}\text{\small\color[rgb]{0,0,0}
SELECT}\\!\\!\\!&\alpha\\\ \text{\small\color[rgb]{0,0,0} FROM}&R\\\
\end{array}\\!\\!\right)\begin{array}[]{c}\text{\small\color[rgb]{0,0,0}
EXCEPT}\\\ \text{\small\color[rgb]{0,0,0}
ALL}\end{array}\left(\\!\\!\begin{array}[]{lr}\text{\small\color[rgb]{0,0,0}
SELECT}\\!\\!\\!&\alpha\\\ \text{\small\color[rgb]{0,0,0} FROM}&R\\\
\text{\small\color[rgb]{0,0,0} WHERE}&\neg\theta\\\ \end{array}\\!\\!\right)$
 $\displaystyle\begin{aligned} &\text{\small\color[rgb]{0,0,0} SELECT}\
\alpha\ \text{\small\color[rgb]{0,0,0} FROM}\,\,R\\\
&\text{\small\color[rgb]{0,0,0}
WHERE}\,\,\beta\,\,\text{\small\color[rgb]{0,0,0} NOT IN}\\\ &\hskip
17.0pt(\text{\small\color[rgb]{0,0,0} SELECT}\ \gamma\
\text{\small\color[rgb]{0,0,0} FROM}\,\,S)\end{aligned}$
${\displaystyle\,\,=\,\,\begin{aligned} &\text{\small\color[rgb]{0,0,0}
SELECT}\ \alpha\ \text{\small\color[rgb]{0,0,0} FROM}\,\,R\\\
&\text{\small\color[rgb]{0,0,0} WHERE }\text{\small\color[rgb]{0,0,0} NOT
}\text{\small\color[rgb]{0,0,0} EXISTS}\\\ &\hskip
17.0pt(\text{\small\color[rgb]{0,0,0}
SELECT}\,\,\mbox{\leavevmode\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@language\small\textasteriskcentered}}}}\,\,\text{\small\color[rgb]{0,0,0}
FROM}\,\,S\\\ &\hskip 17.0pt\text{\small\color[rgb]{0,0,0} WHERE}\
\beta=\gamma)\end{aligned}$ $\displaystyle\begin{aligned}
&\text{\small\color[rgb]{0,0,0} SELECT}\ \alpha\
\text{\small\color[rgb]{0,0,0} FROM}\,\,R\\\ &\text{\small\color[rgb]{0,0,0}
WHERE }\text{\small\color[rgb]{0,0,0} NOT}\,\,\beta\ \omega\
\text{\small\color[rgb]{0,0,0} ANY}\\\ &\hskip
17.0pt(\text{\small\color[rgb]{0,0,0} SELECT}\ \gamma\
\text{\small\color[rgb]{0,0,0} FROM}\,\,S)\end{aligned}$
${\displaystyle\,\,\,\,=\,\,\,\,\begin{aligned}
&\text{\small\color[rgb]{0,0,0} SELECT}\ \alpha\
\text{\small\color[rgb]{0,0,0} FROM}\,\,R\\\ &\text{\small\color[rgb]{0,0,0}
WHERE}\,\,\text{\small\color[rgb]{0,0,0} NOT EXISTS}\\\ &\hskip
17.0pt(\text{\small\color[rgb]{0,0,0}
SELECT}\,\,\mbox{\leavevmode\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@language\small\textasteriskcentered}}}}\,\,\text{\small\color[rgb]{0,0,0}
FROM}\,\,S\\\ &\hskip 17.0pt\text{\small\color[rgb]{0,0,0} WHERE}\,\,\beta\
\omega\ \gamma)\end{aligned}$ $\displaystyle\begin{aligned}
&\text{\small\color[rgb]{0,0,0} SELECT}\ \alpha\
\text{\small\color[rgb]{0,0,0} FROM}\,\,R\\\ &\text{\small\color[rgb]{0,0,0}
WHERE}\ \beta\ \omega\,\text{\small\color[rgb]{0,0,0} ALL}\\\ &\hskip
17.0pt(\text{\small\color[rgb]{0,0,0} SELECT}\ \gamma\
\text{\small\color[rgb]{0,0,0} FROM}\,\,S)\end{aligned}$
${\displaystyle\,\,\,\,=\,\,\,\,\begin{aligned}
&\text{\small\color[rgb]{0,0,0} SELECT}\ \alpha\
\text{\small\color[rgb]{0,0,0} FROM}\,\,R\\\ &\text{\small\color[rgb]{0,0,0}
WHERE}\,\,\text{\small\color[rgb]{0,0,0} NOT EXISTS}\\\ &\hskip
17.0pt(\text{\small\color[rgb]{0,0,0}
SELECT}\,\,\mbox{\leavevmode\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@language\small\textasteriskcentered}}}}\,\,\text{\small\color[rgb]{0,0,0}
FROM}\,\,S\\\ &\hskip 17.0pt\text{\small\color[rgb]{0,0,0} WHERE
}\text{\small\color[rgb]{0,0,0} NOT}\ \beta\ \omega\ \gamma)\end{aligned}$

Figure 6.  SQL queries equivalent under the two-valued semantics but not SQL’s
three-valued semantics ($\alpha,\beta,\gamma$ are attribute lists and $\omega$
is a comparison)

###  E.1. Proving and Extending Theorem 1

theorem 1. The ${\llbracket{\,}\rrbracket}^{\boldsymbol{=}}$ semantics of
$\textsc{RA}^{\textsc{rec}}_{\textsc{sql}}$ expressions captures the SQL
semantics.

We show that this theorem can be further generalized and be proved as a
corollary. We now set the ground for presenting this generalized theorem.

Are ${\llbracket{}\rrbracket}^{{\scriptscriptstyle\boldsymbol{\textsc{2VL}}}}$
and ${\llbracket{}\rrbracket}^{\boldsymbol{=}}$ the only possible two-valued
semantics out there? Of course not. Consider for example the predicate $\leq$.
In both ${\llbracket{\,}\rrbracket}^{\boldsymbol{=}}$ and
${\llbracket{\,}\rrbracket}^{{\scriptscriptstyle\boldsymbol{\textsc{2VL}}}}$,
$\text{\small\color[rgb]{0,0,0} NULL}\leq\text{\small\color[rgb]{0,0,0} NULL}$
is f, but under the syntactic equality interpretation it is not unreasonable
to say that $\text{\small\color[rgb]{0,0,0}
NULL}\leq\text{\small\color[rgb]{0,0,0} NULL}$ is true, as $\leq$ subsumes
equality. This gives a general idea of how different semantics can be
obtained: when some arguments of a predicate are  NULL, we can decide what the
truth value based on other values. Just for the sake of example, we could say
that $n\leq\text{\small\color[rgb]{0,0,0} NULL}$ is f for $n<0$ and t for
$n\geq 0$.

To define such alternative semantics in a general way, we simply state, for
each comparison predicate in $\\{\doteq,\neq,\leq,<,>,\geq\\}$, what happens
when one or two of its arguments are  NULL. To this end, we associate each
comparison predicate with a binary predicate with the same notation. Our
construction is in fact even more general, as it covers also predicates of
higher arities.

We introduce the notion of grounding: It is a function gr that takes an
$n$-ary predicate $P$ of type $\tau$ and a non-empty sequence
$\mathbf{I}=\langle i_{1},\cdots,i_{k}\rangle$ of indices $1\leq
i_{1}<\cdots<i_{k}\leq n$, and produces a relation $\textbf{gr}(P,\mathbf{I})$
that contains $\tau$-records $(t_{1},\cdots,t_{n})$ where
$t_{i}=\text{\small\color[rgb]{0,0,0} NULL}$ for every $i\in\mathbf{I}$, and
$t_{i}\neq\text{\small\color[rgb]{0,0,0} NULL}$ for every
$i\not\in\mathbf{I}$. In the above example, if $P$ is $\leq_{2}$, then
$\textbf{gr}(P,\langle 1\rangle)=\\{(\text{\small\color[rgb]{0,0,0}
NULL},n)\mid n\geq 0\\}$ while $\textbf{gr}(P,\langle
2\rangle)=\\{(\text{\small\color[rgb]{0,0,0} NULL},n)\mid n<0\\}$ and
$\textbf{gr}(P,\langle 1,2\rangle)=\\{(\text{\small\color[rgb]{0,0,0}
NULL},\text{\small\color[rgb]{0,0,0} NULL})\\}$.

The semantics ${\llbracket{\,}\rrbracket}^{\textbf{gr}}$ based on such
grounding is given by redefining the truth value of
${\llbracket{P(t_{1},\ldots,t_{n})}\rrbracket}^{\textbf{gr}}$ as that of
$\bar{t}\in\textbf{gr}(P,\mathbf{I})$, where $\mathbf{I}$ is the list on
indices $i$ such that
${\llbracket{t_{i}}\rrbracket}^{\textbf{gr}}=\text{\small\color[rgb]{0,0,0}
NULL}$.

Such semantics generalize
${\llbracket{\,}\rrbracket}^{{\scriptscriptstyle\boldsymbol{\textsc{2VL}}}}$
and ${\llbracket{\,}\rrbracket}^{\boldsymbol{=}}$. In the former, by setting
$\textbf{gr}(\doteq,\mathbf{I})=\emptyset$ for each nonempty $\mathbf{I}$; in
the latter, it is the same except that $\textbf{gr}(=,\langle 1,2\rangle)$
would contain also the tuple $(\text{\small\color[rgb]{0,0,0}
NULL},\text{\small\color[rgb]{0,0,0} NULL})$.

We say that a grounding is expressible if for each predicate $P$ and each
$\mathbf{I}$ there is a condition $\theta_{P,\mathbf{I}}$ such that
$\bar{t}\in\textbf{gr}(P,\mathbf{I})$ if and only if
$\pi_{\bar{\mathbf{I}}}(\bar{t})$ satisfies $\theta_{P,\mathbf{I}}$. Note that
the projection on the complement $\bar{\mathbf{I}}$ of $\mathbf{I}$ would only
contain non-null elements. The semantics seen previously satisfy this
condition.

###### Theorem 1.

For every expressible grounding gr, the
${\llbracket{\,}\rrbracket}^{\textbf{gr}}$ semantics of
$\textsc{RA}^{\textsc{rec}}_{\textsc{sql}}$ or $\textsc{RA}_{\textsc{sql}}$
expressions captures their SQL semantics.

##### From ${\llbracket{\,}\rrbracket}^{\textbf{gr}}$ to
${\llbracket{\,}\rrbracket}$

Basic conditions
${P(\bar{t})}^{{\textbf{t}}}$
$:={\displaystyle\bigvee_{I\subseteq\\{1,\cdots,k\\}}\Big{(}c_{I}\wedge\theta_{P,\mathbf{I}}(\bar{t})\Big{)}}$
${P(\bar{t})}^{{\textbf{f}}}$
$:=\bigvee_{I\subseteq\\{1,\cdots,k\\}}\Big{(}c_{I}\wedge\neg\theta_{P,\mathbf{I}}(\bar{t})\Big{)}$
where $c_{I}:=\bigwedge_{j\in I}\mathtt{isnull}(N_{j})$ and
$\ell(P):=(N_{1},\cdots,N_{k})$
$\left(t\,\omega\,t^{\prime}\right)^{{\textbf{t}}}$
$:={\displaystyle\bigvee_{I\subseteq\\{1,2\\}}\big{(}c_{I}\wedge\theta_{\omega,I}(t,t^{\prime})\big{)}}$
$\left(t\,\omega\,t^{\prime}\right)^{{\textbf{f}}}$
$:={\displaystyle\bigvee_{I\subseteq\\{1,2\\}}\big{(}c_{I}\wedge\neg\theta_{\omega,I}(t,t^{\prime})\big{)}}$
where $c_{I}:=\bigwedge_{j\in I}\mathtt{isnull}(N_{j})$ with
$N_{1}:=t,N_{2}:=t^{\prime}$
$\left(t\,\omega\,\mathtt{any}(E)\right)^{{\textbf{t}}}$
$:=\neg\mathtt{empty}(\sigma_{\theta}(G))$
$\left(t\,\omega\,\mathtt{any}(E)\right)^{{\textbf{f}}}$
$:=\mathtt{empty}(\sigma_{\theta}(G))$
$\left(t\,\omega\,\mathtt{all}(E)\right)^{{\textbf{t}}}$
$:=\mathtt{empty}(\sigma_{\neg\theta}(G))$
$\left(t\,\omega\,\mathtt{all}(E)\right)^{{\textbf{f}}}$
$:=\neg\mathtt{empty}(\sigma_{\neg\theta}(G))$ $\text{ where
}\theta:={\displaystyle\left(\bar{t}\,\omega\,\ell(E)\right)^{{\textbf{t}}}}$
.

Figure 7. ${\llbracket{}\rrbracket}^{\textbf{gr}}{\,}$ to SQL semantics (new
cases compared to Fig. 2)

  * (b)

    1. (1)

It holds that

${\llbracket{P(\bar{t})}\rrbracket}^{\textbf{gr}}_{D,\eta}={\textbf{t}}$

if and only if (by definition)

${\llbracket{\bigvee_{I\subseteq\\{1,\cdots,k\\}}\Big{(}c_{I}\wedge\theta_{P,\mathbf{I}}(\bar{t})\Big{)}}\rrbracket}_{D,\eta}={\textbf{t}}$

    2. (2)

It holds that

${\llbracket{t\,\omega\,t^{\prime}}\rrbracket}^{\textbf{gr}}_{D,\eta}={\textbf{t}}$

if and only if (by definition)

${\llbracket{\bigvee_{I\subseteq\\{1,2\\}}\Big{(}c_{I}\wedge\theta_{\omega,\mathbf{I}}(\bar{t})\Big{)}}\rrbracket}_{D,\eta}={\textbf{t}}$

    3. (3)

It holds that

${\llbracket{\bar{t}\,\omega\,\mathtt{any}(E)}\rrbracket}^{\textbf{gr}}_{D,\eta}={\textbf{t}}$

if and only if (by definition)

$\bigvee_{\bar{t}^{\prime}\in{\llbracket{E}\rrbracket}^{\textbf{gr}}_{D,\eta}}{\llbracket{\bar{t}\,\omega\,\bar{t}^{\prime}}\rrbracket}^{\textbf{gr}}_{D,\eta}={\textbf{t}}$

if and only if (by induction hypothesis (a))

$\bigvee_{\bar{t}^{\prime}\in{\llbracket{G}\rrbracket}_{D,\eta}}{\llbracket{\bar{t}\,\omega\,\bar{t}^{\prime}}\rrbracket}^{\textbf{gr}}_{D,\eta}={\textbf{t}}$

if and only if (by induction hypothesis (b))

$\bigvee_{\bar{t}^{\prime}\in{\llbracket{G}\rrbracket}_{D,\eta}}{\llbracket{\textsf{tr}^{{\textbf{t}}}(\bar{t}\,\omega\,\bar{t}^{\prime})}\rrbracket}_{D,\eta}={\textbf{t}}$

if and only if (by definition of
$\textsf{tr}^{{\textbf{t}}}(\bar{t}\,\omega\,\bar{t}^{\prime})$)

$\bigvee_{\bar{t}^{\prime}\in{\llbracket{G}\rrbracket}_{D,\eta}}{\llbracket{\bar{t}\,\omega\,\bar{t}^{\prime}}\rrbracket}_{D,\eta}={\textbf{t}}$

if and only if (by definition of $\mathtt{any}$)

${\llbracket{\bar{t}\,\omega\,\mathtt{any}(G)}\rrbracket}_{D,\eta}={\textbf{t}}$

    4. (4)

It holds that

${\llbracket{\bar{t}\,\omega\,\mathtt{all}(E)}\rrbracket}^{\textbf{gr}}_{D,\eta}={\textbf{t}}$

if and only if (by definition)

$\bigwedge_{\bar{t}^{\prime}\in{\llbracket{E}\rrbracket}^{\textbf{gr}}_{D,\eta}}{\llbracket{\bar{t}\,\omega\,\bar{t}^{\prime}}\rrbracket}^{\textbf{gr}}_{D,\eta}={\textbf{t}}$

if and only if (by induction hypothesis (a))

$\bigwedge_{\bar{t}^{\prime}\in{\llbracket{G}\rrbracket}_{D,\eta}}{\llbracket{\bar{t}\,\omega\,\bar{t}^{\prime}}\rrbracket}_{D,\eta}={\textbf{t}}$

if and only if (by induction hypothesis (b))

$\bigwedge_{\bar{t}^{\prime}\in{\llbracket{G}\rrbracket}_{D,\eta}}{\llbracket{\textsf{tr}^{{\textbf{t}}}(\bar{t}\,\omega\,\bar{t}^{\prime})}\rrbracket}_{D,\eta}={\textbf{t}}$

if and only if (by definition of
$\textsf{tr}^{{\textbf{t}}}(\bar{t}\,\omega\,\bar{t}^{\prime})$)

$\bigwedge_{\bar{t}^{\prime}\in{\llbracket{G}\rrbracket}_{D,\eta}}{\llbracket{{\bar{t}\,\omega\,\bar{t}^{\prime}}}\rrbracket}_{\eta}={\textbf{t}}$

if and only if (by definition of $\mathtt{all}$)

${\llbracket{\bar{t}\,\omega\,\mathtt{all}(G)}\rrbracket}_{D,\eta}={\textbf{t}}$

  * (c)

    1. (1)

It holds that

${\llbracket{P(\bar{t})}\rrbracket}^{\textbf{gr}}_{D,\eta}={\textbf{f}}$

if and only if (by definition)

${\llbracket{\bigvee_{I\subseteq\\{1,\cdots,k\\}}\Big{(}c_{I}\wedge\neg\theta_{P,\mathbf{I}}(\bar{t})\Big{)}}\rrbracket}_{D,\eta}={\textbf{t}}$

    2. (2)

It holds that

${\llbracket{t\,\omega\,t^{\prime}}\rrbracket}^{\textbf{gr}}_{D,\eta}={\textbf{f}}$

if and only if (by definition)

${\llbracket{\bigvee_{I\subseteq\\{1,2\\}}\Big{(}c_{I}\wedge\neg\theta_{\omega,\mathbf{I}}(\bar{t})\Big{)}}\rrbracket}_{D,\eta}={\textbf{t}}$

    3. (3)

It holds that

${\llbracket{\bar{t}\,\omega\,\mathtt{any}(E)}\rrbracket}^{\textbf{gr}}_{D,\eta}={\textbf{f}}$

if and only if (by definition of the semantics of $\mathtt{any}$)

$\bigvee_{\bar{t}^{\prime}\in{\llbracket{E}\rrbracket}^{\textbf{gr}}_{D,\eta}}{\llbracket{\bar{t}\,\omega\,\bar{t}^{\prime}}\rrbracket}^{\textbf{gr}}_{D,\eta}={\textbf{f}}$

if and only if (by induction hypothesis (a))

$\bigvee_{\bar{t}^{\prime}\in{\llbracket{G}\rrbracket}_{D,\eta}}{\llbracket{\bar{t}\,\omega\,\bar{t}^{\prime}}\rrbracket}^{\textbf{gr}}_{D,\eta}={\textbf{f}}$

if and only if (by definition of $vee$)

$\text{for all
}{\bar{t}^{\prime}\in{\llbracket{G}\rrbracket}_{D,\eta}}:{\llbracket{\bar{t}\,\omega\,\bar{t}^{\prime}}\rrbracket}^{\textbf{gr}}_{D,\eta}={\textbf{f}}$

if and only if (by induction hypothesis (b))

$\text{for all
}{\bar{t}^{\prime}\in{\llbracket{G}\rrbracket}_{D,\eta}}:{\llbracket{\textsf{tr}^{{\textbf{f}}}(\bar{t}\,\omega\,\bar{t}^{\prime})}\rrbracket}_{D,\eta}={\textbf{t}}$

if and only if (by the definition of the translation and of $\mathtt{empty}$)

${\llbracket{\mathtt{empty}(\sigma_{\neg\theta}(G))}\rrbracket}={\textbf{t}}$

with $\theta:=\textsf{tr}^{{\textbf{f}}}(\bar{t}\,\omega\,\ell(G))$

    4. (4)

It holds that

${\llbracket{\bar{t}\,\omega\,\mathtt{all}(E)}\rrbracket}^{\textbf{gr}}_{D,\eta}={\textbf{f}}$

if and only if (by definition of the semantics of $\mathtt{all}$)

$\bigwedge_{\bar{t}^{\prime}\in{\llbracket{E}\rrbracket}^{\textbf{gr}}_{D,\eta}}{\llbracket{\bar{t}\,\omega\,\bar{t}^{\prime}}\rrbracket}^{\textbf{gr}}_{D,\eta}={\textbf{f}}$

if and only if (by induction hypothesis (a))

$\bigwedge_{\bar{t}^{\prime}\in{\llbracket{G}\rrbracket}_{D,\eta}}{\llbracket{\bar{t}\,\omega\,\bar{t}^{\prime}}\rrbracket}^{\textbf{gr}}_{D,\eta}={\textbf{f}}$

if and only if (by definition of $\wedge$)

$\text{there is
}{\bar{t}^{\prime}\in{\llbracket{G}\rrbracket}_{D,\eta}}:{\llbracket{\bar{t}\,\omega\,\bar{t}^{\prime}}\rrbracket}^{\textbf{gr}}_{D,\eta}={\textbf{f}}$

if and only if (by induction hypothesis (b))

$\text{there is
}{\bar{t}^{\prime}\in{\llbracket{G}\rrbracket}_{D,\eta}}:{\llbracket{\textsf{tr}^{{\textbf{f}}}(\bar{t}\,\omega\,\bar{t}^{\prime})}\rrbracket}_{D,\eta}={\textbf{t}}$

if and only if (by the definition of the translation and of $\mathtt{empty}$)

${\llbracket{\neg\mathtt{empty}(\sigma_{\theta}(G))}\rrbracket}={\textbf{t}}$

with $\theta:=\textsf{tr}^{{\textbf{f}}}(\bar{t}\,\omega\,\ell(G))$

##### From ${\llbracket{\,}\rrbracket}$ to
${\llbracket{\,}\rrbracket}^{\textbf{gr}}$

Basic conditions
${P(\bar{t})}^{{\textbf{t}}}$
$:={\displaystyle\bigwedge_{i=1}^{n}\neg\mathtt{isnull}(t_{i})\wedge
P(\bar{t})}$ ${P(\bar{t})}^{{\textbf{f}}}$
$:={\displaystyle\bigwedge_{i=1}^{n}\neg\mathtt{isnull}(t_{i})\wedge\neg
P(\bar{t})}$ where $\bar{t}:=(t_{1},\cdots,t_{n})$
$\left(t\,\omega\,t^{\prime}\right)^{{\textbf{t}}}$
$:={\displaystyle\neg\mathtt{isnull}(t)\wedge\neg\mathtt{isnull}(t^{\prime})\wedge\theta_{\omega,I}(t,t^{\prime})}$
$\left(t\,\omega\,t^{\prime}\right)^{{\textbf{f}}}$
$:={\displaystyle\neg\mathtt{isnull}(t)\wedge\neg\mathtt{isnull}(t^{\prime})\wedge\neg\theta_{\omega,I}(t,t^{\prime})}$
.

Figure 8. SQL semantics to ${\llbracket{}\rrbracket}^{\textbf{gr}}{\,}$ (new
cases compared to Fig. 5)

We use all the translations that appear in Figure 7 .

The proofs of this direction are shown similarly to the proofs of the
translation from ${\llbracket{}\rrbracket}$ to
${\llbracket{}\rrbracket}^{{\scriptscriptstyle\boldsymbol{\textsc{2VL}}}}$.

###  E.2. Proof of Theorem 3

theorem 3. For a many-valued logic $\mathsf{MVL}$ in which $\wedge$ and $\vee$
are associative and commutative, let
${\llbracket{\,}\rrbracket}^{\mathsf{MVL}}$ be a semantics of
$\textsc{RA}_{\textsc{sql}}$ or $\textsc{RA}^{\textsc{rec}}_{\textsc{sql}}$
expressions based on $\mathsf{MVL}$. Assume that this semantics is SQL-
expressible for atomic predicates. Then it captures the SQL semantics.

Before presenting the translations, we make some observations. Let us denote
the truth values of any MVL by $\tau_{1},\cdots,\tau_{M}$.

###### Lemma 0.

For any truth value $\tau_{i}$ there exists integers
$l^{\vee}_{i},p^{\vee}_{i},l^{\wedge}_{i},p^{\wedge}_{i}$ such that the
following holds for any $j$:

  * •

$\underbrace{\tau_{i}\vee\cdots\vee\tau_{i}}_{j\text{
times}}=\underbrace{\tau_{i}\vee\cdots\vee\tau_{i}}_{l_{i}+\Big{(}(j-l^{\vee}_{i})\mod(p^{\vee}_{i}-l^{\vee}_{i})\Big{)}\text{
times}}$

  * •

$\underbrace{\tau_{i}\wedge\cdots\wedge\tau_{i}}_{j\text{
times}}=\underbrace{\tau_{i}\wedge\cdots\wedge\tau_{i}}_{l_{i}+\Big{(}(j-l^{\wedge}_{i})\mod(p^{\wedge}_{i}-l^{\wedge}_{i})\Big{)}\text{
times}}$

###### Proof.

We start by proving the existence of $l_{i}^{\vee},p_{i}^{\vee}$. For any
$i,j$ we denote by $\tau_{i}^{j}$ the disjunction

$\underbrace{\tau_{i}\vee\cdots\vee\tau_{i}}_{j\text{ times}}.$

Since we have finite number of truth values, the pigeonhole principle ensures
that for any truth value $\tau_{i}$ there are two natural numbers $l<p$ such
that the following holds:

  * •

$\tau^{j^{\prime}}\neq\tau^{j}$ for any $1\leq j^{\prime}<j<p$, and

  * •

$\tau^{l}=\tau^{p}$.

Due to associativity of $\vee$, it follows that the claim holds with
$l_{i}^{\vee}:=l$ and $p_{i}^{\vee}:=p$.

Similar arguments show the existence of $l_{i}^{\wedge}$ and $p_{i}^{\wedge}$.
∎

Since the operator $\vee$ is both associative and commutative, any disjunction
can be written as follows:

$\underbrace{\tau_{1}\vee\cdots\vee\tau_{1}}_{i_{1}\text{
times}}\vee\cdots\vee\underbrace{\tau_{M}\vee\cdots\vee\tau_{M}}_{i_{M}\text{
times}}$

Alternatively, we can denote disjunctions by $f_{\vee}(i_{1},\cdots,i_{M})$
where each $i_{j}$ is the number of times the truth value $\tau_{j}$ appears
in the disjunction. For similar reasons, we can denote any conjunction as
$f_{\wedge}(i_{1},\cdots,i_{M})$ where $i_{j}$ is the number of times the
truth value $\tau_{j}$ appears in the conjunction. The previous lemma leads us
to the following straightforward corollary.

###### Corollary 0.

for any $n_{1},\cdots,n_{M}$ it holds that:

  * •

$f_{\vee}(n_{1},\cdots,n_{M})=f_{\vee}(n^{\prime}_{1},\cdots,n^{\prime}_{M})$
where
$n^{\prime}_{\iota}=l_{\iota}+\Big{(}(n_{\iota}-l^{\vee}_{\iota})\mod(p_{\iota}^{\vee}-l^{\vee}_{\iota})\Big{)}$,
and

  * •

$f_{\wedge}(n_{1},\cdots,n_{M})=f_{\wedge}(n^{\prime\prime}_{1},\cdots,n^{\prime\prime}_{M})$
where
$n^{\prime\prime}_{\iota}=l_{\iota}+\Big{(}(n_{\iota}-l^{\wedge}_{\iota})\mod(p_{\iota}^{\wedge}-l^{\wedge}_{\iota})\Big{)}$

for all $1\leq\iota\leq M$.

##### From ${\llbracket{\,}\rrbracket}^{\mathsf{MVL}}$ to
${\llbracket{\,}\rrbracket}$

The translation is presented in Figure 9.

Basic conditions
$(t\,\omega\,t^{\prime})^{\tau}:=$ $\theta_{\omega,\tau}(t,t^{\prime})$ where
$\omega\in\\{\doteq,<,\leq,>,\geq\\}$ $(\bar{t}\in E)^{\tau}:=$
$(f_{\vee}(n^{\prime}_{1},\cdots,n^{\prime}_{k})\doteq\tau)$ where
$n^{\prime}_{\iota}:=$
$l_{\iota}+\Big{(}(n_{\iota}-l^{\vee}_{\iota})\mod(p_{\iota}^{\vee}-l^{\vee}_{\iota})\Big{)}$
where $n_{i}:=$
$\texttt{Group}_{\emptyset}\langle\texttt{Count}(\star)\rangle\Big{(}\sigma_{\theta_{i}={\textbf{t}}}(E_{i})\Big{)}$
where $E_{i}:=$ $\pi_{\theta_{i}(\bar{N})\to\theta_{i}}(F)$,
$\ell(F):=\bar{N}$, $\theta_{i}(\bar{N}):=(\bar{N}\doteq\bar{t})^{\tau_{i}}$
$(t\,\omega\,\mathtt{any}(E))^{\tau}:=$
$(f_{\vee}(n^{\prime}_{1},\cdots,n^{\prime}_{k})\doteq\tau)$
$(t\,\omega\,\mathtt{all}(E))^{\tau}:=$
$(f_{\wedge}(n^{\prime\prime}_{1},\cdots,n^{\prime\prime}_{k})\doteq\tau)$
where $n^{\prime}_{\iota}:=$
$l_{\iota}+\Big{(}(n_{\iota}-l^{\vee}_{\iota})\mod(p_{\iota}^{\vee}-l^{\vee}_{\iota})\Big{)}$,
$n^{\prime\prime}_{\iota}:=$
$l_{\iota}+\Big{(}(n_{\iota}-l^{\wedge}_{\iota})\mod(p_{\iota}^{\wedge}-l^{\wedge}_{\iota})\Big{)}$,
$n_{i}:=$
$\texttt{Group}_{\emptyset}\langle\texttt{Count}(\star)\rangle\Big{(}\sigma_{(t\,\omega\,\ell(F))\doteq\tau_{i}}(F)\Big{)}$,
Composite conditions
$(\theta_{1}\vee\theta_{2})^{\tau}:=$
$\bigvee_{\tau_{1},\tau_{2}:\tau_{1}\vee\tau_{2}=\tau}\Big{(}(\theta_{1})^{\tau_{1}}\vee(\theta_{2})^{\tau_{2}}\Big{)}$
$(\theta_{1}\wedge\theta_{2})^{\tau}:=$
$\bigvee_{\tau_{1},\tau_{2}:\tau_{1}\wedge\tau_{2}=\tau}\Big{(}(\theta_{1})^{\tau_{1}}\wedge(\theta_{2})^{\tau_{2}}\Big{)}$
$(\neg\theta)^{\tau}:=$
$\bigvee_{\tau^{\prime}:\neg\tau^{\prime}=\tau}(\theta)^{\tau^{\prime}}$

Figure 9. ${\llbracket{\,}\rrbracket}^{\mathsf{MVL}}$ to SQL semantics

We note that the existence of the conditions $\theta_{\omega,\tau}$ and
$\theta_{P,\tau}$ is a consequence of expressibility.

The proof structure is similar to other translations, and we use similar
notations. Note that the following is straightforward from definition:

  * •

${\llbracket{t\,\omega\,t^{\prime}}\rrbracket}^{\mathsf{MVL}}_{D,\eta}=\tau$
if and only if
${\llbracket{\theta_{\omega,\tau}(t,t^{\prime})}\rrbracket}_{D,\eta}={\textbf{t}}$.

  * •

${\llbracket{P(\bar{t})}\rrbracket}^{\mathsf{MVL}}_{D,\eta}=\tau$ if and only
if ${\llbracket{\theta_{P,\tau}(\bar{t})}\rrbracket}_{D,\eta}={\textbf{t}}$.

Before presenting the translations for $\bar{t}\,\omega\,\mathtt{any}(E)$ and
$\bar{t}\,\omega\,\mathtt{all}(E)$, we explain it intuitively. We note that
even though the semantics of these conditions are defined as a disjunction, we
cannot use the translation of composite conditions since the disjunction’s
size (and elements) depend on the actual semantics of $E$. We thus compute the
disjunction by using the ability of $\textsc{RA}_{\textsc{sql}}$ to count, and
the fact the order of elements in the disjunction is not significant. We use
the following observation that is straightforward from the definition of the
semantics of $\textsc{RA}_{\textsc{sql}}$.

###### Proposition 0.

For every database $D$ and environment $\eta$ it holds that the integer
$n_{i}:={\llbracket{\texttt{Group}_{\emptyset}\langle\texttt{Count}(\star)\rangle\Big{(}\sigma_{(t\,\omega\,\ell(F))\doteq\tau_{i}}(F)\Big{)}}\rrbracket}^{\mathsf{MVL}}_{D,\eta}$
is the number of tuples
$\bar{t}^{\prime}\in{\llbracket{F}\rrbracket}^{\mathsf{MVL}}_{D,\eta}$ for
which
${\llbracket{\bar{t}\,\omega\,\bar{t}^{\prime}}\rrbracket}^{\mathsf{MVL}}_{D,\eta}=\tau_{i}$.

With this, we can move to the proof:

  1. (1)

It holds that

${\llbracket{\bar{t}\,\omega\,\mathtt{any}(E)}\rrbracket}^{\mathsf{MVL}}_{D,\eta}=\tau$

if and only if (by definition)

$\bigvee_{\bar{t}^{\prime}\in{\llbracket{E}\rrbracket}^{\mathsf{MVL}}_{D,\eta}}{\llbracket{\bar{t}\,\omega\,\bar{t}^{\prime}}\rrbracket}^{\mathsf{MVL}}_{D,\eta}=\tau$

if and only if (by induction hypothesis)

$\bigvee_{\bar{t}^{\prime}\in{\llbracket{F}\rrbracket}_{D,\eta}}{\llbracket{\bar{t}\,\omega\,\bar{t}^{\prime}}\rrbracket}^{\mathsf{MVL}}_{D,\eta}=\tau$

if and only if (due to associativity and transitivity)

$f_{\vee}(m_{1},\cdots,m_{M})=\tau$

where $m_{i}$ is the number of tuples
$\bar{t}^{\prime}\in{\llbracket{F}\rrbracket}_{D,\eta}$ for which
${\llbracket{\bar{t}\,\omega\,\bar{t}^{\prime}}\rrbracket}^{\mathsf{MVL}}_{D,\eta}=\tau_{i}$,
if and only if (by Corollary 3 and Proposition 4)

${\llbracket{f_{\vee}(n^{\prime}_{1},\cdots,n^{\prime}_{M})\doteq\tau}\rrbracket}={\textbf{t}}$

if and only if (by definition)

${\llbracket{{\bar{t}\,\omega\,\mathtt{any}(E)}^{\tau}}\rrbracket}_{D,\eta}={\textbf{t}}$

  2. (2)

The proof for $(\bar{t}\,\omega\,\mathtt{all}(E))^{\tau}$ can be shown
similarly.

For composite conditions the proof follows directly.

##### From ${\llbracket{\,}\rrbracket}$ to
${\llbracket{\,}\rrbracket}^{\mathsf{MVL}}$

This direction uses the same translation as from ${\llbracket{\,}\rrbracket}$
to
${\llbracket{\,}\rrbracket}^{{\scriptscriptstyle\boldsymbol{\textsc{2VL}}}}$.
The correctness follows directly from the corresponding proof and from the
fact that the many-valued connectors are extensions of the corresponding two-
valued ones.