"IT Nobel" Awarded to IBM Researcher


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:

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.