Loading...
Please wait, while we are loading the content...
Similar Documents
Counting Answers to Existential Positive Queries: A Complexity Classification
| Content Provider | arXiv |
|---|---|
| Author | Chen, Hubie Mengel, Stefan |
| Date of Submission | 2016-04-20 |
| 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. |
| Related Links | https://arxiv.org/pdf/1601.03240.pdf |
| arXiv | 1601.03240 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Computer Science - Databases Computer Science - Computational Complexity Computer Science |
| Content Type | Text |
| Resource Type | Article |
| Subject | Computer Science |
