Tractability beyond β-acyclicity for conjunctive queries with negation

Tractability beyond β-acyclicity for conjunctive queries with negation

Numerous fundamental database and reasoning problems are known to be NP-hard in general but tractable on instances where the underlying hypergraph structure is β-acyclic. Despite the importance of many of these problems, there has been little success in generalizing these results beyond acyclicity....

Cur síos iomlán

Sonraí bibleagrafaíochta
Príomhchruthaitheoir:	Lanzinger, M
Formáid:	Conference item
Teanga:	English
Foilsithe / Cruthaithe:	Association for Computing Machinery 2021

Míreanna comhchosúla

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

The complexity of acyclic conjunctive queries
de réir: Gottlob, G, et al.
Foilsithe / Cruthaithe: (2001)

The Complexity of Acyclic Conjunctive Queries
de réir: Gottlob, G, et al.
Foilsithe / Cruthaithe: (1998)

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

Conjunctive Queries for a Tractable Fragment of OWL 1.1.
de réir: Krötzsch, M, et al.
Foilsithe / Cruthaithe: (2007)

The complexity of conjunctive queries with degree 2
de réir: Lanzinger, M
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)

On Tractable Queries and Constraints
de réir: Gottlob, G, et al.
Foilsithe / Cruthaithe: (1999)

Hypertree Decompositions and Tractable Queries
de réir: Gottlob, G, et al.
Foilsithe / Cruthaithe: (1998)

Hypertree Decompositions and Tractable Queries
de réir: Gottlob, G, et al.
Foilsithe / Cruthaithe: (2002)

Hypertree Decompositions and Tractable Queries
de réir: Gottlob, G, et al.
Foilsithe / Cruthaithe: (1999)

Hypertree Decompositions and Tractable Queries
de réir: Gottlob, G, et al.
Foilsithe / Cruthaithe: (1999)

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

Tractable query answering for description logics via query rewriting
de réir: Perez-Urbina, H, et al.
Foilsithe / Cruthaithe: (2010)

Tractable Query Answering over Conceptual Schemata
de réir: Calì, A, et al.
Foilsithe / Cruthaithe: (2009)

Tractable Query Answering over Ontologies with Datalog+⁄−
de réir: Calì, A, et al.
Foilsithe / Cruthaithe: (2009)

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

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

Rewriting with Acyclic Queries: Mind Your Head
de réir: Gaetano Geck, et al.
Foilsithe / Cruthaithe: (2023-11-01)

Acyclicity Conditions and their Application to Query Answering in Description Logics
de réir: Grau, B, et al.
Foilsithe / Cruthaithe: (2012)

Acyclicity Conditions and their Application to Query Answering in Description Logics
de réir: Grau, B, et al.
Foilsithe / Cruthaithe: (2012)

Tractable query answering and rewriting under description logic constraints.
de réir: Pérez-Urbina, H, et al.
Foilsithe / Cruthaithe: (2010)

Evaluation of relational algebra queries on probabilistic databases: tractability and approximation
de réir: Fink, RD
Foilsithe / Cruthaithe: (2014)

Tractable Query Answering over Conceptual Schemata (Extended Abstract)
de réir: Calì, A, et al.
Foilsithe / Cruthaithe: (2010)

Tractable Query Answering and Rewriting under Description Logic Constraints
de réir: Pérez−Urbina, H, et al.
Foilsithe / Cruthaithe: (2009)

Path querying on acyclic graphs using Boolean grammars
de réir: Ekaterina Nikolaevna Shemetova, et al.
Foilsithe / Cruthaithe: (2019-10-01)

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)

Conjunctive Query Entailment for SHOQ
de réir: Glimm, B, et al.
Foilsithe / Cruthaithe: (2007)

Unions of Conjunctive Queries in SHOQ
de réir: Glimm, B, et al.
Foilsithe / Cruthaithe: (2008)

Conjunctive queries over trees
de réir: Gottlob, G, et al.
Foilsithe / Cruthaithe: (2006)

Conjunctive Queries over Trees
de réir: Gottlob, G, et al.
Foilsithe / Cruthaithe: (2006)

Conjunctive Queries over Trees
de réir: Gottlob, G, et al.
Foilsithe / Cruthaithe: (2004)

Semantic width and the fixed-parameter tractability of constraint satisfaction problems
de réir: Chen, H, et al.
Foilsithe / Cruthaithe: (2020)

Acyclicity notions for existential rules and their application to query answering in ontologies
de réir: Grau, B, et al.
Foilsithe / Cruthaithe: (2013)

Answering Queries using Views over Probabilistic XML: Complexity and Tractability
de réir: Cautis, B, et al.
Foilsithe / Cruthaithe: (2012)

Answering Queries using Views over Probabilistic XML: Complexity and Tractability
de réir: Cautis, B, et al.
Foilsithe / Cruthaithe: (2012)

Conjunctive queries for EL with role composition
de réir: Krötzsch, M, et al.
Foilsithe / Cruthaithe: (2007)

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