ON DECOMPOSITIONS OF CHAIN DATALOG PROGRAMS INTO P(LEFT(-)) LINEAR 1-RULE COMPONENTS

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