Query execution over the Web of Linked Data has attracted much attention
recently. A particularly interesting approach is link traversal based query
execution which proposes to integrate the traversal of data links into the
construction of query results. Hence -in contrast to traditional query
execution paradigms- this approach does not assume a fixed set of relevant data
sources beforehand; instead, it discovers data on the fly and, thus, enables
applications to tap the full potential of the Web.
While several authors study possibilities to implement the idea of link
traversal based query execution and to optimize query execution in this
context, no work exists that discusses the theoretical foundations of the
approach in general. Our paper fills this gap.
We introduce a well-defined semantics for queries that may be executed using
the link traversal based approach. Based on this semantics we formally analyze
properties of such queries. In particular, we study the computability of
queries as well as the implications of querying a potentially infinite Web of
Linked Data. Our results show that query computation in general is not
guaranteed to terminate and that for any given query it is undecidable whether
the execution terminates. Furthermore, we define an abstract execution model
that captures the integration of link traversal into the query execution
process. Based on this model we prove the soundness and completeness of link
traversal based query execution and analyze an existing implementation
approach..

本文研究了基于链接遍历的查询执行方法的理论基础，并且提出了一种具有明确定义语义的查询的定义，分析了其计算性质，发现一般情况下查询计算无法终止，同时基于抽象执行模型证明了以链接遍历为基础的查询执行的完备性和正确性。