IBM Research-Almaden

“IT Nobel” Awarded to IBM Researcher

Share this post:


The IEEE Computer Society has awarded its 2012 W. Wallace McDowell Award to Ronald Fagin, Manager, Foundations of Computer Science at IBM Research – Almaden, “for fundamental and lasting contributions to the theory of databases.”
Popularly referred to as the “IT Nobel,” the W. Wallace McDowell Award is awarded by the IEEE Computer Society for outstanding recent theoretical, design, educational, practical, or other similar innovative contributions that fall within the scope of Computer Society interest. One of computing’s most prestigious individual honors, the W. Wallace McDowell Award has a list of past winners that reads like a who’s who of industry giants. They include FORTRAN creator John W. Backus (1967); supercomputer pioneers Seymour Cray (1968), Gene Amdahl (1976), and Ken Kennedy (1995); the architect of IBM’s mainframe computer Frederick Brooks (1970); Intel Corp. co-founder Gordon Moore (1978); Donald Knuth, the father of algorithm analysis (1980); microprocessor inventor Federico Faggin (1994); World Wide Web inventor Tim Berners-Lee (1996); and Lotus Notes creator and Microsoft Chief Software Architect Ray Ozzie (2000).
Previously, Ron won the 2011 IEEE Technical Achievement Award for pioneering contributions to the theory of rank and score aggregation.
Ron’s first major contribution to relational database theory was the introduction of Fourth Normal Form, which captures crucial desirable aspects of database design. In particular, Ron’s Fourth Normal Form formalizes the intuition that in a well-designed database, 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.
Ron (with Nick Pippenger, Jurg Nievergelt, and Ray Strong) invented extendible hashing, a database access technique in which the user is guaranteed no more than two page faults to locate the data associated with a given unique identifier, or key. Unlike conventional hashing, extendible hashing has a dynamic structure that grows and shrinks gracefully as the database grows and shrinks. Because it combines the speed of hashing with adaptable dynamic behavior, and because it is easy to understand and to program, extendible hashing is now widely studied and widely implemented.
Ron has devised several algorithms (including “Fagin’s Algorithm“) for combining information from multiple sources. This work had a significant influence  on the design of the query processing component of the IBM InfoSphere Federatoin Server, and on the design and implementation of the parametric search for IBM WebSphere Commerce.
With Phokion Kolaitis, Lucian Popa, and Wang-Chiew Tan, Ron laid the foundations for the use of schema mappings, which describe how to convert data from one format to another (data in the second format is called a “solution”). The main problem is that there may be many solutions, and it is not clear which solutions are “good.” They  defined a particular class of solutions, called “universal,” and showed that these are the good solutions.  This paper is considered the fundamental paper in the area.  Their schema mapping work has now been implemented in multiple IBM products, including DB2 Control Center, Rational Data Architect, and Content Manager.
Ron shares a retrospective on his database journey at IBM:

I spent the first two years of my IBM career at Yorktown, where I worked on miss ratios.  I thought I did some pretty good research that I was proud of  on miss ratios, but I found it quite discouraging that this work was almost never cited, and I got very few requests for reprints (the way it worked in those days was that someone who wanted a copy of your paper sent you a postcard, and you mailed them a copy). For family reasons, I wanted to transfer  to IBM Research in San Jose.  The good news about my miss ratio work was that I used it as a successful “job talk” to induce the folks in IBM San Jose Research to transfer me in (I was actually “traded” for someone at San Jose who wanted to transfer to Yorktown).  Once I transferred to San Jose,  I decided to try to work on something different that the world would actually care about.  I looked around the lab to see who seemed interesting, and I pretty quickly decided “Ted Codd looks really interesting.”  Ted was the father of relational databases (in fact, he eventually won the Turing Award for that).  So I started working with Ted on relational databases.  To my delight, all of a sudden lots of people began citing this new research of mine, and I got lots of requests for preprints and reprints. Therefore, I decided to make databases my research focus, and databases have remained one of my main areas of research ever since. 


Ronald Fagin is a member of the IBM Academy of Technology. He has won an IBM Corporate Award, eight IBM Outstanding Innovation Awards, an IBM Outstanding Technical Achievement Award, and two IBM key patent awards. He has published over 100 papers, and has co-authored a book on “Reasoning about Knowledge.” He has served on more than 30 conference program committees, including serving as Program Committee Chair of four different conferences.

He received his B.A. in mathematics from Dartmouth College, and his Ph.D. in mathematics from the University of California at Berkeley.
Accomplishments include:
  • IEEE 2011 Technical Achievement Award for “pioneering contributions to the theory of rank and score aggregation”
  • Winner of the 2004 ACM SIGMOD Edgar F. Codd Innovations Award, a lifetime achievement award in databases, for “fundamental contributions to database theory”
  • IEEE Fellow for “contributions to finite-model theory and to relational database theory”
  • A
    CM Fellow for “creating the field of finite model theory and for fundamental research in relational database theory and in reasoning about knowledge”
  • AAAS Fellow for “fundamental contributions to computational complexity theory, database theory, and the theory of multi-agent systems”
  • Named Docteur Honoris Causa by the University of Paris
  • Named “Highly Cited Researcher” by the Institute for Scientific Information
  • Recipient of Best Paper awards at the 1985 International Joint Conference on Artificial Intelligence, the 2001 ACM Symposium on Principles of Database Systems, and the 2010 International Conference on Database Theory


About IEEE: With nearly 85,000 members, the IEEE Computer Society is the world’s leading organization of computing professionals. Founded in 1946, it is the largest of IEEE’s 38 societies. The Computer Society is dedicated to advancing the theory and application of computing and information technology. 
More IBM Research-Almaden stories

We’ve moved! The IBM Research blog has a new home

In an effort better integrate the IBM Research blog with the IBM Research web experience, we have migrated to a new landing page:

Continue reading

Pushing the boundaries of human-AI interaction at IUI 2021

At the 2021 virtual edition of the ACM International Conference on Intelligent User Interfaces (IUI), researchers at IBM will present five full papers, two workshop papers, and two demos.

Continue reading

From HPC Consortium’s success to National Strategic Computing Reserve

Founded in March 2020 just as the pandemic’s wave was starting to wash over the world, the Consortium has brought together 43 members with supercomputing resources. Private and public enterprises, academia, government and technology companies, many of whom are typically rivals. “It is simply unprecedented,” said Dario Gil, Senior Vice President and Director of IBM Research, one of the founding organizations. “The outcomes we’ve achieved, the lessons we’ve learned, and the next steps we have to pursue are all the result of the collective efforts of these Consortium’s community.” The next step? Creating the National Strategic Computing Reserve to help the world be better prepared for future global emergencies.

Continue reading