Counting methods for cyclic relations

Abstract

In this paper we consider selections of the form “column = constant” on relations defined by linear recursive, two rule datalog programs. 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 semi-linear sets, works by using efficient methods to construct the appropriate semi-linear sets from the database and query constant.