RAW-JENA: Approximate Query Processing for SPARQL Endpoints

Abstract

Sampling-based Approximate Query Processing (S-AQP) has many important use cases for RDF, including computing large-scale statistics, embeddings, join orderings, approximate aggregations, summaries, and exploratory queries. However, current SPARQL endpoints have no support for S-AQP, and many queries just time out on public SPARQL endpoints. In this demonstration, we present RAW-JENA: an extension of Apache Jena to support S-AQP for conjunctive SPARQL queries relying on random walks. RAW-JENA delivers partial random results and cardinality estimates in a pay-as-you-go fashion.

Keywords

• eol>SPARQL
• Sampling
• Approximate query processing
• Random walks

1. Introduction

Public SPARQL endpoints cannot fully execute many SPARQL queries due to their quotas and fair-use policies. After 60 seconds, they stop their execution and return only partial results, forbidding many use cases such as building summaries or computing large-scale statistics. This constitutes a major issue for building decentralized ecosystems of public SPARQL endpoints.

Sampling-based Approximate Query Processing (S-AQP) [ 1 ] tackles this issue for use cases such as computing large-scale statistics [ 2, 3 ], knowledge graph embeddings [ 4 ], join orders [ 5 ], approximate aggregations [ 6 ], summaries [ 7 ], and exploratory queries [ 1 ]. By confining query execution to samples of large datasets, S-AQP drastically reduces execution time, delivering approximate results with error estimates. To support S-AQP in SPARQL, the evaluation of such queries must both (i) return random samples, and (ii) comply with fair-use policies of public SPARQL endpoints. Ad-hoc methods already exist to sample knowledge graphs. For example, a user could draw random triples from Wikidata [ 2 ] by repeatedly executing SELECT * {?s ?p ?o} OFFSET r LIMIT 1, where is a random number between 0 and the dataset size (0 < < 12). However, all queries time out when is above 100 . Some triple stores propose home-made methods for sampling triple patterns1,2, but these solutions are limited to single triple patterns and the underlying complexity is not established.

In this demonstration, we introduce RAW-JENA, an open source extension of Apache Jena that eficiently supports S-AQP for conjunctive SPARQL queries. RAW-JENA evaluates a query } # tp3 # tp2 # tp1

A C

P17 P641 P17 D B E

P361 P641

(b) RDF Graph 1: , , and are cycling sports; and are countries of Central America [ 11 ] over a dataset by drawing random walks guided by , as defined in Wander Join [ 8 ]. Random walks have two desirable properties: (i) As each random walk is independent, a user can distribute its query execution into multiple requests, hence collecting and merging random walks in a pay-as-you-go fashion without impairing the fair-use policy of public SPARQL endpoints. (ii) As each random walk enjoys a logarithmic time complexity, endpoints can draw thousands of random walks per second: the widely used BTree indexes of RDF stores allow endpoints to compute each random walk in (|| log ||) where || is the number of triple/quad patterns in and || is the number of triples/quad in .

RAW-JENA produces random partial results instead of complete results. Without cardinality estimates, users cannot appreciate the quality of provided samples. In Figure 2, RAW-JENA returns 1434 random results after 35 seconds. By adding an estimate of the total number of results (26 ± 3 ), the user acknowledges that her sample represents but a tiny fraction of the whole results. Provided estimates prove highly accurate as long as random walks remain paired with their probability of being drawn [ 9 ]. Despite starting from 35 ± 15 , RAW-JENA improved over time, reaching 26 ± 3 while the actual number of results is 25 .

For the demonstration, we load the dump of Wikidata provided by WDBench [ 10 ] that comprises 1.2 triples. We let users choose a query among the 16 that time out on Apache Jena. We execute it using RAW-JENA to highlight (i) the benefits of S-AQP for ecosystems of public SPARQL endpoints and (ii) the feasibility of implementing S-AQP on well-known engines.

2. RAW-JENA: RAndom Walks for Apache Jena

RAW-JENA is an open source extension of Apache Jena available on the GitHub platform at https://github.com/GDD-Nantes/raw-jena. It eficiently supports Sampling-based Approximate Query Processing (S-AQP) for conjunctive SPARQL queries. This Section provides a formal framework for sampling and applies it on a small toy example; then it details the benefits of RAW-JENA on a larger larger example extracted from WDBench [ 10 ]; finally it describes the demonstration protocol for the live session.

Sampling principles. Let be a SPARQL conjunctive query, and = ⟨1, ..., ⟩ be the join order to perform random walks. A random walk = ⟨1, ..., ⟩ is computed over an RDF graph by randomly picking 1 in J1K, and each subsequent ( > 1) in J− 1 ◁▷ K.

Once computed, the cardinality of is estimated as the inverse probability of sampling [ 8 ], with ( ) = |J1K|− 1 ∏︀=2 |J− 1 ◁▷ K|− 1. For instance, let us consider the query 1 and the RDF graph 1 depicted in Figure 1. Following the join order 3, 2, 1, the random walk 1 is computed as follows: 3 2 1 draw 1 draw 2 draw 3 = (A, 641, 3609) = (, 17, D) = (, 361, 27611) ∈ J(?1, 641, 3609)K1 ∈ J(A, 17, ?3)K1 ∈ J(D, 361, 27611)K1 The cardinality of 1 is then estimated as the inverse probability of sampling 1: ( 1)− 1 = |J(?1, 641, 3609)K1 | · | J(A, 17, ?3)K1 | · | J(D, 361, 27611)K1 | = 2 · 1 · 1 = 2 Note that a random walk may fail if it becomes impossible to sample for some ≤ . In this case, its probability ( ) of being sampled is 0. For instance, if 1 = (, 641, 3609) is picked in J(?1, 641, 3609)K1 instead of (, 641, 3609), then the random walk fails because J(, 17, ?3)K1 = ∅. To improve the quality of estimates, we compute a set of random walks Γ = ⟨ 1, ..., ⟩, and the cardinality of is estimated as |Γ|− 1 ∑︀|Γ=|1 ( )− 1. RAW-JENA in action (https://youtu.be/We5-rG6uxN8). We executed the query 604 of WDBench [ 10 ] presented in Figure 2 that searches for people with the same dates of birth and death. 604 expects 25 results, but times out on the public Wikidata SPARQL endpoint after 60 seconds; and takes longer than 2 hours to complete on Apache Jena.

Each time the user presses the play button, RAW-JENA computes either 10 random walks or as many as possible before reaching 60 seconds of execution time. By repeating the operation, the web client merges the results iteratively in a pay-as-you-go fashion.

The bottom panel of Figure 2 displays both succeeded and failed random walks with their respective probability of being drawn ( ). Increasing the number of random walks allows for displaying more accurate estimates. The left panel of Figure 2 presents the evolution of cardinality estimates and confidence intervals with respect to the number of random walks. The 1 iteration provides a rough estimate of 35 ± 15 expected results. After 35 seconds of execution time and 100 random walks, the 10ℎ iteration provides a more accurate estimate of 26 ± 3 of expected results and 1434 actual random results. The right panel of Figure 2 displays the join order with (i) the estimated cardinality of the partial query up to each triple/quad pattern, and (ii) the number of random walks that reached each triple/quad pattern. Among 100 random walks launched on 1, only 1434 reached 6. This hints that the join order might be suboptimal since 5 is very selective and makes random walks fail. This example shows how S-AQP can be used for exploratory queries and optimization. Nevertheless, S-AQP also provides opportunities for computing large-scale statistics, embeddings, or summaries.

Live demonstration. During the session, we start a local RAW-JENA server on the dataset of WDBench [ 10 ] that comprises 1.2 triples extracted from Wikidata. We present the Web interface of RAW-JENA depicted in Figure 2. The user can choose a query among a predefined set of conjunctive queries that timed out using Apache Jena; or even type her own. We show that using RAW-JENA, after a second of execution time, the user already gets meaningful insights on her query execution. Together, we analyze query plan Web view that highlights where random walks succeeded or failed. We deduce a better join order, emphasizing the benefits of S-AQP for this first use case.

Afterwards, we further show the advantages of pay-as-you-go approaches by starting and stopping the query execution multiple times until reaching the 60 seconds timeout mark of public SPARQL endpoints. The Web client manages to receive and aggregate incoming data, thus providing an estimate of the expected number of results. The cardinality estimation view allows users to observe the accuracy evolution over time. The estimates and confidence intervals converge towards the actual number of results of her query. This demonstrates the approximate aggregations use case [ 6 ] that proves useful for numerous other use cases such as exploratory queries [ 1 ].

Finally, we show that RAW-JENA returns both failed and succeeded random walks along with their probability of being drawn which enables use cases such as the computation of knowledge graph embeddings [ 4 ], or summaries [ 7 ].

3. Conclusion

S-AQP has many important use cases crucial for building and maintaining ecosystems of public SPARQL endpoints. RAW-JENA demonstrates the feasibility of implementing S-AQP on a representative SPARQL endpoint: Apache Jena. As each random walk is independent and enjoys a logarithmic upper bound on its time complexity, users can collect and merge samples across multiple executions of the same query. Such a pay-as-you-go approach perfectly fits the fair-use policies of public SPARQL endpoints.

In future works, we plan to support full SPARQL queries and to show how the SPARQL standard could evolve to integrate sampling as SQL did with the TABLESAMPLE clause.

Acknowledgments

This work is supported by the French ANR project DeKaloG (Decentralized Knowledge Graphs) ANR-19-CE23-0014, and the French Labex CominLabs project MiKroloG (The Microdata Knowledge Graph).

References

[1] S. Agarwal , H. Milner , A. Kleiner , A. Talwalkar , M. I. Jordan , S. Madden , B. Mozafari , I. Stoica , Knowing when you're wrong: Building fast and reliable approximate query processing systems , in: International Conference on Management of Data, SIGMOD , 2014 .

[2] A. Soulet , F. M. Suchanek , Anytime large-scale analytics of Linked Open Data , in: 18th International Semantic Web Conference, ISWC, 2019 .

[3] J. Debattista , S. Londoño , C. Lange , S. Auer , Quality assessment of linked datasets using probabilistic approximation , in: 12th European Semantic Web Conference on The Semantic Web. Latest Advances and New Domains , 2015 .

[4] P. Ristoski , H. Paulheim, RDF2Vec: RDF graph embeddings for data mining , in: 15th International Semantic Web Conference , ISWC, 2016 .

[5] V. Leis , B. Radke , A. Gubichev , A. Kemper , T. Neumann, Cardinality estimation done right: Index-based join sampling , in: Cidr , 2017 .

[6] Y. Wang , A. Khan , X. Xu , S. Ye , S. Pan , Y. Zhou , Approximate and interactive processing of aggregate queries on knowledge graphs: A demonstration , in: 31st ACM International Conference on Information & Knowledge Management , 2022 .

[7] L. Heling , M. Acosta , Estimating characteristic sets for RDF dataset profiles based on sampling , in: The Semantic Web: 17th International Conference, ESWC , 2020 .

[8] F. Li , B. Wu , K. Yi , Z. Zhao , Wander Join and XDB: online aggregation via random walks , ACM Transactions Database Systems ( 2019 ).

[9] Y. Park , S. Ko , S. S. Bhowmick , K. Kim , K. Hong , W. Han, G -CARE: A framework for performance benchmarking of cardinality estimation techniques for subgraph matching , in: International Conference on Management of Data, SIGMOD , 2020 .

[10] R. Angles , C. B. Aranda , A. Hogan , C. Rojas , D. Vrgoč, WDBench: A Wikidata graph query benchmark , in: International Semantic Web Conference, 2022 .

[11] J. Aimonier-Davat , H. Skaf-Molli , P. Molli , M.-H. Dang , B. Nédelec , Join ordering of SPARQL property path queries , in: The Semantic Web: 20th International Conference, ESWC , 2023 .