First Order Rewritability in Ontology Mediated Query Answering

57 concepts41 papers2 proposals

The Impedance Mismatch of Knowledge and Scale

Enterprise data typically resides in massive relational databases optimized for SQL queries, or distributed data warehouses designed for high-throughput parallel processing. However, domain experts and applications often need to interact with this data using high-level, conceptual models known as ontologies. Ontologies represent domain knowledge explicitly through classes, relationships, and logical rules (often formalized using Description Logics).

When we want to query a database through the lens of an ontology—a paradigm known as Ontology-Mediated Query Answering (OMQA)—we encounter a fundamental challenge. Standard relational database engines cannot natively process the logical rules embedded in an ontology. For example, if an ontology states that every Professor is a FacultyMember, a database query for FacultyMember will miss records explicitly labeled only as Professor unless some form of reasoning occurs.

Building a specialized reasoning engine from scratch to handle billions of records is notoriously difficult and rarely matches the performance of mature database technologies. This raises a compelling question: Can we compile the logical rules of the ontology directly into the query itself?

If a high-level query can be translated into an equivalent standard database query (such as a single SQL statement or a First-Order logic expression), the entire reasoning task can be offloaded to existing, highly optimized relational database management systems (RDBMS). This powerful property is known as First-Order (FO) rewritability. When a query is FO-rewritable, the semantic reasoning happens entirely during a preprocessing compilation step, allowing actual query execution to scale efficiently with low data complexity.

The Mechanics of Query Rewriting

To understand how query rewriting works, consider the process of query reformulation. As Diego Calvanese et al. describe, query reformulation takes a user's conjunctive query along with the ontology's axioms and expands them into a single Union of Conjunctive Queries (UCQ). This expanded query explicitly enumerates all the logical possibilities allowed by the ontology, turning implicit semantic relationships into explicit relational OR and AND operations that a standard SQL engine can execute directly.

As Magdalena Ortiz 0001 notes in Improving Data Management using Domain Knowledge, this transformation allows us to evaluate complex queries incorporating ontological knowledge without modifying the underlying data storage. In industrial settings, such as the Optique project discussed by Martin Giese et al. and Evgeny Kharlamov et al., this is often referred to as "semantic query unfolding." By leveraging mappings between the ontology and physical database schemas, abstract domain-specific terminology is translated into optimized low-level SQL instructions, allowing organizations to query heterogeneous data natively.

The Boundaries of Tractability

We cannot compile every ontology into a standard SQL query. There is a strict theoretical boundary governing when FO-rewritability is possible.

Diego Calvanese et al. demonstrated that the DL-Lite family of Description Logics represents the maximal expressivity allowed if you want to guarantee that queries can always be compiled into standard SQL while maintaining a low data complexity of LOGSPACE. If you add more expressive logical constructs—such as qualified existential quantification or disjunction—the query answering problem exceeds the capabilities of traditional relational engines, and a finite FO rewriting ceases to exist.

When we step beyond the boundaries of DL-Lite into other popular families like the $\mathcal{EL}$ description logic, achieving FO-rewritability by modifying the query alone becomes impossible for certain structures, as noted by Carsten Lutz et al.. To circumvent this limitation, researchers employ two primary strategies:

  1. Targeting Datalog: Instead of compiling queries into standard First-Order logic (SQL), queries can be rewritten into Linear Datalog (the logical foundation of recursive SQL). Carsten Lutz et al. and Carsten Lutz demonstrate that breaking down query structures into non-recursive Datalog programs or linear Datalog allows systems to retain tractability for expressive ontologies.
  2. The Combined Approach: If rewriting the query alone is insufficient, Carsten Lutz et al. propose modifying both the underlying data representation (the ABox) and the query structure simultaneously, enabling industrial relational databases to handle massive biomedical and biological ontologies.

Bridging Open and Closed Worlds

Traditional relational databases operate under the Closed World Assumption (CWA): if a fact is missing from the database, it is assumed to be false. Ontologies, conversely, operate under the Open World Assumption (OWA): missing data is treated simply as unknown, allowing for incomplete information.

Managing this conceptual conflict during query rewriting is a major focus of the field. Inanç Seylan et al. introduced the concept of DBoxes, which designate specific ontology predicates as complete, closed database tables, using logic-based interpolation to safely rewrite queries. When dealing with partially closed datasets, Carsten Lutz et al. showed that while closing certain relationships can easily cause the problem to become computationally intractable (coNP-hard), the queries remain efficiently translatable to standard SQL if they are restricted to lightweight description logics and quantifier-free structures.

Coping with Inconsistent Data

In real-world enterprise environments, data frequently conflicts with the rules defined in an ontology. For instance, an ontology might dictate that a person can have only one employee ID, but a poorly maintained database might contain duplicate entries. Under classical logic, an inconsistency can invalidate the entire query answering process.

To resolve this, researchers use Consistent Query Answering (CQA), which evaluates queries against "repairs"—maximal consistent subsets of the database. Thomas Lukasiewicz et al. analyzed the complexity of this problem and discovered that while consistency-aware querying is generally hard, specific "intersection semantics" preserve FO-rewritability for certain rule fragments like linear and sticky Datalog$^{\pm}$. Furthermore, Meghyn Bienvenu demonstrated that the exact boundary of FO-rewritability in consistency-aware querying depends heavily on the number of quantified variables present in the query, providing a clear roadmap for designing scalable, error-tolerant query engines.

Scaling to Distributed Big Data

The ultimate practical validation of FO-rewritability is its application to massive, distributed big data frameworks. Rather than building custom distributed graph databases from scratch, frameworks like SANSA leverage query rewriting to repurpose existing big data infrastructure.

As shown by Ivan Ermilov et al. and Claus Stadler et al., high-level graph queries (written in SPARQL) can be translated directly into native SQL statements or distributed data processing functions (like map, filter, and join). This translation layer allows semantic queries to run natively on engines like Apache Spark and Flink, inheriting decades of industry-standard optimization research and distributed execution strategies.

On a smaller scale, Hans Chalupsky et al. demonstrated with the Kypher language that compiling declarative graph patterns into optimized SQL commands allows massive datasets like the entirety of Wikidata to be queried efficiently using lightweight, file-based relational engines right on a standard laptop. By transforming the problem of logical reasoning into a problem of query translation, FO-rewritability bridges the gap between rich semantic knowledge and high-performance data processing.

Key Foundational Work

SAPHIR + RESEDA: A New Approach to Intelligent Data Base Access (1985) — contributed 2 concept elements to this direction.
Accessing Relational Databases via XML Schema (2003) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_first_order_rewritability_591cc6ff,
  title = {first-order rewritability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/first-order-rewritability/rdr_591cc6ff5009441585d8ea42288a497a},
  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_591cc6ff_v1,
  title = {first-order rewritability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/first-order-rewritability/rdr_591cc6ff5009441585d8ea42288a497a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake