Rada Chirkova and Michael R. Genesereth: "Linearly Bounded Reformulations of Conjunctive Databases", in Proceedings of the Sixth International Conference on Deductive and Object-Oriented Databases (DOOD-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 databases in a way that reduces the processing time of a query workload while satisfying a strong storage limit.
In previous work we have investigated database reformulation for the case of unary databases. In this paper we extend this work to databases of arbitrary arity, while concentrating on conjunctive rules. The main result of the paper is that the database reformulation problem is decidable for conjunctive databases.