This paper presents a methodology for testing a logic program containing function symbols and built-in predicates for safety and effective computability. Safety is the property that the set of answers for a given query is finite. A related issue is whether the evaluation strategy can effectively compute all answers and terminate. We consider these problems under the assumption that queries are evaluated using a fair bottom-up fixpoint computation. We also model the use of function symbols, to construct complex terms such as lists, and arithmetic operators, by considerating Datalog programs with infinite base relations over which finiteness constraints and monotonicity constraints are imposed. One of the main results of this paper is a recursive algorithm, check clique, to test the safety and effective computability of predicates in arbitrarily complex cliques in the predicate connection graph. This algorithm takes certain procedures as parameters, and its applicability can be strengthened by making these procedures more sophisticated. We specify the properties required of these procedures precisely, and present a formal proof of correctness for the algorithm check clique. This work can be seen as providing a framework for testing safety and effective computability of recursive programs, in some ways analogous to the capture rules framework of Ullman. A second important contribution is a framework for analyzing programs that are produced by the Magic Sets transformation utilizing check clique to analyze recursive cliques. The transformed program unfortunately often has a clique structure that combines several cliques of the original program. Given the complexity of algorithm check clique, it is important to keep cliques as small as possible. We deal with this problem by considering cliques in an intermediate program, called the adorned program, produced by the Magic Sets transformation. The clique structure of the adorned program is similar to that of the original program, and by showing how to analyze the transformed program in terms of the cliques in the adorned program, we avoid the potentially expensive analysis of the cliques in the transformed program.