Evaluating navigational RDF queries over the Web

Jorge Baier, Dietrich Daroch, Juan L. Reutter, Domagoj Vrgoc

TL;DR

This paper introduces a novel approach to evaluating navigational queries (property paths) over the decentralized Web of Linked Data by framing the problem as an AI search task. By adapting the classical A* algorithm with a query-aware heuristic, the authors provide a method that minimizes expensive network requests and guarantees finding the shortest paths—a feature currently missing from standard SPARQL engines.

What Problem Does This Paper Address?

The Semantic Web relies on the Resource Description Framework (RDF), which represents data as a massive, distributed graph. While we have powerful tools to query local RDF databases, querying the "Web of Linked Data" is much harder. In this setting, the graph isn't stored in one place; instead, it is discovered on-the-fly by "dereferencing" IRIs (essentially clicking links via HTTP requests) to find neighboring nodes.

Standard navigational queries, known as property paths in SPARQL, allow users to find nodes connected by complex patterns (e.g., "find all co-authors of co-authors of X"). Evaluating these over the live Web is challenging because:

  1. Network Latency: Every new node discovery requires an HTTP request, which is orders of magnitude slower than memory access.
  2. Open World: We don't know the full graph structure in advance.
  3. Efficiency: Traditional search methods like Breadth-First Search (BFS) or Depth-First Search (DFS) either waste time on shallow, irrelevant nodes or get lost in deep, long paths before finding a single answer.

Methods

The authors propose using the A* search algorithm to navigate this unknown graph. The core idea is to treat query evaluation as a path-finding problem on a "product graph" formed by the Web data and a Non-deterministic Finite Automaton (NFA) representing the query.

Key technical components include:

  • Automata-based Heuristic: The authors define an admissible heuristic $h(s)$ based on the query's NFA. It estimates the remaining distance to a "goal" state by looking at the minimum number of transitions needed in the NFA to reach an accepting state.
  • Parallel Expansions: To combat network latency, the algorithm is modified to fetch multiple IRIs in parallel (k-A*), significantly speeding up discovery.
  • Hybrid Infrastructure: The system combines standard IRI dereferencing with public SPARQL endpoints to overcome common data gaps, such as missing "backwards" links.
  • Pathmax Heuristic: A specialized tweak to the heuristic function that prevents the algorithm from prematurely expanding goal nodes, further reducing unnecessary network traffic.
Figure 1: An automaton finding papers of the co-authors of M. Stonebraker.

Datasets

The researchers evaluated their approach using 11 real-world navigational queries across several prominent Linked Data domains:

  • DBLP: Computer science bibliography data.
  • YAGO: A large-scale knowledge base derived from Wikipedia.
  • DBPedia: The structured version of Wikipedia.
  • Linked Movie Database (LMDB): A semantic dataset for movie information.

These queries ranged from simple fixed-depth paths to complex patterns involving multiple Kleene star (*) operations, such as calculating "Bacon numbers" across multiple datasets.

Key Insights and Ideas

  • Query Evaluation is Search: The fundamental "aha moment" is realizing that navigating the Web of Linked Data is exactly the kind of problem A* was designed for: finding a path in an implicitly defined graph where edge expansion is costly.
  • Minimizing Requests is Everything: In Web querying, the number of HTTP requests is the primary bottleneck. A* is optimal here because its heuristic allows it to ignore parts of the graph that cannot possibly lead to a shorter solution.
  • Shortest Paths Matter: Unlike DFS, which might return a very long, convoluted path as its first answer, A* (and BFS) guarantees finding the shortest path first. This provides better "quality" answers for users.
  • Parallelism is a Great Equalizer: While A is superior in sequential execution, as the degree of parallelism increases, the performance gap between A, BFS, and DFS narrows, though A* remains the most consistent.

Key Results

The experimental results demonstrate that A* consistently outperforms or matches BFS and DFS across different query types.

  • Efficiency: In queries like q_Bacon, A* strictly beats both BFS and DFS by using the heuristic to prune irrelevant links.
  • Throughput: For queries requiring deep navigation (like q_Coauthor), BFS often requires hundreds of requests before finding its first answer, whereas A* starts producing results almost immediately.
  • Speedup: Implementing parallel requests (20-40 threads) resulted in a nearly tenfold decrease in execution time across all algorithms.
Figure 2: Performance comparison showing that A* minimizes the requests needed to obtain answers for three different query types.

Limitations and Future Work

The authors highlight a few ongoing challenges:

  • Data Completeness: The "Linked Data Principles" are not always followed perfectly; many servers don't provide all triples for an IRI, especially inverse links.
  • Infrastructure: Relying on full SPARQL endpoints can be unreliable due to erratic uptime. The authors suggest exploring Triple Pattern Fragments as a more lightweight and robust alternative.
  • Language Extension: Future work includes applying these A* techniques to more expressive navigational languages like NautiLOD and LDQL, which offer finer control over how the Web is traversed.

Summary updated

Abstract

Semantic Web, and its underlying data format RDF, lend themselves naturally to navigational querying due to their graph-like structure. This is particularly evident when considering RDF data on the Web, where various separately published datasets reference each other and form a giant graph known as the Web of Linked Data. And while navigational queries over singular RDF datasets are supported through SPARQL property paths, not much is known about evaluating them over Linked Data. In this paper we propose a method for evaluating property path queries over the Web based on the classical AI search algorithm A*, show its optimality in the open world setting of the Web, and test it using real world queries which access a variety of RDF datasets available online.
BibTeX
@inproceedings{baier2017evaluating,
  author = {Jorge Baier and Dietrich Daroch and Juan L. Reutter and Domagoj Vrgoc},
  title = {{Evaluating navigational RDF queries over the Web}},
  booktitle = {HT},
  year = {2017},
  doi = {10.1145/3078714.3078731},
}
Figure