Introduction to Link Traversal Query Processing

Ruben Taelman

KNoWS, 30 November 2020

Introduction to Link Traversal Query Processing

Ghent University – imec – IDLab, Belgium

What is Link Traversal Query Processing?

Finding the names of my friends

SELECT ?name WHERE {
    <https://www.rubensworks.net/#me> foaf:knows ?person.
    ?person foaf:name ?name.
}
  1. Determine seed URLs: https://www.rubensworks.net/#me if query-driven
  2. Dereference https://www.rubensworks.net/#me
  3. Dereference all discovered URLs in https://www.rubensworks.net/#me
  4. Repeat dereference process recursively...
  5. Execute query over all discovered RDF triples
Live example

🕰️ Brief History of LTQP

Pioneered by Olaf Hartig
  • Executing SPARQL queries over the web of linked data. (ISWC 2009)

    Introduction of the LTQP concept
    A non-blocking iterator-based pipeline for querying
  • Zero-Knowledge Query Planning for an Iterator Implementation of Link Traversal Based Query Execution. (ESWC 2011)

    Formalization of LTQP
    Query plan selection rules

🕰️ Brief History of LTQP (2)

🧐 Open Problems with LTQP

🤝 Content Policies Reduce Search Space

🌲 Exploiting Linking Structure

🧬 Hybrid Query Execution

🏋 How to evaluate and test all of this?

👨‍💻 Current status