REFLECTIVE RELATIONAL MACHINES

We propose a model of database programming with reflection (dynamic ge neration of queries within the host programming language), called the reflective relational machine, and characterize the power of this mach ine in terms of known complexity classes. In particular, the polynomia l-time restriction of the reflective relational machine is shown to ex press PSPACE, and to correspond precisely to uniform circuits of polyn omial depth and exponential size. This provides an alternative, logic- based formulation of the uniform circuit model, which may be more conv enient for problems naturally formulated in logic terms, and establish es that reflection allows for more ''intense'' parallelism, which is n ot attainable otherwise (unless P = PSPACE). We also explore the power of the reflective relational machine subject to restrictions on the n umber of variables used, emphasizing the case of sublinear bounds. (C) 1998 Academic Press.