Counting Answers to Existential Positive Queries

Abstract

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. We prove this trichotomy theorem by establishing a result which we call the equivalence theorem, which shows that for each class of existential positive formulas, there exists a class of conjunctive queries having the same complexity (in a sense made precise).