AAAI 2023technical2 citations
Efficient Answer Enumeration in Description Logics with Functional Roles
Carsten Lutz, Marcin Przybyłko
Abstract
We study the enumeration of answers to ontology-mediated queries when the ontology is formulated in a description logic that supports functional roles and the query is a CQ. In particular, we show that enumeration is possible with linear preprocessing and constant delay when a certain extension of the CQ (pertaining to functional roles) is acyclic and free-connex acyclic. This holds both for complete answers and for partial answers. We provide matching lower bounds for the case where the query is self-join free.
BibTeX
@article{Lutz_Przybyłko_2023, title={Efficient Answer Enumeration in Description Logics with Functional Roles}, volume={37}, url={https://ojs.aaai.org/index.php/AAAI/article/view/25797}, DOI={10.1609/aaai.v37i5.25797}, abstractNote={We study the enumeration of answers to ontology-mediated queries
when the ontology is formulated in a description logic that supports
functional roles and the query is a CQ. In particular, we show that
enumeration is possible with linear preprocessing and constant delay
when a certain extension of the CQ (pertaining to functional roles)
is acyclic and free-connex acyclic. This holds both for complete answers and
for partial answers. We provide matching lower bounds for the
case where the query is self-join free.}, number={5}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Lutz, Carsten and Przybyłko, Marcin}, year={2023}, month={Jun.}, pages={6483-6490} }