On the implementation of a simple class of logic queries for databases

Reviewer: Jaroslav Pokorny

In this paper, the problem of efficient implementation of queries about relational databases is studied. These queries are expressed in function free first-order logic as a collection of Horn clauses (in the rule-goal form). The authors focus on so-called canonical, strongly linear queries (CSL queries) where associated logical programs contain exactly one recursive rule (with one recursive predicate symbol, say R). The predicate symbol in the goal and in the head of all the rules is R. The binding graph associated with a CSL query permits you to specify the binding-passing property of the query, which guarantees that the initial bindings of the query can be propagated down, via database relations, to any depth of recursion. In subsequent sections, the special class of CSL queries, 1-bound CSL queries, and their implementation are discussed. The authors provide a description of four methods in a unifying framework: the counting method; the eager method; the magic set method; and a new and efficient method, called the magic counting method. This method works better than the others in most cases. The paper is well organized but is not easy to read. It is written at a high level, presupposing a good familiarity with studied questions. Nevertheless, the paper is too short with respect to the complexity of the formalism used and the covered issues (e.g., all results are presented without proofs).