Performance of recursive query processing methods in the presence of cycles

Abstract

An experimental performance analysis of three recursive query processing methods [the magic-sets method (MAG), the magic-counting method (MCS), and the synchronized-counting method (SCM)] in deductive databases in the presence of cycles is presented. We define a set of characteristics that affects the performance of query processing methods for cyclic data. Although there are other experimental performance analysis studies of recursive query processing methods in the literature, these studies have covered only acyclic databases. There are only some bounds for the worst case and best case analysis of recursive query processing methods on cyclic data. This paper introduces a set of graph characteristics on which similar performance studies can be based, and it is, to our knowledge, the first comparative experimental study on the performance of recursive query processing methods for cyclic data.