Some database queries come with background knowledge, an ontology, that adds facts the data does not state explicitly. For the description logic EL, a common rule language for such ontologies, the cost of answering every fixed query is already fully classified. Each query is either as cheap as plain SQL, or it needs directed reachability (the NL-complete case, "can I get from here to there along arrows"), or it needs full polynomial-time recursion A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic EL. A separate line of complexity theory shows that directed reachability becomes much more structured when every shortest path is unique. The property is called min-uniqueness, and in graphs that have it, reachability can be decided by an unambiguous log-space machine: a nondeterministic machine that never has more than one accepting run On the power of unambiguity in log-space. This proposal joins the two results. We ask which ontology queries keep min-uniqueness when they reason over data that has it, and which ones produce many equal-length derivations on their own even when the data does not.
The point of the question is that it yields an unconditional new split inside the NL-complete bucket. The split is not a split over all databases, which, as explained below, would be impossible to prove without settling NL versus UL. It is a split over data classes that the uniqueness literature has shown to be easier: min-unique graphs, graphs with polynomially few paths, and 2-page book embeddings. The target theorem has this form. For every EL query in the NL bucket and each such data class $\mathcal{D}$, evaluation over $\mathcal{D}$ is either in unambiguous log-space (UL) or NL-hard over $\mathcal{D}$, and a tree-automata procedure decides which.
Why the obvious idea fails, and what replaces it
The obvious move is to "refine the EL trichotomy with a UL bucket." This cannot work as stated. Lutz and Sabellek prove that every non-first-order query in the linear-Datalog bucket of (EL, CQ) is NL-hard over arbitrary data A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic EL. Placing any of these queries in UL would therefore prove NL = UL. That is exactly the open problem which On the Power of Unambiguity in Logspace ties to deciding min-uniqueness in UL. The L-versus-NL refinement that Lutz and Sabellek conjecture, tied to symmetric Datalog Classifying the Complexity of Ontology-Mediated Queries in EL: From Atomic Queries to Conjunctive Queries (Extended Abstract), runs into the same wall for plain EL. Its natural home is inverse roles, and the file reports that classifying those is currently blocked by open CSP problems.
The refinement becomes provable when the restriction moves to the data. Their hardness proofs build ABox gadgets (an ABox is the set of data facts) that encode arbitrary directed graphs, and those gadgets have unrestricted path multiplicity. If the data class $\mathcal{D}$ is restricted, some queries lose their hardness and others keep it. Pavan, Tewari and Vinodchandran supply the upper-bound engine: reachability is in UL on min-unique graphs, and ReachFewL is contained in UL ∩ co-UL. They study bare graphs only and never ask how a logical rule set transforms a graph's path structure. The closest existing work therefore classifies queries over all data, or classifies graphs with no queries attached. We classify queries relative to data classes.
Core Claim
Evaluating a linear Datalog rewriting of an NL-bucket query is reachability in a configuration graph. This graph is the product of the data graph with a bounded set of query states: which concept names or which part of the query the derivation is currently tracking. Min-uniqueness is not preserved by products. A data graph with a unique shortest $a$-to-$b$ path becomes ambiguous when two state "lanes" can follow that path in parallel and rejoin. Our claim is that this lane ambiguity is the only obstruction, and that it can be decided.
Concretely, we conjecture the following. Call a query lane-collapsing if its configuration graph admits a quotient onto the data graph that preserves shortest-path lengths and merges equal-length parallel lanes reaching the same configuration. Lane-collapsing queries are in UL over min-unique data and in UL ∩ co-UL over few-path data. Every other NL-bucket query is NL-hard already over min-unique ABoxes. The hardness side would work by building data that is itself min-unique but lets the query's lanes simulate the edge choices of an arbitrary graph. Membership of a query in the lane-collapsing class should be decidable in ExpTime by adapting the two-way alternating parity tree automata that decide the original trichotomy.
Research Program
The first strand fixes definitions and settles small cases. We treat evaluation over $\mathcal{D}$ as a promise problem, because checking min-uniqueness of the input is not itself known to be in UL. We then classify atomic queries over EL ontologies with one and two role names by hand. Two sides must both turn out nonempty for the program to make sense. Single-role propagation, such as $\exists r.B \sqsubseteq B$, has a configuration graph that is a copy of the data graph, so it inherits min-uniqueness. Ontologies with two concepts that both propagate along $r$ and feed back into each other produce equal-length parallel lanes, and we will try to turn these into an NL-hardness reduction using min-unique data.
The second strand proves the upper bound. We transfer the inductive counting technique of Pavan et al. to configuration graphs of lane-collapsing rewritings. The canonical shortest path in the data graph, combined with the collapsing quotient, should fix a canonical derivation. Lutz and Sabellek show that the arity of the rewriting's derived relations cannot be bounded by a constant. Each fixed query still has fixed arity, so its configuration space stays polynomial and log-space bookkeeping still applies. We will check this carefully, because it is where the transfer could break.
The third strand proves the lower bound and the decision procedure. Hardness generalizes the REACH gadgets of the trichotomy paper. Decidability encodes the existence of a lane-merging quotient as a property of the tree-shaped witnesses that the TWAPA construction already reads.
The fourth strand varies the data class. For 2-page book embeddings, reachability is in UL while 3-page reachability is NL-complete On the power of unambiguity in log-space. We ask whether lane-collapsing queries preserve page number, or whether some queries map 2-page data to configuration graphs with 3 or more pages. The semantic tree-likeness results of When is Ontology-Mediated Querying Efficient? characterize tractability through bounded treewidth, a much coarser structural measure. We expect page number to separate queries that treewidth does not.
Baselines
The do-nothing reference is the existing trichotomy. Over any data class, every NL-bucket query has the generic NL upper bound and nothing better. Any query we prove to be in UL over $\mathcal{D}$ beats this reference for that data class.
The strongest competitor on the theory side is naive composition: assume that min-unique data makes every linear Datalog rewriting min-unique, then apply Pavan et al. directly. We will run it fairly by testing it against our own small-case classification. If no NL-bucket query turns out to be NL-hard over min-unique ABoxes, naive composition is correct and the proposal collapses into a uniform transfer theorem. That outcome is still worth publishing, but it is a different paper. We beat this competitor only by exhibiting a query that is provably NL-hard over min-unique data.
The ablation that isolates our key ingredient is deterministic linear Datalog. These are queries whose configuration graph has out-degree one given the data, so they are in L with no uniqueness argument at all. Lane-collapsing must strictly contain this class, with a witness query that is in UL over min-unique data but has a genuinely nondeterministic configuration graph. Otherwise unambiguity adds nothing over determinism.
On the empirical side, the baseline evaluator is semi-naive linear Datalog evaluation, the standard bottom-up method for recursive rules, run on the same machine, data and ontology. The nearest reported optimization numbers come from quotient-summary pruning in Query Optimization for Ontology-Mediated Query Answering: up to three orders of magnitude speedup for UCQ rewritings on LUBM∃, and only "marginal improvements" for USCQs. Those numbers concern non-recursive rewritings, and no reported result was found on Lacuna for evaluating NL-bucket EL queries on LUBM∃ or any other benchmark. We will therefore set our own baseline numbers rather than compare against a published figure.
Why not just…?
Why not just use symmetric Datalog and Reingold's theorem, as Lutz and Sabellek suggest? Reingold's construction puts undirected reachability in L Undirected connectivity in log-space, and Symmetric Logspace is Closed Under Complement gives the companion closure result. Both need symmetric transitions. EL rules are directed implications, so in plain EL every non-first-order NL-bucket query is NL-hard and no symmetric refinement exists. The inverse-role setting where symmetry could appear is blocked by CSP open problems. Our approach applies to directed EL as it stands. We will still record which of our UL queries become L-complete once inverse roles are added, as partial evidence on the conjecture.
Why not just restrict to deterministic queries, which are trivially in L? This alternative is a real threat, and it is the ablation in the Baselines section. If every lane-collapsing query turns out to be deterministic after a log-space normalization, unambiguity buys nothing and we will say so. The two-lane examples suggest otherwise: their lanes rejoin, so the derivation is nondeterministic but unique. The decisive check is to find one such query that is in UL over min-unique data and has no deterministic rewriting.
Why not just argue that NL-complete queries are already fast in practice? For a single machine, semi-naive evaluation is probably faster in wall-clock time than any log-space-style evaluator, and we will not claim otherwise. The value lies elsewhere. The classification tells you whether a query's recursion depends on ambiguity in the data or creates ambiguity itself. That determines whether it can be evaluated in small working memory and how data cleaning that removes redundant paths affects cost. The unbounded-arity result for these rewritings makes intermediate relations large, which strengthens the memory argument.
Proposed Experiments
The theory gives the result. The experiments test whether its preconditions hold on real ontologies and data.
For ontologies, we take EL fragments of GALEN and the Gene Ontology from KRR-Oxford/BoxSquaredEL, the code release of Dual Box Embeddings for the Description Logic EL++. We add the EL-expressible part of LUBM∃₂₀, reported at 449 rules and 163 relations Query Optimization for Ontology-Mediated Query Answering. From these we sample atomic and conjunctive queries. We run the trichotomy meta-procedure to keep only the NL-bucket queries, then run our lane-collapsing test on each.
For data, we use LUBM∃ instances from 1 million to 150 million facts, generated as in the same paper. GALEN and GO ship as ontologies rather than data, so for them we generate synthetic ABoxes. On each data instance we count shortest paths by breadth-first search to measure how much of the role graph is min-unique. On each configuration graph we measure the same quantity, which gives the "ambiguity created by the query."
We will report the fraction of NL-bucket queries that are lane-collapsing, the gap between data ambiguity and configuration ambiguity, and the running time of the decision procedure. For lane-collapsing queries we will also report peak working memory of a canonical-path evaluator against semi-naive evaluation, with time reported alongside.
Two outcomes would decide the project. The first is an explicit NL-bucket query that is NL-hard over min-unique ABoxes, together with a non-deterministic one in UL over them. If both exist, the split is real. The second is empirical evidence that real ontology queries fall on both sides in non-negligible proportions. If every sampled query is lane-collapsing, or none is, the classification is correct but uninformative in practice, and we will report it that way.
References
- A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic EL
- On the power of unambiguity in log-space
- On the Power of Unambiguity in Logspace
- Classifying the Complexity of Ontology-Mediated Queries in EL: From Atomic Queries to Conjunctive Queries (Extended Abstract)
- When is Ontology-Mediated Querying Efficient?
- Query Optimization for Ontology-Mediated Query Answering
- Undirected connectivity in log-space
- Symmetric Logspace is Closed Under Complement
- Dual Box Embeddings for the Description Logic EL++.