SPARQL Rewriting: Towards Desired Results

Recent years witnessed the emergence of various applications on knowledge graphs, which are often represented as RDF graphs. However, due to the lack of data schema and the complexity of SPARQL language, there is usually a gap between the user's real desire and the actual meaning of a SPARQL query, especially when the query itself is complicated. In this paper, we try to narrow this gap by modifying a given query with a set of modifiers, so that its result approaches a user-provided example set. Specifically, we model this problem as two individual sub-problems, query-restricting, and query-relaxing, both of which are shown to be NP-hard. We further prove that unless P=NP, query-restricting has no polynomial-time approximation scheme (PTAS), and query-relaxing has no polynomial-time constant-factor approximation algorithm. Despite their hardness, we propose a (1-1/ε)-approximation method for query-restricting and 2 heuristics for query-relaxing. Extensive experiments have been conducted on real-world knowledge graphs to evaluate the effectiveness and efficiency of our proposed solutions.