Ontological query rewriting: termination criteria

Abstract

Ontological queries are queries evaluated against a database and an ontology, i.e. a set of logic rules and constraints from which new knowledge can be derived from. Ontological database systems can thus be more powerful than traditional database systems. A smooth transition between the two requires their connection which comes in the form of rewriting ontological queries into equivalent ones for traditional databases, thus leading to the creation of algorithms that do that. Using the ontology is an iterative process and as such the termination of these rewrite algorithms comes into question. We focus on one such algorithm, firstly going through its basics and workings, and then exploring the cases that will lead to its termination, by applying restrictions to the form of the ontology the algorithm accepts as input. In particular, we find the size of the obtained rewriting in case of non-recursive ontology and provide proof of termination for a less restrictive case of ontology.