Generalization of ZYT-linearizability for bilinear datalog programs

Abstract

We propose a new type of linearizability, called right-linear-first (RLF) linearizability. The well-known ZYT-linearizability deals with only one bilinear rule. RLF-linearizability is a generalization of ZYT-linearizability since RLF-linearizability deals with general bilinear datalog programs consisting of multiple bilinear and linear rules. We identify sufficient conditions for RLF-linearizability. The test of the sufficient conditions is exponential in the size of the input datalog program, which is, however, usually very small compared with the size of the extensional database in deductive database applications. (C) 2003 Elsevier Inc. All rights reserved.