Please use this identifier to cite or link to this item: https://research.matf.bg.ac.rs/handle/123456789/1310
Title: Solving the SPARQL query containment problem with SpeCS
Authors: Spasić, Mirko 
Vujošević Janičić, Milena 
Affiliations: Informatics and Computer Science 
Informatics and Computer Science 
Keywords: FOL modeling;Query containment;SMT solving;SPARQL;SpeCS solver
Issue Date: 1-Apr-2023
Rank: М22
Publisher: Elsevier
Journal: Journal of Web Semantics
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.
URI: https://research.matf.bg.ac.rs/handle/123456789/1310
ISSN: 15708268
DOI: 10.1016/j.websem.2022.100770
Rights: Attribution-NonCommercial-NoDerivs 3.0 United States
Appears in Collections:Research outputs

Files in This Item:
File Description SizeFormat Existing users please
Solving the SPARQL query containment problem with SpeCS.pdf1.61 MBAdobe PDF
Embargoed until April 30, 2025    Request a copy
Show full item record

Page view(s)

23
checked on Dec 24, 2024

Download(s)

1
checked on Dec 24, 2024

Google ScholarTM

Check

Altmetric

Altmetric


This item is licensed under a Creative Commons License Creative Commons