In this chapter, we consider classes of decision rule systems that are closed under certain operations. First, we study classes closed under the operation of attribute removal and analyze functions characterizing the dependence in the worst case of the minimum depth of deterministic and nondeterministic decision trees solving the problem of finding all realizable rules in a decision rule system on the number of different attributes in this system. Second, we extend our analysis to classes closed under attribute and rule removal by studying the behavior of the minimum decision tree depth in the worst case for the problem of finding at least one realizable rule. Third, we study classes closed under attribute and rule removal in the context of finding all right-hand sides of realizable rules. We prove that in all three cases, the corresponding functions characterizing the minimum depth of decision trees in the worst case are either bounded from above by a constant or grow linearly.