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 ℰℒ and ℰℒℐ 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.
using unary and binary relation symbols. Let ℒ be one of the TGD classes mentioned above (including ℰℒ(ℐ)-CIs). Further let (P, N) be a pair of finite sets of instances, henceforth called a fitting instance . We say that an ℒ-ontology fits (P, N) if |= for all ∈ P and ̸|= for all ∈ N. For a single ℒ-TGD , fitting (P, N) is defined in exactly the same way. The induced decision problems of fitting ℒ-ontology existence and fitting ℒ-TGD existence ask whether a given (P, N) admits a fitting ℒ-ontology or a fitting ℒ-TGD. We also consider the corresponding construction problems, where the goal is to construct a fitting ℒ-ontology or a fitting ℒ-TGD for (P, N), if one exists.
Example 1. Consider the instances = {(, ), (, )}, = {(, ), (, ), (, )}. Then ({ }, { }) has no fitting ℰℒℐ-CI, but it has fitting GTGDs such as
(, ) → (, ).
Now let ′ = ∪ {(, ), (, ), (, )}. Then ({ }, { ′}) has no fitting GTGD. But it has fitting FGTGDs such as
(, ) ∧ (, ) ∧ (, ) → (, ).
Example 2. Having ⊥ or not makes a diference. Let = {(, )}, = {(, )}. Then ∃.∃.⊤ ⊑ ⊥ fits ({ }, { }), but ({ }, { }) has no fitting ℰℒℐ-ontology.
All negative claims in Examples 1 and 2 are a consequence of the semantic characterizations for
iftting ℒ-TGD existence established in [
How are fitting ontologies and fitting TGDs related? The following is an immediate consequence of the definition of fitting and the semantics of ontologies and TGDs.
Lemma 1. Let (P, N) be a fitting instance. Then there is an ℒ-ontology that fits (P, N) if and only if for every ∈ N, there is an ℒ-TGD that fits (P, { }).
Hence, if (P, N) admits a fitting ℒ-ontology, it admits one with at most |N| TGDs.
The problem of fitting an ontology to a given set of examples turns out to be closely related to a
problem that has been studied in the area of description logic and is known as finite basis construction
[
Lemma 2. Let (P, N) be a fitting instance and let P be a finite ℒ-basis of P. Then P fits (P, N) if and only if (P, N) has a fitting ℒ-ontology.
If finite ℒ-bases always exists, we can thus solve the ℒ-ontology fitting problem for any (P, N) by constructing P and checking whether it fits the input examples. This approach in fact often yields decidability and tight upper complexity bounds.
We first consider the DLs ℰℒ and ℰℒℐ as well as their extensions with the ⊥ concept. We reprove the
existence of finite bases for ℰℒ, already known from [
In order to obtain lower complexity bounds, we provide a semantic characterization of fitting ℰℒ- and ℰℒℐ-CI existence in terms of simulations and direct products. Let ℒ ∈ {ℰℒ, ℰℒℐ}. For unary pointed instances (, ) and (, ) we write (, ) ⪯ ℒ (, ) if there exists an ℒ-simulation from to that contains the pair (, ). Recall that an ℰℒ-simulation preserves concept names and the existence of role-successors, whereas an ℰℒℐ-simulation must in addition preserve role-predecessors, reflecting inverse roles. For a non-empty finite set H of instances with pairwise disjoint active domains, we use ⨄︀H to denote the instance ⋃︀ H. When the domains of the instances in H are not pairwise disjoint, we assume that renaming is used to achieve disjointness before forming ⨄︀H. We next present the characterization for fitting ℰℒ⊥- and ℰℒℐ⊥-CI existence.
Theorem 1. Let ℒ ∈ {ℰℒ, ℰℒℐ}. Let (P, N) be a fitting instance where N = {1, . . . , } and let = ⨄︀P. Then no ℒ⊥-concept inclusion fits (P, N) if and only if for all ¯= ( 1, . . . , ) ∈ ∆ ∏︀ N, the following condition is satisfied: ¯ = {(, ) | (∏︁ N, ¯) ⪯ ℒ (, )} is non-empty and ∏︁ ¯ ⪯ ℒ (, ) for some ∈ [].
An extended version of Theorem 1, also covering the cases of ℰℒ and ℰℒℐ without ⊥ is provided
in [
We next turn to TGDs. For guarded TGDs, we implement exactly the same program described above for ℰℒ(ℐ), but obtain diferent complexities. We show that finite GTGD-bases always exist and establish a tight single exponential bound on their size. Succinct representation does not help to reduce the size. We give a characterization of fitting GTGD existence and fitting GTGD-ontology existence in terms of products and homomorphisms, show that fitting GTGD existence and fitting GTGD-ontology existence is coNExpTime-complete, and give a tight single exponential bound on the size of fitting GTGDs and GTGD-ontologies. The coNExpTime upper bound may be obtained either via finite bases or via the semantic characterization.
For the remaining classes of TGDs, the approach via finite bases fails: for the frontier-guarded, frontier-one, and full case, we prove that finite bases need not exist. For inclusion dependencies, finite bases trivially exist but approaching fitting via this route does not result in an optimal upper complexity bound. For unrestricted TGDs, the existence of finite bases is left open.
Theorem 2. For ℒ ∈ {FGTGD, F1TGD, FullTGD}, there exist instances that have no finite ℒ-basis. Example 3. Consider the instance = {(, ), (, )}. It has no finite FGTGD- and no finite F1TGDbasis. For every ≥ 1, consider the frontier-one TGD =
⋀︁ ∈[− 1]
(, +1) ∧ (, 1) → (1, 1).
The TGD expresses that if 1 lies on a cycle of length , then 1 has a reflexive loop. We have |= for all odd because (i) a cycle homomorphically maps to if and only if it is of even length and (ii) contains no reflexive loops. Note that the rule bodies of the TGDs with odd get larger with increasing . Intuitively, this means that also the rule bodies of any finite FGTGD-basis of must be of unbounded size, which means that there is no finite FGTGD-basis.
We may, however, still approach fitting existence in a direct way or via a semantic characterization. For inclusion dependencies (IND), we use direct arguments to show that fitting IND existence and fitting IND-ontology existence is NP-complete, and that the size of fitting IND-ontologies is polynomial. For all remaining cases, we establish semantic characterizations in terms of products and homomorphisms and then use them to approach fitting existence. In this way, we prove the following. Fitting ontology existence and fitting TGD existence are coNExpTime-complete for TGDs that are frontier-guarded or frontier-one. For full TGDs, fitting TGD existence is coNExpTime-complete and fitting ontology existence is in Σ 2 and DP-hard. In the case of unrestricted TGDs, both problems are coNExpTime-hard and we prove a co2NExpTime upper bound for fitting ontology existence and a co3NExpTime upper bound for fitting TGD existence. We also show tight single exponential size bounds for fitting TGDs and ontologies in the case of frontier-guarded and frontier-one TGDs. We do the same for fitting full TGDs while if there is a fitting FullTGD-ontology, then there is always one of polynomial size. For unrestricted TGD and TGD-ontology fittings, we give a single exponential lower bound and a triple (for TGDs) and double (for ontologies) exponential upper bound on the size.
This work is partly supported by BMFTR (Federal Ministry of Research, Technology and Space) in DAAD project 57616814 (SECAI, School of Embedded Composite AI) as part of the program Konrad Zuse Schools of Excellence in Artificial Intelligence.
The second and third author were supported by DFG project JU 3197/1-1.
The authors have not employed any Generative AI tools.