Moshe Y. Vardi
2008 SIGMOD Edgar F. Codd Innovations Award
Moshe Y. Vardi is the recipient of the 2008 SIGMOD Edgar F. Codd Innovations Award for fundamental contributions to the foundations of relational databases. He has made significant contributions to the foundations of relational databases by establishing deep connections between database theory, mathematical logic, complexity theory, and AI. His important contributions span many areas of database theory, including the complexity of query evaluation, the semantics of database updates, conjunctive queries, data integration, data dependencies, and deductive databases.
The most prominent examples of Vardi’s deep contributions are the following fundamental results.
- Query processing complexity: Vardi has established the distinction between data complexity, which is complexity with respect to the size of the data, and expression complexity, which is complexity with respect to the expression denoting the query. This fundamental distinction is now used in most discussions of query-evaluation complexity, and outside of databae theory as well.
- Logics and query languages: Vardi is one of the pioneers of finite model theory, which is a cornerstone of relational database theory. His pioneering contributions include classical results on capturing complexity classes with fixpoint logics, on 0-1 laws, and on infinitary logics that have been instrumental in the study of relational query languages.
- Connections between databases and other areas of computer science: Vardi has established connections between databases and AI (for example, between database updates and belief-revision problems in AI, and also between query containment and constraint satisfation problems). He was the first to point out connections between database theory and automata, more than a decade before automata have become a common tool in the study of XML.