In this chapter, we study structures that contain predicates and do not contain functions. Local approach means that in computation trees solving a problem we can use only predicates from the problem description. In the first eight sections of this chapter, we consider structures that contain only 1-ary predicates. For these structures, called 1-predicate structures, we study problems with only one input variable and computation trees in which the predicates depend on this variable. The consideration is based on results obtained for decision trees over information systems and for closed classes of decision tables. In the last section of this chapter, we consider predicate structures that can contain predicates of arbitrary arity. For such structures, we study problems with several input variables and computation trees for these problems.