A counting algorithm for a cyclic binary query

摘要

In this paper we consider selection queries on a generalization of the Datalog program known as the “same generation.” This program has received a great deal of attention in the literature because selection queries on this simple, binary program have no monadic equivalent. As such, the program encapsulates many of the difficulties that arise in more general recursive query processing. In general, counting methods perform well on such queries. However, counting methods fail in the presence of cycles in the database. We present an algorithm in the spirit of counting methods that correctly deals with cyclic data and has the same asymptotic running time as counting methods. The algorithm, which is based on reducing a query on a database to a question about intersections of semilinear sets, works by using efficient methods to construct the appropriate semilinear sets from the database and query constant.