  To counter societal and economic problems caused by data silos on the Web,
efforts such as Solid strive to reclaim private data by storing it in
permissioned documents over a large number of personal vaults across the Web.
Building applications on top of such a decentralized Knowledge Graph involves
significant technical challenges: centralized aggregation prior to query
processing is excluded for legal reasons, and current federated querying
techniques cannot handle this large scale of distribution at the expected
performance. We propose an extension to Link Traversal Query Processing (LTQP)
that incorporates structural properties within decentralized environments to
tackle their unprecedented scale. In this article, we analyze the structural
properties of the Solid decentralization ecosystem that are relevant for query
execution, and provide the SolidBench benchmark to simulate Solid environments
representatively. We introduce novel LTQP algorithms leveraging these
structural properties, and evaluate their effectiveness. Our experiments
indicate that these new algorithms obtain accurate results in the order of
seconds for non-complex queries, which existing algorithms cannot achieve.
Furthermore, we discuss limitations with respect to more complex queries. This
work reveals that a traversal-based querying method using structural
assumptions can be effective for large-scale decentralization, but that
advances are needed in the area of query planning for LTQP to handle more
complex queries. These insights open the door to query-driven decentralized
applications, in which declarative queries shield developers from the inherent
complexity of a decentralized landscape.
