Databases often store and manage sensitive data. Regulating the access to databases is, therefore, essential. To this end, database security researchers have developed both access control and inference control mechanisms. The former limit direct access to sensitive data, whereas the latter prevent leaks caused by combining query results with external information such as prior knowledge or data dependencies. Ideally, all these mechanisms should come with security proofs clearly stating what attacks they are designed to thwart, as with security mechanisms in other domains. Unfortunately, this is far from reality. Existing protection mechanisms are implemented in an ad hoc fashion, with neither precise security guarantees nor the means to verify them. This has immediate consequences as existing mechanisms are inadequate to secure modern databases and are susceptible to attacks. In this thesis, we develop theoretical foundations for access and inference control in databases. We leverage these foundations to design provably secure and practical protection mechanisms for modern database systems.