Parallel complexity of logical query programs (Q1104095)

We consider the parallel time complexity of logic programs without function symbols, called logical query programs, or Datalog programs. We give a PRAM algorithm for computing the minimum model of a logical query program, and show that for programs with the ``polynomial fringe property'', this algorithm runs in time that is logarithmic in the input size, assuming that concurrent writes are allowed if they are consistent. As a result, the ``linear'' and ``piecewise linear'' classes of logic programs are in \({\mathcal N}{\mathcal C}\). Then we examine several nonlinear classes in which the program has a single recursive rule that is an ``elementary chain''. We show that certain nonlinear programs are related to GSM mappings of a balanced parentheses language, and that this relationship implies the ``polynomial fringe property''; hence such programs are in \({\mathcal N}{\mathcal C}\). Finally, we describe an approach for demonstrating that certain logical query programs are log space complete for \({\mathcal P}\), and apply it to both elementary single rule programs and nonelementary programs.