{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T07:00:55Z","timestamp":1762326055564,"version":"build-2065373602"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,11]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.24963\/kr.2025\/40","type":"proceedings-article","created":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:10:44Z","timestamp":1762323044000},"page":"407-416","source":"Crossref","is-referenced-by-count":0,"title":["Fitting Ontologies and Constraints to Relational Structures"],"prefix":"10.24963","author":[{"given":"Simon","family":"Hosemann","sequence":"first","affiliation":[{"name":"Leipzig University"}]},{"given":"Jean Christoph","family":"Jung","sequence":"additional","affiliation":[{"name":"TU Dortmund University"}]},{"given":"Carsten","family":"Lutz","sequence":"additional","affiliation":[{"name":"Leipzig University"},{"name":"Center for Scalable Data Analytics and Artificial Intelligence (ScaDS.AI)"}]},{"given":"Sebastian","family":"Rudolph","sequence":"additional","affiliation":[{"name":"TU Dresden"},{"name":"Center for Scalable Data Analytics and Artificial Intelligence (ScaDS.AI)"}]}],"member":"10584","event":{"name":"22nd International Conference on Principles of Knowledge Representation and Reasoning {KR-2025}","theme":"Artificial Intelligence","location":"Melbourne, Australia","acronym":"KR-2025","number":"22","sponsor":["Artificial Intelligence Journal","Principles of Knowledge Representation and Reasoning Inc.","Academic College of Tel-Aviv","European Association for Artificial Intelligence","National Science Foundation"],"start":{"date-parts":[[2025,11,11]]},"end":{"date-parts":[[2025,11,17]]}},"container-title":["Proceedings of the TwentySecond International Conference on Principles of Knowledge Representation and Reasoning"],"original-title":[],"deposited":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:11:09Z","timestamp":1762323069000},"score":1,"resource":{"primary":{"URL":"https:\/\/proceedings.kr.org\/2025\/40"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2025,11]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/kr.2025\/40","relation":{},"subject":[],"published":{"date-parts":[[2025,11]]}}}