Linearizing datalog programs with multiple bilinear rules

Abstract

In this paper, we consider linearization of nonlinear datalog programs with multiple bilinear rules and multiple linear rules. If a nonlinear program can be Linearized, if is possible to process queries on the program efficiently by using well-known cost-effective techniques for linear programs. We define a transformation, called flight-Linear-First (RLF) transformation, for linearizing such nonlinear programs. A nonlinear program is RLF-linearizable if it is logically equivalent to its RLF-transformed program. We present three sufficient conditions, called LCR-consistency, LCRN1-consistency, and LCRN2-consistency, for identifying such RLF-linearizable programs. These conditions can be tested in polynomial time. Our work presented in this paper extends the work on ZYT-linearizability in a sense that RLF-linearizability considers multiple bilinear rules with multiple linear rules.