2008 SIGMOD Edgar F. Codd Innovations Award
Moshe Y. Vardi
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.
|
