KR2022Proceedings of the 19th International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 19th International Conference on Principles of Knowledge Representation and Reasoning

Haifa, Israel. July 31–August 5, 2022.

Edited by
  1. Gabriele Kern-Isberner
  2. Gerhard Lakemeyer
  3. Thomas Meyer

ISSN: 2334-1033
ISBN: 978-1-956792-01-0

Sponsored by
Published by

Copyright © 2022 International Joint Conferences on Artificial Intelligence Organization

Ontology-Mediated Querying on Databases of Bounded Cliquewidth

  1. Carsten Lutz(Leipzig University)
  2. Leif Sabellek(University of Bremen)
  3. Lukas Schulze(Leipzig University)
PDF
BibTeX
https://doi.org/10.24963/kr.2022/25

Keywords

  1. Ontology-based data access, integration, and exchange
  2. Description logics

Abstract

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.