On the computation of approximations of database queries
Flavio Antonio Ferrarotti, José María Turull-Torres · 2004
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 di#erent logics to express dynamic queries: one for queries and a possibly di#erent 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 FO^k theories. Finally, we summarize a few open problems related to our work.