Parallel Complexity of Logical Query Programs

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 logarithmic time. As a result, the "linear" and "piecewise linear" classes of logic programs are in NC. 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 NC. Finally, we describe an approach for demonstrating that certain logical query programs are log space complete for P, and apply it to both elementary single rule programs and nonelementary programs.

Authors

• Jeffrey D. Ullman
• Allen Van Gelder

Keywords

• Polynomials
• Logic
• Phase change random access memory
• GSM
• Concurrent computing
• Algebra
• Piecewise linear techniques
• Very large scale integration
• Relational databases
• Contracts
• Complex Program
• Nonlinear Programming
• Program Logic
• Single Rule
• Partial Model
• Basal Rate
• End Stage
• Set Of Rules
• Starting State
• Constant Vector
• Beginning Of Stage
• Application Of Theorem
• Basic Program
• Complete Tree
• Turing Machine
• Dependency Graph
• Iterative Stages
• Input String
• Transitive Closure
• Context-free Grammar
• Linear Equivalent
• Input Symbols
• Current Graph
• Cross-product