Count-Preserving Forgetting for Ontologies

Ontology engineers often "forget" auxiliary vocabulary. They delete helper concept names from a knowledge base while keeping every consequence that can be stated in the remaining words. The resulting view is called a uniform interpolant. Tools that compute these views are judged by one criterion: the view must entail exactly the same yes/no facts as the original. This note starts from a small observation. That criterion says nothing about how many answers a query has. Take the axioms "every A has an R-successor that is B", "every A has an R-successor that is C", and "nothing is both B and C". Forgetting B and C yields the standard interpolant "every A has an R-successor". A reasoner that counts guaranteed R-successors of an A-individual finds two under the original ontology and one under the interpolant. The Boolean view is correct and still gives the wrong count.

We propose to make count preservation a first-class notion of forgetting and to study its finite representability. The idea has two parts. First, a forgotten ontology may have no finite axiomatization in its own logic. Even so, its counting behaviour on finite data can have a finite representation: a constant-depth arithmetic formula over the remaining vocabulary. Second, the logics that characterize $\#\text{AC}^0$, the class of functions computed by constant-depth circuits of unbounded fan-in addition and multiplication, are the right target language for such representations. For the shallow Horn ontologies that dominate practice, we conjecture that count-preserving views always exist in this form, even when the Boolean interpolant does not exist in the host description logic.

Core Claim

The Boolean semantics of uniform interpolation is invariant under bisimulation. Bisimulation is the equivalence that cannot distinguish one witness from two. This invariance is exactly what lets it drop cardinality information. Lutz and Wolter characterize interpolants through $\Sigma$-bisimulations and tree automata, decide their existence in 2-EXPTIME, and show a triple-exponential size blowup (Foundations for Uniform Interpolation and Forgetting in Expressive Description Logics). They also show that the missing interpolants live in the modal μ-calculus, a fixpoint logic that is equally blind to counts.

Our claim has three parts. First, standard forgetting is not count-preserving, and the failure is not rare on real ontologies with disjointness axioms. Second, fix a counting conjunctive query, meaning a query that asks how many distinct matches must exist in every model of the ontology plus the data, as studied by Bienvenu, Manière and Thomazo (Counting Queries over ELHI⊥ Ontologies). For depth-bounded Horn ontologies whose Boolean query answering is first-order rewritable, the count is a function of the data over the target vocabulary that lies in $\#\text{AC}^0$. It is therefore definable by counting winning strategies in a first-order model-checking game, the $\#\text{Win-FO}$ characterization of Haak and Vollmer (A model-theoretic characterization of constant-depth arithmetic circuits). Third, this representation stays finite and polynomial in the query even when the Boolean interpolant is infinite, as in the chain example "A ⊑ ∃R.B, B ⊑ ∃R.B" after forgetting B.

The intuition for the second part is the following. In a depth-bounded Horn ontology, the anonymous part of the least model hangs off each data individual as a bounded tree. The shape of that tree depends only on the individual's finite concept type. The count then splits into two sums: a sum over matches inside the data, and a sum over individuals of a constant determined by their type. When types are first-order definable, that expression is a sum of products of first-order indicators, which is the normal form of $\#\text{Win-FO}$. The coNP-hardness shown by Bienvenu et al. marks where this breaks. It arises when anonymous witnesses may merge with named individuals in data-dependent ways. Our characterization must say precisely which syntactic conditions exclude such merges. That boundary is the main theoretical deliverable, not an assumption.

Research Program

The first strand is definitional. We define a count-preserving $\Sigma$-view of an ontology $\mathcal{O}$ as any object $V$ satisfying

$$\mathrm{cnt}_{\mathcal{O},\mathcal{A}}(q) = \mathrm{cnt}_{V,\mathcal{A}}(q)$$

for every finite data set $\mathcal{A}$ and every counting query $q$ over the target signature $\Sigma$. Here $\mathrm{cnt}$ is the minimum number of distinct matches over all models, following Bienvenu et al. We then separate three kinds of representation for $V$: a finite TBox in the host logic, a finite TBox in the host logic extended with qualified number restrictions, and a query-indexed family of $\#\text{Win-FO}$ counting terms. The counterexample above shows that the first kind can fail where Boolean interpolants exist. The second kind can repair that particular case with the axiom "A ⊑ ≥2 R.⊤". However, it inherits the infinite-chain problem of Lutz and Wolter. The third kind is our candidate for a representation that always exists on the tractable fragment.

The second strand is the characterization theorem and its boundary. The positive direction builds, from a depth-bounded Horn ontology with bottom and a fixed query, a uniform $\#\text{Win-FO}[+,\times]$ formula computing the count. We then transfer that formula to arithmetic circuits through Haak and Vollmer's uniform correspondence (their Theorem 19). The negative direction adapts the Bienvenu et al. hardness construction. The goal is to show that once role inclusions or inverses allow anonymous witnesses to merge with named individuals, the count leaves $\#\text{AC}^0$ unless standard complexity assumptions fail. Podolskii's analysis of query rewritings (Circuit Complexity Meets Ontology-Based Data Access) supplies the method for tying circuit class to "theory depth". He shows that depth-one theories give $\text{NC}^1$ Boolean rewritings and that greater depth leads to $\text{NP}/\text{poly}$. His results are Boolean and monotone, while ours concern arithmetic counting. The Skolem-function characterization of Durand, Haak, Kontinen and Vollmer (Descriptive Complexity of #AC0 Functions) gives an equivalent syntax that we expect to be easier to compile into SQL aggregates.

The third strand is quantitative. We measure the size of counting terms by total quantifier number, the measure Carmosino et al. showed tracks description size rather than depth (On the Number of Quantifiers Needed to Define Boolean Functions). Our conjecture is that count-sensitive depth, not Lutz and Wolter's worst case, controls this size. Count-sensitive depth is the depth to which cardinality lower bounds must be unfolded for a given query. If the conjecture holds, it would explain the empirical shrinkage reported by forgetting tools on real ontologies.

Baselines

The naive reference point is to do nothing about counts. We compute the Boolean view with UI-FAME (UI-FAME: A Deductive Forgetting Tool for Creating Views of ALC-TBoxes) and FAME (The FAME Family: A Family of Reasoning Tools for Forgetting in Expressive Description Logics). We then evaluate counting queries over that view with the same counting procedure used everywhere else. This is the strongest existing forgetting method on these corpora. FAME reports eliminating all requested symbols in over 90% of test cases. UI-FAME reports producing results logically equivalent to LETHE's in 97.08% of cases while using about 4x less memory. No reported result on count preservation for these tools was found on Lacuna. Beating this baseline means exhibiting a nontrivial rate of count divergence on real signatures where our view has zero divergence.

The second baseline is graded forgetting with FAME 2.0. This tool computes interpolants in a logic with qualified number restrictions and is therefore the most direct competitor. It will be run on identical ontology–signature pairs with the same timeout. Beating it means either finding count divergences that it misses, or finding cases where it fails to terminate or leaves definers behind while our counting terms exist.

The reference oracle is direct counting over the original ontology without forgetting, using a reimplementation of the Bienvenu et al. semantics on small generated data sets. That paper is theoretical, so no reported runtime exists to compare against. All methods get the same data, the same queries, and a fixed per-instance time budget. A key ablation replaces our count-sensitive unfolding with Boolean depth truncation at query size. This isolates whether cardinality-aware unfolding matters.

Why not just…?

Why not just use the μ-calculus interpolants of Lutz and Wolter? They make the infinite chain finite, but they are bisimulation-invariant by construction. They therefore cannot preserve the two-versus-one count in the opening example. No experiment is needed to show this. The disjointness counterexample settles it.

Why not just forget into a logic with number restrictions, as FAME 2.0 does? This is the real threat. On ontologies without recursive existentials it may already be count-preserving in practice. The experiments measure exactly this. If FAME 2.0 shows zero divergence and no termination failures on the corpus, our contribution shrinks to the theoretical claim for recursive cases. We would then report that honestly.

Why not just truncate the ontology at depth equal to query size? Query-size truncation preserves Boolean answers for bounded queries. But disjointness can force distinct witnesses beyond the depth the query touches, for example when a query counts successors whose distinctness is certified only deeper in the tree. The ablation measures how often count-sensitive depth exceeds query size on real ontologies. If it never does, the simpler truncation should be adopted as the method.

Why not just skip forgetting and count over the original ontology? Bienvenu et al. show coNP-complete data complexity for this counting in general. A precompiled $\#\text{AC}^0$ term would instead run as a single aggregate query. We compare wall-clock time against the oracle on the tractable fragment.

Proposed Experiments

We use the 396 clinical ontologies from BioPortal evaluated by FAME and the 494 Oxford-ISG ontologies evaluated by UI-FAME, which that paper stratifies into small, medium and large corpora. We restrict each ontology to its Horn fragment with bottom. Lutz and Wolter report that over 80% of 429 BioPortal ontologies have depth one (The Data Complexity of Description Logic Ontologies), so we expect most of the corpus to fall in the regime our theorem targets. Forgetting signatures of 10% and 30% of the vocabulary are sampled as in UI-FAME.

Neither corpus ships with data, so we generate synthetic data sets per ontology by sampling individuals and assertions over the target signature. We also generate counting queries up to a fixed size. The metrics are the following: the fraction of ontology–signature–query triples on which each baseline's count diverges from the oracle; exactness of our counting terms against the oracle; quantifier number of the terms as a function of count-sensitive depth; and evaluation time as SQL aggregates versus oracle time.

The first decisive check is whether divergence of Boolean views is nonzero and concentrated in ontologies with disjointness axioms. If it is essentially zero, the practical motivation fails. The second is whether counting terms match the oracle on every instance in the claimed fragment and fail only where the hardness boundary predicts. The third is whether term size tracks count-sensitive depth rather than ontology size.