Ronald Fagin


2004 SIGMOD Edgar F. Codd Innovations Award

Ronald Fagin received the 2004 SIGMOD Edgar F. Codd Innovation Award for his influential and lasting contributions to the principles and the practice of database systems over a period spanning nearly three decades. Fagin is one of the founders of relational database theory. His first seminal contribution to this area was the introduction of the fourth normal form, based on the concept of multivalued dependencies, which capture crucial desirable aspects of database design. In particular, Fagin’s fourth normal form formalizes the intuition that in a well-designed database schema unrelated data should not be stored in the same table. This normal form is now universally accepted and is included in all standard database books, from undergraduate textbooks to advanced research monographs. Fagin and his collaborators introduced the fundamental concept of an acyclic database schema. After this, Fagin carried out a comparative study of several different notions of acyclicity in databases. This work had significant impact on our understanding of the complexity of query processing and data integration. Fagin’s contributions to relational databases also include the co-invention of extendible hashing, a fast, flexible, and widely implemented access technique that adapts gracefully as the database undergoes dynamic changes.

In recent years, Fagin has made pioneering contributions to the area of accessing and retrieving fuzzy data from multimedia databases, such as “graded” data about color and shape. Fagin has studied the semantics of combining traditional data with fuzzy data; moreover, he has investigated important algorithmic issues, such as the problem of efficiently aggregating fuzzy information. Some of Fagin’s algorithms have become part of the Garlic information system developed at the IBM Almaden Research Center. Fagin also co-discovered a formula that makes it possible to weight the importance of the various attributes in combining fuzzy information. Although this work was originally carried out with multimedia systems in mind, it turned out to have applications in other fields, including multicriterion decision-making in economics.

Biography Ronald Fagin is manager of the Foundations of Computer Science group at the IBM Almaden Research Center in San Jose, California. He received his B.A. in mathematics from Dartmouth College and his Ph.D. in mathematics from the University of California at Berkeley. Much of his research has focused on applications of logic to computer science, including database theory, finite model theory, logic and complexity, and knowledge in multi-agent systems. He has published over 100 papers, and has co-authored a book on “Reasoning about Knowledge.” He has received six IBM Outstanding Innovation Awards, and an IBM key patent award. He has won the Best Paper Award at the International Joint Conference on Artificial Intelligence and the ACM Symposium on Principles of Database Systems. He was named a Fellow of the Institute of Electrical and Electronic Engineers, a Fellow of the Association for Computing Machinery, and a “Highly Cited Researcher” by ISI (the Institute for Scientific Information). He was named Docteur Honoris Causa by the University of Paris.