Rada Chirkova and Michael R. Genesereth: "Linearly Bounded Reformulations of Unary Databases", in Proceedings of the Symposium on Abstraction, Reformulation and Approximation (SARA-2000), July 2000
Abstract
Database reformulation is the process of rewriting the data and rules of a deductive database in a functionally equivalent manner. We focus on the problem of automatically reformulating a database in a way that reduces the processing time of a query workload under a strong storage limit.
In this paper we consider one class of deductive databases - those where all stored relations are unary. For this class of unary databases, we show that the database reformulation problem is decidable if all rules can be expressed in nonrecursive datalog with negation. Moreover, we show that for such databases there always exists an optimal reformulation, that is, a reformulation that minimizes the processing time of the query workload among all reformulations that satisfy the storage limit. We also consider how this solution for unary databases might be extended to the general case, that is, to database reformulation for databases of arbitrary arity.