[Dissertation] A descriptive approach to database languages and dynamic complexity

✍ Scribed by Patnaik, Sushant

• Publisher: University of Massachusetts Amherst
• Year: 1994
• Tongue: English
• Leaves: 201
• Category: Library

✦ Synopsis

In the first part of the thesis, we characterize exactly the expressiveness of a family of typed database transaction languages based on a traversal (or recursion) scheme devised by Fegaras, Sheard and Stemple (in (FSS92)), and we capture the complexity of reflection in a first order calculus framework. Reflection in a programming language refers to the ability to generate a program and execute it in the same environment. Using a first-order interpretation from PSPACE to the quantified Boolean formula value problem, we are able to derive an easy proof of the fact that reflection when added to first-order algebra captures exactly the problems in PSPACE. Further, we give a partial answer toward resolving the complexity of higher order reflection. In the second part, eschewing traditional (static) complexity classes for measuring the complexity of database query languages, we propose a complexity theoretic framework for studying dynamic complexity classes. In this thesis we define the requisite dynamic complexity classes. In particular, we introduce and investigate a natural logic for a parallel dynamic complexity class, Dynamic First-Order Logic (Dyn-FO). We show that many interesting graph problems are in Dyn-FO, including, among others, graph connectivity and the computation of minimum spanning trees. We prove that certain standard complete problems for static complexity classes, such as AGAP for P remain complete via these new reductions. On the other hand, we prove that other such problems including GAP for NL and 1GAP for L are no longer complete via bounded expansion reductions. Our results shed light on some of the interesting differences between static and dynamic complexity. We examine the dynamic complexity of maintaining approximate solutions to NP optimization problems in the descriptive framework. We introduce a new approximation class called BMAXSNP that is a subset of MAX SNP and includes interesting problems such as MAX CUT, MAX SAT and MAX 3SAT. We define reductions that honor dynamic complexity while preserving approximations. We then show the completeness, via such reductions, of a number of NP optimization problems for BMAXSNP, and we further show that this class has constant approximable solutions which can be maintained in Dyn-FO.