Test of Time Awards


EDBT 2016 Test of Time Award

In 2014, Extended Database Technologies (EDBT http://www.edbt.org) began awarding the EDBT test-of-time (ToT) award, with the goal of recognizing one paper, or a small number of papers, presented at EDBT earlier and that have best met the "test of time », i.e. that has had the most impact in terms of research, methodology, conceptual contribution, or transfer to practice over the past decade(s). The EDBT ToT award for 2016 will be presented during the EDBT/ICDT 2016 Joint Conference, March 15-18, 2016 - Bordeaux, France (http://edbticdt2016.labri.fr)

The EDBT 2016 Test of Time Award committee was formed by
    Sihem Amer-Yahia, CNRS, Laboratoire d’Informatique de Grenoble, France,
    Yannis Ioannidis, University of Athens, Greece, and
    Christian S. Jensen, Aalborg University, Denmark,
all PC chairs of former EDBT conferences including EDBT 2006.

The committee was asked to select a paper or a small number of papers from the EDBT 2006 proceedings that has had the most impact in terms of research, methodology, conceptual contribution, or transfer to practice over the past decade. After thorough consideration, the committee came up with some recommendation.

After careful consideration, the committee and the EDBT executive board have decided to select the following paper as the EDBT ToT Award winner for 2016:

Bridging Physical and Virtual Worlds: Complex Event Processing for RFID Data Streams
by Dr. Fusheng Wang, Shaorong Liu, Peiya Liu, Yijian Bai
published in the EDBT 2006 proceedings, 588-607.

The paper proposes an event-oriented approach to the processing of RFID data which makes it possible to automate the translation of RFID based application semantics through complex event detection. In particular, it demonstrates the ability to process complex events by capturing temporal constraints in an algebra. The resulting declarative event-based approach is shown to simplify RFID data processing and is shown to be scalable.
The paper pioneers declarative event-based RFID processing. The simplicity and expressiveness of the proposed framework are admirable. For example, the framework makes it possible to express object tracking on historical data as well as to formulate real-time monitoring.

The committee and the EDTB executive board find that this paper stands out in terms of relevance, impact, and influence in databases. It has had substantial impact. In particular, it has impacted real systems, and the engine it proposes has been integrated into Siemens RFID Middleware. It is also the most cited EDBT 2006 paper, has spurred a significant amount of follow-up work, and remains relevant today.


ICDT 2016 Test of Time Award

In 2013, the International Conference on Database Theory (ICDT) began awarding the ICDT Test-of-Time (ToT) award, with the goal of recognizing one paper, or a small number of papers, presented at earlier ICDT conferences that have best met the "test of time". In 2016, the award will recognize a paper selected from the proceedings of the ICDT 1995 & 1997 conferences, that has had the highest impact in terms of research, methodology, conceptual contribution, or transfer to practice over the past decade. The award will be presented during the EDBT/ICDT 2016 Joint Conference, March 15-18, 2016 in Bordeaux, France.

The 2016 ToT Committee consisting of Foto Afrati, Claire David, and Georg Gottlob (Chair)
has chosen the following contribution for the 2016 ICDT Test-of-Time Award:

Conjunctive Query Containment Revisited
by Chandra Chekuri and Anand Rajaraman
ICDT 1997

This landmark paper made highly significant contributions to the problems of conjunctive query containment and optimization. While it was known that these NP-hard problems are tractable in case of acyclic queries, Chekuri and Rajaraman observed that the most commonly encountered queries, while not necessarily acyclic, are in some sense nearly acyclic and still lend themselves to polynomial-time containment and minimization algorithms. To make this precise, they introduced the concept of query-width, which is based on the notion of query-decomposition combining treewidth-like decomposition techniques with set covering methods. In particular, the class of acyclic queries coincides with the class of queries having query-width 1. They showed that the problems of query-containment and query minimization are tractable for classes of queries whose query width is bounded by some constant k in case a query decomposition of widh ≤ k is given.

The paper contains a number of further important results on (i) the relationship between the query-width of a query to the treewidth of its incidence graph, (ii) the hardness of approximating query minimization, and (iii) rewriting and answering queries of bounded query-width in presence of views.

This highly cited paper, whose full version has appeared in Theoretical Computer Science, had a major impact on subsequent work in database theory and artificial intelligence (in particular, constraint satisfaction). Its pioneering use of hypergraph-based rather than graph-based decomposition techniques marked the beginning of a still ongoing series of investigations that have led to the definition of further, successively more general decomposition techniques, rooted in the very idea of query decomposition.