The study of the relationships between decision rule systems and decision trees is of considerable interest in computer science. In this paper, we consider classes of decision rule systems that are closed under the operation of attribute removal. For an arbitrary closed class, we study functions that characterize the dependence in the worst case of the minimum depth of deterministic and nondeterministic decision trees that solve the problem of finding all realizable rules in a decision rule system on the number of different attributes in this system. We prove that these functions are either bounded from above by a constant or grow linearly.