TL;DR
This paper introduces DeKaloG, a novel system for automatically selecting relevant SPARQL endpoints for queries in the decentralized web of data. By leveraging "web preemption" and generating RDF summaries of endpoints, DeKaloG enables efficient and scalable source selection, addressing a key challenge in querying the vast and distributed Linked Data landscape.
What Problem Does This Paper Address?
The web of data, comprised of interconnected knowledge graphs accessible via SPARQL endpoints, offers immense potential. However, querying this distributed data at scale is challenging, primarily due to the "source selection" problem: identifying the minimal set of relevant endpoints that contain the data needed to answer a given SPARQL query. Existing approaches often rely on static catalogs or require extensive upfront data transfer, which doesn't scale to the dynamic and decentralized nature of the web. Unlike web search engines that automatically discover and index web content, there's no equivalent for automatically exploring and understanding the content of SPARQL endpoints. This paper aims to bridge this gap by proposing an automated, web-scale source selection service.
Methods
DeKaloG tackles source selection by building and querying RDF summaries of SPARQL endpoints. The core idea is to use "web preemption," a technique that allows SPARQL queries to execute in timed slices, enabling the computation of aggregations and summaries without overwhelming endpoints.
Here's a breakdown of their approach:
- RDF Summaries: DeKaloG automatically constructs RDF summaries of endpoints. These summaries are essentially reduced versions of the original RDF graphs, capturing structural information. The authors explore various "summary functions" (ψ) with different levels of accuracy and granularity, ranging from highly accurate but large "identity" summaries to more compact "predicate-aware" and "suffix-authority-aware" summaries.
- Web Preemption for Summary Generation: Instead of transferring entire datasets, DeKaloG uses SPARQL queries to extract these summaries. The "web preemption" principle ensures these queries terminate, allowing for efficient data transfer proportional to the summary size, not the original data size.
- Query Rewriting for Source Selection: Once summaries are built, DeKaloG rewrites the user's original SPARQL query (Q) into a query (Qs) that operates on these summaries. The results of this rewritten query on the summaries directly provide the source selection for the original query.
- Two Source Selection Strategies:
- Triple-Pattern Based Source Selection (TPSS): This approach selects sources for each triple pattern in the query independently.
- BGP-Based Source Selection (BGPSS): This strategy considers Conjunctive Graph Patterns (BGP), taking into account join variables shared across triple patterns for potentially more accurate selection.
Datasets
The authors evaluated their approach using a workload of 14 SPARQL queries extracted from the LargeRDF Benchmark [13]. They ran these queries on nine datasets, which are not explicitly detailed beyond being referred to as "orig" in Figure 3a.
Key Insights and Ideas
- Automated Source Selection is Crucial for Decentralized Data: Just as search engines are vital for the web of documents, a source selection service is essential for the web of data to be discoverable and usable.
- Web Preemption is a Game-Changer: This technique is key to enabling automated summary generation and efficient data transfer, making web-scale source selection feasible.
- Trade-offs in Summaries: There's a clear trade-off between the accuracy of the summary (and thus source selection) and its size, which directly impacts data transfer and execution time. More accurate summaries lead to fewer selected sources but take longer to compute and transfer.
- BGPSS Outperforms TPSS in Accuracy: Considering join variables in BGPSS leads to a more precise source selection compared to TPSS, which treats triple patterns independently.
- "hib" Summary Offers a Good Balance: The "hib" (authorities-aware) summary, when used with BGPSS, provides a good trade-off between source selection accuracy and execution time.
Key Results
- Efficient Summary Extraction: Data transfer for summaries is significantly reduced, being proportional to the summary size rather than the original graph size.
- Improved Source Selection Accuracy: The BGPSS engine, especially with more accurate summaries like "suf" (suffix-authority-aware) and "hib," significantly reduces the number of selected sources (SSQ) compared to TPSS. For example, for query S2, SSQ dropped from 7 to 3 with BGPSS and the "hib" summary.
- Execution Time: While more accurate summaries generally lead to longer execution times, the "hib" summary with BGPSS offers a good balance, performing better than "suf" for execution time while maintaining high accuracy. The "void" summary, being less informative, showed no significant difference in accuracy between TPSS and BGPSS.
Limitations and Future Work
- Summary Function Exploration: The authors acknowledge that their work is an "open garden" with many potential summary functions and combinations yet to be explored.
- Join Ordering: The current approach focuses on source selection. Future work could extend summary functions to collect statistics for join ordering, further optimizing query execution.
- Query Complexity: While the paper focuses on BGP queries, extending the approach to handle more complex SPARQL constructs like union and optional graph patterns is a natural next step.
- Trade-off Management: The paper highlights the inherent trade-off between accuracy, execution time, and summary size. Future research could explore methods to dynamically manage these trade-offs based on user needs or query characteristics.
Summary updated