Fitting Ontologies and Constraints to Relational Structures

Simon Hosemann, Jean Christoph Jung, Carsten Lutz, Sebastian Rudolph
8/11/2025
cs.AIcs.DB

No confident code implementation found for this paper.

Abstract

We study the problem of fitting ontologies and constraints to positive and negative examples that take the form of a finite relational structure. As ontology and constraint languages, we consider the description logics $\mathcal{E\mkern-2mu L}$ and $\mathcal{E\mkern-2mu LI}$ as well as several classes of tuple-generating dependencies (TGDs): full, guarded, frontier-guarded, frontier-one, and unrestricted TGDs as well as inclusion dependencies. We pinpoint the exact computational complexity, design algorithms, and analyze the size of fitting ontologies and TGDs. We also investigate the related problem of constructing a finite basis of concept inclusions / TGDs for a given set of finite structures. While finite bases exist for $\mathcal{E\mkern-2mu L}$, $\mathcal{E\mkern-2mu LI}$, guarded TGDs, and inclusion dependencies, they in general do not exist for full, frontier-guarded and frontier-one TGDs.

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

CSPs with Few Alien Constraints

80% match2024

Fitting Description Logic Ontologies to ABox and Query Examples

79% match2025

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

77% match2024

Efficient Dependency Analysis for Rule-Based Ontologies

77% match2022

Robustness of Constraint Automata for Description Logics with Concrete Domains

76% match2026

Decidability of Querying First-Order Theories via Countermodels of Finite Width

76% match2023

Cite this paper

@article{hosemann2025fitting,
  title  = {Fitting Ontologies and Constraints to Relational Structures},
  author = {Simon Hosemann and Jean Christoph Jung and Carsten Lutz and Sebastian Rudolph},
  year   = {2025},
  eprint = {2508.13176},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2508.13176v1}
}

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.13176.svg)](https://codeofpaper.com/paper/2508.13176)

Discussion