Cooperative Techniques for SPARQL Query Relaxation in RDF Databases

This paper addresses the problem of failing \(\mathtt {RDF}\) queries. Query relaxation is one of the cooperative techniques that allows providing users with alternative answers instead of an empty result. While previous works on query relaxation over \(\mathtt {RDF}\) data have focused on defining new relaxation operators, we investigate in this paper techniques to find the parts of an \(\mathtt {RDF}\) query that are responsible of its failure. Finding such subqueries, named Minimal Failing Subqueries (\(\mathtt {MFSs}\)), is of great interest to efficiently perform the relaxation process. We propose two algorithmic approaches for computing \(\mathtt {MFSs}\). The first approach (\(\mathtt {LBA}\)) intelligently leverages the subquery lattice of the initial \(\mathtt {RDF}\) query while the second approach (\(\mathtt {MBA}\)) is based on a particular matrix that improves the performance of \(\mathtt {LBA}\). Our approaches also compute a particular kind of relaxed RDF queries, called Ma x imal Succeeding Subqueries (\(\mathtt {XSSs}\)). \(\mathtt {XSSs}\) are subqueries with a maximal number of triple patterns of the initial query. To validate our approaches, a set of thorough experiments is conducted on the \(\mathtt {LUBM}\) benchmark and a comparative study with other approaches is done.