In the effort to build the Semantic Web, researchers encountered a fundamental "complexity wall." As ontologies—the logical blueprints of knowledge—grow more expressive, the computational cost of reasoning over them explodes. Traditional symbolic reasoning for highly expressive Description Logics (DL) often hits exponential or even double-exponential time complexities, making them unusable for massive, real-world datasets.
To solve this, a research direction has emerged around Approximate Reasoning and Ontology Approximation. The core intuition is simple: if a problem is too hard to solve exactly, we should transform the knowledge base into a simpler, "tractable" format that can be processed in polynomial time, even if we lose a small amount of logical nuance.
The Tractability Frontier
The central challenge in Knowledge Representation is the trade-off between expressivity (what you can say) and complexity (how hard it is to reason about it). P. Groot, Ian Horrocks, and Boris Motik argue in Methods for Approximate Reasoning that we can trade absolute logical perfection for scalability by simplifying deductions or weakening the logic language itself.
This idea traces back to the concept of "vivid" knowledge proposed by David W. Etherington and Ronald J. Brachman. In Vivid Knowledge and Tractable Reasoning, they suggest transforming ambiguous logical knowledge into a simplified, database-like format. By doing so, "commonsense reasoning" can perform as fast as a simple database lookup.
Mechanisms of Approximation
How do we actually "down-convert" a complex logic? Researchers use several key mechanisms to bridge the gap between high expressivity and computational tractability.
1. Language Mapping and Complement Tables
One of the most successful strategies involves mapping a high-complexity logic (like $\mathcal{R}$ or $\mathcal{SHIQ}$) into a simpler, polynomial-time logic (like $\mathcal{EL}^+$ or $\mathcal{DL}$-Lite). Jeff Z. Pan and Yuan Ren demonstrated this in Soundness Preserving Approximation for TBox Reasoning in R. They introduced "complement tables" to track negations that the simpler logic couldn't natively handle. This allows the system to remain sound—meaning every answer it finds is definitely true—even if it isn't complete (it might miss some subtle inferences).
2. Approximating "From Below"
When querying databases through ontologies (Ontology-Mediated Querying), the data complexity can be $coNP$-complete. Anneke Haga, Carsten Lutz, and Frank Wolter explore "approximating from below" in How to Approximate Ontology-Mediated Queries. By relaxing the ontology's constraints into Horn-logic fragments, they slash complexity to polynomial or even linear time. This ensures that the results returned are correct (sound), which is often more important in industrial applications than finding every possible theoretical answer.
3. Syntactic Rewriting and Auxiliary Symbols
Sometimes, a direct translation isn't possible. In these cases, researchers use "conservative rewritability." Boris Konev and Michael Zakharyaschev show in Conservative Rewritability of Description Logic TBoxes that by introducing "helper" or auxiliary symbols, we can simplify complex ontologies into less expressive languages that would otherwise be unreachable. Similarly, Mark Kaminski and Bernardo Cuenca Grau developed algorithms to compute Horn-logic rewritings that prevent an "exponential explosion" of rules, keeping the simplified version polynomially sized relative to the original.
Why It Works: Intuition over Perfection
The reason these approximations are so effective is that real-world ontologies often contain "heavyweight" logical features that are only used sparingly. For example, the Foundational Model of Anatomy (FMA) is notoriously complex. However, the TrOWL infrastructure, described by Jeff Z. Pan et al. in Reasoning the FMA Ontologies with TrOWL, achieves massive speedups by mapping these models into tractable sub-languages. They found that even with approximation, they could maintain 100% recall for classification tasks.
By treating reasoning as a compilation problem—transforming a high-level "source code" (expressive logic) into an "executable" (tractable fragment)—the field has moved from theoretical proofs to systems like ONTOSEARCH2 Edward Thomas and Ubergraph Ugur Bayindir. These systems allow users to perform deep, relationship-based queries over millions of assertions at speeds up to 100x faster than traditional reasoning tools.