Paper: The power of reflective relational machines (at LICS 1994)
Authors: Serge Abiteboul Christos Papadimitrou Victor VianuAbstract
A model of database programming with reflection, called reflective relational machine, is introduced and studied. The reflection consists here of dynamic generation of queries in a host programming language. The main results characterize the power of the machine in terms of known complexity classes. In particular, the polynomial-time restriction of the machine is shown to express PSPACE, and to correspond precisely to uniform circuits of polynomial depth and exponential size. This provides an alternative, logic-based formulation of the uniform circuit model, more convenient for problems naturally formulated in logic terms. Since time in the polynomially-bounded machine coincides with time in the uniform circuit model, this also shows that reflection allows for more “intense” parallelism, which is not attainable otherwise (unless P=PSPACE). Other results concern the power of the reflective relational machine subject to restrictions on the number of variables used
BibTeX
@InProceedings{AbiteboulPapadimitr-Thepowerofreflectiv, author = {Serge Abiteboul and Christos Papadimitrou and Victor Vianu}, title = {The power of reflective relational machines}, booktitle = {Proceedings of the Ninth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1994}, year = 1994, editor = {Samson Abramsky}, month = {July}, pages = {230--240}, location = {Paris, France}, publisher = {IEEE Computer Society Press} }