The Chase as Decompressor: Certified Knowledge-Base Completion via Sample Compression

When a knowledge base comes with an ontology, many of its facts are redundant. Given "Alice is a Person" and the rule "every Person has a parent who is a Person," much of what is true follows from a few observed facts. This note proposes to make that redundancy into a formal generalization guarantee. The tool is a sample compression scheme: a way of keeping only a few training examples from which a fixed procedure can rebuild a hypothesis that agrees with all of them. When such a scheme exists, the hypothesis provably generalizes to unseen examples at a rate set by how few examples were kept.

The observation driving this note is simple. For any set of existential rules (logical rules that may assert the existence of unnamed objects), the map "database ↦ the ground facts it entails" is a closure operator. Rule-closed fact sets therefore form an intersection-closed concept class, and such classes admit a known compression scheme: keep a minimal generating set of positive examples, and rebuild by closing it. For these rules the rebuilding step is the chase, the forward-chaining procedure that applies rules until nothing new is derived. The chase can run forever. Recent Datalog rewritings for guarded rules make it a finite, total procedure on ground facts. Together, these give a learner whose generalization certificate is computed from the training data alone, and whose decompressor is a reasoner.

Core Claim

Fix a signature, a finite set of constants, and a rule set $\Sigma$. Write $\mathrm{cl}_\Sigma(D)$ for the set of ground atoms over those constants entailed by database $D$ under $\Sigma$. Three properties hold. The operator is extensive, since $D \subseteq \mathrm{cl}_\Sigma(D)$. It is monotone. It is idempotent, because adding entailed ground facts does not change the set of models. Hence the family $\mathcal{C}_\Sigma = \{\mathrm{cl}_\Sigma(D)\}$ is closed under intersection. This holds even though the chase itself may build an infinite structure of labeled nulls. Concretely, if both $\mathrm{cl}_\Sigma(D_1)$ and $\mathrm{cl}_\Sigma(D_2)$ contain a set $I$, monotonicity and idempotence put $\mathrm{cl}_\Sigma(I)$ inside both.

The learning task is knowledge-base completion. Ground atoms are drawn i.i.d. from a distribution over the atom space. Each atom is labeled by membership in an unknown $\Sigma$-closed target set. The learner keeps a minimal subset $K$ of the observed positives whose closure covers every observed positive, and predicts $h(\alpha)=1$ exactly when $\alpha \in \mathrm{cl}_\Sigma(K)$. Because the target is closed, $h$ never contradicts a negative example. Standard compression bounds then give, with probability $1-\delta$ over $n$ samples,

$$ \mathrm{err}(h) \;\le\; \frac{k\ln(en/k) + \ln(n/\delta)}{n-k}, $$

where $k=|K|$ is the observed compression size. The form comes from a union bound over at most $\binom{n}{k}$ choices of compression set and over the possible values of $k$. In this bound, "how much does the ontology buy?" becomes the number $k/n$. With no ontology ($\Sigma=\emptyset$), $K$ is every positive example and the certificate is vacuous. A rich ontology makes $k$ small and the certificate tight.

Relation to Prior Work

Prior work plays three roles here. The first group motivates the proposal by showing that sample compression can certify real learners. Floyd established that size-$k$ compression implies PAC learnability, but only for static binary classification. Pick-to-Learn wraps any base learner in a greedy selection loop: repeatedly add the worst-predicted point and retrain. This yields non-vacuous bounds without a held-out set, but it was demonstrated only on binary MNIST and one-dimensional regression. It also pays for repeated retraining, and it has no notion of examples that entail one another. We keep Pick-to-Learn's idea of certifying from the training data alone. We replace its generic retraining with an exact logical decompressor, so selection is a covering computation rather than a training loop. Finzi et al. obtain tight bounds by compressing the model's own description. We instead compress the data, and the "model" is the ontology plus a handful of facts.

The second group supplies the method. Compression schemes for intersection-closed classes are known: Rubinstein et al. give unlabelled schemes of size $11d$, and labeled closure-based schemes are classical. What has been missing is a naturally occurring, computationally nontrivial family of such classes where the closure is a reasoning problem. Making the closure computable is the job of Rewriting the Infinite Chase and Datalog Rewriting for Guarded TGDs. These works compile guarded existential rules (rules whose body variables all appear in one atom) into Datalog programs that entail exactly the same ground facts. Datalog is the existential-free fragment, so its evaluation always terminates. Their one-pass chase replaces repeated derivation loops with shortcut rules. This is the reconstructor we use, unchanged.

The third group constrains the design. Chase termination is undecidable in general (Cuenca Grau et al.). A reconstructor must be a total deterministic function, so our scheme is defined only for rule classes with a terminating rewriting or a verified acyclicity condition. These are guarded rules, linear rules (Leclère et al.), or rule sets that pass checks like the one in Carral and Urbani. The rewritings also degrade sharply as relation arity grows. That cost lands directly on our decompressor, and we measure it rather than hide it. Finally, Chase et al. show that embedding general classes into extremal ones forces an exponential blowup in dimension. This is why we do not route through extremal classes. Intersection-closed classes are a different "nice" family, and $\Sigma$-closed classes land in it directly.

Research Program

The theoretical strand has two parts. The first characterizes the VC dimension of $\mathcal{C}_\Sigma$ in terms of the rewritten Datalog program. For intersection-closed classes this dimension is the largest minimal generating set. We will bound it using the body sizes and dependency structure of the rewritten rules, and test whether the doubly exponential worst case of guarded rewriting shows up in the dimension or only in computation. The second part treats disjunctive existential rules, analyzed for termination by Gerlach and Carral. These rules break the closure property, so their consequence classes are not intersection-closed, and no $O(d)$ compression scheme is known for them. On small instances we will compute VC dimension and optimal compression size exhaustively. This gives the sample compression conjecture a structured, logic-generated testbed, rather than the hand-built combinatorial examples it usually relies on.

The systems strand builds the learner. The pipeline rewrites $\Sigma$ once with the existential-based or hyperresolution-based algorithm from Benedikt et al. It then computes $K$ by greedy or integer-programming set cover of the observed positives by closures of candidate generators, and evaluates $\mathrm{cl}_\Sigma(K)$ by Datalog materialization. To handle real, noisy knowledge bases, we add the standard agnostic extension, in which the compression scheme may misclassify a few training points. The bound then gains a training-error term, and the number of tolerated errors is chosen inside the union bound.

Baselines

The naive reference point is the same closure learner with an empty ontology. Its hypothesis is simply the observed positives, so $k$ equals the number of positives. Any certificate gain from the ontology must be measured against this. The practical reference point is a held-out test split with a binomial tail bound, run on the same total data budget, with the held-out fraction tuned over a small grid. Beating it means a tighter certified error at equal $n$ while training on all the data.

The strongest existing compression competitor is Pick-to-Learn (Paccagnan et al.). We run it in two forms. The first wraps a neural link predictor trained on the same facts. The second wraps our closure learner, which tests whether greedy worst-point selection finds smaller compression sets than exact covering. Both forms get the same data and wall-clock budget, with Pick-to-Learn's stopping threshold tuned on the training data only. The file reports no number for Pick-to-Learn on relational data; there is no reported result found on Lacuna for Pick-to-Learn on knowledge-base completion. We will therefore report its bound and test error side by side with ours.

The model-compression competitor is a description-length bound in the style of Finzi et al., applied to a quantized neural link predictor. For rule learning we also run a direct Occam bound that encodes the hypothesis as a subset of atoms.

The key ablation is to degrade the decompressor while keeping the class fixed. We approximate the closure with a depth-bounded chase instead of the exact rewriting. If the certificate stays as tight, exact infinite-chase reasoning is not doing the work.

Why not just…?

Why not just hold out a test set? For most purposes a holdout is the honest default, and we treat it as the bar to beat. The gap appears when facts are scarce, which is typical for incomplete knowledge bases. Every held-out fact is a fact the reasoner cannot use to derive others. The experiments sweep $n$ and report where, if anywhere, the compression certificate crosses below the holdout bound. If it never does, that is a negative result worth publishing.

Why not just use an Occam bound on the hypothesis description? This is a real threat. Our hypothesis is literally $k$ atoms, so encoding it costs about $k\log|\text{atom space}|$ bits, versus roughly $k\ln n$ for the compression bound. The two will be close when the atom space is small. The compression bound should win when the atom space is much larger than the sample. That is the knowledge-base regime, with many constants and high arity. We will plot both bounds against atom-space size to settle this, and report honestly if Occam matches us.

Why not just run Pick-to-Learn with a neural model? Pick-to-Learn retrains after each added point, and the file notes this overhead as a known limitation. Its decompressor is also a trained network, which cannot exploit the fact that one observed atom entails many others. The direct comparison above measures both compression size and compute.

Why not just run the chase with a depth cutoff, or use goal-driven query answering? A depth cutoff makes the reconstructor total, but it changes the hypothesis class and can lose entailments. The ablation measures exactly this loss. Goal-driven answering (Benedikt, Motik, and Tsamoura) is a reasonable alternative for evaluating single atoms. It is less suited to the covering step, which needs full closures of many candidate sets. We will report both runtimes.

Proposed Experiments

The first experiment uses synthetic data where the realizability assumption holds by construction. We take guarded rule sets of the kind used in the rewriting benchmarks of Rewriting the Infinite Chase, with arity controlled from 2 to 5 and above. We draw random base databases and close them to form targets. We then report compression size, certified error, true error on fresh atoms, and decompression time as functions of $n$ and arity.

The second experiment applies the agnostic variant to ontology-annotated knowledge bases with injected label noise, against all baselines above. The third is the exhaustive conjecture testbed for small disjunctive rule sets, recording the ratio of optimal compression size to VC dimension.

The decisive checks are two. First, does the certificate with the ontology beat the empty-ontology and holdout references at realistic $n$? Second, does exact rewriting beat the depth-bounded ablation? If the answer to both is no, the closure observation is mathematically correct but practically empty, and we will say so.