SPARQL Rewriting: Towards Desired Results

CategoryPublications 226

Authors: Xun Jian, Yue Wang, Xiayu Lei, Libin Zheng, Lei Chen

Name of Conference: ACM Conference on Management of Data(SIGMOD 2020), June 14-19, 2020, Portland Oregon, USA

Date of Publication: June 14, 2020


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.

View Full Text

Keywords2020Data qualitySIGMODYue Wang Previous: Next: