UC Santa Cruz Distinguished Professor Emeritus Phokion Kolaitis and former Professor Wang-Chiew Tan have been awarded the 2020 Alonzo Church Award for Outstanding Contributions to Logic and Computation for their ground-breaking work laying the logical foundations for data exchange.
The Church Award recognizes an outstanding contribution represented by a paper or small group of papers within the past 25 years. According to the sponsoring organizations, this time span allows the contribution to have established evidence of lasting impact and depth. The award can be given to an individual, or a group of individuals.
The award was established in 2015 by the ACM Special Interest Group for Logic and Computation (SIGLOG), the European Association for Theoretical Computer Science (EATCS), the European Association for Computer Science Logic (EACSL), and the Kurt Goedel Society (KGS).
Data exchange is the problem of transforming data structured under a schema, called the source schema, into data conforming to a different schema, called the target schema. The results and techniques developed have in addition to gaining theoretical insights influenced the development of industrial and academic tools.
Also recognized were Ronald Fagin, Renée J. Miller, and Lucian Popa.
The 2020 Church Award was selected by a panel consisting of Mariangiola Dezani, Thomas Eiter (chair), Javier Esparza, Radha Jagadeesan and Natarajan Shankar for the following papers:
(1) Ronald Fagin, Phokion G. Kolaitis, Lucian Popa, Renée J. Miller. Data exchange: Semantics and Query Answering, Proceedings of the 9th International Conference on Database Theory (ICDT 2003), pp. 207-223, 2003.
Full journal version: Theoretical Computer Science, Vol. 336, No. 1, pp. 89-124, 2005.
(2) Ronald Fagin, Phokion G. Kolaitis, Lucian Popa, Wang Chiew Tan. Composing Schema Mappings: Second-Order Dependencies to the Rescue, Proceedings of the 23rd ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS 2004), pp. 83-94, 2004.
Full journal version: ACM Transactions on Database Systems, Vol. 30, No. 4, pp. 994-1055, 2005.
THE CONTRIBUTION
Data exchange is an old and ubiquitous problem in data management that was described by Philip Bernstein as the “oldest problem in databases”. Early work on data exchange used low-level, ad hoc programs to transform data from the source schema to the target schema, which resulted in inefficiencies and limited reusability. Publications (1) and (2) laid the logical foundations for data exchange and became the catalyst for the development of data exchange as a research area in its own right. Publication (1) is about logic in computer science: a fragment of first-order logic, called source-to-target tuple-generating dependencies (in short, s-t tgds), is systematically used as a specification language in data exchange. The algorithmic and structural properties of s-t tgds are explored, and the concept of a universal solution is introduced as the preferred way to carry out the data exchange task. Publication (2) is about logic from computer science: first, it is shown that the language of s-t tgds is not closed under composition; second, a new fragment of second-order logic, called second-order tuple-generating dependencies (in short, SO tgds) is identified and shown to be the “right” logic-based specification language for composing s-t tgds. The award publications are well-cited and have been recognized with two test-of-time awards.
For more information on the award please visit: https://siglog.org/
