  The emergence of Linked Data on the WWW has spawned research interest in an
online execution of declarative queries over this data. A particularly
interesting approach is traversal-based query execution which fetches data by
traversing data links and, thus, is able to make use of up-to-date data from
initially unknown data sources. The downside of this approach is the delay
before the query engine completes a query execution. In this paper, we address
this problem by proposing an approach to return as many elements of the result
set as soon as possible. The basis of this approach is a traversal strategy
that aims to fetch result-relevant data as early as possible. The challenge for
such a strategy is that the query engine does not know a priori which of the
data sources that will be discovered during the query execution contain
result-relevant data. We introduce 16 different traversal approaches and
experimentally study their impact on response times. Our experiments show that
some of the approaches can achieve significant improvements over the baseline
of looking up URIs on a first-come, first-served basis. Additionally, we verify
the importance of these approaches by showing that typical query optimization
techniques that focus solely on the process of constructing the query result
cannot have any significant impact on the response times of traversal-based
query executions.
