Scaling Federated SPARQL Queries Under Server Quotas

24 concepts19 papers1 proposal

The vision of the Semantic Web is a decentralized, global knowledge graph formed by linking independent triple stores across the web. To query this network, clients use federated query engines that decompose a single query into subqueries distributed across multiple public endpoints. However, as networks scale to billions of records (Dumontier et al.), a fundamental operational conflict emerges. Public endpoints must protect their resources from monopolization and denial-of-service, leading them to enforce strict quotas, time limits, and rate limits (Benedikt et al.; Aimonier-Davat et al.).

When a complex query—such as a property path or deep aggregation—is executed, it frequently hits these server-side limits, resulting in timeouts, incomplete results, or outright execution failures (Montoya et al.; Katayama et al.). To scale federated query processing from a handful of nodes to hundreds of independent data owners (Tong et al.), modern research focuses on architectures designed to work with rather than against these operational constraints. These strategies fall into three main categories: web preemption, result-aware source pruning, and approximate query processing.

Web Preemption: Turning Timeouts into Checkpoints

Traditionally, a server timeout is a catastrophic failure: the server stops processing, and the client receives a partial, un-resumable answer. Web preemption redefines this relationship by turning timeouts into cooperative checkpoints.

Instead of allowing a query to run until it is forcefully killed, a preemptable server suspends query execution just before the quota expires. It saves the execution state and returns a continuation token to the client. The client can then issue a continuation query using this token to resume execution exactly where it left off.

Aimonier-Davat et al. demonstrated this mechanism for complex property path queries, which evaluate reachability and paths over graphs. By introducing a Partial Transitive Closure (PTC) operator, they allowed servers to yield complete results across multiple HTTP requests without requiring massive client-side data transfers or complex query decomposition (Aimonier-Davat et al.). Building on this paradigm, the PASSAGE framework by Pham et al. chains these continuation queries iteratively, effectively transforming public timeouts from a failure state into an opportunity for incremental progress.

Result-Aware Planning: Pruning Wasted Work

In a large-scale federation, a query's structural "shape" (such as stars, chains, or trees) can cause a massive network bottleneck due to the volume of HTTP requests required to coordinate subqueries (Montoya et al.). Traditional federated engines often generate plans that blindly query dozens of endpoints, only to receive empty result sets from most of them. This wasted effort consumes precious server quotas and introduces severe latency.

To solve this, recent architectures focus on result-aware query planning. For example, the FedUP engine proposed by Aimonier-Davat et al. uses compact structural overviews called "quotient summaries." These summaries allow the engine to predict which combinations of data sources will actually yield results before sending any queries over the network. By eliminating empty subqueries at the planning stage, the engine avoids wasting server execution time and drastically reduces the join space.

For analytical workloads involving nested patterns and aggregates, the CoDA optimizer by Ibragimov et al. uses specialized strategies like semi-joins and partial aggregations. Instead of pulling raw data to a central mediator, CoDA pushes partial aggregation tasks directly to the remote endpoints, minimizing data transfer and ensuring queries complete within standard timeout windows.

Approximate Query Processing: Trading Completeness for Speed

For exploratory data analysis, data summary generation, or interactive applications like query autocompletion, waiting for a multi-hour preempted query to complete is impractical. When exact results are too expensive, engines pivot to Sampling-based Approximate Query Processing (S-AQP).

The intuition behind S-AQP is to explore remote knowledge graphs via statistical sampling rather than exhaustive traversal. The RAW-JENA engine (Aimonier-Davat et al.) leverages random walks over SPARQL endpoints to provide rapid, incremental partial results and cardinality estimates. Similarly, the FRAW engine (Boisteau-Desdevises et al.) extends this sampling paradigm to federated environments, making interactive query exploration feasible over hundreds of endpoints simultaneously.

This sampling approach can also be tailored to specific query types. For instance, computing exact COUNT(DISTINCT ...) values is notoriously resource-intensive and prone to timeouts. The CRAWD framework (Pham et al.) optimizes this by sampling the frequencies of distinct values. Because the number of distinct frequencies is typically orders of magnitude smaller than the number of unique entities, CRAWD can estimate count-distinct values with high accuracy while consuming only a fraction of the server's quota.

The Path to a Resilient Web of Data

As Hose observes, the Web of Data is inherently "wild"—characterized by endpoint crashes, dynamic data evolution, and unpredictable server availability. Deep recursive reasoning across decentralized endpoints introduces severe latency bottlenecks (Al-Bakri et al.). By shifting from rigid, centralized assumptions to adaptive, quota-aware execution strategies—whether through preemption, result-aware pruning, or statistical approximation—modern federated query engines turn these operational constraints from system failures into manageable parameters of distributed computation.

Key Foundational Work

A Heuristic-Based Approach for Planning Federated SPARQL Queries (2012) — contributed 3 concept elements to this direction.
A journey to Semantic Web query federation in the life sciences (2009) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_federated_query_scalability_00008884,
  title = {federated query scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/federated-query-scalability/rdr_00008884a787430fa39711c09f94008e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_federated_query_scalability_00008884_v1,
  title = {federated query scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/federated-query-scalability/rdr_00008884a787430fa39711c09f94008e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake