Project

General

Profile

Actions

QaRS System Documentation

This project implements two main functionnalities:
  • It gives explanation for the failure of a SPARQL query;
  • It performs relaxation of a SPARQL query in order to return top-k alternative answers.
The explanation functionnality of QaRS returns the following subqueries:
  • Minimal Failing Subqueries (MFSs). Each MFS is a minimal part of a SPARQL query that fails;
  • MaXimal Succeeding Subqueries (XSSs). Each XSS is a maximal (in terms of triple patterns) non-failing subquery viewed as a relaxed query.
These MFSs and XSSs can be computed with two algorithms (for details, please see our publications):
  • Lattice-Based Approach (LBA);
  • Matrice-Based Approach (MBA).
The following four algorithms are implemented to obtain top-k alternative answers. They use different levels of information about the MFSs to speed up the relaxation process (again, please see our publications for details).
  • Best first Search (BFS) Algorithm (A related work algorithm).
  • MFS-Based Search (MBS) Algorithm.
  • Optimized MFS-Based Search (O-MBS) Algorithm.
  • Full MFS-Based Search (F-MBS) Algorithm.

Software requirements

  • Java version >= 7.
  • An integrated development environment (i.e. Eclipse: https://eclipse.org/downloads/).
  • All operating systems that support at least the Java 7 version.

Download

QaRS System can be downloaded at http://forge.lias-lab.fr/projects/qars/files

The archive file (qars.zip) is composed of:
  • qars-dist.jar: a jar file that contains both the QaRS binary code and all required dependencies (i.e. Jena).
  • lubm1.owl: a data set file generated with the Lehigh University Benchmark (LUBM).
  • univ-bench.owl: a file that contains the LUBM ontology available on the Lehigh University Benchmark web site (http://swat.cse.lehigh.edu/projects/lubm/).

Classpath Initialization instructions

  • Create a Java project from your favorite IDE (i.e. QaRSSample).
  • Copy qars-dist.jar file into the root of your Java project.
  • Add qars-dist.jar file to the classpath.

Step 0: Data Initialization instructions (Mandatory before any experiment)

  • Copy lubm1.owl data set file into a directory named "lubm" (i.e. c:/lubm/lubm1.owl).
  • Copy the univ-bench.owl file into the previous directory (i.e. c:/lubm/univ-bench.owl).
  • Create a snippet class (i.e. QARSInitializationSample) with a Java main method and fill it with the following code.
public class QARSInitializationSample {
    public static void main(String[] args) {
        String[] params = new String[5];
        params[0] = "c:/lubm"; // Data folder
        params[1] = "OWL";
        params[2] = "TDB";
        params[3] = "c:/tdbrepository-saturated"; // TDB repository path
        params[4] = "true"; // Enable RDFS entailment
        JenaBulkLoader.main(params);
    }
}

Step 1: Using the LBA and MBA Algorithms

  • Create a snippet class (i.e. QARSMFSComputeSample) with a Java main method and fill it with the following code.
  • Initialize QaRS session and the query.
public class QARSMFSComputeSample {
    public static void main(String[] args) {
        Session session = SessionFactory.getTDBSession("c:/tdbrepository-saturated");

        String QUERY_2 = "PREFIX base: <http://www.lehigh.edu/~zhp2/2004/0401/univ-bench.owl> " 
        + "PREFIX ub:   <http://swat.cse.lehigh.edu/onto/univ-bench.owl#> " 
        + "PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#> " 
        + "PREFIX rdf:  <http://www.w3.org/1999/02/22-rdf-syntax-ns#> " 
        + "PREFIX owl:  <http://www.w3.org/2002/07/owl#> " 
        + "PREFIX xdt:  <http://www.w3.org/2001/XMLSchema#> " 
        + "SELECT ?X ?Y1 ?Y2 ?Y3 ?Y4 ?Y5 " 
        + "WHERE { ?X rdf:type ub:UndergraduateStudent . " 
        + "?X ub:memberOf ?Y1 . " 
        + "?X ub:mastersDegreeFrom <http://www.University822.edu>  . " 
        + "?X ub:emailAddress ?Y2 . " 
        + "?X ub:advisor <http://www.Department0.University0.edu/FullProfessor0> . " 
        + "?X ub:takesCourse ?Y4. " 
        + "?X ub:name ?Y5  . " 
        + " }";
  • Instructions to compute the MFSs and XSSs with the Lattice-Based Approach (LBA).
        CQuery conjunctiveQuery = CQueryFactory.createCQuery(QUERY_2);
        MFSSearch relaxationStrategy = StrategyFactory.getLatticeStrategy(session, conjunctiveQuery);
        List<CQuery> allMFS = relaxationStrategy.getAllMFS();
        List<CQuery> allXSS = relaxationStrategy.getAllXSS();
  • Instructions to compute the MFSs and XSSs with the Matrice-Based Approach (MBA). Use only this approach for star-shaped queries.
        CQuery conjunctiveQuery = CQueryFactory.createCQuery(QUERY_2);
        MFSSearch relaxationStrategy = StrategyFactory.getMatrixStrategy(session, conjunctiveQuery);
        List<CQuery> allMFS = relaxationStrategy.getAllMFS();
        List<CQuery> allXSS = relaxationStrategy.getAllXSS();
    }
}

Step 2: Using the BFS, MBS, O-MBS and F-MBS Algorithms

  • Create a snippet class (i.e. QARSRelaxationSample) with a Java main method and fill it with the following code.
public class QARSRelaxationSample {
    public static void main(String[] args) {
        Session session = SessionFactory.getTDBSession("c:/tdbrepository-saturated");

        String QUERY_2 = "PREFIX base: <http://www.lehigh.edu/~zhp2/2004/0401/univ-bench.owl> " 
        + "PREFIX ub:   <http://swat.cse.lehigh.edu/onto/univ-bench.owl#> " 
        + "PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#> " 
        + "PREFIX rdf:  <http://www.w3.org/1999/02/22-rdf-syntax-ns#> " 
        + "PREFIX owl:  <http://www.w3.org/2002/07/owl#> " 
        + "PREFIX xdt:  <http://www.w3.org/2001/XMLSchema#> " 
        + "SELECT ?X ?Y1 ?Y2 ?Y3 ?Y4 ?Y5 " 
        + "WHERE { ?X rdf:type ub:UndergraduateStudent . " 
        + "?X ub:memberOf ?Y1 . " 
        + "?X ub:mastersDegreeFrom <http://www.University822.edu>  . " 
        + "?X ub:emailAddress ?Y2 . " 
        + "?X ub:advisor <http://www.Department0.University0.edu/FullProfessor0> . " 
        + "?X ub:takesCourse ?Y4. " 
        + "?X ub:name ?Y5  . " 
        + " }";

        final int TOP_K = 50; 
  • Initialize the list for retrieving relaxed solutions.
        final LinkedHashMap<String, Double> solutions = new LinkedHashMap<String, Double>(TOP_K);
  • Create CQuery object with QUERY_2 and a RelaxationStrategy object. This relaxation strategy is MBS (MFS-based Search).
        CQuery conjunctiveQuery = CQueryFactory.createCQuery(QUERY_2);
        RelaxationStrategy relaxedQuery = new MFSBaseRelaxationStrategy(conjunctiveQuery, session);
  • Use the following code to get a maximum of k alternative answers
        while ((!hasTopk)&&(relaxedQuery.hasNext())){
        QueryStatement stm = session.createStatement(relaxedQuery.next().toString());

        ResultSet results = (ResultSet) stm.executeQuery();
        double sim = relaxedQuery.getCurrentSimilarity();
        while ((results.hasNext()) && (solutions.size() < TOP_K)) {
            QuerySolution sol = results.nextSolution();
            if(!solutions.keySet().contains(sol.toString())){
                solutions.put(sol.toString(), sim);
            }
        }

        hasTopk = solutions.size() >= TOP_K;
    }
}

Remarks

  • As relaxation strategy, Qars implements four differents algorithms with different performance. For using these algorithms you have to change the following instruction.
RelaxationStrategy relaxedQuery = new MFSBaseRelaxationStrategy(conjunctiveQuery, session);
  • by one of these other instructions
1- RelaxationStrategy relaxedQuery = new BasicRelaxationStrategy(conjunctiveQuery, session); // BFS
2- RelaxationStrategy relaxedQuery = new MFSBaseOptimizedRelaxationStrategy(conjunctiveQuery, session); // O-MBS
3- RelaxationStrategy relaxedQuery = new IncrementalMFSBaseRelaxationStrategy(conjunctiveQuery, session); // F-MBS

Results

  • With all the previous relaxation strategies, we obtain the following results for Query_2 (all the results are associated with a score)
( ?Y4 = <http://www.Department10.University0.edu/GraduateCourse24> ) ( ?Y5 = "GraduateStudent93" ) ( ?Y2 = "GraduateStudent93@Department10.University0.edu" ) ( ?X = <http://www.Department10.University0.edu/GraduateStudent93> ) ( ?Y1 = <http://www.Department10.University0.edu> )---->0.5914630829395665
( ?Y4 = <http://www.Department10.University0.edu/GraduateCourse39> ) ( ?Y5 = "GraduateStudent93" ) ( ?Y2 = "GraduateStudent93@Department10.University0.edu" ) ( ?X = <http://www.Department10.University0.edu/GraduateStudent93> ) ( ?Y1 = <http://www.Department10.University0.edu> )---->0.5914630829395665
( ?Y4 = <http://www.Department10.University0.edu/GraduateCourse12> ) ( ?Y5 = "GraduateStudent93" ) ( ?Y2 = "GraduateStudent93@Department10.University0.edu" ) ( ?X = <http://www.Department10.University0.edu/GraduateStudent93> ) ( ?Y1 = <http://www.Department10.University0.edu> )---->0.5914630829395665
( ?Y4 = <http://www.Department0.University0.edu/GraduateCourse59> ) ( ?Y5 = "GraduateStudent48" ) ( ?Y2 = "GraduateStudent48@Department0.University0.edu" ) ( ?X = <http://www.Department0.University0.edu/GraduateStudent48> ) ( ?Y1 = <http://www.Department0.University0.edu> )---->0.5613006264956873
( ?Y4 = <http://www.Department10.University0.edu/GraduateCourse24> ) ( ?Y5 = "GraduateStudent93" ) ( ?Y2 = rdfs:Resource ) ( ?X = <http://www.Department10.University0.edu/GraduateStudent93> ) ( ?Y1 = <http://www.Department10.University0.edu> )---->0.394308721959711
( ?Y4 = <http://www.Department10.University0.edu/GraduateCourse24> ) ( ?Y5 = "GraduateStudent93" ) ( ?Y2 = <http://swat.cse.lehigh.edu/onto/univ-bench.owl#Person> ) ( ?X = <http://www.Department10.University0.edu/GraduateStudent93> ) ( ?Y1 = <http://www.Department10.University0.edu> )---->0.394308721959711
( ?Y4 = <http://www.Department10.University0.edu/GraduateCourse24> ) ( ?Y5 = "GraduateStudent93" ) ( ?Y2 = <http://swat.cse.lehigh.edu/onto/univ-bench.owl#Student> ) ( ?X = <http://www.Department10.University0.edu/GraduateStudent93> ) ( ?Y1 = <http://www.Department10.University0.edu> )---->0.394308721959711
( ?Y4 = <http://www.Department10.University0.edu/GraduateCourse24> ) ( ?Y5 = "GraduateStudent93" ) ( ?Y2 = _:b0 ) ( ?X = <http://www.Department10.University0.edu/GraduateStudent93> ) ( ?Y1 = <http://www.Department10.University0.edu> )---->0.394308721959711
( ?Y4 = <http://www.Department10.University0.edu/GraduateCourse24> ) ( ?Y5 = "GraduateStudent93" ) ( ?Y2 = <http://swat.cse.lehigh.edu/onto/univ-bench.owl#GraduateStudent> ) ( ?X = <http://www.Department10.University0.edu/GraduateStudent93> ) ( ?Y1 = <http://www.Department10.University0.edu> )---->0.394308721959711
( ?Y4 = <http://www.Department10.University0.edu/GraduateCourse24> ) ( ?Y5 = "GraduateStudent93" ) ( ?Y2 = _:b1 ) ( ?X = <http://www.Department10.University0.edu/GraduateStudent93> ) ( ?Y1 = <http://www.Department10.University0.edu> )---->0.394308721959711

Publications

  • Géraud FOKOU, Stéphane JEAN, Allel HADJALI, Mickael BARON, RDF Query Relaxation Strategies Based on Failure Causes, In Proceedings of the 13th Extended Semantic Web Conference (ESWC 2016).
  • Géraud FOKOU, Stéphane JEAN, Allel HADJALI, Mickael BARON, Handling failing RDF queries: from diagnosis to relaxation, In Knowledge and Information Systems (KAIS),2016. [[http://link.springer.com/article/10.1007/s10115-016-0941-0]]
  • Géraud FOKOU, Stéphane JEAN, Allel HADJALI, Mickael BARON, Cooperative Techniques for SPARQL Query Relaxation in RDF Databases, In Proceedings of the 12th Extended Semantic Web Conference (ESWC 2015).
  • Géraud FOKOU, Stéphane JEAN, Allel HADJALI, Mickael BARON, Cooperative Techniques for SPARQL Query Relaxation in RDF Databases, Technical Report available at Report_MFS_XSS.pdf

Historic Contributors

Code analysis

  • Lines of Code: 7 253
  • Programming Language: Java

Updated by Mickael BARON over 4 years ago · 208 revisions