|
Name |
Fagin, Ronald |
Location
|
IBM Almaden Research Center |
Primary Field
|
Computer and Information Sciences |
Secondary Field
|
Mathematics |
Election Citation
|
Fagin developed "Fagin's Theorem," which connects how hard it is to solve a problem with how hard it is to express it. |
Research Interests
|
Ronald Fagin's primary interest is in applying mathematical logic to computer science. His Ph.D. thesis created the field of finite model theory. He is best known for "Fagin's Theorem", which gives a surprising connection between how hard it is to solve a problem and how hard it is to express it. He has done much research on "reasoning about knowledge" and is co-author of the key book on the topic. The main area of his research is the theory of databases. He contributed to database design with his introduction of Fourth Normal Form for relational databases, which formalizes the intuition that in a well-designed database schema, unrelated data should not be stored in the same table. He is the co-inventor of acyclic database schemes, and showed that there are a number of desirable properties of database schemas that are all equivalent, and are equivalent to the structure of the tables in the database schema being acyclic in a certain precise sense. He is a co-inventor of extendible hashing, a fast method for data access with a dynamic structure that grows and shrinks gracefully as the database grows and shrinks.
He has created widely used algorithms for accessing and retrieving imprecise, or fuzzy data from multimedia databases. Another of his research areas is data exchange, which deals with how to cope with data in multiple formats, and how to convert from one format to another.
|
|
|
|