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....
מחבר ראשי: | Lanzinger, M |
---|---|
פורמט: | Conference item |
שפה: | English |
יצא לאור: |
Association for Computing Machinery
2021
|
פריטים דומים
-
Tractability beyond β-acyclicity for conjunctive queries with negation and SAT
מאת: Lanzinger, MP
יצא לאור: (2022) -
The complexity of acyclic conjunctive queries
מאת: Gottlob, G, et al.
יצא לאור: (2001) -
The Complexity of Acyclic Conjunctive Queries
מאת: Gottlob, G, et al.
יצא לאור: (1998) -
Containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons
מאת: Sherkhonov, E, et al.
יצא לאור: (2016) -
Conjunctive Queries for a Tractable Fragment of OWL 1.1.
מאת: Krötzsch, M, et al.
יצא לאור: (2007)