Learning novel concepts from relational databases is an important problem with applications in several disciplines, such as data management, natural language processing, and bioinformatics. For a learning algorithm to be effective, the input data should be clean and in some desired representation. However, real-world data is usually heterogeneous – the same data may be represented under different representations. The current approach to effectively use learning algorithms is to find the desired representations for these algorithms, transform the data to these representations, and clean the data. These tasks are hard and time-consuming and are major obstacles for unlocking the value of data. This thesis demonstrates that it is possible to develop robust learning algorithms that learn in the presence of representational variations. We develop two systems called Castor and CastorX, which exploit data dependencies to be robust against different types of representational variations. Further, we propose several techniques that allow these systems to learn efficiently over large databases. The proposed systems learn over the original data, removing the need for transforming the data before applying learning algorithms. Our results show that Castor and CastorX learn accurately and efficiently over real-world databases. This work paves the way for new approaches that replace pre-processing tasks such as data wrangling with robust learning algorithms.