SpeCS - An Efficient and Comprehensive SPARQL Query Containment Solver

Tracking #: 2667-3881

This paper is currently under review
Authors: 
Mirko Spasić
Milena Vujošević Janičić

Responsible editor: 
Guest Editors Web of Data 2020

Submission type: 
Full Paper
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 optimization. In this paper, we present a new approach for solving the query containment problem in SPARQL. It is based on reducing the query containment problem to the satisfiability problem in first order logic. It covers a wide range of 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 relevant benchmarks, Query Containment Benchmark and SQCFramework. The evaluation shows that SpeCS is highly efficient and that compared to state-of-the-art solvers, it gives more precise results, and in a shorter amount of time. In addition, SpeCS has the highest coverage of supported language constructs.
Full PDF Version: 
Tags: 
Under Review