A conceptual model of a database, such as an Entity-Relationship (ER) model, is a specification of objects, attributes, and their relationships. A conceptual model plays important roles in developing successful database applications. Although critical, a conceptual rijodel of a legacy database may not be always available in practice, and discovering and constructing such a model from the data, and from the data only, is a challenging problem. In this paper, we develop a new approach to address object identification and model construction. Our approach has many favorable features, including its robustness in dealing with noise data and scalability to large databases and data sets. We implement this approach in a system called McKey (Model Construction with Key identification) for discovering and building ER models from instances of large legacy databases. We apply McKey to three very large legacy databases, and obtain comprehensive models within hours, which gives many magnitudes of savings of manpower.