Dirk Van Gucht
Computer Science Department
Indiana University

Resource Bounded Computing in Databases

Database systems offer shared access to large, possibly distributed data sources. To offer efficient and fair access in this context, such systems restrict their support to programs written in a resource bounded programming language. The best known example is SQL whose programs run in polynomial time.

I will give an overview of resource bounded database programming languages. In particular, I will discuss the relational algebra (RA) and its extension with a least fixed point operator (LFRA). RA is in LOGSPACE and LFRA is in PTIME.

I will follow up this discussion by surveying work of Bellantoni, Cook, and Leivant on resource bounding computing in programming languages. In this work, programming is done using a syntactically restricted form of the primitive recursion schema.

I will then present a resource bounded language for tree-structured databases objects, such as XML databases. This language is shown to express exactly the polynomial time computations over trees. The language controls complexity by carefully restricting the replication of values and limiting the nesting of recursion.

We conclude by discussing other possibilities in the design of resource bounded programming languages which have the potential to offer the programmer more syntactic flexibility.

Host: Bob Harper
Appointments: Margaret Weigand

Principles of Programming Seminars