DEALER: A Fuzzy EL++ Description Logic Reasoner in Rust — Architecture, Fuzzy Reasoning, and the Road to Mobile Ontology Intelligence

By Jonathan Borden, M.D. (jonathan@loxation.com)

Introduction

Ontology reasoning has been traditionally the domain of desktop and server-side systems — complex Java frameworks like Protege and OWL API dominate the landscape. I know this landscape intimately: in the early 2000s, I served as an invited expert on the W3C OWL Working Group, where I helped design the Web Ontology Language with healthcare's needs in mind. The challenge then was creating a language expressive enough for clinical terminologies yet decidable enough for practical computation. Two decades later, we have OWL 2 and massive ontologies built on it — SNOMED CT with 350,000+ concepts, GALEN-EL for clinical modeling, Gene Ontology for biology — but the reasoning still happens on servers. As knowledge graphs move to the edge, we encounter a new problem: how do you reason over these semantically rich ontologies on mobile devices and edge servers with sub-second latency and minimal memory footprint?

Enter DEALER, an OWL-2 fuzzy EL++ Description Logic reasoner written in Rust. It's a minimal, high-performance implementation of a saturation-based classification algorithm, engineered from the ground up for resource-constrained environments. DEALER parses OWL 2 ontologies, normalizes axioms into canonical forms, applies a fixed-point completion algorithm, and extracts a subsumption taxonomy. The entire pipeline — parsing through taxonomy extraction — typically completes in microseconds-milliseconds on small to medium-scale ontologies. Large ontologies currently take 10s of seconds but that's the price of running a classifier on a mobile device.

But DEALER goes further: it extends EL++ with fuzzy reasoning, allowing axioms to carry degrees of truth that propagate through inference chains using configurable triangular norms (t-norms). This opens the door to representing uncertainty, confidence scores, and approximate subsumption in domains like healthcare (where clinical severity varies), IoT (where sensor readings have noise), and knowledge base enrichment (where automated extraction always has uncertainty).

This article dives deep into DEALER's architecture, the saturation algorithm it implements, the Rust patterns that make it fast, fuzzy reasoning mechanics, and lessons learned porting from the ELK reasoner (a popular Java implementation) to pure Rust. We'll explore how graph databases fit into the pipeline, and discuss the path toward mobile-first ontology reasoning. In the companion set of articles we show the process of optimizing the reasoning pathway.

What Is EL++ and Why It Matters

Description Logic (DL) is a family of formal languages for representing knowledge. Unlike first-order logic, which is undecidable, DLs are designed to be decidable — typically with known complexity bounds. They sit at a sweet spot: expressive enough to model real-world domains, yet tractable enough to compute inference in polynomial time.

EL++ (EL with role hierarchies, transitive roles, and range restrictions) is one such logic. It's the dialect used by SNOMED CT (the clinical reference terminology with 350,000+ concepts), Gene Ontology (used in biomedics), GALEN-EL (a large healthcare ontology where fuzzy DL has proven particularly valuable for modeling clinical gradations), and many industrial taxonomies. The key properties of EL++ are:

1. Concept Constructors: Intersection (A ⊓ B), existential restriction (∃r.B), and nominal (singleton sets like {john}).
2. Decidability: Reasoning is decidable.
3. Complexity: In polynomial time — specifically, subsumption can be checked in PTIME (polynomial time deterministic).
4. Practicality: EL++ is expressive enough for most taxonomy use cases, yet efficient enough that you can classify ontologies with hundreds of thousands of axioms in seconds on a single machine.

EL++ achieves this via the saturation algorithm, a forward-chaining procedure that applies completion rules until reaching a fixpoint. Unlike backward-chaining approaches (like SLD resolution), saturation precomputes all subsumption relationships upfront. This amortizes classification cost: once saturated, answering a subsumption query "is A subsumed by B?" is a simple table lookup.

For mobile and edge deployments, this is transformative. A mobile health app can parse a clinical ontology once, saturate it offline, and store the resulting taxonomy in a compact database. At runtime, query the pre-computed taxonomy in microseconds — no reasoning engine needed. If axioms change (e.g., new drug interactions), re-saturate locally on the device and push updates to the backend.

Architecture: A Seven-Crate Pipeline

DEALER is a Rust workspace with seven crates, each handling one stage of the pipeline. This modular design allows easy testing, reuse, and future optimizations.

dealer-core: Shared Abstractions (563 LOC)

At the foundation, dealer-core defines the types used across all crates: ConceptId(u32) and RoleId(u32) are newtype wrappers around integers, enabling type-safe interning. ConceptId(0) is reserved for owl:Thing, ConceptId(1) for owl:Nothing. All IRIs are mapped to integer IDs for O(1) lookup in hash tables. The crate also includes an Interner (hash table mapping strings to IriIds), Degree (fuzzy membership in [0.0, 1.0] with epsilon-based comparison), TNorm (trait for triangular norms), and Axiom/NormalizedAxiom AST types.

The use of newtypes (ConceptId(pub u32)) is a key Rust pattern. It provides zero-cost abstraction — the compiler erases the wrapper at runtime — but grants compile-time safety: you cannot accidentally pass a ConceptId where a RoleId is expected.

dealer-parser: Recursive Descent (1,527 LOC)

The parser implements a recursive descent grammar for OWL 2 Functional Syntax (.ofn files). It handles prefix declarations and namespace resolution, class axioms (SubClassOf, EquivalentClasses, DisjointClasses), class expressions (ObjectIntersectionOf, ObjectSomeValuesFrom, ObjectOneOf), property axioms (SubObjectPropertyOf, ObjectPropertyChain, TransitiveObjectProperty), assertions (ClassAssertion, ObjectPropertyAssertion), and fuzzy annotations via the http://dealer.io/ontology#degree IRI.

Unsupported constructs (ObjectUnionOf, DataProperties, etc.) are silently skipped, making the parser lenient enough for real-world OWL files. The parser is hand-written rather than generated (no ANTLR or similar). This keeps the binary small and gives fine-grained error reporting. For a small ontology like the Pizza example (7 test files, ~2KB each), parsing takes ~200 microseconds.

dealer-normalizer: Axiom Canonicalization (1,048 LOC)

The normalizer converts arbitrary class axioms into eight canonical forms:

Why normalize? The saturation algorithm works on these canonical forms, making the completion rules (CR1-CR9) simple and uniform. For instance, CR1 (the conjunction rule) checks for NF1 axioms; CR2 handles NF2; and so on. Without normalization, the reasoner would need to handle arbitrary nested expressions, complicating the algorithm.

The normalizer also allocates fresh concept names for decomposition. When normalizing A ⊓ B ⊑ C, which is already in NF1, no allocation is needed. But when normalizing A ⊑ ∃r.(B ⊓ C), the normalizer creates a fresh concept F, emits two NF2 axioms (A ⊑ ∃r.F and A ⊑ ∃r.C), and a single NF1 axiom (B ⊓ C ⊑ F), ensuring the filler is atomic.

Each axiom carries a degree (default 1.0 for crisp), and the normalizer preserves degrees through decomposition, threading them through the generated axioms so that fuzzy semantics are maintained during normalization.

dealer-reasoner: Saturation Algorithm (1,915 LOC)

The reasoner is the heart of DEALER. It implements the saturation loop: first, initialization — for each named concept, create a context with its label set S(A) = {A, Thing}. Then, saturation — repeatedly apply completion rules (CR1-CR9) until no new inferences are derived. Finally, termination — when the work queue is empty, every entailed subsumption has been discovered.

Contexts and Label Sets

Each concept A has a context holding its subsumers, role edges, and predecessors:

The label set S(A) is a map from ConceptId to Degree, representing all concepts B such that A ⊑ B with the given degree. After saturation, S(A) contains the complete set of subsumers of A. The successors and predecessors track role edges — e.g., if there is an axiom A ⊑ ∃r.B, then after applying CR2, B appears in the successors of A under role r.

Completion Rules

The nine completion rules form the core of saturation:

CR1 (Conjunction): When a concept is added to S(ctx_id), check if any conjunction axiom's two conjuncts are both present. If so, derive the right-hand side.

CR2 (Existential Right): When a concept is added to S(ctx_id), apply existential axioms.

CR3 (Existential Left): When an edge (X, r, Y) is added, apply existential axioms on the other side.

CR4-CR9: Handle role chains, range restrictions, transitivity, and nominals.

Each rule is triggered lazily via an axiom index:

The Axiom Index: Smart Rule Triggering

Naive saturation would iterate all axioms after every work item, resulting in O(n^2) behavior. DEALER pre-indexes axioms by their "trigger" parts:

When a concept A is added to S(X), the reasoner looks up conjunction_by_conjunct[A] and applies only the relevant axioms. This reduces the per-work-item cost from O(axioms) to O(matching axioms).

SmallVec is key here: most axioms have only a few entries per key, so SmallVec uses inline storage (e.g., 4 entries before heap allocation), avoiding pointer chasing for common cases.

The Work Queue and Deduplication

The work queue is a FIFO buffer of work items (concepts added or edges added). After processing an item, new items are enqueued. To avoid duplicate work, the queue uses a high-water-mark strategy:

Before enqueuing a work item, the reasoner checks if it's already in the queue. If so, it's skipped. This prevents O(n^2) duplicates.

Fuzzy Degree Propagation

When combining degrees, the reasoner uses the configured t-norm:

Zadeh (min-based): Conjunction(a, b) = min(a, b). Conservative — the weakest link dominates.

Lukasiewicz (sum-based): Conjunction(a, b) = max(0, a + b - 1). Stricter — accumulated uncertainty degrades the degree.

For a chain A ⊑ B ⊑ C with degrees 0.8 and 0.7: Zadeh gives A ⊑ C at min(0.8, 0.7) = 0.7. Lukasiewicz gives A ⊑ C at max(0, 0.8 + 0.7 - 1) = 0.5.

The choice of t-norm is application-dependent: medical ontologies might prefer Zadeh (one bad link invalidates the chain), while IoT sensor confidence might prefer Lukasiewicz (compound uncertainty).

dealer-taxonomy: DAG Extraction (367 LOC)

After saturation, the reasoner has computed S(A) for every concept. The taxonomy extractor identifies equivalence classes (two concepts A and B are equivalent if A ⊑ B and B ⊑ A both hold with degree >= threshold), computes direct subsumption via transitive reduction, and builds a DAG where nodes are equivalence classes and edges are direct subsumption relations with degrees.

dealer-store: Graph Database Integration (1,719 LOC)

The final stage exports the taxonomy to a graph database for persistent storage and querying. DEALER supports two backends: rukuzu (Rust, embedded — lightweight, no server, ideal for on-device storage) and kuzu (C++, optional — high-performance with advanced query planning for large-scale analytics).

The schema is minimal:

This allows queries like "What are the direct superclasses of MargheritaPizza?" to be answered with simple edge traversals:

Rust Performance Patterns: Why DEALER Is Fast

Performance is DEALER's raison d'etre. Rust enables several patterns that make saturation fast:

Pattern 1: String Interning with FxHashMap

IRIs are long strings (e.g., http://purl.obolibrary.org/obo/HP_0000118). Storing them directly in maps would incur large memory footprint and expensive string comparisons. DEALER interns all IRIs to u32 handles:

Once interned, all reasoning uses integer handles (ConceptId, RoleId, IriId). Lookups and comparisons are O(1) and involve only u32 arithmetic.

Pattern 2: FxHashMap Over HashMap

The standard HashMap uses SipHash (cryptographically secure but slow). For non-adversarial cases, rustc_hash::FxHashMap (a Rust compiler-internal hash function) is 2-3x faster. DEALER uses FxHashMap in 63+ places — every axiom index, context, and work queue.

Pattern 3: SmallVec for Axiom Collections

Most axioms have few entries per index key. SmallVec uses inline storage (4-8 elements) before allocating on the heap:

This eliminates pointer dereferences and improves cache locality. For a typical ontology, 80% of index buckets fit in the inline buffer.

Pattern 4: Newtype Wrappers for Type Safety

ConceptId(u32) is a zero-cost wrapper that prevents type confusion:

The compiler optimizes these away, but they enforce correctness at compile time. You cannot accidentally pass a RoleId to a function expecting ConceptId.

Pattern 5: Copy Semantics for Cheap Cloning

ConceptId, RoleId, Degree, and IriId all derive Copy. Passing them by value (not reference) is faster than reference-based borrowing for tiny types:

Benchmarks: Sub-Microsecond Reasoning

On a small ontology (pizza_subset.ofn, 33 axioms):

On a medium ontology (trust_test_scenarios.ofn, ~300 axioms):

The consistency of these times — all under a millisecond — is what makes DEALER suitable for mobile: a typical smartphone can classify a clinical ontology in the time it takes to render a single frame.

Fuzzy Reasoning: Toward Uncertain Semantics

Real-world ontologies are not crisp. A clinical diagnosis might be "probable" rather than "certain". A sensor reading has measurement error. An automated knowledge extraction might have confidence scores. This has been demonstrated convincingly in healthcare: GALEN-EL, a large clinical ontology, has shown that fuzzy description logic is valuable for representing the gradations inherent in medical knowledge — where severity is a spectrum, diagnoses carry confidence levels, and treatment efficacy varies by population. Fuzzy DL extends EL++ to model these uncertainties systematically.

Fuzzy Sets and T-Norms

In crisp set theory, membership is binary: x either is or is not in set A. In fuzzy set theory, membership is a degree u(x) in [0, 1], representing how much x belongs to A.

Fuzzy subsumption extends this: A ⊑ B at degree d means "A is a subclass of B with certainty d". In a clinical context, "Asthma ⊑ RespiratoryDisease" might hold at degree 0.95 (because some edge cases blur the boundary), while "SleepApnea ⊑ RespiratoryDisease" is 1.0 (fully certain).

Triangular norms (t-norms) define how conjunction behaves in fuzzy logic. DEALER implements both Zadeh (min-based) and Lukasiewicz (sum-based), configurable via --t-norm flag:

Degree Propagation Through Inference

The completion rules propagate degrees. When inferring a subsumption B ⊑ C from A ⊑ B and A ⊑ C via transitivity, the resulting degree is the t-norm conjunction of the two input degrees.

Example: ontology with three classes and two axioms:

The reasoner infers A ⊑ C by chaining the rules. With Zadeh: 0.7 (limited by the weaker link). With Lukasiewicz: 0.5 (compound uncertainty).

This is valuable in medical domains: if you're uncertain at two steps of a clinical reasoning chain, the final conclusion should reflect compounded doubt.

Equivalence Thresholds

By default (--equiv-threshold 1.0), concepts A and B are equivalent only if both A ⊑ B and B ⊑ A hold at degree 1.0. Lowering the threshold (e.g., 0.9) groups near-equivalences. This allows fuzzy equivalence classes for approximate taxonomies.

Application: Clinical Ontology with Confidence

Consider a clinical ontology where drug efficacy varies:

When querying "Is Aspirin suitable for pain and inflammation together?", the reasoner infers: with Zadeh: 0.8 (limited by the weaker link, inflammation). With Lukasiewicz: 0.75 (0.95 + 0.8 - 1). The choice reflects your confidence model: Zadeh is pessimistic (one weak link breaks the chain), Lukasiewicz is moderate.

From ELK to DEALER: Porting Lessons and Claude as a Development Partner

DEALER is inspired by ELK, a Java-based reasoner with decades of optimization. Building DEALER in Rust — and separately, porting the kuzu C++ graph database to Rust as rukuzu — taught several lessons. Claude proved to be a valuable development partner throughout this process, particularly for the mechanical aspects of translation and for working through algorithm edge cases where having a "second pair of eyes" on complex logic was invaluable.

What Translated Well (and Where Claude Helped)

Claude excelled at the mechanical translation work: converting C++ data structures to idiomatic Rust, suggesting appropriate crate equivalents, and identifying where C++ patterns had direct Rust analogs. The axiom indexing structures (multi-maps from trigger concepts to axiom data) mapped directly to Rust's FxHashMap + SmallVec, and Claude could generate these translations quickly. The saturation loop's basic FIFO queue + work item pattern was identical across languages; Rust's ownership model just required explicit lifetime management. Context representations using maps-within-maps for labels and successors worked seamlessly.

For the rukuzu port specifically — translating kuzu's C++ graph database engine to Rust — Claude was particularly useful for working through graph algorithm edge cases and query execution semantics. The sheer volume of boilerplate translation (type definitions, accessor methods, serialization code) is where an AI assistant saves the most time.

What Needed Human Rethinking

Some patterns simply don't translate mechanically. C++ and Java's garbage collection hides aliasing; Rust's borrow checker requires careful restructuring. The reasoner's global contexts map and per-item access patterns needed rearchitecting to avoid multiple mutable borrows — this was a design decision, not a translation, and required understanding the algorithm's invariants at a level Claude couldn't always reach.

String interning is another example. Java's intern pool is global and automatic. Rust requires explicit interning. DEALER's solution (a single Interner passed through the pipeline) is more transparent and allows per-ontology interners — but arriving at this design required thinking about the ownership story end-to-end.

Floating-point comparison for fuzzy degrees was subtle: DEALER defines Degree::EPSILON (1e-10) for stable comparisons, and the choice of epsilon required understanding the downstream numerical effects on degree propagation chains.

Performance Wins from Rust

The payoff for this effort was substantial. No GC pauses: Java's garbage collector can halt the world for 100ms+ on large heaps, while Rust's stack allocation and ownership eliminate this entirely — DEALER's saturation never pauses. Monomorphization allows FxHashMap<ConceptId, ...> to be optimized at compile time, something Java's type erasure cannot do. And the binary size tells the story: DEALER is ~20 MB (release build), while a comparable Java tool (ELK + JVM) is 200+ MB. For edge deployment, this matters enormously.

What Required Human Judgment

Fuzzy degree semantics — which ELK (being crisp) doesn't have — required reading the fuzzy DL literature and making design choices that no translation tool could automate. The choice of t-norms, the epsilon-based comparison thresholds, the decision to propagate degrees through all nine completion rules rather than just a subset: these were informed by the needs of healthcare ontologies like GALEN-EL, where fuzzy reasoning has proven most valuable.

ELK uses bidirectional indexes heavily, and Rust's borrow checker makes some bidirectional patterns awkward. DEALER went single-direction in places, requiring an extra pass to rebuild reverse mappings (predecessors). This was an architectural trade-off that required understanding the performance profile, not just the code structure.

Error handling was another area where human judgment trumped mechanical translation. Java's checked exceptions enforce error propagation; Rust's Result<T, E> is more flexible but requires discipline. DEALER uses a DealerError enum to cover parse errors, type errors, and unsupported constructs — a design that emerged from iteration, not translation.

Graph Database Integration: From Memory to Persistence

Once a taxonomy is extracted, it's valuable to persist it. DEALER integrates two graph database options.

rukuzu (Rust, Embedded) is a lightweight graph database written in Rust, designed for embedded scenarios: single-file storage with index pages for O(1) node and edge lookup, no server required (the database is a library), suitable for on-device storage (mobile, IoT). DEALER exports the taxonomy as Concept nodes and DirectSubClassOf edges, with degree properties on edges.

kuzu (C++, High-Performance) offers optimized join algorithms, distributed query processing, and rich query language (openCypher) for large-scale analytics. Trade-off: kuzu requires a running server, but scales to billion-node graphs. rukuzu is simpler and sufficient for clinical ontologies.

A future extension could add axiom provenance (which axioms imply which subsumptions), enabling explanation and debugging.

Performance Characteristics and Mobile Readiness

For an embedded deployment, performance must be predictable.

Initialization Overhead

Parsing and normalization happen once, offline:

Even a large clinical ontology (100k axioms) takes ~100ms on a modern CPU.

Saturation Cost

Saturation dominates the cost but scales predictably: small ontology (33 axioms) takes 116us, medium ontology (300 axioms) takes 300us, and large (100k axioms) is expected to take ~10s (linear in axioms + inference steps). The saturation algorithm is single-threaded; parallelization is future work but non-trivial due to data dependencies.

Query Cost

Once saturated, a subsumption query is O(1) average-case lookup:

For mobile apps: microsecond latency.

Memory Footprint

For a typical ontology: 33 axioms uses ~50 KB memory, 300 axioms uses ~500 KB, 100k axioms uses ~100 MB. Compare to Java tools which require 500 MB+ (JVM overhead + framework). For mobile and edge, DEALER fits in tight budgets.

Mobile Deployment Pattern

1. Offline: On a server, classify the clinical ontology, export to rukuzu.
2. Distribution: Package the small binary (~20 MB) + lightweight database (~1 MB for 100k concepts) in the app.
3. Runtime: Load the database, answer queries in microseconds.
4. Updates: If axioms change, re-classify locally and sync back.

This is what makes DEALER suitable for healthcare apps where low latency and offline-first capability are critical.

Testing and Validation

DEALER includes 49+ unit tests across the pipeline and 8 test ontologies: simple_hierarchy.ofn (GoldenRetriever ⊑ Dog ⊑ Animal), conjunction.ofn (tests CR1), existential.ofn (tests CR2/CR3), role_chain.ofn (tests CR8), equivalence.ofn (tests equivalence class grouping), fuzzy_chain.ofn (degree propagation under different t-norms), pizza_subset.ofn (a realistic ontology with existential restrictions), and trust_test_scenarios.ofn (scenario-based testing for fuzzy reasoning).

Tests are organized per crate:

Each test verifies both correctness (expected subsumptions exist) and performance (queries complete in expected time).

Future Directions

Parallelization. The saturation loop currently processes one work item at a time. The work queue could be partitioned by concept, allowing multiple threads to process independent rule applications in parallel.

Incremental Updates. If an axiom is added or removed, re-saturating from scratch is wasteful. Incremental reasoning could reduce cost from O(axioms) to O(affected concepts).

Explanation and Provenance. Why is A subsumed by B? Which axioms contributed? Adding a trace during saturation would enable explanation graphs useful for debugging and ontology curation.

Advanced Fuzzy Semantics. Fuzzy DL with more expressive t-norms (e.g., parameterized families), modular semantics, and multiple conflicting evidence sources could extend reasoning for uncertain domains.

Integration with Vector Embeddings. Embedding concepts as vectors (using techniques like TransE or node2vec) could enable approximate subsumption queries complementing exact reasoning.

Mobile UI Toolkit. A React Native library wrapping DEALER could make ontology querying accessible to mobile app developers without Rust expertise.

Conclusion

DEALER demonstrates that high-performance, resource-constrained ontology reasoning is achievable in Rust. By combining EL++ saturation with careful performance engineering (string interning, hash maps, SmallVec), fuzzy degree propagation, and lightweight persistence via rukuzu, DEALER opens a new frontier: ontology intelligence on mobile devices and edge servers.

For healthcare, supply chains, IoT, and knowledge bases, this means: Privacy — reason locally on sensitive data; don't send everything to the cloud. Latency — microsecond queries, not seconds. Efficiency — sub-100 MB deployments, not gigabytes.

The path from ELK (a mature Java reasoner) to DEALER (a Rust version implementing fuzzy classification) shows that porting complex symbolic reasoning to systems languages is feasible and rewarding. The lessons — string interning, performance-conscious data structures, careful fuzzy semantics — apply beyond ontologies to any symbolic reasoning system targeting mobile and edge.

The future of knowledge representation may not be in server farms, but in the billions of connected devices waiting for local semantic intelligence.

---