scientific article; zbMATH DE number 1149474
This paper considers the evaluation of Datalog programs. Datalog has become popular in the 1980s as a declarative language for relational (and even complex-object) databases, since it allows to study issues of language expressiveness and language evaluation complexity in a uniform framework that can exploit numerous results from mathematical logic. In essence, a Datalog program is a set of Horn clauses, possibly with recursion and negation; if the latter two language elements are dropped, the result is basically the relational algebra without difference. Since the algebra is a highly efficient language, efficient evaluation algorithms for Datalog are essential (since otherwise there would be little motivation to use Datalog instead of the algebra). However, since Datalog is declarative, efficiency of a program evaluation is seldomly obvious, so researchers have studied corresponding algorithms for many years. A basic approach to evaluation a Datalog program is the so-called naive evaluation, in which input relations are assigned to predicates, rules are evaluated to produce more input, and the process is iterated until nothing changes anymore. Since rule evaluation frequently amends to join computations, it is reasonable to exploit optimization techniques for joins, suitably translated to the Datalog setting. This is exactly what the present paper does; it describes an ``efficient semi-naive evaluation algorithm in which the (old) idea of computing output relations incrementally is refined in various ways. Although technically correct, the paper does not make a significant contribution, since the only results the authors can prove for their algorithm say that it does not perform worse than previous algorithms. Moreover, the paper is written in a pretty dry style, without giving too much background, and it does not at all refer to relevant literature that has been published on the subject in recent years (and this literature is truly huge).
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4386992)
