Abstract

The goal of this thesis is not only to introduce and present new chase-based algorithms, but also to investigate the differences between the main existing chase procedures. In order to achieve this, first we will investigate and do a clear delimitation between the existing chase algorithms based on their termination criteria. This will give a better picture of which chase algorithm can be used for different dependency classes. Next, we will investigate the data exchange, data repair and data correspondence problems and show how the chase algorithm can be used to characterize different types of solutions. For the later two problems, we will also investigate the data complexity of solution-existence and solution-check problems. Further, we will introduce a new chase based algorithm which computes representative solutions under constructible models, a new closed world semantics. This new semantics is, in our view, appropriate to be used as a closed world semantics in data exchange. We will also show that the conditional table computed by this chase algorithm can help to get both possible and certain answers for general queries. And finally, we will investigate strong representation systems and strong data exchange representation system. We will prove, by introducing a new chase based algorithm, that mappings specified by source-to-target second order dependencies and target richly acyclic TGD’s are strong data exchange representation systems for the class of first order queries.