Organizations have been storing huge amounts of data for years, but over time, the knowledge about these legacy databases may be lost or corrupted.; In this thesis, we study the problem of discovering (approximate) keys and foreign keys satisfied in a relational database, of which we assume no previous knowledge.; The main ideas underlying our method for tackling this problem are not new; however, we propose two novel optimizations. First, we extract only key-based unary inclusion dependencies (UINDs) instead of all UINDs. Second, we add a pruning pass to the foreign key discovery; performed on a small data sample, it reduces the number of candidates tested against the database.; We validate our contributions on both real-life and synthetic data. We investigate the influence of input parameters on the performance of the pruning pass, and provide guidance on how to best set these parameters. |