Many organizations want to ask questions over sensitive data through an ontology, a set of logical rules such as "every cardiologist is a physician." The rules let a query for physicians also return records filed only as cardiologists. They also want to run those queries on untrusted cloud hardware inside a trusted execution environment (TEE), an encrypted region of the processor that the host operating system cannot read. TEEs still leak which memory locations and which code branches the computation touches. The standard way to answer ontology queries is first-order rewriting: compile the query and the rules into one large SQL query, a union of many small join queries, then run it on an ordinary database. Run inside an enclave, that union is a poor fit. Its size can grow exponentially with the ontology, so making each part oblivious multiplies the overhead. Each part also leaks how many records it matched unless it is padded, and per-part counts reveal which rules fired on the secret data.
We propose a different execution strategy taken from constraint satisfaction theory. Ontology query answering can be recast as asking whether the data maps homomorphically into a fixed "template" structure derived from the ontology. In that view, rewritability into first-order logic coincides with a property called bounded tree duality: non-answers are always witnessed by tree-shaped patterns of bounded height. Bounded tree duality means a fixed number $h$ of rounds of arc consistency decides the query. Arc consistency is a local pruning procedure in which every data element keeps a set of still-possible template elements and repeatedly removes those its neighbors rule out. Each round is a single pass over the relation tables whose memory access pattern depends only on table sizes. The query can therefore run with an access trace that does not depend on the data, at a cost linear in $h$ instead of in the number of union parts. The same classification also predicts where oblivious execution becomes expensive.
Core Claim
For ontology-mediated queries (OMQs) with atomic answer predicates over the description logics $\mathcal{ALC}$ and $\mathcal{ALCI}$, the CSP classification of an OMQ fixes how much it costs to answer obliviously, meaning with a memory trace that is independent of the data. The three cases, and how each is evaluated, are as follows.
If the OMQ is first-order rewritable, it can be evaluated obliviously in $h$ fixed rounds of arc consistency, where $h$ is the height bound of its tree obstructions. No step of this procedure depends on which rewriting disjunct holds.
If the OMQ is rewritable into monadic Datalog but not into first-order logic, arc consistency still decides it, but the number of rounds is data-dependent. Two options remain. The engine can pad the rounds to the number of individuals, or it can reveal the convergence round, which leaks the length of the longest derivation chain.
If the OMQ is coNP-hard, no polynomial oblivious procedure of this kind exists, under the usual assumption that P differs from NP.
The claim is new on the systems side. On the theory side, it adds an oblivious-cost reading of the existing dichotomies and gives the height bound $h$ an operational meaning: it is the number of oblivious passes.
The cost contrast we expect is
$$ C_{\text{UCQ}} \approx \sum_{q \in Q} C_{\text{obl}}(q), \qquad C_{\text{AC}} \approx h \cdot \sum_{R} C_{\text{obl}}(|R|\cdot|T|). $$
Here $Q$ is the set of disjuncts in the rewriting, and $C_{\text{obl}}(q)$ is the cost of an oblivious join plan for disjunct $q$ in an engine such as ObliDB. On the right, $R$ ranges over the role relations of the data and $|T|$ is the size of the template. The template is fixed by the ontology but can be exponential in it. The bet is that $h\,|T|$ is far smaller than $|Q|$ on realistic ontologies, because tree-shaped rewritings share subtrees that the union evaluates repeatedly.
Grounding in Prior Work
The method comes from the CSP line of work on OMQs. Non-Uniform Data Complexity of Query Answering in Description Logics reduces individual $\mathcal{ALC}$/$\mathcal{ALCI}$ ontologies to homomorphism problems into finite templates, and we reuse those templates directly. Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP ties these OMQs to monadic disjunctive Datalog and CSPs and shows that deciding first-order rewritability is NEXPTIME-complete. Query Rewriting Beyond DL-Lite proves that rewritable OMQs have unions of tree-shaped disjuncts and connects rewritability to tree duality. Both papers treat these as language-level results. We use the same characterization to build an execution plan rather than an SQL string.
The same theory also limits the design. Functional roles make rewritability undecidable (Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP), and closed predicates lead to surjective CSPs whose classification is open (Ontology-Mediated Queries with Closed Predicates). We therefore exclude both and say so.
The motivation for the work comes from the systems side. ObliDB and Doquet show that relational operators run in enclaves leak access patterns and that oblivious operators can be practical. Both accept plain SQL over a fixed schema and know nothing of ontologies. Branch Shadowing shows that data-dependent branches leak at the granularity of a single if/else. Our propagation loop has to be branch-free as well as access-oblivious.
On the rewriting side, Data Complexity of Query Answering in Description Logics describes reformulation into unions of conjunctive queries (UCQs) and the blow-up in their size. Benchmarking Ontology-Based Query Rewriting Systems found that every tested rewriter was unsound or incomplete on some input. That finding argues for an evaluation path that never materializes the rewriting at all.
One claim in our own research file needs correcting: that subsumption pruning of UCQs "amplifies" side-channel leakage. Pruning happens before any data is seen, so on its own it leaks nothing. The real leaks come from per-disjunct intermediate sizes and from early termination when a disjunct succeeds. Our analysis targets those.
Research Program
The first component is a compiler from a Horn or general $\mathcal{ALCI}$ ontology plus an atomic query to the CSP template, following the Lutz–Wolter construction. It also computes the obstruction height $h$, either by an explicit decision procedure on small ontologies or by iterating arc consistency on canonical tree-shaped data until a fixpoint certificate appears. Because rewritability is NEXPTIME-complete to decide, the compiler gets a time budget. When it cannot certify a bound, it falls back to padded rounds and reports this to the user.
The second component is an enclave engine. Each individual stores a bitvector over template elements. Each round performs one oblivious join between every role table and the bitvector table, followed by an oblivious bitwise update. The join is built from the operators in ObliDB: oblivious sort plus linear scan. The update uses only conditional moves, with no data-dependent branches. Answers are read off in one final linear scan, padded to the number of individuals.
The third component is a leakage analysis. We prove trace equivalence for pairs of datasets with equal table sizes. We also measure, for the padded monadic-Datalog case, how much information the convergence round reveals when it is not padded.
Baselines
The naive reference point is a full linear scan of every table with the ontology materialized in the clear before upload. This fixes the security floor and also measures what offline saturation costs.
The strongest existing competitor is rewrite-then-oblivious-SQL. It generates the UCQ with a standard rewriter, chosen from the tools evaluated in Benchmarking Ontology-Based Query Rewriting Systems after a correctness check against the Sygenia checker, and executes it in ObliDB's oblivious operators with per-disjunct outputs padded. It is the strongest because it is exactly what a practitioner would assemble today from published components. Both systems get the same enclave, the same data, and the same memory limit, and the UCQ baseline gets the rewriter's best pruning settings.
No paper in the file reports oblivious OMQ answering, so no reported result was found on Lacuna for this baseline. The closest reported figures are that ObliDB is "1.1–19x faster than Opaque on the Big Data Benchmark" and runs "within 2.6x of Spark SQL" (ObliDB).
We beat this baseline if we achieve lower end-to-end latency at equal trace-independence on ontologies whose UCQ has more disjuncts than $h|T|$. We also need to report the crossover honestly where it does not.
The third baseline is the differentially oblivious variant: the same UCQ run through Doquet-style operators. It trades exact obliviousness for speed, and that paper reports "up to an order of magnitude speedup" over fully oblivious schemes.
Two ablations isolate the key ingredient. The first runs arc consistency with rounds padded to the number of individuals instead of $h$, which isolates the value of the CSP-derived bound. The second runs arc consistency non-obliviously, which isolates the cost of obliviousness itself.
Why not just…?
Why not just feed the rewritten SQL to ObliDB? This is the main threat, and for DL-Lite ontologies with small UCQs it may well win, since $|Q|$ is then small and no template is needed. The case against it rests on UCQ blow-up, documented in Data Complexity of Query Answering in Description Logics. Two more problems follow. Padding each disjunct separately compounds the overhead, and leaving them unpadded leaks per-rule counts. The crossover experiment below plots latency against $|Q|$ and $h|T|$ and decides the question directly.
Why not just materialize all inferences offline and upload saturated data? For static data with a single fixed ontology owned by the data owner, this is a strong option. We include it as the naive baseline and expect it to win on query latency. It fails when different analysts bring different ontologies to the same encrypted data, or when data is appended, because saturation then reruns a data-dependent fixpoint. Doquet already notes its own restriction to static data. Our experiments report the storage blow-up from materialization and its re-saturation cost per update.
Why not just compile an ordinary reasoner with branch obfuscation such as Zigzagger? Zigzagger costs 1.34x overhead and hides only branches (Branch Shadowing). The memory accesses of a chase-style reasoner still depend on the data. Our trace-comparison test applies directly to such a build, and we expect it to fail that test.
Proposed Experiments
We use the Sygenia ontologies (AX, S, U, V and others), where rewriters produce large UCQs, and the DBpedia OMQA benchmark (A DBpedia-based Benchmark for Ontology-mediated Query Answering). The DBpedia benchmark lets us vary rewriting depth from 1 to 10, rule count, and data size from 5M to 20M triples. Its reported conventional baseline is that Graal takes 80.3 s at 10M triples and times out at 20M.
Correctness. Answers must match a reference reasoner on every query.
Leakage. We record cache-line memory traces with an instrumented SGX simulator and LBR branch traces. For each query we generate pairs of datasets with equal table sizes but different answers, then report trace equality and an estimate of the mutual information between the trace and the answer set.
Cost. We measure latency against data size, and rewriting depth against $h$.
Decisive checks. The proposal succeeds if three things hold together. Oblivious arc consistency must yield identical traces across the dataset pairs while the unpadded UCQ baseline does not. Its latency must scale with $h$ rather than $|Q|$ across the depth sweep. And on the monadic-Datalog-only queries, the convergence round must measurably leak derivation depth unless it is padded. The proposal fails if the template size $|T|$ is so large on realistic ontologies that the UCQ baseline wins everywhere. That outcome is still informative, because it would bound where CSP-based oblivious evaluation can help.
References
- Non-Uniform Data Complexity of Query Answering in Description Logics
- Ontology-based data access: a study through disjunctive datalog, CSP, and MMSNP
- Query Rewriting Beyond DL-Lite
- Ontology-Mediated Queries with Closed Predicates
- ObliDB: Oblivious Query Processing using Hardware Enclaves
- Doquet: Differentially Oblivious Range and Join Queries with Private Data Structures
- Inferring Fine-grained Control Flow Inside SGX Enclaves with Branch Shadowing
- Data Complexity of Query Answering in Description Logics (Extended Abstract)
- Benchmarking Ontology-Based Query Rewriting Systems
- A DBpedia-based Benchmark for Ontology-mediated Query Answering