Estimating the Cost of Link Traversal-based Execution of SPARQL Queries

This library provides a set of methods that allow estimating the cost of executing a SPARQL query through zero-knowledge link traversal.

Brief description of our four cost estimation methods.

Each method below extends its previous method.

1. Method 1 - No prior knowledge
   Estimate the query cost execution without assuming anything about its predicates.
2. Method 2 - Known predicate bindings
   Estimate the query cost execution by taking into consideration known predicates with their average object and subject bindings.
3. Method 3 - Star-shaped Joins
   Estimate the query cost execution by extending Method 2 and taking into consideration cost limiting star-shaped joins.
4. Method 4 - Filters
   Estimate the query cost execution by extending Method 3 by considering SPARQL filter clauses.

Brief description of JAVA packages and classes:

Package 'costEstimationMethods'

The four cost estimation methods as described above.

Package 'ldaq'

Code for checking whether a SPARQL query is linked-data answerable as well as transforming it to its equivalent SPARQL-LD query that evaluates the query through zero-knowledge link traversal.
See LDaQ.

Package 'predicateStats'

Mainly used for Method 2.
Code we used to work with predicates such as getting their average subject bindings.

Package 'util'

Scripts and helpful code used in our work.

• BindPair.java A Simple pair of doubles.
• ChangeCostJsonFolder.java Script for changing the values of a folder of QueryWrapper.java files, like our ground_truth folder.
• CompareCostEstimations.java Compare all methods in package costEstimationMethods.
• FilterLogFile.java Deal with big log file of SPARQL queries.
• FindOptimalFactor.java Find the optimal factor of Method 3 or Method 4.
• QueryCostDatabase.java Build a database from QueryWrapper.java files.
• QueryWrapper.java Store interesting data relating to a Query, its execution and cost estimating methods.
• SplitDataset.java What we used to split the dataset into two in order to base optimizations on one half and run tests on the other avoiding any biases.
• TSV.java Code for dealing with tsv formatting.

Dataset Description

We provide a complete dataset, with results and our ground-truth

• ground_truth folder contains:

  • all_queries.7z All the queries we gathered, in .json files. Each .json file is serialized in QueryWrapper.java and contains the following fields:

    1. a unique query id
    2. the SPARQL query
    3. its equivalent SPARQL-LD query
    4. the query pattern
    5. the real cost we got when executing the query (see timestamp below)
    6. the method 1 cost estimation
    7. the method 2 cost estimation
    8. the method 3 cost estimation
    9. the method 4 cost estimation
    10. the timestamp of our real cost execution
    11. a list of all the uris that were access during the execution

  • ground_truth.tsv a tab-separated file containing all queries. Each line represents a different query and contains the following:

    1. a unique query id
    2. the SPARQL query
    3. Its equivalent SPARQL-LD query
    4. The real cost

• results

We calculated the accuracy of our methods using different queries (non-biased) from the ones we optimized the methods for (biased).

Each file below contains the following columns:

1. a unique query id
2. the SPARQL query
3. The estimated cost of Method 1
4. The estimated cost of Method 2
5. The estimated cost of Method 3
6. The estimated cost of Method 4

The folder contains the following files:

• QueryCostDatabase_OnlyMethod3Queries.tsv Accuracy of Method 3 on queries with star-shaped joins.
• QueryCostDatabase_OnlyMethod4Queries.tsv Accuracy of Method 4 on queries with filters.
• QueryCostDatabase_OnlyMethod4Queries_strict.tsv Accuracy of Method 4 on queries with filter clauses AND star-shaped joins.
• QueryCostDatabase.tsv Comparing all of our methods on our non-biased queries.

External Dependencies

• Apache Jena 3.16.0 Work with SPARQL queries
• Json Build Json objects, used in DbpediaPredicateAverageHttp.java
• Gson Serialize Java objects into json files, used in QueryWrapper.java

Acknowledgements

This work has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 890861 (Project ReKnow).