Reflective relational machines (Q1271557)

In this paper, the authors extend the relational machine by allowing the dynamic generation of queries, thus modeling reflective database programming. The results concern the expressive power of the reflective relational machine with time and space restrictions on resources, and with limitations on the number of variables allowed in queries. The reflective relational machine also provides a model of parallel computation analogous to the uniform circuit model, only formulated in logic terms. The close correspondence to circuits, which does not hold for nonreflective machines, suggests that reflection allows one to express more ``intense'' parallelism than nonreflective programming. The paper is divided into five sections: Introduction, background, the model, polynomially bounded reflective machines, sublinear variable complexity. The paper begins with an informal review of some query languages and of the relational machine. This is followed by a description of the reflective relational machine model and some basic facts about it. The polynomial time/space restrictions of the machine are considered in section 4. The results on sublinear bounds on the number of variables are presented in section 5. Altogether this is a useful paper for scientists engaged in research in this field.