Ronald Fagin
# Ronald Fagin

Ronald Fagin (* 1. Mai 1945 in Oklahoma City) ist ein US-amerikanischer Informatiker.

## Leben

Fagin studierte am Dartmouth College und wurde 1973 an der University of California, Berkeley, bei Robert Vaught promoviert. Danach ging er in die Forschung zu IBM, zuerst am Thomas J. Watson Research Center und ab 1975 am IBM Almaden Research Center in San José (Kalifornien). Er ist dort in der Gruppe zu Grundlagen der Informatik (Foundations of Computer Science).

## Werk

1973 bewies er in seiner Dissertation den Satz von Fagin der deskriptiven Komplexitätstheorie und endlichen Modelltheorie.

Er ist für grundlegende Resultate in der Theorie der Datenbanken bekannt, zum Beispiel seine weithin akzeptierte Definition der vierten Normalform in der Theorie relationaler Datenbanken, seine Theorie azyklischer Datenbanksysteme oder Arbeiten über ungenaue (fuzzy) Abfragen von Datenbanken (siehe zum Beispiel Top-N-Anfrage). Er ist einer der Erfinder von extendible Hashing.

Er ist auch für ein grundlegendes wahrscheinlichkeitstheoretisches Resultat zur Logik bekannt. 1976 bewies er, dass die Prädikatenlogik über endlichen Strukturen ein 0–1 Gesetz (zero one law) erfüllt, unabhängig bewiesen von Y. Glebsky und seinen Studenten D. Kogan, M. Liogonki, V. Talanov 1969 in der Sowjetunion. Dies war der erste 0-1-Satz in der Logik.

2012 erhielt Fagin den W. Wallace McDowell Award und 2004 den ACM SIGMOD Edgar F. Codd Innovation Award. Er ist IBM Fellow und Mitglied der IBM Academy of Technology und erhielt acht IBM Outstanding Innovation Awards, den IBM Outstanding Technical Achievement Award, den IBM Corporate Award und zwei IBM Preise für Patente. 1985 erhielt er den Best Paper Award der International Joint Conference on Artificial Intelligence, 2001 den Best Paper Award des ACM Symposium on Principles of Database Systems und 2010 den Best Paper Award der International Conference on Database Theory. Außerdem ist er IEEE Fellow, ACM Fellow und Mitglied der American Association for the Advancement of Science. Er ist Ehrendoktor der Universität Paris. Für 2014 wurde ihm mit Moni Naor und Amnon Lotem der Gödel-Preis von ACM und EATCS zugesprochen für ihre Arbeit Optimal Aggregation Algorithms for Middleware, die den Treshold Algorithmus und Instance Optimality einführte. Ferner wurde er 2014 in die American Academy of Arts and Sciences aufgenommen, 2020 in die National Academy of Sciences.

## Schriften

* mit J. Y. Halpern, Y. Moses, Moshe Y. Vardi: Reasoning about Knowledge, MIT Press 1995, 2003.
