Approximately counting answers to conjunctive queries with disequalities and negations

Approximately counting answers to conjunctive queries with disequalities and negations

Taispeáin leaganacha eile (1)

<p>We study the complexity of approximating the number of answers to a small query 𝜑 in a large database D. We establish an exhaustive classification into tractable and intractable cases if 𝜑 is a conjunctive query possibly including disequalities and negations:</p> <br> <p>•...

Cur síos iomlán

Sonraí bibleagrafaíochta
Príomhchruthaitheoirí:	Focke, J, Goldberg, L, Roth, M, Zivny, S
Formáid:	Journal article
Teanga:	English
Foilsithe / Cruthaithe:	Association for Computing Machinery 2024

Míreanna comhchosúla

Approximately counting answers to conjunctive queries with disequalities and negations
de réir: Focke, J, et al.
Foilsithe / Cruthaithe: (2022)

Counting answers to unions of conjunctive queries: natural tractability criteria and meta-complexity
de réir: Focke, J, et al.
Foilsithe / Cruthaithe: (2024)

The complexity of approximately counting retractions
de réir: Focke, J, et al.
Foilsithe / Cruthaithe: (2019)

The complexity of approximately counting retractions
de réir: Focke, J, et al.
Foilsithe / Cruthaithe: (2020)

The complexity of approximately counting retractions to square-free graphs
de réir: Focke, J, et al.
Foilsithe / Cruthaithe: (2021)

The Weisfeiler-Leman dimension of conjunctive queries
de réir: Göbel, A, et al.
Foilsithe / Cruthaithe: (2024)

Conjunctive Query Answering in Probabilistic Datalog+/- Ontologies.
de réir: Gottlob, G, et al.
Foilsithe / Cruthaithe: (2011)

Conjunctive query answering for the description logic SHIQ
de réir: Glimm, B, et al.
Foilsithe / Cruthaithe: (2008)

Conjunctive Query Answering for the Description Logic SHIQ
de réir: Glimm, B, et al.
Foilsithe / Cruthaithe: (2008)

Conjunctive Query Answering in Probabilistic Datalog+⁄− Ontologies
de réir: Gottlob, G, et al.
Foilsithe / Cruthaithe: (2011)

Conjunctive Query Answering in the Description Logic SHIQ
de réir: Glimm, B, et al.
Foilsithe / Cruthaithe: (2007)

Conjunctive Query Answering in the Description Logic SHIQ
de réir: Glimm, B, et al.
Foilsithe / Cruthaithe: (2006)

Counting homomorphisms to K4-minor-free graphs, modulo 2
de réir: Focke, J, et al.
Foilsithe / Cruthaithe: (2021)

Nominals‚ Inverses‚ Counting‚ and Conjunctive Queries
de réir: Rudolph, S, et al.
Foilsithe / Cruthaithe: (2010)

Counting homomorphisms to K4-minor-free graphs, modulo 2
de réir: Focke, J, et al.
Foilsithe / Cruthaithe: (2021)

Conjunctive Query Answering for Description Logics with Transitive Roles
de réir: Glimm, B, et al.
Foilsithe / Cruthaithe: (2006)

The complexity of counting surjective homomorphisms and compactions
de réir: Focke, J, et al.
Foilsithe / Cruthaithe: (2017)

The complexity of counting surjective homomorphisms and compactions
de réir: Focke, J, et al.
Foilsithe / Cruthaithe: (2019)

Conjunctive query answering over unrestricted OWL 2 ontologies
de réir: Igne, F, et al.
Foilsithe / Cruthaithe: (2023)

Conjunctive query answering over unrestricted OWL 2 ontologies
de réir: Igne, F
Foilsithe / Cruthaithe: (2022)

Boolean tensor decomposition for conjunctive queries with negation
de réir: Abo Khamis, M, et al.
Foilsithe / Cruthaithe: (2019)

Bounds for the query complexity of approximate equilibria
de réir: Goldberg, PW, et al.
Foilsithe / Cruthaithe: (2016)

OLAP Techniques for Approximation and Mining Query Answering
de réir: Murtadaha Hamd, et al.
Foilsithe / Cruthaithe: (2010-12-01)

Tractability beyond β-acyclicity for conjunctive queries with negation
de réir: Lanzinger, M
Foilsithe / Cruthaithe: (2021)

Answering conjunctive queries over EL knowledge bases with transitive and reflexive roles
de réir: Stefanoni, G, et al.
Foilsithe / Cruthaithe: (2015)

The complexity of answering conjunctive and navigational queries over OWL 2 EL knowledge bases
de réir: Stefanoni, G, et al.
Foilsithe / Cruthaithe: (2014)

Complexity of approximate query answering under inconsistency in datalog+/-
de réir: Lukasiewicz, T, et al.
Foilsithe / Cruthaithe: (2018)

Complexity of approximate query answering under inconsistency in Datalog+/-
de réir: Lukasiewicz, T, et al.
Foilsithe / Cruthaithe: (2018)

Nominals‚ Inverses‚ Counting‚ and Conjunctive Queries or Why Infinity is your Friend!
de réir: Glimm, B, et al.
Foilsithe / Cruthaithe: (2009)

Complexity of answering counting aggregate queries over DL-Lite
de réir: Kostylev, E, et al.
Foilsithe / Cruthaithe: (2013)

Complexity of answering counting aggregate queries over DL - Lite
de réir: Kostylev, E, et al.
Foilsithe / Cruthaithe: (2015)

Containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons
de réir: Sherkhonov, E, et al.
Foilsithe / Cruthaithe: (2016)

The Hidden Disequities of Carbon Trading: Carbon Emissions, Air Toxics, and Environmental Justice
de réir: Raul P. Lejano, et al.
Foilsithe / Cruthaithe: (2020-11-01)

Tractability beyond β-acyclicity for conjunctive queries with negation and SAT
de réir: Lanzinger, MP
Foilsithe / Cruthaithe: (2022)

The Complexity of Explaining Negative Query Answers in DL−Lite
de réir: Calvanese, D, et al.
Foilsithe / Cruthaithe: (2012)

Answering counting aggregate queries over ontologies of the DL-Lite family
de réir: Kostylev, E, et al.
Foilsithe / Cruthaithe: (2013)

Explanations for negative query answers under existential rules
de réir: Ceylan, I, et al.
Foilsithe / Cruthaithe: (2020)

Conjunctive queries with negation over DL-Lite: A closer look
de réir: Gutiérrez-Basulto, V, et al.
Foilsithe / Cruthaithe: (2013)

Semantic optimization of conjunctive queries
de réir: Barcelo, P, et al.
Foilsithe / Cruthaithe: (2020)

Handling Cyclic Conjunctive Queries
de réir: Glimm, B, et al.
Foilsithe / Cruthaithe: (2005)