Caching Experiment for Link Traversal Based Query Execution

Olaf Hartig
Database and Information System Research Group
Department of Computer Science
Humboldt-Universität zu Berlin

This page provides everything that is necessary to reproduce the caching experiments of our LDOW 2011 submission; this includes the query templates, the actual SPARQL queries, and the software used to run our experiments. Furthermore, we provide all our measurements. The content provided on this page is licensed under the Creative Commons Attribution-Share Alike 3.0 License.

Queries

The experiments are based on the following five types of SPARQL queries:

Type Description Query Template
Contact Queries of this type ask for various properties of a user's acquaintances. queryContactInfo.template
UnsetProps Queries of this type ask for properties from the FOAF vocabulary that are specified by acquaintances of a user, restricted to properties that are not specified for the user. queryUnsetProps.template
Incoming Queries of this type ask for "incoming contacts" of a user; i.e. persons who know the user that are not listed to be known by the user. queryIncoming.template
2ndDegree1 Queries of this type ask for persons commonly known by two distinct acquaintances of a user, restricted to persons who are not listed to be known by the user. query2ndDegree1.template
2ndDegree2 Queries of this type ask for common "incoming contacts" for two distinct acquaintances of a user, restricted to "incoming contacts" who are not listed to be known by the user. query2ndDegree2.template

We instantiated the templates for these five query types to create the following 115 SPARQL queries for 23 people:

Person URI Queries
http://apassant.net/alex Contact query, UnsetProps query, Incoming query, 2ndDegree1 query, 2ndDegree2 query
http://www.anjeve.de/foaf.rdf#AnjaJentzsch Contact query, UnsetProps query, Incoming query, 2ndDegree1 query, 2ndDegree2 query
http://axel.deri.ie/~axepol/foaf.rdf#me Contact query, UnsetProps query, Incoming query, 2ndDegree1 query, 2ndDegree2 query
http://ben.adida.net/card.xhtml#i Contact query, UnsetProps query, Incoming query, 2ndDegree1 query, 2ndDegree2 query
http://www.semantic-web.at/people/blumauer/card#me Contact query, UnsetProps query, Incoming query, 2ndDegree1 query, 2ndDegree2 query
http://danbri.org/foaf.rdf#danbri Contact query, UnsetProps query, Incoming query, 2ndDegree1 query, 2ndDegree2 query
http://danny.ayers.name/index.rdf#me Contact query, UnsetProps query, Incoming query, 2ndDegree1 query, 2ndDegree2 query
http://bigasterisk.com/foaf.rdf#drewp Contact query, UnsetProps query, Incoming query, 2ndDegree1 query, 2ndDegree2 query
http://inkdroid.org/ehs Contact query, UnsetProps query, Incoming query, 2ndDegree1 query, 2ndDegree2 query
http://eyaloren.org/foaf.rdf#me Contact query, UnsetProps query, Incoming query, 2ndDegree1 query, 2ndDegree2 query
http://bblfish.net/people/henry/card#me Contact query, UnsetProps query, Incoming query, 2ndDegree1 query, 2ndDegree2 query
http://web.mit.edu/jambo/www/foaf.rdf#jambo Contact query, UnsetProps query, Incoming query, 2ndDegree1 query, 2ndDegree2 query
http://www.cs.rpi.edu/~hendler/foaf.rdf#jhendler Contact query, UnsetProps query, Incoming query, 2ndDegree1 query, 2ndDegree2 query
http://presbrey.mit.edu/foaf.rdf#presbrey Contact query, UnsetProps query, Incoming query, 2ndDegree1 query, 2ndDegree2 query
http://people.csail.mit.edu/lkagal/foaf#me Contact query, UnsetProps query, Incoming query, 2ndDegree1 query, 2ndDegree2 query
http://www.leobard.net/rdf/foaf.xml#me Contact query, UnsetProps query, Incoming query, 2ndDegree1 query, 2ndDegree2 query
http://mmt.me.uk/foaf.rdf#mischa Contact query, UnsetProps query, Incoming query, 2ndDegree1 query, 2ndDegree2 query
http://people.apache.org/~oshani/foaf.rdf#me Contact query, UnsetProps query, Incoming query, 2ndDegree1 query, 2ndDegree2 query
http://teole.jfouffa.org/People/Teole/card.rdf#me Contact query, UnsetProps query, Incoming query, 2ndDegree1 query, 2ndDegree2 query
http://homepages.cwi.nl/~troncy/troncyr-foaf.rdf#rt Contact query, UnsetProps query, Incoming query, 2ndDegree1 query, 2ndDegree2 query
http://inamidst.com/sbp/foaf#Sean Contact query, UnsetProps query, Incoming query, 2ndDegree1 query, 2ndDegree2 query
http://www.uni-koblenz.de/~sschenk/foaf.rdf#me Contact query, UnsetProps query, Incoming query, 2ndDegree1 query, 2ndDegree2 query
http://moustaki.org/foaf.rdf#moustaki Contact query, UnsetProps query, Incoming query, 2ndDegree1 query, 2ndDegree2 query

A ZIP file with all the queries is here: queries.zip.

Software

We executed the queries using the Semantic Web Client Library (SWClLib). SWClLib is a prototype of a query engine that implements our link traversal based query execution paradigm using an iterator based implementation approach. SWClLib is part of NG4J, a Named Graphs API for Jena. For the experiments we used an improved version of NG4J release 0.9.3. The source code for this improved version is here: ng4j-0.9.4-SNAPSHOT.zip.

The tool to execute the experiments, including the source code, is available here: CacheExperiment.zip. Notice, this software is Free Software, licensed under the GNU General Public License (GPL), version 3.

Measurements

Here are CSV files with the measurements from our experiments:

The columns in these CSV files represent:

  1. experiment name
  2. query number
  3. query name
  4. number of results returned
  5. overall query execution time
  6. number of RDF graphs retrieved during the query execution
  7. number RDF graphs that the graph cache contained after query execution
  8. hit rate