First-Order Rewritability for Scalable Ontological Reasoning

This direction is merged into another direction: first-order rewritability. Its last version stays readable and citable here.

Version 1 of 137 papers47 conceptsfrozen 2026-10-04

In modern data management, there is a fundamental tension between expressivity and scale. On one hand, domain experts want to query data using rich, semantic concepts (e.g., "Find all patients with a respiratory infection"). On the other hand, data is often stored in massive, "flat" relational databases that only understand specific table columns (e.g., DiagnosisCode = 'J06.9').

The research direction of Ontology-Mediated Query Answering (OMQA) bridges this gap. Its core insight is that we can treat an ontology not as a separate database to be "reasoned" over, but as a set of instructions for transforming a high-level semantic query into a standard SQL statement. This property is known as First-Order (FO) Rewritability.

The Intuition: Query Expansion as Reasoning

Traditionally, reasoning over an ontology involved complex, iterative algorithms that were difficult to scale. FO-rewritability changes the strategy: instead of changing the data to fit the logic, we change the query to fit the data.

Imagine a user asks a query $Q$ against an ontology $\mathcal{T}$. If the logic used to describe $\mathcal{T}$ is FO-rewritable, we can "compile" the pair $(Q, \mathcal{T})$ into a new, expanded query $Q_{SQL}$. This expanded query contains all the logical implications of the ontology. For example, if the ontology says "A Viral Infection is a Respiratory Infection," the rewriter will automatically add a UNION clause to the SQL to look for viral infection codes whenever a user asks for respiratory ones.

As Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati 0001 demonstrate in EQL-Lite: Effective First-Order Query Processing in Description Logics, this allows complex reasoning to be offloaded to highly optimized relational database engines (RDBMS). The database doesn't even know it's performing "reasoning"; it's just executing a very efficient, albeit large, SQL join and union operation.

The Computational Sweet Spot: DL-Lite

Not all logics allow for this clean translation. If a logic is too expressive, the rewritten query might become infinitely long or require features that SQL doesn't support (like recursion).

The research has identified a "computational sweet spot" in the DL-Lite family of description logics. In Data Complexity of Query Answering in Description Logics, the authors prove that DL-Lite is essentially the most expressive logic that still guarantees FO-rewritability. This ensures that the "data complexity"—the time it takes to answer a query relative to the size of the dataset—remains in LOGSPACE, the same complexity class as standard SQL. This is critical for industrial applications where datasets reach billions of rows.

Scaling with Big Data Infrastructure

Because FO-rewritability turns semantic problems into relational ones, it allows the Semantic Web to "piggyback" on decades of progress in distributed systems.

Frameworks like SANSA, described by Ivan Ermilov and Claus Stadler in The Tale of Sansa Spark, translate SPARQL queries into Spark-SQL. By doing so, they enable knowledge graph reasoning on massive clusters without building a custom "semantic" distributed engine from scratch. Similarly, Claus Stadler and Gezim Sejdiu show in Querying Large-scale RDF Datasets Using the SANSA Framework that this approach inherits the mature optimization strategies of Spark and Flink, making it possible to query billions of triples on commodity hardware.

Beyond Static Schemas: Mappings and Constraints

In real-world scenarios, the data isn't just sitting in a single table; it's scattered across heterogeneous sources. Ontology-Based Data Access (OBDA) uses "mappings" to link these sources to the ontology.

Systems like Optique, highlighted by Evgeny Kharlamov and Martin Giese in Optique 1.0: Semantic Access to Big Data, use a process called query unfolding. This takes the semantic query, applies the ontology axioms, and then "unfolds" the result through the mappings to generate the final SQL.

Recent work by David Toman 0001 and Grant E. Weddell in First Order Rewritability in Ontology-Mediated Querying in Horn Description Logics suggests that FO-rewritability isn't just a property of the logic itself, but a systemic property. By considering database integrity constraints (like foreign keys), we can sometimes achieve FO-rewritability even in more expressive "Horn" logics that would otherwise be considered too complex for SQL translation.

Handling Inconsistency and Preferences

As the field matures, researchers are extending FO-rewritability to handle the "messiness" of real data:

  1. Inconsistency Tolerance: Real databases often conflict with their ontologies. Thomas Lukasiewicz and colleagues have explored how to rewrite queries so they only return "cautious" answers—those that are true in every possible "repair" of the database—while still staying within the bounds of FO-rewritability (Complexity of Inconsistency-Tolerant Query Answering in Datalog+/-).
  2. Ranked Answers: When a query returns too many results, users need preferences. Ismail Ilkan Ceylan and Thomas Lukasiewicz demonstrate in Query Answering in Ontologies under Preference Rankings that preference-based reasoning can also be compiled into SQL, allowing for ranked retrieval at scale.
  3. Assumptive Queries: Medina Andresel and Magdalena Ortiz 0001 have shown that even "what-if" queries—which return answers that would be true if certain assumptions were met—can be FO-rewritten in specific contexts (Query Rewriting for Ontology-Mediated Conditional Answers).

By focusing on FO-rewritability, this research direction ensures that as our knowledge representations become more sophisticated, our ability to query them remains anchored in the high-performance reality of modern database systems.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_first_order_rewritability_for_scalable_o_fabdf6d3,
  title = {First-Order Rewritability for Scalable Ontological Reasoning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/first-order-rewritability-for-scalable-ontological-reasoning/rdr_fabdf6d36ef64fa892cd6ee740075a58},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_first_order_rewritability_for_scalable_o_fabdf6d3_v1,
  title = {First-Order Rewritability for Scalable Ontological Reasoning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/first-order-rewritability-for-scalable-ontological-reasoning/rdr_fabdf6d36ef64fa892cd6ee740075a58/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}