Author: Evgeny Sherkhonov

Supervisors: Prof. Enrico Franconi, Prof. Steffen Hölldobler

Abstract: Definability and interpolation are important notions in logic which appear in many fundamental and application problems in mathematics and computer sci- ence. These notions are underpinnings of the rewriting technique for query answering under generic constraints developed in [Borgida et al., 2010]. The underlying idea of this technique is that it allows to rewrite certain queries in terms of the database vocabulary. Thus it leads to a possibility of exploiting standard database technologies to answer such queries very efficiently. However, this technique is only applicable to the restricted class of queries, namely definable queries. As not all queries are definable, this gives rise to a new fundamental question: is it possible to amend the current knowledge base such that a given formula becomes definable from a particular set of predicates under the new constraints? In this thesis we tackle this problem by reducing it to an abductive problem. By this reason we call the problem as definability abductive problem. As the problem seems to be very immense, we concentrate on two particular cases of definability abductive problem: data exchange setting and the description logic ALC. For the first issue, the definability abductive problem is applied to a data exchange setting to get definability of the target schema from the source schema. For the second issue, we attempt to devise a solution generating algorithm based on the tableau calculus for ALC.