zbMATH — the first resource for mathematics

Linearly bounded reformulations of unary databases. (English) Zbl 0989.68505
Choueiry, Berthe Y. (ed.) et al., Abstraction, reformulation, and approximation. 4th international symposium, SARA 2000, Horseshoe Bay, TX, USA, July 26-29, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1864, 144-163 (2000).
Summary: 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 query processing time while satisfying strong storage space constraints.
In this paper we consider one class of deductive databases – those where all stored relations are unary. For this class of so-called 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. We also suggest how this solution for unary databases might be extended to the general case, i.e., to that of reformulating databases with stored relations of arbitrary arity.
For the entire collection see [Zbl 0941.00037].
68P15 Database theory