Ontology-Mediated Querying on Databases of Bounded Cliquewidth
Not on the map. Why?
Abstract (arXiv)
We study the evaluation of ontology-mediated queries (OMQs) on databases of bounded cliquewidth from the viewpoint of parameterized complexity theory. As the ontology language, we consider the description logics ALC and ALCI as well as the guarded two-variable fragment GF2 of first-order logic. Queries are atomic queries (AQs), conjunctive queries (CQs), and unions of CQs. All studied OMQ problems are fixed-parameter linear (FPL) when the parameter is the size of the OMQ plus the cliquewidth. Our main contribution is a detailed analysis of the dependence of the running time on the parameter, exhibiting several interesting effects.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 5 of its 69 references that are in the map. First posted on arXiv 4 May 2022.
Builds on
5 of 69 references.
References · 5
- 2013Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNPcited by 15
- 2021A Single-Exponential Time 2-Approximation Algorithm for Treewidthcited by 8
- 2019An Experimental Study of the Treewidth of Real-World Graph Data (Extended Version)cited by 7
- 2013Unary negationcited by 4
- 2021How to Approximate Ontology-Mediated Queriescited by 2
Built on by
Not cited yet.