Structured P2P systems in the form of distributed hash tables (DHT) are a promising approach for building massively distributed data management platforms. However, for many applications the supported key lookup queries are not sufficient. Instead, techniques for managing and querying (relational) structured data are required. In this paper, we argue that in order to cope with the dynamics in large-scale P2P systems such query techniques should be work in a best effort manner. We describe such operations (namely grouping/ aggregation, similarity and nearest neighbor search) and discuss appropriate query evaluation strategies.