On the Computation of Approximations of Database Queries

Abstract

Reflective Relational Machines were introduced by S. Abiteboul, C. Papadimitriou and V. Vianu in 1994, as variations of Turing machines which are suitable for the computation of queries to relational databases. The machines are equipped with a relational store which can be accessed by means of dynamically built first order logic queries. We initiate a study on approximations of computable queries, defining, for every natural k, the k-approximation of an arbitrary computable query q. This, in turn, motivates us to define a new variation of Reflective Relational Machines by considering two different logics to express dynamic queries: one for queries and a possibly different one for updates to the relational store. We prove several results relating k-approximations of queries with the new machines, and also with classes of queries defined in terms of preservation of equality of F O k theories. Finally, we summarize a few open problems related to our work.