Linearization of bilinear datalog programs

Abstract

If a nonlinear program can be linearized, it is possible to process queries on the program efficiently by using well-known cost-effective techniques for linear programs. There is an already known linearization problem, called {\em ZYT-linearizability}, which is concerned with the programs with only one bilinear rule (a nonlinear rule with two recursive subgoals in its body). The general linearizability is undecidable if the complexity class $\cal P$ is not equal to the complexity class $\cal NC$. Even though ZYT-linearizability is very simple compared to the general linearization problem, it is $\cal NP$-hard. In this dissertation, we consider linearization of bilinear programs that are nonlinear programs with multiple bilinear rules and multiple linear rules. That is, we generalize ZYT-linearizability by relaxing the restriction on the number of recursive rules. We propose a transformation, called {\em Right-Linear-First (RLF for short) transformation}, for linearizing such bilinear programs. We define a bilinear program to be {\em RLF-linearizable} if it is logically equivalent to its RLF-transformed program. We attempt two approaches in order to identify the conditions for RLF-linearizability. The first one does not impose any restriction on the EDB subgoals. The other one restricts the number of EDB subgoals in the body of recursive rules. The former is a very general approach. To overcome the complexity of the problem induced from multiple recursive rules, we solve the problem by characterizing it as two small but typical subproblems. The first one does not involve linear rules. So, all the recursive rules are bilinear. The second one involves only one bilinear rule and only one linear rule. Using the results for the typical subproblems, we derive a sufficient condition for RLF-linearizability that can be tested in exponential time. The form of the programs for the latter approach is a special case of that for the former. The restriction on the number of E...