Acknowledgment

This work was supported by National Natural Science Foundation of China (Grant No. 61502336) and National Key Research and Development Program of China (Grant No. 2016YFB1000603).

Supplement

Appendix: Preliminaries and Proofs.

References

[1] Prudhommeaux E, Seaborne A. SPARQL query language for RDF. W3C Recommendation. 2008. https://www.w3.org/TR/rdf-sparql-query/. Google Scholar http://scholar.google.com/scholar_lookup?title=Prudhommeaux E, Seaborne A. SPARQL query language for RDF. W3C Recommendation. 2008. https://www.w3.org/TR/rdf-sparql-query/&

[2] Angles R, Gutierrez C. The expressive power of SPARQL. In: Proceedings of the 7th International Conference on the Semantic Web, Karlsruhe, 2008. 114--129. Google Scholar http://scholar.google.com/scholar_lookup?title=Angles R, Gutierrez C. The expressive power of SPARQL. In: Proceedings of the 7th International Conference on the Semantic Web, Karlsruhe, 2008. 114--129&

[3] Pérez J, Arenas M, Gutierrez C. Semantics and complexity of SPARQL. ACM Trans Database Syst, 2009, 34: 1--45. Google Scholar http://scholar.google.com/scholar_lookup?title=Pérez J, Arenas M, Gutierrez C. Semantics and complexity of SPARQL. ACM Trans Database Syst, 2009, 34: 1--45&

[4] Zhang X, Van den Bussche J. On the primitivity of operators in SPARQL. Inf Process Lett, 2014, 114: 480-485 CrossRef Google Scholar http://scholar.google.com/scholar_lookup?title=On the primitivity of operators in SPARQL&author=Zhang X&author=Van den Bussche J&publication_year=2014&journal=Inf Process Lett&volume=114&pages=480-485

[5] Kontchakov R, Kostylev E. On expressibility of non-monotone operators in SPARQL. In: Proceedings of International Conference Principles of Knowledge Representation and Reasoning (KR-16), Cape Town, 2016. 369--379. Google Scholar http://scholar.google.com/scholar_lookup?title=Kontchakov R, Kostylev E. On expressibility of non-monotone operators in SPARQL. In: Proceedings of International Conference Principles of Knowledge Representation and Reasoning (KR-16), Cape Town, 2016. 369--379&

[6] Zhang X, Van den Bussche J, Picalausa F. On the Satisfiability Problem for SPARQL Patterns. jair, 2016, 56: 403-428 CrossRef Google Scholar http://scholar.google.com/scholar_lookup?title=On the Satisfiability Problem for SPARQL Patterns&author=Zhang X&author=Van den Bussche J&author=Picalausa F&publication_year=2016&journal=jair&volume=56&pages=403-428

[7] Arenas M, Gutierrez C, Miranker D P. Querying semantic data on the web?. SIGMOD Rec, 2013, 41: 6-17 CrossRef Google Scholar http://scholar.google.com/scholar_lookup?title=Querying semantic data on the web?&author=Arenas M&author=Gutierrez C&author=Miranker D P&publication_year=2013&journal=SIGMOD Rec&volume=41&pages=6-17

[8] Kaminski M, Kostylev E. Beyond well-designed SPARQL. In: Proceedings of International Conference on Database Theory (ICDT-16), Bordeaux, 2016. Google Scholar http://scholar.google.com/scholar_lookup?title=Kaminski M, Kostylev E. Beyond well-designed SPARQL. In: Proceedings of International Conference on Database Theory (ICDT-16), Bordeaux, 2016&

[9] Zhang X W, Van den Bussche J, Wang K, et al. On the satisfiability problem of patterns in SPARQL 1.1. In: Proceedings of AAAI Conference on Artificial Intelligence (AAAI-18), New Orleans, 2018. 2054--2061. Google Scholar http://scholar.google.com/scholar_lookup?title=Zhang X W, Van den Bussche J, Wang K, et al. On the satisfiability problem of patterns in SPARQL 1.1. In: Proceedings of AAAI Conference on Artificial Intelligence (AAAI-18), New Orleans, 2018. 2054--2061&