Practical Rewriting Techniques for Warded Ontology-Mediated Queries

Existential rules, a.k.a. tuple-generating dependencies (TGDs), form a well-established formalism for specifying ontologies, i.e., logical descriptions of a domain of interest. One of the main tasks in this context is Ontology-Mediated Query (OMQ) Answering. That is, given an Ontology-Mediated Query O = (q, Σ), comprising a TGD-based ontology Σ and a query q (usually a conjunctive query), find all the answers to q that can be entailed from the logical theory D ∧ Σ, where D is a given database encoded as a conjunction of facts. It is well-known that even checking if a tuple is an answer to an OMQ O is undecidable, due to the high expressiveness of TGDs. Hence, different classes of TGD-based ontologies have been introduced in the literature with the goal of restoring decidability. Such classes can be categorized in two main groups, depending on the strategy employed to obtain decidability. The first group comprises ontologies Σ for which an explicit and finite materialization of the facts that can be derived using the database and the TGDs in Σ can be constructed; such a materialization is usually achieved by means of the well-known chase procedure. The second group comprises ontologies Σ guaranteeing that any OMQ O = (q, Σ) can be rewritten to a query q′ in some other (decidable) query language such that for every database D, the answers of O over D coincide with the answers of q′ over D. From the second such a group, warded ontologies recently emerged as a well-behavedclass of TGD-based ontologies, striking a good balance between expressive power and computational complexity of Ontology-Mediated Query Answering. The theoretical foundations of OMQ Answering over warded ontologies are by now well-understood, where the problem is known to be solvable in polynomial time, in data complexity, i.e., when only the database is considered as part of the input. In particular, it is well-known that OMQ Answering under warded ontologies is Datalog-rewritable, i.e., given an OMQ over a warded ontology, it is possible to construct a query written in Datalog, a well known database query language introduced in the 80’s, such that for every database, the answers to the OMQ over the database coincide with the answers of the Datalog query over the database alone. Unfortunately, very few efforts exist in the literature that exploit such a rich theory for building practical query answering algorithms under warded ontologies. The main contribution of this thesis is to fill the above gap by designing a novel rewriting algorithm for OMQs over warded ontologies which is more amenable to practical implementations, as well as providing an implementation and an experimental evaluation, with the aim of understanding which key input parameters affect the performance of this approach, and what are its limits. Furthermore, the thesis will show how to use the above analysis to draw key insights on the practical applicability of a rewritingbased approach for query answering under warded ontologies, when using off-the-shelf Datalog-based engines.