Posted: 5th February 2015

Oxford’s Michael Benedikt, along with co-authors Wenfei Fan and Floris Geerts, have won the coveted 2015 ACM  PODS (Association for Computing Machinary Symposium on Principles of Database Systems)  Alberto O. Mendelzon Test-of-Time Award, for their paper ‘XPath satisfiability in the presence of DTDs’.

The annual award is given for a paper, or a small number of papers, published in the PODS proceedings ten years prior that had the most impact in terms of research, methodology, or transfer to practice over the intervening decade.

The citation for the award describes how “the paper studies the satisfiability problem for XPath queries under schema constraints.  The satisfiability problem is a classical problem associated with query languages, and the query languages considered in this paper represent tree pattern languages of universal interest. The paper considers an exhaustive combination of query languages and schema formalism, establishing tight complexity bounds for the satisfiability problem.  The conference paper, and its full version published in the Journal of the ACM three years later, contain a treasure trove of complexity results and proof techniques, most of which are state of the art today. The proofs are technically sophisticated, yet a pleasure to read.  The paper has a large number of citations, has influenced many researchers, and it is considered today the standard reference for complexity results on the satisfiability problem for XPath expressions.”  

The winners of the ACM PODS Alberto O. Mendelzon Test-of-Time Award receive plaques and the sum of $1,000 (divided equally among the winners). The award, funded by IBM, is named after Alberto O. Mendelzon, an international leader in the principles of database systems. His pioneering work on database dependencies has been influential in both the theory and practice of data management.

Luc Segoufin and Victor Vianu’s paper ‘Views and queries: determinacy and rewriting’, also won a 2015 PODS 2015 Test-of-Time Award.