Introduction to Link Traversal-Based Query Processing

Assumption: Data is decentralized

How to query over this?

Necessary if we want to build applications

• Centralized and query

  Unlikely to happen on global scale

• Use smaller indexes, and do federated querying

  Existing techniques scale to ~10 sources → we may have billions of pods

• Query over documents, and follow links

  Just like humans browse the Web
  Link Traversal-Based Query Processing (LTQP)

Example: Find names of my friends

SELECT ?name WHERE {
    <https://www.rubensworks.net/#me> foaf:knows ?person.
    ?person foaf:name ?name.
}

The Link Traversal Query Process

1. Determine seed URLs (https://www.rubensworks.net/#me if query-driven)
   → Add to link queue
2. Repeat until link queue is empty
   1. Pop head URL in queue, and dereference
   2. Add all discovered URLs to queue
3. Execute query over all discovered RDF triples

Differences LTQP and traditional querying

• Traditional query execution: index-based

  For example: SPARQL query execution over the DBpedia SPARQL endpoint.
  ➖ Indexing phase can be expensive.
  ➕ Once index is built, queries are mostly fast.
  ➖ Combining with data outside of the index is harder.
  ➖ Index can become stale.

• Link traversal-based query processing (LTQP): explorative

  Based on the follow-your-nose principle of Linked Data.
  ➕ Implicit combinations of different sources.
  ➕ Query execution always happens over live data.
  ➖ Querying is mostly slower.
  ➖ Harder to achieve (and define) completeness.

🕰️ Brief History of LTQP

🕰️ Brief History of LTQP (2)

• Foundations of Traversal Based Query Execution over Linked Data. (HT 2011)

  More formalizations
  Reachability semantics: what links should be followed

• LDQL: A query language for the Web of Linked Data. (JWS 2016)

  Query language with ability to express navigation paths

• Walking without a Map: Optimizing Response Times of Traversal-Based Linked Data Queries. (ISWC 2016)

  Prioritize certain URLs to achieve most relevant results faster

🧐 Open Problems with LTQP

• Slow query execution compared to index-based

  Mainly caused by number of lookups

• No guarantee of termination

  Web is unbounded

• No guarantee of completeness

  No links may exist between source and target

🤝 Content Policies Define Trust Scopes

• Reachability semantics: all triples from followed links are considered applicable

  Carol defines an incorrect name for Bob.

• Content policies: user-defined "trust" preferences

  Different people trust different sources
  Alice queries over her contact information, but only wants to obtain friend-defined names.

• Hypothesis 1: Content policies do not slow down querying

• Hypothesis 2: Reduction of search space → faster querying

🌲 Exploiting Linking Structure

• Document linking structure can be declaratively exposed

  Footprints, Shapetrees, TREE, ...
  To enable auto-discovery, should be fully self-descriptive

• Query execution can prune away links that would not give results

  Querying for pictures in May 2020 enables us to prune all other years.
  Important nuance: due to the open-world assumption, only pruning is possible, not selecting.

• Hypothesis: More fine-grained linking structures will increase performance

🧬 Hybrid Query Execution

• LTQP optimizations will only go so far

  May never be sufficient for performance-critical cases

• A hybrid of link-traversal-based and index-based query processing

  Combines advantages of both approaches

• Hypothesis: At the cost of preprocessing and partially stale data, LTQP can be made faster

🏋 How to evaluate and test all of this?

• The Web itself is not suited

  Too large and unpredictable to execute reproducible experiments

• Creating a (closed) simulated Web of data

  Based on a social network use case
  Different fragmentation strategies for testing different LTQP approaches

👨‍💻 Current status

• Implementation of existing LTQP strategies

  ✅ Separate modules in Comunica

• Creation of an LTQP Benchmark

  Based on the well-established LDBC Social Network Benchmark
  ✅ Additional layer that applies fragmentations
  ⏳ Additional layer that generates fake data: WIP

• Incorporating Content policies

  Experimental implementation in Comunica
  ⏳Performance tests: WIP

🤝 Content Policies: Example

FOLLOW (?friend WITH POLICIES) {
  <https://alice.pods.org/profile#me> foaf:knows ?friend.
} INCLUDE {
  ?friend ?p ?o.
}

1. Identifies what links to FOLLOW
2. Identifies what triples to INCLUDE from followed documents

Carol's data:

✅ <https://carol.org/#me> foaf:name "Carol" .
✅ <https://carol.org/#me> foaf:knows <https://alice.pods.org/profile#me> .
❌ <https://bob.pods.org/profile#me> foaf:name "Not Bob" .

🏋 LDBC SNB Schema