Link Traversal Query Processing over Decentralized Environments with Structural Assumptions

Querying Decentralized Knowledge Graphs

• Lack of centralized index(es)

• Massive number of sources

• Permissioned data

Discovering data by following links

Focus on Solid

Personal data pods

Full control of where your pod is stored and who can access it

Pods can store any kind of data

Personal data, photo's, friends, ...

How to query data from Solid pods?

• Centralizing all data in a single triplestore

  ❌ Privacy and legal reasons

• SPARQL Federation

  ❌ No SPARQL endpoints, authentication, large number of sources

• Link Traversal Query Processing (LTQP)

  ✅ Live discovery of Linked Data documents
  Compatible with Solid's document-based authorization

LTQP was designed for querying Linked Open Data

• Introduced more than a decade ago

  Hartig, O.: SPARQL for a Web of Linked Data: Semantics and computability

• Web of Linked Open Data as a globally distributed dataspace

  No prior indexing in a central location

• Follow-your-nose principle

  Discover data during query execution

• No practical usage so far

  Due to performance concerns (large number of links, non-termination)
  Additional assumptions with Solid → potential for improved performance!

No assumptions for LTQP over Linked Open Data

→ All links need to be followed to ensure completeness!

• Introduction of reachability-based completeness semantics

  Hartig, O., Freytag, J.-C.: Foundations of Traversal based Query Execution over Linked Data

• Reachability criteria

  cAll: Follow all links
  cMatch: Follow links matching any triple patern
  cNone: Follow no links
  

Solid provides structural properties

• Linked Data Platform

  Pods implement subset of the LDP specification
  LDP Basic Containers: nested directories with resources

  PREFIX ldp: <http://www.w3.org/ns/ldp#>
  <> a ldp:Container, ldp:BasicContainer, ldp:Resource;
     ldp:contains <file.ttl>, <posts/>.
  <file.ttl> a ldp:Resource.
  <posts/> a ldp:Container, ldp:BasicContainer, ldp:Resource.

• Type Indexes

  Mapping of classes to resources containing type instances

  <#ab09fd> a solid:TypeRegistration;
    solid:forClass <http://example.org/Post>;
    solid:instance </public/posts.ttl>.

LTQP discovery using structural assumptions

• Linked Data Platform

  Recurse all directories and resources to find all triples in a pod

• Type Indexes

  Based on classes in a query, find triples in documents for type mapping

  SELECT ?post WHERE {
    ?post a <http://example.org/Post>;
      <http://example.org/title> ?name.
  }

Implemented as modules in Comunica

• Comunica is a modular SPARQL framework

  Taelman, R., Van Herwegen, J., Vander Sande, M., Verborgh, R.: Comunica: a Modular SPARQL Query Engine for the Web

• Pluggable modules

  Reachability criteria
  Solid-specific discovery approaches

• Open-source

  https://github.com/comunica/comunica-feature-link-traversal
  Live demo: https://comunica.dev/research/link_traversal/#try-it-out

We experiment using SolidBench

• SolidBench: simulated Solid environment

  Derived from LDBC's Social Network Benchmark dataset
  

• Large number of files and pods

  158.233 RDF files across 1.531 pods (configurable)
  Variation in file fragmentation

• 27 query templates

  Grouped by 3 categories: short, complex, discover

• 18 combinations of query engine configuration

  Structural assumptions: None, LDP, Type Index, Filtered Type Index,
  LDP + Type Index, LDP + Filtered Type Index
  Reachability criteria: cNone, cMatch, cAll

Discover queries can be answered before the timeout

• Discover queries achieve full accuracy

  Only 0,86% timeout
  First result: 0,925 seconds
  Last result: 2,372 seconds
  Results: 39,13

• Half of the short queries timeout (55,61%)

  Cross-pod queries cause (too) many links to be followed

• All of the complex queries timeout

  Many triple patterns slow down query execution

Structural assumptions lead to difference in HTTP requests

• HTTP requests for type index significantly lower than LDP

Structural assumptions perform similarly

• No significant difference in execution time

  HTTP requests not main bottleneck for discover queries

Query plans are the bottleneck

• We use zero-knowledge query planning

  No cardinality information available before execution
  Hartig, O.: Zero-knowledge query planning for an iterator implementation of link traversal based query execution.

• Better query plan can make discover queries 2 times faster

  Based on experiment with theoretically optimal query plan

Conclusion

• LTQP is relevant for decentralized environments

  Non-complex queries can be answered in the order of seconds

• Completeness can be guaranteed in scope of pods

  Due to structural properties of Solid

• Future work is needed for more complex queries

  Better (adaptive?) query planning
  More selective reachability criteria

Pipeline-based architecture