This paper is a must for whoever likes optimization and, more precisely, join algorithms. If you are not particularly attracted by joins, you may still want to read it to find out about the algorithms developed in order to deal efficiently with attributes storing references or collections of references. Maybe a concrete example is appropriate here. In an object-oriented or object relational database, you have the ability to represent in a single element the fact that, e.g., one customer passes several orders. The database element corresponding to a customer simply features an attribute whose value is a set of references towards the various orders he/she hsa passed. The problem is then to process queries that require navigating along these set-valued attributes (the problem is nearly the same with single valued reference attributes). For instance, "what are the suppliers of the products ordered by my favourite customers?". (Interestingly, this is a typical query on XML data).

The first part of the paper does a very good job in explaining in few words (i) the different implementations of references in database systems and (ii) various ways of processing joins involving references. It provides all the good pointers. The second part is the main contribution: a new algorithm to process queries of the above kind, and experimental results. The authors worked hard to explain their contribution in 7 pages, I am not going to try and do it in 1 paragraph. I suggest that you read the paper instead.

a service of Schloss Dagstuhl - Leibniz Center for Informatics