Fitting Description Logic Ontologies to ABox and Query Examples

Maurice Funk, Marvin Grosser, Carsten Lutz
8/11/2025
cs.AIcs.LO

No confident code implementation found for this paper.

Abstract

We study a fitting problem inspired by ontology-mediated querying: given a collection of positive and negative examples of the form $(\mathcal{A},q)$ with $\mathcal{A}$ an ABox and $q$ a Boolean query, we seek an ontology $\mathcal{O}$ that satisfies $\mathcal{A} \cup \mathcal{O} \vDash q$ for all positive examples and $\mathcal{A} \cup \mathcal{O}\not\vDash q$ for all negative examples. We consider the description logics $\mathcal{ALC}$ and $\mathcal{ALCI}$ as ontology languages and a range of query languages that includes atomic queries (AQs), conjunctive queries (CQs), and unions thereof (UCQs). For all of the resulting fitting problems, we provide effective characterizations and determine the computational complexity of deciding whether a fitting ontology exists. This problem turns out to be ${\scriptsize CO}NP$ for AQs and full CQs and $2E{\scriptsize XP}T{\scriptsize IME}$-complete for CQs and UCQs. These results hold for both $\mathcal{ALC}$ and $\mathcal{ALCI}$.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Fitting Ontologies and Constraints to Relational Structures

79% match2025

DELE: Deductive $\mathcal{EL}^{++}$ Embeddings for Knowledge Base Completion

79% match1 repo32024

Enhancing Geometric Ontology Embeddings for $\mathcal{EL}^{++}$ with Negative Sampling and Deductive Closure Filtering

79% match2024

Reverse Engineering of Temporal Queries Mediated by LTL Ontologies

78% match2023

Logic Embeddings for Complex Query Answering

77% match1 repo202021

Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings

77% match1 repo2132020

Cite this paper

@article{funk2025fitting,
  title  = {Fitting Description Logic Ontologies to ABox and Query Examples},
  author = {Maurice Funk and Marvin Grosser and Carsten Lutz},
  year   = {2025},
  eprint = {2508.08007},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2508.08007v2}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2508.08007.svg)](https://codeofpaper.com/paper/2508.08007)

Discussion