Skip to Main content Skip to Navigation
New interface
Conference papers

Counting Answers to Existential Positive Queries: A Complexity Classification

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).
Document type :
Conference papers
Complete list of metadata
Contributor : Fabien DELORME Connect in order to contact the contributor
Submitted on : Tuesday, July 27, 2021 - 12:49:42 PM
Last modification on : Wednesday, November 3, 2021 - 9:19:55 AM


  • HAL Id : hal-03301000, version 1



Hubie Chen, Stefan Mengel. Counting Answers to Existential Positive Queries: A Complexity Classification. 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS'16), 2016, San Francisco, CA, USA, Unknown Region. pp.315--326. ⟨hal-03301000⟩



Record views