Challenges in Query-driven Data Integration for a Decentralized Web

Data is highly decentralized

• Produced by governments, companies, individuals, …
• Stored at different locations across the world
• Consumed through interactive applications, processes, intelligent agents, …

Decentralized data integration is challenging for application developers

• Discovering data

  How can I find data sources? How can I find data within a source?

• Combining data

  How to combine data across different data sources?

• Preserving privacy

  How to not leak sensitive data?

Query engines abstract access to decentralized data

Hide the complexities of reading and writing for app developers

↔ ↔

Image credit

SPARQL processing over centralized data

• Dataset is collocated with query engine

  All data is known beforehand

• Single dataset

  With precomputed indexes

• Execute queries of any complexity

  SELECT ?name ?deathDate WHERE {
    ?person a dbpedia-owl:Artist;
            rdfs:label ?name;
            dbpedia-owl:birthPlace [ rdfs:label "York"@en ].
    FILTER LANGMATCHES(LANG(?name),  "EN")
    OPTIONAL { ?person dbpprop:dateOfDeath ?deathDate. }
  }
                  

Centralization not always possible

• Private data

  Technical and legal reasons

• Evolving data

  Requires continuous re-indexing

• Web scale data

  Indexing the whole Web is infeasible (for non-tech-giants)

How to query over decentralized data?

• Data and query engine are not collocated

  Query engine runs on a separate machine

• Not just one datasets

  Data is spread over the Web into multiple data sources

Approaches for querying over decentralized data

• Federated Query Processing

  Distributing query execution across known sources

• Link Traversal Query Processing

  Local query execution over sources that are discovered by following links

Client distributes query over query APIs

• Clients do limited effort

  Split up the query, distribute it (source assignment), and combine results

• Servers perform most of the effort

  They actually execute the queries, over potentially huge datasets

Federation over SPARQL endpoints

• Servers are SPARQL endpoints (most common)

  They accept any valid SPARQL query

• Client-side source assignment

  Rewrite query in terms of SERVICE clauses

SELECT ?drug ?title WHERE {
  ?drug db:drugCategory dbc:micronutrient.
  ?drug db:casRegistryNumber ?id.
  ?keggDrug rdf:type kegg :Drug.
  ?keggDrug bio2rdf:xRef ?id.
  ?keggDrug purl:title ?title.
}

SELECT ?drug ?title WHERE {
  SERVICE <http://example.com/drb> {
    ?drug db:drugCategory dbc:micronutrient.
    ?drug db:casRegistryNumber ?id.
  }
  SERVICE <http://example.com/kegg> {
    ?keggDrug rdf:type kegg :Drug.
    ?keggDrug bio2rdf:xRef ?id.
    ?keggDrug purl:title ?title.
  }
}

Federation over heterogeneous sources

• Public SPARQL endpoints have low availability (95%)

  ~1.5 days downtime per month!
  Due to high query expressivity is high and public nature

• Alternative interfaces besides SPARQL endpoints

  Linked Data Fragments: TPF, WiseKG, brTPF, Passage, ...
  Different levels of server expressivity

• Trade-off between server and client effort

  Low-cost publishing prevents server availability issues
  Executing parts of queries client-side

Limitations of federated querying

• All federation members must be known before execution starts

  Source assignment distributes query across list of sources
  No discovery of new sources

• Limited scalability in terms of number of endpoints

  Current federation techniques scale to the order of 10 sources

• Public endpoints have restrictions

  Timeouts, rate limits, …
  Current federation techniques can not cope with them

Exploit interlinking of documents

• Linked Data documents are linked to each other

  Following the Linked Data principles

• Query engine can follow links

  Start from one document, and discover new documents on the fly

Example: decentralized address book

Example: Find Alice's contact names

SELECT ?name WHERE {
    <https://alice.pods.org/profile#me>
        foaf:knows ?person.
    ?person foaf:name ?name.
}

Query process:

1. Start from Alice's address book
2. Follow links to profiles of Bob and Carol
3. Query over union of all profiles
4. Find query results: [ { "name": "Bob" }, { "name": "Carol" } ]

Limitations of link traversal

• Too slow for querying over Linked Open Data

  Can perform well for specific environments (e.g. Solid) (Taelman 2023)

• Some queries can cause number of links to become too high

  Prioritizing links has no impact (Hartig 2016, Eschauzier 2025)
  Server-driven guidance to relevant links (e.g. Shapes Indexes: Tam 2024)

• Traditional query planning is impossible

  Due to zero knowledge at the start of query execution (no cardinalities, …)
  Need for adaptive query planning (Hanski 2025)

• Restricted to document-based interface

Conclusion: Query engines are a good match for integrating decentralized data

• This requires intelligent query processing algorithms

  Abstract away complexities of decentralized data
  

• Trade-offs between federated querying and link traversal

  Federation faster, but lacks source discovery and limited in #sources
  Link traversal currently only works over documents
  Need for a hybrid between federation and link traversal?
• 

  Active research

  https://comunica.dev/: Engine for federation + link traversal

Solid pods adhere to Linked Data Principles

• Client-side engines can discover data by following links

  Link Traversal Query Processing:
      Lookup more information about things by following links
  
  ➕ Fully decentralized
          No dependency on intermediaries
          Robust against partial unavailability
  ➖ Slow for complex queries

Query results arrive incrementally
within human attention limits

• SPARQL query with 6 triple patterns
• Across 1.531 simulated Solid pods (158.233 files, 3.556.159 triples)
• Taelman, Ruben, and Ruben Verborgh. "Link traversal query processing over decentralized environments with structural assumptions." International Semantic Web Conference 2023.

Query execution time mainly influenced by number of followed links

• Queries requiring few links are fast (Discover 4)
• Queries requiring many links are slower (Complex 2)
• Eschauzier, Ruben, Ruben Taelman, and Ruben Verborgh. "How Does the Link Queue Evolve during Traversal-Based Query Processing?." QuWeDa/MEPDaW@ISWC. 2023.

If pods expose more information, complex querying can become faster

• When following links, engines can discover optimizations

  If pods expose them

• A pod can guide engines more efficiently towards relevant data

  Type indexes, shape trees, shape indexes, …

• Cross-pod indexes can prune out irrelevant pods

  Aggregations or summarization of data across collections of pods
  Dangers: staleness, trust, censorship, …

Pods exposing shape information allows query engines to skip many links

• Tam, Bryan-Elliott, et al. "Opportunities for Shape-based Optimization of Link Traversal Queries." arXiv preprint arXiv:2407.00998 (2024).

Pods exposing cardinality information allows engines to make better query plans

• Hanski, Jonni, et al. "Link Traversal over Decentralised Environments using Restart-Based Query Planning." ICWE 2025.