Conjunctive queries form an important subset of relational algebra. Each conjunctive query has a unique minimum equivalent (up to isomorphism). However, the computational of the minimum equivalent is complete for co-𝒩𝒫. Johnson and Klug have proposed a subclass of conjunctive queries, the fanout-free queries, for which minimization may be performed in polynomial time. In this paper, the authors show that a strict superclass of the fanout-free queries, the restricted-fanout queries, can be minimized in polynomial time.
