KR2025Proceedings of the 22nd International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning

Melbourne, Australia. November 11-17, 2025.

Edited by
  1. Magdalena Ortiz
  2. Renata Wassermann
  3. Torsten Schaub

ISSN: 2334-1033
ISBN: 978-1-956792-08-9

Sponsored by
Published by

Copyright © 2025 International Joint Conferences on Artificial Intelligence Organization

Fitting Ontologies and Constraints to Relational Structures

  1. Simon Hosemann(Leipzig University)
  2. Jean Christoph Jung(TU Dortmund University)
  3. Carsten Lutz(Leipzig University, Center for Scalable Data Analytics and Artificial Intelligence (ScaDS.AI))
  4. Sebastian Rudolph(TU Dresden, Center for Scalable Data Analytics and Artificial Intelligence (ScaDS.AI))
PDF
BibTeX
https://doi.org/10.24963/kr.2025/40

Keywords

  1. Fitting Problems
  2. Ontologies
  3. Database Constraints
  4. Description Logic
  5. Tuple-generating Dependencies
  6. Data Examples

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 EL and ELI 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 EL, ELI, guarded TGDs, and inclusion dependencies, they in general do not exist for full, frontier-guarded and frontier-one TGDs.