Evaluating Navigational RDF Queries over the Web

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

Abstract

The "Web of Linked Data" presents a massive, distributed graph of information that is challenging to query in real-time. Traditional approaches rely on dereferencing IRIs via HTTP requests, which are significantly slower than local memory access. This paper treats navigational query evaluation as a search problem on an unknown graph and proposes an adaptation of the A algorithm. By utilizing a heuristic derived from the query's Non-deterministic Finite Automaton (NFA), the proposed method minimizes expensive network calls. Experimental evaluations across diverse datasets demonstrate that A consistently outperforms Breadth-First Search (BFS) and Depth-First Search (DFS) in efficiency and result quality.

Introduction

The Resource Description Framework (RDF) has enabled the creation of a global "Web of Linked Data," comprising billions of triples spread across a multitude of independent servers. While structured query languages like SPARQL are effective for local or federated databases, querying the entire live Web remains a significant challenge. The primary bottleneck is network latency; each step in a navigational path may require a new HTTP request to "dereference" an IRI.

The core problem addressed in this research is finding answers to complex navigational queries (e.g., "find all co-authors of co-authors") while making the absolute minimum number of network requests. The authors propose that this is best framed as an AI search problem on a graph where the structure is initially unknown.

Methodology: A* for the Web

The researchers adapt the classic A* search algorithm to the context of the live Web. In this model:

  • Cost ($g$): Each hop in the graph (one dereferencing step) is assigned a cost of 1.
  • Expansion: Expanding a node corresponds to performing an actual HTTP request to fetch an RDF document.
  • Goal: Reaching a state that satisfies the navigational query.

The NFA-Based Heuristic

To guide the A* search effectively, a heuristic function ($h$) is required to estimate the distance to the goal. The authors observe that any regular path query can be represented as a Non-deterministic Finite Automaton (NFA).

An NFA representation of a navigational query used to derive the A* heuristic.

The heuristic $h(s)$ is defined as the shortest path from the current state in the query's NFA to an accepting state. This provides a "map" that allows the algorithm to prioritize links that are more likely to lead to an answer. Because this heuristic is "admissible" (it never overestimates the distance), the A* algorithm is guaranteed to find the shortest paths to answers using the minimum number of node expansions.

Parallelism and Hybrid Infrastructure

To mitigate the impact of network latency, the authors introduced $k$-A*, which expands the top $k$ nodes in the priority queue simultaneously. Furthermore, the system supplements standard dereferencing by querying public SPARQL endpoints when available. This hybrid approach helps overcome the "missing inverse link" problem, where a resource might link to another, but the reverse link is not explicitly stated in the RDF data.

Experimental Evaluation

The approach was tested using 11 real-world navigational queries across major Linked Data domains, including DBLP (bibliography), YAGO (knowledge base), DBPedia (Wikipedia), and LinkedMDB (movies). Specific queries included finding co-authorship chains ($q\_Coauthor$), NATO-related locations ($q\_NATO$), and actor connections ($q\_Bacon$).

Performance comparison of A*, DFS, and BFS across three different query types: q_Coauthor, q_NATO, and q_Bacon.

The results demonstrate the "dominance" of the A approach. As shown in the figures above, A consistently returns more answers with fewer network requests compared to BFS. While DFS can sometimes find answers quickly, it often explores deep, irrelevant paths, leading to lower-quality (longer) results and higher total request counts.

Key Insights and Results

  • Optimality: A* is mathematically optimal in this setting, expanding the absolute minimum number of nodes required to find answers.
  • Latency Management: Through parallelization ($k$-A*), the researchers achieved up to a tenfold speedup in wall-clock time, effectively hiding network latency.
  • Robustness: The live A* search proved more robust than static SPARQL engines, which often timed out on the same complex queries when run against local snapshots of the datasets.

Conclusion and Future Work

By treating Web-scale RDF querying as a search problem, this research provides a highly efficient framework for navigating the Web of Linked Data. The NFA-based heuristic allows A* to navigate the unknown graph with surgical precision. Future work aims to extend this methodology to more expressive traversal languages and to integrate more lightweight protocols like Triple Pattern Fragments to further enhance reliability and reduce server load.

Summary updated

BibTeX
@inproceedings{baier2017evaluating,
  author = {Jorge A. 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