# Counting Answers to Existential Positive Queries: A Complexity Classification

arXiv: https://arxiv.org/abs/1601.03240 · HTML: https://mlsanity.com/paper/1601.03240/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jan 2016.

## Built on by (most cited first, 3 of 3)

- [Homomorphism Counts for Graph Neural Networks: All About That Basis](https://mlsanity.com/paper/2402.08595/) (2024)
- [On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters](https://mlsanity.com/paper/2309.17053/) (2023)
- [Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability](https://mlsanity.com/paper/2311.14579/) (2023)

## Abstract (arXiv)

Existential positive formulas form a fragment of first-order logic that includes and is semantically equivalent to unions of conjunctive queries, one of the most important and well-studied classes of queries in database theory. We consider the complexity of counting the number of answers to existential positive formulas on finite structures and give a trichotomy theorem on query classes, in the setting of bounded arity. This theorem generalizes and unifies several known results on the complexity of conjunctive queries and unions of conjunctive queries.