###
On decompositions of chain datalog programs into P (left)-linear 1-rule components

Guozhu Dong,
The University of Melbourne

Seymour Ginsburg

University of Southern California,

#### Status

Journal of Logic Programming, 23(3):203--236, June 1995.

#### Abstract

As an approach to optimization, this paper examines the decomposition
of chain Datalog programs into P (left-)linear sequences of 1-rule programs.
The notion of P (left-)linear, introduced here,
encompasses numerous special (left-)linear forms and includes the traditional
(left) linear as a subcase. The
decompositions are first characterized in
terms of properties of associated context-free languages. More
specific characterizations are provided for
three types of P (left-)linear decompositions
with 1-rule components, and the corresponding decision problems considered.
Finally, arbitrarily large, inherently nondecomposable,
P-linear size-prime programs are exhibited.