By a relational database, the author means a finite set of relation symbols, each of a fixed arity. An interpretation for a relational database is a domain along with an interpretation of each of the relation symbols of the database by a relation of the same arity on the domain.

A finite set of function-free Horn clauses, written with the symbols of a relational database, is called a recursive query over the database. Given an interpretation, each recursive query determines a new relation. A context-free graph grammar is associated with a recursive query. It generates hypergraphs whose hyperedges are labeled with the relation symbols of the database. These hypergraphs are called the computation graphs of the query. The main result of the paper is that the semantics of the query in a given interpretation can be defined from the set of its computation graphs.

The monadic second-order theory of a context-free set of hypergraphs is known to be decidable (an earlier result of the author). Therefore, the properties of recursive queries that are expressible as monadic second-order properties of their computation graphs are decidable. A few examples of decidable properties of the sort are given.

This beautiful result may also be interesting from a practical viewpoint. The paper is written clearly, provides sufficient detail, and is well organized.