Semantic Acyclicity with Numbers: Simplifying Queries over Ontologies with Inverse Roles and Concrete Comparisons

Database engines answer a query fastest when its join structure is a tree. Such queries are called acyclic, and Yannakakis's algorithm evaluates them in time linear in the data. Cyclic queries can cost exponentially more. A query that looks cyclic can still be equivalent to an acyclic one once you account for the rules every valid database must obey. Examples are "every advisor works in the department of the student they advise" or "a student's enrolment year is never before their advisor's hire year." Deciding whether such an acyclic equivalent exists is the semantic acyclicity problem. The theory for it is well developed, but only for purely symbolic rules. Real schemas are full of numbers: dates, ages, readings, prices. The comparisons in a query, such as s.enrolYear >= p.hireYear, are often exactly the atoms that close a cycle. No existing result says when a constraint solver for numbers, run together with symbolic rules, can remove such a comparison or reroute it so that the query becomes a tree.

We propose to study semantic acyclicity for conjunctive queries that contain comparison atoms, under guarded rules. Guarded rules are database dependencies whose premises are anchored in a single relational atom; they capture the Horn description logics used in ontology-based data access, including inverse roles, which let a rule follow an edge backwards so that a child can constrain its parent. Our central claim is that semantic acyclicity stays decidable when comparisons are themselves guarded and the numeric domain is convex, meaning that any entailed disjunction of comparisons already has one disjunct entailed. We further claim that the decision procedure is a symbolic chase interleaved with calls to a linear-arithmetic solver. Without the guardedness condition, inverse roles let numeric values be equated along two different paths, and the problem becomes undecidable. We will build the procedure, prove where the boundary lies, and measure how often real and benchmark queries become acyclic only once arithmetic is taken into account.

What Exists and What Is Missing

The symbolic theory supplies our method. Semantic Acyclicity Under Constraints decides whether a cyclic query is equivalent to an acyclic one under integrity constraints. It shows the problem is 2EXPTIME-complete for guarded tuple-generating dependencies (NP-complete for fixed schemas), because the chase (repeatedly firing rules to complete a database) preserves tree-like structure. It shows the problem is undecidable for full tgds. That work is purely relational, and we reuse its chase-based argument. When is Ontology-Mediated Querying Efficient? shows that, for the Horn logic with inverse roles $\mathcal{ELHI}_\bot$, efficient evaluation coincides with equivalence to a bounded-treewidth union of queries. That result tells us the right target notion, but it ignores datatypes entirely.

The concrete-domain side supplies the solver interface and the admissibility conditions. A Scheme for Integrating Concrete Domains into Concept Languages defines how abstract reasoning hands numeric predicates to an external solver through functional "concrete features." Query Rewriting for DL-Lite with n-ary Concrete Domains gives polynomial-data-complexity rewriting for multi-attribute numeric predicates under "cr-admissibility," whose key ingredient is convexity. Its restrictions shape our design. It has no inverse roles. Queries may use only predicates already present in the ontology. It reports no implementation. We drop the first restriction and keep convexity.

Two negative results constrain the design. NExpTime-complete Description Logics with Concrete Domains proves that inverse roles combined with feature agreements, which force two different paths to reach the same numeric value, are undecidable even for plain satisfiability. Keys, Nominals, and Concrete Domains proves that general key constraints over concrete features are undecidable, and it leaves the combination of keys with inverse roles explicitly open. These two results tell us that any comparison able to link values of individuals not joined by a single atom must be excluded. Our guardedness condition for comparisons is designed directly from them.

The closest existing work that combines constraints, inverse roles and optimization is First Order Rewritability in Ontology-Mediated Querying in Horn Description Logics. It shows that keys and foreign keys can make Horn-$\mathcal{SHIQ}$ queries rewritable into SQL. It handles no datatypes, and it targets rewritability into SQL rather than acyclicity. No paper in the file asks the acyclicity question in the presence of numeric comparisons and inverse roles. Our work differs from each of these in the same way: we treat comparisons as first-class atoms whose removal or relocation is decided jointly by the chase and a solver.

Core Claim

Let $\Sigma$ be a set of guarded tgds in which every comparison atom has all its variables inside the guard atom. Let $\mathcal{D}$ be a convex numeric domain such as the rationals with $<, \le, =$ and constants. Let $Q$ be a conjunctive query with comparison atoms over $\mathcal{D}$. We ask whether there is an acyclic query $Q'$ with

$$Q \equiv_{\Sigma,\mathcal{D}} Q' ,$$

meaning that $Q$ and $Q'$ return the same answers on every database that satisfies $\Sigma$ and interprets comparisons according to $\mathcal{D}$. A comparison counts toward acyclicity only if its variables are not already covered by one relational atom.

We conjecture three things. First, this problem is decidable, with the same 2EXPTIME and fixed-schema NP bounds as the symbolic case. The reason is convexity: entailed comparisons over a finite set of variables can be computed by a polynomial solver call and never force case splits that would branch the chase. Second, inverse roles are what make the numeric case non-trivial. A guarded rule like "if $s$ is advised by $p$ then $s.\mathrm{enrol} \ge p.\mathrm{hire}$" propagates a numeric fact across an edge in whichever direction the query happens to traverse it. Third, allowing a single unguarded comparison between two non-adjacent individuals, together with inverse roles, makes the problem undecidable. We expect to show this by adapting the feature-agreement reduction of NExpTime-complete Description Logics with Concrete Domains.

Research Program

The theoretical part has three pieces.

The first is the upper bound. We extend the chase so that each fired rule adds both relational atoms and guarded comparisons. Each bag of the tree-shaped chase then carries a small linear-arithmetic constraint store. The solver closes that store under entailment before the acyclicity test of Semantic Acyclicity Under Constraints is applied. The proof obligation is that guarded comparisons never link values in non-adjacent bags, so the store stays local and the original small-witness argument survives.

The second is the lower bound and the undecidability boundary. This includes the case of key constraints over concrete features, which answers part of the question left open in Keys, Nominals, and Concrete Domains.

The third is a non-convex counterpart. If the domain allows $\neq$, entailed disjunctions appear, and we expect a jump in complexity. Characterizing that jump is useful even if it turns out negative.

The engineering part is a prototype, which we will call AcyNum. It parses SQL or SPARQL conjunctive queries with comparisons and reads guarded ontology axioms or database dependencies with numeric side conditions. It runs the solver-augmented chase with Z3 restricted to linear rational arithmetic. When an acyclic equivalent exists, AcyNum emits it together with a proof trace. We then evaluate that equivalent with a Yannakakis-style plan inside PostgreSQL.

Baselines

The naive reference point is to do nothing. Each cyclic query goes unchanged to PostgreSQL, whose planner already handles inequality joins with hash and merge strategies. Any claimed speedup must be measured against this on the same machine, the same indexes and the same data. A rewrite counts as worthwhile only if it lowers median and tail latency by a margin larger than run-to-run variance. We will report each query separately rather than as an average, because a few large wins can hide many regressions.

The strongest existing method for deciding acyclicity is the symbolic semantic-acyclicity procedure of Semantic Acyclicity Under Constraints, applied with comparison atoms treated as uninterpreted relations. It is the only published procedure that decides the question at all. It is exact on the symbolic part, so it isolates precisely what arithmetic adds. We will run it inside our own chase implementation with the solver switched off, which gives identical code paths, timeouts and hardware. AcyNum beats it if it certifies strictly more queries acyclic on the same workload without exceeding its decision time by more than a constant factor. The file reports no numerical results for that paper, so we have no reported result found on Lacuna for semantic-acyclicity decision rates on any benchmark.

The strongest practical competitor is a guess-and-verify pipeline. It enumerates acyclic candidates by deleting or relocating comparison atoms, then checks each candidate with VeriEQL: Bounded Equivalence Verification for Complex SQL Queries with Integrity Constraints, using the same constraint set encoded as SQL CHECK and foreign-key constraints and the same wall-clock budget. On the Apache Calcite rule suite, VeriEQL reports that it "proves or disproves equivalence for over 70% of benchmarks within a 10-minute timeout." On LeetCode it generates counterexamples for 14.9% of query pairs. On Calcite, the algebraic prover UDP from Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries reports 33 of 39 supported cases. We will also run UDP as a sound but arithmetic-blind check.

Two ablations isolate the ingredients. The first disables backward propagation along inverse edges, firing rules only parent-to-child. This measures how much of the gain depends on inverse roles specifically. The second drops convexity by enabling $\neq$. This tests whether the complexity cost we predict shows up in practice.

Why not just…?

Why not just treat comparisons as ordinary relations and use the existing acyclicity test? That approach misses every entailment that relies on arithmetic. A rule implying $x \ge y$ cannot make a query atom $x \ge y - 1$ redundant if both are opaque symbols. Towards a Scalable Query Rewriting Algorithm in Presence of Value Constraints shows the same failure in view pruning, where interpreting value ranges is what lets views be discarded. Our solver-off ablation measures exactly this gap. If the gap is near zero on real workloads, the honest conclusion is that arithmetic rarely matters for acyclicity, and we will report that.

Why not just guess acyclic candidates and check them with VeriEQL? This is the real threat for practitioners, and it may well find many of the same rewrites. It has two weaknesses. Its guarantee is bounded: input bounds "up to 5, and even up to 100 for some cases." Counterexamples on chase-generated structures that follow long inverse-role cycles can exceed that size, and the VeriEQL authors themselves note that counterexamples needing more than 1000 tuples exceed practical SMT bounds. It also offers no completeness, so when it fails we learn nothing. The experiment settles the question by counting rewrites in three groups: those both systems find, those only AcyNum certifies, and those VeriEQL accepts but AcyNum refutes with an unbounded proof. The last group would be outright errors in a bounded optimizer.

Why not just let PostgreSQL's planner handle inequality joins? For small and medium data it may be good enough, and our do-nothing baseline measures that directly. The reason to expect gains is asymptotic: for cyclic queries the gap between linear-time and worst-case join evaluation grows with data size. We therefore sweep scale factors instead of reporting one size.

Why not just materialize everything with forward chaining first? Existential rules combined with inverse roles generate infinite chains of new individuals, so materialization does not terminate. First Order Rewritability in Ontology-Mediated Querying in Horn Description Logics needed Skolemization and interpolation precisely to avoid this.

Proposed Experiments

We use three workloads.

The first is the Lehigh University Benchmark (LUBM), already used at LUBM(5) with about 100,000 individuals in Integrity Constraints in OWL. We extend it with numeric features such as hire year, enrolment year and course year. We add guarded numeric rules that use inverse roles, such as advisor and teaching edges read backwards. Then we write cyclic queries in which a comparison closes the cycle. Because we control the rules, this workload gives exact ground truth on which queries are semantically acyclic.

The second is the Norwegian Petroleum Directorate FactPages from Optique 1.0: Semantic Access to Big Data: The Case of Norwegian Petroleum Directorate's FactPages. It is a real ontology-based access setting with abundant dates and depths. We found no reported result on Lacuna for NPD query performance, so our measurements there will be first numbers rather than comparisons.

The third is the Calcite rule suite of 397 query pairs used by VeriEQL. Its subset with numeric predicates gives an external check that AcyNum agrees with VeriEQL and UDP wherever their supported fragments overlap.

The metrics are the fraction of cyclic queries certified acyclic, the decision time, the evaluation speedup of the emitted rewrite against the original query, and the agreement counts described above.

The decisive checks are four. AcyNum must certify a non-trivial share of queries that the solver-off baseline cannot. The inverse-propagation ablation must lose a measurable part of that share, which would show that inverse roles drive the phenomenon. Every rewrite AcyNum emits must also pass VeriEQL at its bounds and return identical answers under randomized differential testing at full scale. Finally, on the synthetic queries just beyond our guardedness boundary, which are the unguarded-comparison cases, the procedure must provably refuse to answer rather than silently loop. That refusal is the practical sign of the undecidability result we aim to prove.