Ronald Fagin

Established the field of finite-model theory, connecting mathematical logic, complexity theory, and database theory, and elaborated Fagin's theorem and Fagin's zero-one law. Founding figure of relational database theory underlying the success of relational databases. Introduced fundamental concepts for database design, especially: fourth normal form, multivalued dependencies, and acyclic schemas, and invented an extendible-hashing algorithm used to find data quickly. Invented algorithms for querying and aggregating imprecise data, key capabilities for information retrieval systems. Created the foundations for data integration and transformation with his work on data exchange and tuple-generating dependencies, considered the most significant development in database theory over the last decade. Invented a highly scalable, widely used method for differential backup of files, and an algorithm for assigning encryption keys, techniques crucial to IBM products. Developed a logical foundation to reasoning about group knowledge and coauthored Reasoning about Knowledge (2d ed. 2003), now considered a classic on knowledge in multi-agent systems.