Ronald Fagin

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Ronald Fagin

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

Leben[Bearbeiten]

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[Bearbeiten]

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[2] bewies er dass die Prädikatenlogik über endlichen Strukturen ein 0–1 Gesetz (zero one law) erfüllt[3], unabhängig bewiesen von Y. Glebsky und seinen Studenten D. Kogan, M. Liogonki, V. Talanov 1969[4] 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[5]. 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 und ACM Fellow und Mitglied der American Association for the Advancement of Science. Er ist Ehrendoktor der Universität Paris. Für 2014 wurde ihm der Gödel-Preis von ACM und EATCS zugesprochen.

Schriften[Bearbeiten]

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

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. Lebens- und Karrieredaten nach American Men and Women of Science, Thomson Gale 2004
  2. Fagin Probabilities on Finite Models, Journal of Symbolic Logic, Band 41, 1976, S. 50-58.
  3. Das heißt, mit der Prädikatenlogik gebildete Sätze über eine Menge von Strukturen D gelten für fast alle oder fast keine der Strukturen, asymptotisch mit Wahrscheinlichkeit 1 oder 0.
  4. Kibernetika, Band 2, 1969, S. 31-42.
  5. Codd Award