Counting answers to unions of conjunctive queries: natural tractability criteria and meta-complexity

Counting answers to unions of conjunctive queries: natural tractability criteria and meta-complexity

We study the problem of counting answers to unions of conjunctive queries (UCQs) under structural restrictions on the input query. Concretely, given a class C of UCQs, the problem #UCQ (C) provides as input a UCQ Ψ ∈ C and a database D and the problem is to compute the number of answers of Ψ in D. &...

Descripció completa

Dades bibliogràfiques
Autors principals:	Focke, J, Goldberg, LA, Roth, M, Živný, S
Format:	Conference item
Idioma:	English
Publicat:	Association for Computing Machinery 2024

Ítems similars

Approximately counting answers to conjunctive queries with disequalities and negations
per: Focke, J, et al.
Publicat: (2022)

Approximately counting answers to conjunctive queries with disequalities and negations
per: Focke, J, et al.
Publicat: (2024)

The complexity of approximately counting retractions
per: Focke, J, et al.
Publicat: (2020)

The Weisfeiler-Leman dimension of conjunctive queries
per: Göbel, A, et al.
Publicat: (2024)

The complexity of approximately counting retractions
per: Focke, J, et al.
Publicat: (2019)

Unions of Conjunctive Queries in SHOQ
per: Glimm, B, et al.
Publicat: (2008)

The complexity of counting surjective homomorphisms and compactions
per: Focke, J, et al.
Publicat: (2017)

The complexity of counting surjective homomorphisms and compactions
per: Focke, J, et al.
Publicat: (2019)

Tractability beyond β-acyclicity for conjunctive queries with negation
per: Lanzinger, M
Publicat: (2021)

The complexity of approximately counting retractions to square-free graphs
per: Focke, J, et al.
Publicat: (2021)

Nominals‚ Inverses‚ Counting‚ and Conjunctive Queries
per: Rudolph, S, et al.
Publicat: (2010)

Counting homomorphisms to K4-minor-free graphs, modulo 2
per: Focke, J, et al.
Publicat: (2021)

Conjunctive Queries for a Tractable Fragment of OWL 1.1.
per: Krötzsch, M, et al.
Publicat: (2007)

Tractability beyond β-acyclicity for conjunctive queries with negation and SAT
per: Lanzinger, MP
Publicat: (2022)

Tractable Query Answering over Conceptual Schemata
per: Calì, A, et al.
Publicat: (2009)

Tractable Query Answering over Ontologies with Datalog+⁄−
per: Calì, A, et al.
Publicat: (2009)

Tractable query answering for description logics via query rewriting
per: Perez-Urbina, H, et al.
Publicat: (2010)

Answering Queries using Views over Probabilistic XML: Complexity and Tractability
per: Cautis, B, et al.
Publicat: (2012)

Answering Queries using Views over Probabilistic XML: Complexity and Tractability
per: Cautis, B, et al.
Publicat: (2012)

Conjunctive Query Answering for the Description Logic SHIQ
per: Glimm, B, et al.
Publicat: (2008)

Conjunctive Query Answering in Probabilistic Datalog+⁄− Ontologies
per: Gottlob, G, et al.
Publicat: (2011)

Conjunctive Query Answering in the Description Logic SHIQ
per: Glimm, B, et al.
Publicat: (2007)

Conjunctive Query Answering in Probabilistic Datalog+/- Ontologies.
per: Gottlob, G, et al.
Publicat: (2011)

Conjunctive Query Answering in the Description Logic SHIQ
per: Glimm, B, et al.
Publicat: (2006)

Conjunctive query answering for the description logic SHIQ
per: Glimm, B, et al.
Publicat: (2008)

Conjunctive Query Answering for Description Logics with Transitive Roles
per: Glimm, B, et al.
Publicat: (2006)

Counting homomorphisms to K4-minor-free graphs, modulo 2
per: Focke, J, et al.
Publicat: (2021)

The complexity of acyclic conjunctive queries
per: Gottlob, G, et al.
Publicat: (2001)

The Complexity of Acyclic Conjunctive Queries
per: Gottlob, G, et al.
Publicat: (1998)

Tractable Query Answering over Conceptual Schemata (Extended Abstract)
per: Calì, A, et al.
Publicat: (2010)

Tractable query answering and rewriting under description logic constraints.
per: Pérez-Urbina, H, et al.
Publicat: (2010)

Tractable Query Answering and Rewriting under Description Logic Constraints
per: Pérez−Urbina, H, et al.
Publicat: (2009)

Complexity of answering counting aggregate queries over DL-Lite
per: Kostylev, E, et al.
Publicat: (2013)

Complexity of answering counting aggregate queries over DL - Lite
per: Kostylev, E, et al.
Publicat: (2015)

The complexity of answering conjunctive and navigational queries over OWL 2 EL knowledge bases
per: Stefanoni, G, et al.
Publicat: (2014)

Conjunctive query answering over unrestricted OWL 2 ontologies
per: Igne, F, et al.
Publicat: (2023)

Conjunctive query answering over unrestricted OWL 2 ontologies
per: Igne, F
Publicat: (2022)

The complexity of conjunctive queries with degree 2
per: Lanzinger, M
Publicat: (2022)

Nominals‚ Inverses‚ Counting‚ and Conjunctive Queries or Why Infinity is your Friend!
per: Glimm, B, et al.
Publicat: (2009)

On Tractable Queries and Constraints
per: Gottlob, G, et al.
Publicat: (1999)