Secure "table-look-up" operation
Kolesnikov &amp; Kumaresan defined a primitive called "string select OT" which basically covers your setting but with a database of 2 items. Sender has $x^1, y^1, x^2, y^2$. Receiver has $x^*$. If $x^* = x^i$ then the receiver learns the corresponding $y^i$.

I think a generalization of their protocol would work, at the cost of $n$ 1-out-of-2 string OTs where $n$ is the number of bits in the $x$ values.


Parties do $n$ instances of string OTs on random strings $(m_0^1, m_1^1), (m_0^2, m_0^2), \ldots$ The receiver uses the bits of $x^*$ as his choice bits.
For an $n$-bit value $x$, sender defines $K_x = H( \bigoplus_i m_{x[i]}^i )$ where $H$ is a random oracle. The thing inside $H$ is the XOR of the things that the receiver would get if his choice bits were $x$. (the hash is there to kill the correlations among the different $K_x$ values)
For every $(x^i, y^i)$ in the database, sender sends gives $\textsf{Enc}(K_{x^i}, y^i)$. (assume it is an authenticated encryption, so you know when you have successfully decrypted)
Receiver can decrypt exactly one of these ciphertexts, and learn $y^i$.



  Vladimir Kolesnikov, Ranjit Kumaresan: Improved Secure Two-Party Computation via Information-Theoretic Garbled Circuits. SCN 2012: 205-221


edit: Here is another approach, using ideas from one of my papers. The paper only needs this functionality for database of size 2, but I think it would generalize as well. (we refer to this subprotocol as PFE of a universal hash function).


Parties do an MPC where receiver inputs $x^*$, sender inputs randomly chosen $a$ and $b$ from a large field. Receiver learns $ax^* + b$. Think of this as evaluating a private a 2-universal hash function. It has the property that even given $ax^*+b$, any other $ax'+b$ value is uniformly distributed.
Sender sends $\textsf{Enc}( H(ax^i+b), y_i)$ for each $(x^i, y^i)$ pair in the database. Receiver can decrypt exactly one of them.



  Zhangxiang Hu, Payman Mohassel, Mike Rosulek:
  Efficient Zero-Knowledge Proofs of Non-algebraic Statements with Sublinear Amortized Cost. CRYPTO (2) 2015: 150-169