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.
翻译:我们从参数复杂理论的角度研究对受约束的分界数据库中以本体介质查询(OMQs)的评价。作为本体学语言,我们考虑描述逻辑值$\mathcal{ALC}$和$mathcal{ALCI}$,以及第一级逻辑的两处可调控的碎片值$2GF$。答案是原子查询(AQs)、连结查询(CQs)和CQs的结合。当参数是OMQ和cloquewid的大小时,所有所研究的OMQ问题都是固定的参数线性线性(FPL)。我们的主要贡献是对运行时间对参数的依赖性进行详细分析,显示出一些有趣的效果。