If a knowledge-based system contains rules expressed in terms of predicates then some predicates may be stored as relations. Once the rules to be represented in a knowledge-based system have been identified, the performance of that system may be tuned by deciding which predicates to actually store. We discuss the problem of tuning a knowledge-based system for optimal performance. Two solutions for unconstrained knowledge-based systems are given. When realistic constraints are present it is shown that this problem is NP-complete. A sub-optimal algorithm is given which operates in polynomial time when the knowledge-based system is not heavily constrained.