Query Rewriting for Existential Rules with Compiled Preorder

Mélanie König, Michel Leclère, Marie-Laure MugnierIJCAI 2015

Abstract

This paper addresses the challenge of efficient query answering over ontologies by mitigating the combinatorial explosion of query sizes during the rewriting process. By pre-compiling hierarchical ontological rules into a preorder, the authors propose a novel rewriting algorithm that generates compact "pivotal" queries. Experimental results demonstrate that this approach significantly reduces query size and improves execution time compared to state-of-the-art tools.

Introduction

Ontology-Based Query Answering (OBQA) enables querying databases while incorporating domain knowledge expressed through ontological rules. A standard technique is Query Rewriting, where a user query is transformed into a Union of Conjunctive Queries (UCQ) that accounts for all possible specializations defined by the ontology. However, even simple taxonomies can lead to an exponential increase in the number of queries within the UCQ, making them impractical for standard Relational Database Management Systems (RDBMS). This paper introduces a method to "tame" this complexity within the framework of existential rules (Datalog±).

Methodology

The proposed approach separates simple hierarchical rules from more complex existential rules through a two-step process:

  1. Rule Compilation (The Preorder): Rules describing taxonomies or relation signatures (e.g., "A is a specialization of B") are identified as "compilable." These are pre-compiled into a mathematical preorder on atoms, creating a map of subsumption relationships before query processing begins.
  2. ≼-Rewriting Algorithm: A new rewriting operator, β≼, utilizes the pre-compiled preorder. Instead of exhaustively generating every variation of a query atom, the algorithm produces a "pivotal representation"—a compact query that represents all potential specializations.
  3. Pivotal Evaluation: These pivotal queries can either be evaluated directly using specialized homomorphisms or "unfolded" into standard UCQs at the final stage of processing.

Experimental Evaluation

The authors implemented their approach in a tool called PURE$_C$ and evaluated it against several benchmarks, including DL-Lite datasets (ADOLENA, STOCKEXCHANGE, UNIVERSITY, VICODI) and large-scale ontologies (OpenGalen2 and OBOProtein). These ontologies were translated into existential rules to test the algorithm's generality.

Results and Discussion

The primary advantage of the preorder-based approach is the drastic reduction in the size of the rewritten queries. As shown in Figure 1, the number of queries in the pivotal representation (gen PURE$_C$) is often orders of magnitude smaller than the traditional UCQ expansion. For instance, in the "A" dataset (ADOLENA), a query that expands to 624 UCQs is represented by a single pivotal query.

Comparison of query sizes across different methods.

Furthermore, PURE$_C$ demonstrates superior performance in terms of execution time. Figure 2 illustrates that PURE$_C$ consistently outperforms or remains competitive with specialized tools like Nyaya, Requiem, and Rapid. On the OBOProtein dataset ("O"), PURE$_C$ successfully generates rewritings where other tools frequently time out (TO).

Performance comparison (in ms) of PURE_C against other rewriting tools.

The results indicate that hierarchical relationships are the primary source of query "inflation." By handling these relationships via a preorder rather than active rewriting steps, the combinatorial explosion is effectively bypassed.

Conclusion and Future Work

The preorder-based rewriting method provides a scalable solution for OBQA with existential rules. While the algorithm is sound and complete, its termination depends on the ruleset having a finite rewriting (the "fus" property). Future work includes optimizing the "unfolding" process to reduce redundancy and exploring rewritings into more expressive formats like Datalog programs to handle even broader rule fragments.

Summary updated

BibTeX
@inproceedings{konig2015query,
  author = {Mélanie König and Michel Leclère and Marie-Laure Mugnier},
  title = {{Query Rewriting for Existential Rules with Compiled Preorder}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure