Advances in relational database technology have made available relational database systems that support state of the art query languages and query processing algorithms. However, because database systems do not include adequate tools for database design, their use and accessibility is hampered by major difficulties that users experience in the process of designing a database. In this dissertation, we present methods and algorithms for automating the design of relational databases and describe a prototype design tool. Unlike researchers who have advocated the use of higher level data models, we focus on the pure relational model, because of its sound theoretical foundation and investigate issues in automatic design of relational databases. We present a new graph representation for functional dependencies, which simplifies and enhances several design algorithms, such as algorithms for computing closures, keys, and projecting dependency sets. We define the basis $B(F)$, a compact representation of $F^{+}$, which is used to find multiple BCNF decompositions. The basis also provides a way to find the generator of the $F$-closed sets, an essential component in the computation of Armstrong relations, which are relations representing a set of functional dependencies. We study the inference of multivalued dependencies from an acyclic relational scheme. These multivalued dependencies capture the relationship between the relations in the database. For the inference of functional dependencies within a relation, we optimize previously proposed algorithms. Queries can be used to rate candidate schemes according to how queries perform against them. We present an algorithm for finding the exact query formulation for a particular design, given a scheme independent definition of the query. Multiple ways of accessing the data or no way of accessing the data consistently can be a result indicating that the current design is not valid. Until now, there has been limited experience with feasibility and performance aspects of automatic relational design. We describe a prototype design tool and present a detailed performance study of the dependency inference algorithms implemented in this prototype.