Ronald Fagin
Encyclopedia
Ronald Fagin is the Manager of the Foundations of Computer Science group at the IBM Almaden Research Center. He is best known for his pioneering work in database theory
, finite model theory
, and reasoning about knowledge. He has received numerous professional awards for his work (see list on right).
, where he attended Northwest Classen High School
. Following that, he completed his undergraduate degree at Dartmouth College
. Fagin received his Ph.D. in Mathematics from the University of California, Berkeley
in 1973, where he worked under the supervision of Robert Vaught. He joined the IBM Research
Division in 1973, spending two years at the Thomas J. Watson Research Center
, and then transferred in 1975 to what is now the IBM Almaden Research Center in San Jose, California
.
, which he proved in his PhD thesis states that existential second-order logic
coincides with the complexity class NP
in the sense that a decision problem can be expressed in existential second-order logic if and only if it can be solved by a nondeterministic Turing machine
in polynomial time. This work was seminal to the area of finite model theory
. Another famous result that he proved is that first-order logic has a zero-one law
, a tool for proving inexpressibility results for database query languages. This result was proven independently by Glebskiĭ et al. slightly earlier in Russia.
He is also known for his work on higher Normal Forms
in Database Theory
, particularly 4NF
.
He has served as program committee chair for ACM Symposium on Principles of Database Systems 1984, Theoretical Aspects of Reasoning about Knowledge 1994, ACM Symposium on Theory of Computing 2005, and the International Conference on Database Theory 2009.
Database theory
Database theory encapsulates a broad range of topics related to the study and research of the theoretical realm of databases and database management systems....
, finite model theory
Finite model theory
Finite Model Theory is a subarea of model theory . MT is the branch of mathematical logic which deals with the relation between a formal language and its interpretations . FMT is a restriction of MT to interpretations of finite structures, i.e...
, and reasoning about knowledge. He has received numerous professional awards for his work (see list on right).
Early life
Ron Fagin was born on May 1, 1945 and grew up in Oklahoma CityOklahoma city
Oklahoma City is the capital and largest city of the U.S. state of Oklahoma.Oklahoma City may also refer to:*Oklahoma City metropolitan area*Downtown Oklahoma City*Uptown Oklahoma City*Oklahoma City bombing*Oklahoma City National Memorial...
, where he attended Northwest Classen High School
Northwest Classen High School
Northwest Classen High School is a public high school serving students in grades 9-12 in Oklahoma City, Oklahoma.- History :Northwest Classen High School was built in 1955 to accommodate the growing population in the northwest corridor of Oklahoma City. Along with Classen School of Advanced...
. Following that, he completed his undergraduate degree at Dartmouth College
Dartmouth College
Dartmouth College is a private, Ivy League university in Hanover, New Hampshire, United States. The institution comprises a liberal arts college, Dartmouth Medical School, Thayer School of Engineering, and the Tuck School of Business, as well as 19 graduate programs in the arts and sciences...
. Fagin received his Ph.D. in Mathematics from the University of California, Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
in 1973, where he worked under the supervision of Robert Vaught. He joined the IBM Research
IBM Research
IBM Research, a division of IBM, is a research and advanced development organization and currently consists of eight locations throughout the world and hundreds of projects....
Division in 1973, spending two years at the Thomas J. Watson Research Center
Thomas J. Watson Research Center
The Thomas J. Watson Research Center is the headquarters for the IBM Research Division.The center is on three sites, with the main laboratory in Yorktown Heights, New York, 38 miles north of New York City, a building in Hawthorne, New York, and offices in Cambridge, Massachusetts.- Overview :The...
, and then transferred in 1975 to what is now the IBM Almaden Research Center in San Jose, California
San Jose, California
San Jose is the third-largest city in California, the tenth-largest in the U.S., and the county seat of Santa Clara County which is located at the southern end of San Francisco Bay...
.
Academic contributions
Fagin's theoremFagin's theorem
Fagin's theorem is a result in descriptive complexity theory that states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP...
, which he proved in his PhD thesis states that existential second-order logic
Second-order logic
In logic and mathematics second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory....
coincides with the complexity class NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
in the sense that a decision problem can be expressed in existential second-order logic if and only if it can be solved by a nondeterministic Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
in polynomial time. This work was seminal to the area of finite model theory
Finite model theory
Finite Model Theory is a subarea of model theory . MT is the branch of mathematical logic which deals with the relation between a formal language and its interpretations . FMT is a restriction of MT to interpretations of finite structures, i.e...
. Another famous result that he proved is that first-order logic has a zero-one law
Kolmogorov's zero-one law
In probability theory, Kolmogorov's zero-one law, named in honor of Andrey Nikolaevich Kolmogorov, specifies that a certain type of event, called a tail event, will either almost surely happen or almost surely not happen; that is, the probability of such an event occurring is zero or one.Tail...
, a tool for proving inexpressibility results for database query languages. This result was proven independently by Glebskiĭ et al. slightly earlier in Russia.
He is also known for his work on higher Normal Forms
Database normalization
In the design of a relational database management system , the process of organizing data to minimize redundancy is called normalization. The goal of database normalization is to decompose relations with anomalies in order to produce smaller, well-structured relations...
in Database Theory
Database theory
Database theory encapsulates a broad range of topics related to the study and research of the theoretical realm of databases and database management systems....
, particularly 4NF
Fourth normal form
Fourth normal form is a normal form used in database normalization. Introduced by Ronald Fagin in 1977, 4NF is the next level of normalization after Boyce–Codd normal form . Whereas the second, third, and Boyce–Codd normal forms are concerned with functional dependencies, 4NF is concerned with a...
.
He has served as program committee chair for ACM Symposium on Principles of Database Systems 1984, Theoretical Aspects of Reasoning about Knowledge 1994, ACM Symposium on Theory of Computing 2005, and the International Conference on Database Theory 2009.