Logic in Computer Science (LICS 1994)

Paper: The power of reflective relational machines (at LICS 1994)

Authors: Serge Abiteboul Christos Papadimitrou Victor Vianu

Abstract

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}
  }