Linearizing Datalog Programs with Multiple Bilinear Rules

Ji-Hoon KANG  Ki-Hyung HONG  Kyu-Young WHANG  Jung-Wan CHO 

Publication
IEICE TRANSACTIONS on Information and Systems  Vol.E83-D  No.4  pp.824-834
Publication Date: 2000/04/20
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Databases
Keyword: 
datalog programs,  bilinear rules,  linearization, 

Full Text: PDF(737.3KB)

Summary: 
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, it is possible to process queries on the program efficiently by using well-known cost-effective techniques for linear programs. We define a transformation, called Right-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.