On the Decomposition of Datalog Program Mappings

Document Type


Publication Date



In an earlier paper one of the authors initiated an investigation into the composition of datalog program mappings in order to analyze serially executed datalog queries. In this paper, the reverse process of composition, namely decomposition, and related topics are examined. A number of results are presented and shown to be useful for the optimization of datalog queries. In particular, a canonical decomposition into (usually) smaller programs is given, as well as the decomposition of strongly linear programs and bounded programs into single-rule programs. The class of prime or nondecomposable programs is then introduced and scrutinized. Major results include the primality of a class of single-rule programs called symmetric, and the existence of arbitrarily large primes. Finally established are the decomposition of bounded programs into single-rule primes, and a condition for the uniqueness of decomposition into primes.



Find in your library

Off-Campus WSU Users