On the Decomposition of Datalog Program Mappings

Document Type

Article

Publication Date

10-31-1990

Abstract

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.

DOI

10.1016/0304-3975(90)90015-A

Find in your library

Off-Campus WSU Users


Share

COinS