Link Traversal over Decentralised Environments using Restart-Based Query Planning

With the emergence of decentralisation initiatives to address various issues around regulatory compliance and barriers of entry to data- driven markets, data access abstraction layers in the form of query engines are needed to assist in developing services on top of such environments. Prior work, however, has demonstrated significant network overhead dur- ing data retrieval in traversal-based query execution over decentralised Linked Data sources, dwarfing the relative impact of local processing and query optimisations. Certain decentralisation initatives, however, offer an environment with seemingly sufficient structure to address this, allowing client-side query engines to attain measurable performance improvements through local optimisations. One example is the Solid initiative, offering distributed well-defined user data stores, helping traversal-based query execution approaches in efficiently locating and accessing query-relevant data. Within this work, we demonstrate the impact of client-side adaptive query planning optimisations within structured distributed environments, using the Solid ecosystem as an example, to highlight the potential for tangible improvements in traversal-based execution. Through the implementation of a restart-based query planning technique, we achieve average query execution time reductions of up to 36% compared to a baseline of unchanged query plan execution. Conversely, we also demonstrate how such techniques, when applied without robust cost-benefit estimation, can effectively double the query execution time. This illustrates the importance and potential of client-side techniques even in such distributed environments, and highlights the importance of further investigation in the direction of these techniques.

@inproceedings{hanski_icwe_restart_2025,
  author = {Hanski, Jonni and Taelman, Ruben and Verborgh, Ruben},
  title = {Link Traversal over Decentralised Environments using Restart-Based Query Planning},
  booktitle = {Proceedings of the 25th International Conference on Web Engineering},
  year = {2025},
  month = jun,
  url = {https://www.rubensworks.net/raw/publications/2025/hanski_icwe_restart_2025.pdf}
}