Solving the SPARQL query containment problem with SpeCS

Abstract

The query containment problem is a fundamental computer science problem which was originally defined for relational queries. With the growing popularity of the SPARQL query language, it became relevant and important in this new context: reliable and efficient SPARQL query containment solvers may have various applications within static analysis of queries, especially in the area of query optimizations and refactoring. In this paper, we present a new approach for solving the query containment problem in SPARQL. The approach is based on reducing the query containment problem to the satisfiability problem in first order logic. It covers a wide range of the SPARQL language constructs, including union of conjunctive queries, blank nodes, projections, subqueries, clauses from, filter, optional, graph, etc. It also covers containment under RDF schema entailment regime, and it can deal with the subsumption relation. We describe an implementation of the approach, an open source solver SPECS and its thorough experimental evaluation on two relevant benchmarks, Query Containment Benchmark and SQCFramework. As a side result, SPECS identified incorrect test cases within both benchmarks, which were manually checked, confirmed and fixed, resulting in better and more reliable benchmarks. The evaluation also shows that SPECS is highly efficient and that compared to the state-of-the-art solvers, it gives more precise results in a shorter amount of time. In addition, SPECS has the highest coverage of the supported language constructs.