  Partial evaluation has recently been used for processing SPARQL queries over
a large resource description framework (RDF) graph in a distributed
environment. However, the previous approach is inefficient when dealing with
complex queries. In this study, we further improve the "partial evaluation and
assembly" framework for answering SPARQL queries over a distributed RDF graph,
while providing performance guarantees. Our key idea is to explore the
intrinsic structural characteristics of partial matches to filter out
irrelevant partial results, while providing performance guarantees on a network
trace (data shipment) or the computational cost (response time). We also
propose an efficient assembly algorithm to utilize the characteristics of
partial matches to merge them and form final results. To improve the efficiency
of finding partial matches further, we propose an optimization that
communicates variables' candidates among sites to avoid redundant computations.
In addition, although our approach is partitioning-tolerant, different
partitioning strategies result in different performances, and we evaluate
different partitioning strategies for our approach. Experiments over both real
and synthetic RDF datasets confirm the superiority of our approach.
