Please login using the form on menu list.|
It is required to login for Full-Text PDF.
Linearizing Datalog Programs with Multiple Bilinear Rules
IEICE TRANSACTIONS on Information and Systems Vol.E83-D No.4 pp.824-834
Publication Date: 2000/04/20
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Full Text: PDF(737.3KB)
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.