Semantic summaries try to extract compact information from the original RDF graph, while reducing its size. State of the art structural semantic summaries, focus primarily on the graph structure of the data, trying to maximize the summary’s utility for a specific purpose, such as indexing, query answering and source selection. In this paper, we present an approach that is able to construct, high quality summaries, exploiting a small part of the query workload, maximizing their utility for query answering, i.e. the query coverage. We demonstrate our approach using two real world datasets and the corresponding query workloads and we show that we strictly dominate current state of the art in terms of query coverage.