Logical Query Program (LQP)

Input

An extended logic program $P$, and a ground clause $C$ of the form $p(\overline{x}) \coloneq q_1(\overline{y}_1), \ldots, q_k(\overline{y}_k)$.

Problem

Is $C$ a theorem of $P$?

Definitions

A ground clause is one in which all arguments (e.g. $\overline{x}$ and $\overline{y}_i$ above) are constants. An extended logic program is a basic logic program plus an extensional data base instance. A basic logic program is a finite set of rules. A rule is a disjunction of literals having exactly one positive literal, called the head. The negative literals in the clause are called subgoals. The set of predicate symbols that appear only in subgoals is called the Extensional Database, or EDB. An EDB fact is an EDB predicate with constants as arguments. An EDB instance is a finite set of EDB facts. $C$ is a theorem of $P$ if the head of $C$ is derivable from its subgoals in $P$.

Status

$\P$-complete (Ullman and Van Gelder [1]).

Remarks

The reduction to show hardness is from PATH. Remains $\P$-complete even for very restricted programs. In $\NC$ for programs with the “polynomial fringe property.” See [1] for details. Afrati and Papadimitriou classify simple chain programs according to their parallel complexities [2]. They show a certain subclass of simple chain programs are in $\NC$ and that all other simple chain programs are $\P$-complete.

Afrati describes additional classes of logic programs that can be solved in $\NC$, and also provides sufficient conditions for single rule programs to be $\P$-complete [3]. Refer to [3] for definitions, further details, and numerous open problems.