Web Querying

Linked Data on the Web is multifaceted

• RDF Serializations
• Publication APIs
• Access patterns
• Query languages
• ...

Difficulties for app developers

• Distinguishing APIs

  What kind of API is this?

• Interacting with APIs

  How to efficiently get data from this API?

• Combining APIs

  How to combine data across different APIs?

Query Engines abstract access

Hide the complexities of reading and writing for app developers

↔ ↔

Image credit

Queries as abstraction layer

• Say what needs to happen, not how

  Declarative queries hide complexities of data retrieval

• Queries are reusable

  Queries are not API-specific

• Execution via a generic, reusable query engine

  Abstracts away complexities for executing queries
  New optimisations can be used by merely updating query engine

SPARQL Protocol and RDF Query Language

• The specification describes a protocol and a query language

  Focus in this presentation is on the SPARQL query language
  Declarative language for querying RDF graphs

• W3C recommendation

  SPARQL 1.1 (21 March 2013)
  SPARQL 1.2 (Upcoming mid-2024)

• Widely adopted

  Virtuoso (commercial)
  Apache Jena (open-source)
  Amazon Neptune (commercial)

Different query forms in SPARQL

• SELECT: selecting values in tabular form
• CONSTRUCT: construct new triples
• ASK: check if data exists
• DESCRIBE: describe a given resource
• INSERT: insert new triples
• DELETE: delete existing triples

Find all artists born in York

• 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. }
  }
  

How do query engines process a query?

RDF dataset + SPARQL query
↓
...
↓
query results

How do query engines process a query?

RDF dataset + SPARQL query
↓
SPARQL query processing
↓
query results

Basic Graph Patterns enable graph pattern matching

• Basic Graph Pattern (BGP)

  A collection of triple patterns.

•     ?person a dbpedia-owl:Artist.
      ?person rdfs:label ?name.
      ?person dbpedia-owl:birthPlace ?birthPlace.
      

• Triple Pattern

  A triple in which any component may be a variable.
  Variables start with ?, followed by a label. (e.g. ?name)

• More complex operators are possible

  OPTIONAL, UNION, FILTER, ...

Query results representation

• Solution Mapping

  Mapping from a set of variable labels to a set of RDF terms.

• Solution Sequence

  A list of solution mappings.

Steps in SPARQL query processing

• 1. Parsing

  Transform a SPARQL query string into an algebra expression

• 2. Optimization

  Transform algebra expression into a query plan

• 3. Evaluation

  Executes query plan to obtain query results

1. Parsing: Transform query string into SPARQL Algebra

• SPARQL Algebra = Abstract Syntax Tree (AST)

  Algebraic datastructure that represents the query structure
  
  Tree where each node is a separate operator: join, BGP, filter, ...
  
  Easier for engines to work with than strings
  
  Enables algebraic query optimizations
  
  A.k.a query plan → basis for query planning
  
  

1. Parsing: SPARQL Algebra example

SELECT ?x ?y ?z WHERE {
  ?x ?y ?z
}

{
  "type": "project",
  "input": {
    "type": "bgp",
    "patterns": [
      {
        "type": "pattern",
        "subject": {
          "termType": "Variable",
          "value": "x"
        },
        "predicate": {
          "termType": "Variable",
          "value": "y"
        },
        "object": {
          "termType": "Variable",
          "value": "z"
        }
      }
    ]
  },
  "variables": [
    { "termType": "Variable",
      "value": "x" },
    { "termType": "Variable",
      "value": "y" },
    { "termType": "Variable",
      "value": "z" }
  ]
}

2. Optimization: Why do we need it?

• Queries are declarative

  They say what needs to be done, not how.
  
  Transformation into executable code can happen in many different ways.

• Factors that influence performance

  Dataset
  
  Available data indexes
  
  Order of operators in AST
  
  Available operator algorithm implementations

2. Optimization: Different levels

• Algebraic optimization

  Independent of underlying data
  
  Based on formally provable equivalence of operations

• Low-level optimization

  Based on the underlying data
  
  Select and configure specific algorithms of algebra operators

3. Evaluation: executing the plan

• Bottom-up

  Start with leaves in query plan, and work up to the root.

• Parallelisation

  Evaluate independent branches in parallel on different threads.

• Pipelining

  Reduce time to first result by streaming intermediary results.

Common solution to Web querying: Centralization

• First index all data you want to query over

  Querying from a single location is easy

• Dataset is collocated with query engine

  All data is assumed to be known beforehand

Centralization not always possible

• Private data (Solid)

  Technical and legal reasons

• Evolving data

  Requires continuous re-indexing

• Web scale data

  Indexing the whole Web is infeasible for most organizations

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 across multiple 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 selection), 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 selection

  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

• Servers are not only SPARQL endpoints

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

• Clients may have to take up more effort

  Executing parts of queries client-side

• Trade-off between server and client effort

  Low-cost publishing and preventing server availability issues

Limitations of federated querying

• All federation members must be known before execution starts

  Source selection 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

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

Link Traversal Query Processing

Querying by following links between documents

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 profile
2. Follow links to profiles of Bob and Carol
3. Query over union of all profiles
4. Find query results: [ { "name": "Bob" }, { "name": "Carol" } ]

The Link Traversal Query Process

• 1. Initialize link queue with seed URLs

  Seed URLs can be user-defined, or derived from query

• 2. Iterate and append link queue

  Iteratively pop head off queue, and follow link to document
  
  Add all URLs in document to link queue

• 3. Execute query

  Over union of all discovered RDF triples

Difficulties with Link Traversal

• Link queue rarely becomes empty

  It grows in size due to massive size of the Web
  
  Discovery and Query Processing must be done in parallel

• Too many links are followed

  Link filtering strategies are required

• Traditional query planning algorithms don't work

  Heuristics or adaptive query planning techniques are needed

Open problems with Link Traversal

• Slow query execution for complex queries

  Large number of links and lack of indexing

• Query termination for some queries

  Virtually infinite number of links

• Security issues in uncontrolled environments

  Possibility of malicious data publishers

The future of querying over decentralized data

• Neither Link Traversal nor Federated Querying will be sufficient

  A combination of both will be needed

The following will make use of Comunica

• Flexible and Modular Meta-Query Engine

  Building blocks to build engine with specific functionality
  Presets like Comunica SPARQL, Comunica SPARQL Solid

• Open-source

  Available under the MIT license

• Implemented in TypeScript

  Can be used in any JavaScript application or from the command line

💻 Using Comunica in a JS app

• Querying from a single source

  Using @comunica/query-sparql

• Federated querying from multiple sources

  Using @comunica/query-sparql

• Link traversal querying over Solid pods

  Using @comunica/query-sparql-link-traversal-solid

Learn more about using Comunica

• @comunica/query-sparql

  From one or multiple sources
  Try in your browser

• @comunica/query-sparql-link-traversal-solid

  To traverse over one or multiple Solid pods
  Try in your browser

• Or anything else

  https://comunica.dev/

Conclusions

• SPARQL querying as abstraction layer

  Read/write Linked Data using simple declarative queries

• Querying over multiple sources

  Federated querying or link traversal

• Comunica

  Open-source TS/JS engine providing abstraction layer