Ontology-Mediated Querying on Databases of Bounded Cliquewidth
This work addresses query evaluation efficiency in databases with structural constraints, providing incremental theoretical improvements for computational logic and database communities.
The paper tackled the evaluation of ontology-mediated queries on databases with bounded cliquewidth, showing that all studied problems are fixed-parameter linear with respect to the combined parameter of OMQ size and cliquewidth.
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 $\mathcal{ALC}$ and $\mathcal{ALCI}$ as well as the guarded two-variable fragment GF$_2$ 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.