Abstract
Ontology-Mediated Query Answering (OMQA) is a well-established framework to answer queries over an rdfs or owl Knowledge Base (KB). OMQA was originally designed for unions of conjunctive queries (UCQs), and based on certain answers. More recently, OMQA has been extended to sparql queries, but to our knowledge, none of the efforts made in this direction (either in the literature, or the so-called sparql entailment regimes) is able to capture both certain answers for UCQs and the standard interpretation of sparql over a plain graph. We formalize these as requirements to be met by any semantics aiming at conciliating certain answers and sparql answers, and define three additional requirements, which generalize to KBs some basic properties of sparql answers. Then we show that a semantics can be defined that satisfies all requirements for sparql queries with SELECT, UNION, and OPTIONAL, and for DLs with the canonical model property. We also investigate combined complexity for query answering under such a semantics over \(\textit{DL-Lite}_{\mathcal {R}}\) KBs. In particular, we show for different fragments of sparql that known upper-bounds for query answering over a plain graph are matched.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
This is without loss of expressivity, but normalization may cause an exponential blowup.
References
Ahmetaj, S., Fischl, W., Pichler, R., Šimkus, M., Skritek, S.: Towards reconciling SPARQL and certain answers. In: Proceedings of the 24th International Conference on World Wide Web, pp. 23–33. ACM (2015)
Arenas, M., Pérez, J.: Querying semantic web data with SPARQL. In: Proceedings of the Thirtieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 305–316. ACM (2011)
Artale, A., Calvanese, D., Kontchakov, R., Zakharyaschev, M.: The DL-Lite family and relations. J. Artif. Intell. Res. 36, 1–69 (2009)
Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P. (eds.): The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, Cambridge (2003)
Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Tractable reasoning and efficient query answering in description logics: the DL-Lite family. J. Autom. Reason. 39(3), 385–429 (2007)
Glimm, B., Ogbuji, C.: SPARQL 1.1 entailment regimes. Technical report, W3C, March 2013
Gutierrez, C., Hernández, D., Hogan, A., Polleres, A.: Certain answers for SPARQL? In: AMW (2016)
Harris, S., Seaborne, A., Prud’hommeaux, E.: SPARQL 1.1 query language. W3C recommendation, W3C (2013)
Hernández, D., Gutierrez, C., Hogan, A.: Certain answers for SPARQL with blank nodes. In: Vrandečić, D., et al. (eds.) ISWC 2018. LNCS, vol. 11136, pp. 337–353. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-00671-6_20
Kontchakov, R., Rezk, M., Rodríguez-Muro, M., Xiao, G., Zakharyaschev, M.: Answering SPARQL queries over databases under OWL 2 QL entailment regime. In: Mika, P., et al. (eds.) ISWC 2014. LNCS, vol. 8796, pp. 552–567. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-11964-9_35
Kostylev, E.V., Cuenca Grau, B.: On the semantics of SPARQL queries with optional matching under entailment regimes. In: Mika, P., et al. (eds.) ISWC 2014. LNCS, vol. 8797, pp. 374–389. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-11915-1_24
Letelier, A., Pérez, J., Pichler, R., Skritek, S.: Static analysis and optimization of semantic web queries. ACM Trans. Database Syst. (TODS) 38(4), 25 (2013)
Mengel, S., Skritek, S.: On tractable query evaluation for SPARQL. arXiv preprint arXiv:1712.08939 (2017)
Pérez, J., Arenas, M., Gutierrez, C.: Semantics and complexity of SPARQL. ACM Trans. Database Syst. (TODS) 34(3), 16 (2009)
Schmidt, M., Meier, M., Lausen, G.: Foundations of SPARQL query optimization. In: Proceedings of the 13th International Conference on Database Theory, pp. 4–33. ACM (2010)
Xiao, G., et al.: Ontology-based data access: a survey. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-18, International Joint Conferences on Artificial Intelligence Organization, pp. 5511–5519, July 2018
Acknowledgments
This research has been partially supported by the EU H2020 project INODE, by the Italian PRIN project HOPE, and by the Free University of Bozen-Bolzano through the projects QUADRO, KGID and GeoVKG.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Corman, J., Xiao, G. (2020). Certain Answers to a sparql Query over a Knowledge Base. In: Wang, X., Lisi, F., Xiao, G., Botoeva, E. (eds) Semantic Technology. JIST 2019. Lecture Notes in Computer Science(), vol 12032. Springer, Cham. https://doi.org/10.1007/978-3-030-41407-8_21
Download citation
DOI: https://doi.org/10.1007/978-3-030-41407-8_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-41406-1
Online ISBN: 978-3-030-41407-8
eBook Packages: Computer ScienceComputer Science (R0)