Encrypted databases can now compute sums and counts directly on encrypted rows. Every such system assumes the stored rows are the whole truth, so a missing row means a missing fact. Many outsourced datasets are not like that. Medical registries, federated logs and partially loaded warehouses come with background rules such as "every clinic employs at least one doctor" or "every order has a customer." Under these rules a missing row means an unrecorded fact, not an absent one. The correct answer to "how many doctors are there?" is then the certain lower bound: the smallest count that holds in every world consistent with the data and the rules. Counting only the stored rows gives a number that can be wrong in the unsafe direction.
This note proposes compiling certain lower-bound counting queries into fixed plans of filters, sums and threshold tests, before any data is touched, so that existing encrypted aggregation engines can run them unchanged. The bet rests on a known result: for important query classes this problem sits in $\mathrm{TC}^0$, the complexity class of constant-depth circuits that may count. That result suggests the answer is a fixed counting expression over the stored data rather than a search. The compilation depends only on the rules and the query, never on the data. So it adds no information leakage beyond what the encrypted engine already reveals for the compiled plan, and the same rule-level reasoning can also delete tables and joins before expensive encrypted operations run.
Core Claim
For positive DL-Lite ontologies, the certain lower bound of a parameterized query is a data-independent arithmetic expression. DL-Lite is the lightweight rule language behind ontology-based access to relational data; it expresses inclusions such as foreign keys and "every X has some Y." The queries in scope are atomic concept counts with attribute filters and rooted counting conjunctive queries, meaning joins in which every variable is linked to a known constant or an answer variable. The expression has the form
$$\mathrm{lb}_{\mathcal T}(q,\mathcal A) \;=\; \sum_{j=1}^{m} c_j \cdot \min\!\Big(\tau_j,\ \textstyle\sum_{r\in \mathcal A} \phi_j(r)\Big),$$
where $\mathcal T$ is the rule set, $\mathcal A$ the stored rows, $\phi_j$ are 0/1 row predicates that the compiler derives from $\mathcal T$ and the query $q$, $\tau_j$ are constant caps, and $c_j$ are integer coefficients. The point is that $m$ and the $\tau_j$ do not grow with the data. An expression of this shape uses exactly the operations that encrypted engines already support: predicate vectors multiplied into sums, as in HEDA, plus a constant number of encrypted comparisons, as in Engorgio.
A simple case shows where the min terms come from. Under "every clinic has staff who are doctors," with no rule saying a doctor works at only one clinic, the certain doctor count is the number of named doctors. If that number is zero and at least one clinic exists, the count is one, because a single unnamed doctor can staff every clinic. The cap is what prevents overcounting.
Two parts of this claim are new. The first is the compiler itself. Cardinality Queries over DL-Lite Ontologies proves $\mathrm{TC}^0$ data complexity using merging strategies, which collapse unnamed individuals into named ones or into each other to find the smallest valid world. It explicitly leaves a practical SQL rewriting open. Answering Counting Queries over DL-Lite Ontologies extends tractability to rooted exhaustive queries, also without executable rewritings. The second is execution over ciphertexts. HEDA and Engorgio compute exact closed-world aggregates and have no notion of unnamed individuals that the rules force to exist.
Research Program
The first strand is theory and compilation. We will turn the merging arguments of the two DL-Lite counting papers into constructive rewritings that produce the predicates $\phi_j$ and caps $\tau_j$. The work starts with concept counting in DL-Lite$_{\text{core}}$ and DL-Lite$^H_{pos}$, then adds filters on stored attribute values, then handles rooted exhaustive counting conjunctive queries. Some cases are provably out of reach. Negative constraints make the problem coNP-complete, and some role-counting queries are co-PM-complete, where co-PM is the complement of the perfect-matching problem. A fixed circuit of this form should not exist in those cases unless complexity classes collapse, so they serve as a principled boundary. The compiler will reject such queries rather than approximate them. For queries outside the rooted class we will report how often realistic workloads fall outside it, because that frequency limits the practical reach of the claim.
The second strand is data-independent pruning. The compiler applies schema-level rules before compiling: foreign keys treated as existential rules, value ranges in the style of value-constraint rewriting, and constraint-driven join removal following Semantic Acyclicity Under Constraints. These rules drop predicates $\phi_j$ that are identically zero and joins that are redundant. Dropping joins matters for privacy as well as cost. Equi-Joins Over Encrypted Data shows that encrypted hash joins leak which records share join values, and that leakage accumulates across a series of queries. A join that is removed at compile time leaks nothing.
To check that pruning is safe, we will use the U-semiring decision procedure of Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries, which proves two SQL queries equivalent under keys and foreign keys. Its scope limits how we use it. The procedure works under closed-world semantics, so it cannot check the open-world step. We apply it only to the closed-world step, proving that the pruned compiled plan equals the unpruned compiled plan. It is complete only for unions of conjunctive queries and does not handle the min operator, so we will verify the inner sums with it and argue the min-cap layer by hand.
The third strand is encrypted execution and leakage. The compiled plan runs on a reimplementation of HEDA-style filter-times-sum aggregation, with comparisons for the min terms following Engorgio's quantized comparison design. We will prove a simulation statement: the server's view equals the leakage of the underlying engine on a plan determined by $(\mathcal T, q)$ alone. The output is a single encrypted number, so we deliberately avoid volume padding with differential-privacy noise as in εpsolute. Random noise would break the guarantee that the answer is certain. The tension with noise-based volume hiding is real, and we leave it to future work rather than paper over it.
Baselines
The ground truth is a plaintext solver for certain lower bounds. It searches over merges of unnamed individuals, written as an integer program, and is exact but slow. Every encrypted method must reproduce its answer exactly on every query instance. This is the correctness reference, not a competitor.
The naive reference point is epistemic counting on the same encrypted engine: counting only stored rows that match the query, the standard behavior of HEDA and Engorgio. Kostylev and Reutter and the DL-Lite counting papers show that this undercounts whenever existential rules force unrecorded individuals. We will measure how often and by how much. Our method beats it if it matches the ground truth on all queries at a latency overhead we will report against it directly.
The strongest existing system for efficiency is the encrypted aggregation engine itself. For the reported figures, HEDA takes about 430 seconds for an aggregation over 8,000 encrypted rows on modified TPC-H queries, with its bootstrapping step (re-encrypting ciphertexts into a different plaintext space) taking about 92% of runtime. Engorgio reports amortized runtimes under 3 seconds for relational queries on a 10K-row hybrid database on a 48-core processor. All methods run on the same reimplemented engine, the same hardware, the same encryption parameters and the same row counts. Success means certain-lower-bound answers within a small constant factor of epistemic-count latency on that engine; we target under 2x. With pruning enabled, it also means fewer bootstraps and comparisons than the unpruned epistemic plan on join-heavy queries.
Two further baselines change the data rather than the query. The canonical-model baseline adds every unnamed individual the rules require as an explicit row before encryption, then counts. The single-merged-model baseline adds one globally minimized world instead. The first overcounts by construction, per the cardinality-query paper. The second is the serious competitor discussed below.
One ablation isolates the pruning ingredient: our compiled plan with constraint pruning turned off. It separates the cost of open-world correctness from the savings that pruning provides.
Why not just…?
Why not just count the encrypted rows that are there? That computes the closed-world answer. Under existential rules the closed-world answer can be zero when the certain answer is positive, as the cardinality-query paper shows for the clinic example. The epistemic baseline experiment reports the error rate on our benchmarks. If that rate is negligible on realistic data, the motivation weakens, and we will say so.
Why not just precompute the lower bounds in plaintext before encrypting? This is a real threat for parameter-free atomic counts. A rule set has few concepts, so the data owner could store every answer encrypted. It fails for parameterized queries: filters on attribute values, rooted queries bound to a particular constant such as "doctors at clinic $c$," and data that changes after upload. The number of possible answers grows with the parameter domain, and every update invalidates the stored answers. We will measure the size of the precomputed table and its update cost against our per-query latency. Our evaluation emphasizes parameterized workloads precisely because the unparameterized case may favor precomputation.
Why not just add one minimal world to the data and then use any encrypted engine? If a single merged world gave the certain lower bound for every query, materialization would win outright. The certain bound, however, is a minimum taken separately for each query. Merging an unnamed individual into one constant can lower one count while raising another. We expect no single world to be minimal for all queries, but this is an empirical question on our benchmarks. The single-merged-model baseline settles it by measuring the fraction of queries it answers incorrectly. If that fraction is near zero for the positive fragments, we will narrow the contribution to the cases where it is not.
Why not just download and decrypt everything, then reason on the client? The equi-join paper reports decryption costs of 21 to 53 ms per row. εpsolute keeps its client footprint under 30 MB for a million records and reports that it outperforms secure linear scans by 18x. Both suggest full download is costly at scale. We include client-side reasoning as a baseline at 10K to 1M rows and report the crossover size, conceding that it wins below that size.
Proposed Experiments
The first workload is TPC-H. We treat its foreign keys as existential rules, for example "every order has a customer," and delete 5–40% of referenced rows to create incompleteness. Queries are parameterized versions of Q1, Q6 and Q19, matching HEDA's modifications, plus rooted counting joins on orders and customers. The second workload is the Lehigh University Benchmark (LUBM), a synthetic university ontology and dataset generator. We restrict its ontology to the DL-Lite fragment and delete assertions at ratios like those used in the inconsistency-tolerant explanation study. Metrics are exact-match rate against the plaintext solver, end-to-end latency, counts of bootstraps and encrypted comparisons, number of joins remaining after pruning, and the server's leakage profile.
Three outcomes decide the claim. First, on both workloads the number of terms $m$ in the compiled expression must stay constant as data grows from 1K to 100K rows. Growth with data would falsify the core claim. Second, the single-merged-model baseline must give wrong answers on a measurable fraction of queries. If it does not, the compiler matters only for parameterized and changing data. Third, the server transcripts of our method must be indistinguishable across datasets of equal size that have different certain answers. We test this empirically alongside the simulation proof.
References
- HEDA: Multi-Attribute Unbounded Aggregation over Homomorphically Encrypted Database
- Engorgio: An Arbitrary-Precision Unbounded-Size Hybrid Encrypted Database via Quantized Fully Homomorphic Encryption
- Cardinality Queries over DL-Lite Ontologies
- Answering Counting Queries over DL-Lite Ontologies
- Towards a Scalable Query Rewriting Algorithm in Presence of Value Constraints
- Semantic Acyclicity Under Constraints
- Equi-Joins over Encrypted Data for Series of Queries
- Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries
- εpsolute: Efficiently Querying Databases While Providing Differential Privacy
- Complexity of Answering Counting Aggregate Queries over DL-Lite
- Explaining Inconsistency-Tolerant Query Answering over Description Logic Knowledge Bases