Neues Papier klärt Komplexität von Ontologien in relationalen Strukturen

In einer kürzlich veröffentlichten Studie auf arXiv (2508.13176v1) wird das Problem untersucht, Ontologien und Einschränkungen an positive und negative Beispiele anzupassen, die als endliche relationale Strukturen vorliegen. Die Autoren betrachten dabei die Description Logics EL und ELI sowie verschiedene Klassen von tuple-generating Dependencies (TGDs) – darunter voll, guarded, frontier-guarded, frontier-one und unrestricted TGDs – sowie Inclusion Dependencies.

Die Arbeit liefert präzise Ergebnisse zur Rechenkomplexität, entwickelt effiziente Algorithmen und analysiert die Größe der passenden Ontologien und TGDs. Zusätzlich wird das verwandte Problem der Konstruktion einer endlichen Basis aus Konzeptinklusionen bzw. TGDs für gegebene Strukturen untersucht. Während für EL, ELI, guarded TGDs und Inclusion Dependencies solche endlichen Basen existieren, sind sie im Allgemeinen bei voll, frontier-guarded und frontier-one TGDs nicht vorhanden.