Instance based learning and clustering are popular methods in propositional machine learning. Both methods use a notion of similarity between objects. This dissertation investigates these methods in a relational setting. First, a number of new metrics are proposed. Next, these metrics are used to upgrade clustering and instance based learning to first order logic.