Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations

Jacob Focke, Leslie Ann Goldberg, Marc Roth +1

We study the complexity of approximating the number of answers to a small query $\ddot{I}†$ in a large database $\mathcal{D}$. We establish an exhaustive classification into tractable and…