On Decompositions of Chain Datalog Programs into P (Left-)Linear 1-Rule Components
Document Type
Article
Publication Date
6-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.
Repository Citation
Dong, G.,
& Ginsburg, S.
(1995). On Decompositions of Chain Datalog Programs into P (Left-)Linear 1-Rule Components. Journal of Logic Programming, 23 (3), 203-236.
https://corescholar.libraries.wright.edu/knoesis/370
DOI
10.1016/0743-1066(94)00027-4
