Although the problem is not properly motivated (some good examples in information retrieval and databases should be detailed), and despite the weaknesses of the results pointed in the reviews, the paper is clear and the originality of the work well established after the rebuttal. I thus recommend to accept it, and I encourage the authors to follow the suggestions of the reviews for the final version (if the paper is finally accepted) or before a re-submission (if it is not).