# Fitting Ontologies and Constraints to Relational Structures

arXiv: https://arxiv.org/abs/2508.13176 · HTML: https://mlsanity.com/paper/2508.13176/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 47 references that are in the map.
- First posted on arXiv 11 Aug 2025.

## Builds on (most cited first, 7 of 7)

- [Logical Separability of Labeled Data Examples under Ontologies](https://mlsanity.com/paper/2007.01610/) (2020)
- [The complexity of reverse engineering problems for conjunctive queries](https://mlsanity.com/paper/1606.01206/) (2016)
- [Extremal Fitting Problems for Conjunctive Queries](https://mlsanity.com/paper/2206.05080/) (2022)
- [Separating Data Examples by Description Logic Concepts with Restricted Signatures](https://mlsanity.com/paper/2107.05285/) (2021)
- [SAT-Based PAC Learning of Description Logic Concepts](https://mlsanity.com/paper/2305.08511/) (2023)
- [Mining EL Bases with Adaptable Role Depth](https://mlsanity.com/paper/2102.10689/) (2021)
- [On the non-efficient PAC learnability of conjunctive queries](https://mlsanity.com/paper/2208.10255/) (2022)

## Built on by (most cited first, 1 of 1)

- [Fitting Horn DL Ontologies to ABox and Query Examples: A Tale of Simulation Quantifiers and Finite Models](https://mlsanity.com/paper/2604.26976/) (2026)

## Abstract (arXiv)

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 Emkern-2mu L and Emkern-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 Emkern-2mu L, Emkern-2mu LI, guarded TGDs, and inclusion dependencies, they in general do not exist for full, frontier-guarded and frontier-one TGDs.