Abstract
In ontology-mediated query answering, access to incomplete data sources is mediated by a conceptual layer constituted by an ontology, which can be formulated in a description logic (DL) or using existential rules. In the literature, there exists a multitude of complex techniques for incorporating ontological knowledge into queries. However, few of these approaches were designed for explainability of the query answers. We tackle this challenge by adapting an existing proof framework toward conjunctive query answering, based on the notion of universal models. We investigate the data and combined complexity of determining the existence of a proof below a given quality threshold, which can be measured in different ways. By distinguishing various parameters such as the shape of the query, we obtain an overview of the complexity of this problem for several Horn DLs.
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.
- 2.
This derivation structure is uniquely determined except for the names of the vertices, which are irrelevant for our purposes since we use only their labels.
- 3.
Unary encoding of n would make the problem much easier due to imposing a small (polynomial) upper bound on the (domain/tree) size of proofs. Hence, binary encoding puts more emphasis on the impact of the KB and the query on the decision problem.
- 4.
A subproof S of a hypergraph H is a subgraph of H that is a proof s.t. the leaves of S are a subset of the leaves of H.
References
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases (1995)
Alrabbaa, C., Baader, F., Borgwardt, S., Dachselt, R., Koopmann, P., Méndez, J.: Evonne: interactive proof visualization for description logics (system description). In: IJCAR (2022). https://doi.org/10.1007/978-3-031-10769-6_16
Alrabbaa, C., Baader, F., Borgwardt, S., Koopmann, P., Kovtunova, A.: Finding small proofs for description logic entailments: theory and practice. In: LPAR-23 (2020). https://doi.org/10.29007/nhpp
Alrabbaa, C., Baader, F., Borgwardt, S., Koopmann, P., Kovtunova, A.: On the complexity of finding good proofs for description logic entailments. In: DL Workshop (2020). http://ceur-ws.org/Vol-2663/paper-1.pdf
Alrabbaa, C., Baader, F., Borgwardt, S., Koopmann, P., Kovtunova, A.: Finding good proofs for description logic entailments using recursive quality measures. In: CADE (2021). https://doi.org/10.1007/978-3-030-79876-5_17
Alrabbaa, C., Borgwardt, S., Koopmann, P., Kovtunova, A.: Explaining ontology-mediated query answers using proofs over universal models (technical report) (2022). https://doi.org/10.48550/ARXIV.2208.14381
Alrabbaa, C., Borgwardt, S., Koopmann, P., Kovtunova, A.: Finding good proofs for answers to conjunctive queries mediated by lightweight ontologies. In: DL Workshop (2022). http://ceur-ws.org/Vol-3263/paper-3.pdf
Alrabbaa, C., Hieke, W., Turhan, A.: Counter model transformation for explaining non-subsumption in EL. In: Workshop on Formal and Cognitive Reasoning (2021). http://ceur-ws.org/Vol-2961/paper_2.pdf
Baader, F., Horrocks, I., Lutz, C., Sattler, U.: An Introduction to Description Logic (2017). https://doi.org/10.1017/9781139025355
Baader, F., Peñaloza, R., Suntisrivaraporn, B.: Pinpointing in the description logic \(\cal{EL} ^+\). In: Annual German Conference on AI (KI) (2007). https://doi.org/10.1007/978-3-540-74565-5_7
Borgida, A., Calvanese, D., Rodriguez-Muro, M.: Explanation in the DL-Lite family of description logics. In: On the Move to Meaningful Internet Systems: OTM (2008). https://doi.org/10.1007/978-3-540-88873-4_35
Borgida, A., Franconi, E., Horrocks, I.: Explaining \(\cal{ALC} \) subsumption. In: ECAI (2000). http://www.frontiersinai.com/ecai/ecai2000/pdf/p0209.pdf
Bourgaux, C., Ozaki, A., Peñaloza, R., Predoiu, L.: Provenance for the description logic ELHr. In: IJCAI (2020). https://doi.org/10.24963/ijcai.2020/258
Calì, A., Gottlob, G., Lukasiewicz, T.: A general datalog-based framework for tractable query answering over ontologies. J. Web Semant. (2012). https://doi.org/10.1016/j.websem.2012.03.001
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. (2007). https://doi.org/10.1007/s10817-007-9078-x
Calvanese, D., Lanti, D., Ozaki, A., Peñaloza, R., Xiao, G.: Enriching ontology-based data access with provenance. In: IJCAI (2019). https://doi.org/10.24963/ijcai.2019/224
Calvanese, D., Ortiz, M., Simkus, M., Stefanoni, G.: The complexity of explaining negative query answers in DL-Lite. In: KR (2012). http://www.aaai.org/ocs/index.php/KR/KR12/paper/view/4537
Carral, D., Dragoste, I., Krötzsch, M.: The combined approach to query answering in Horn-\(\cal{ALCHOIQ} \). In: KR (2018). https://aaai.org/ocs/index.php/KR/KR18/paper/view/18076
Ceylan, İ.İ., Lukasiewicz, T., Malizia, E., Molinaro, C., Vaicenavicius, A.: Explanations for negative query answers under existential rules. In: KR (2020). https://doi.org/10.24963/kr.2020/23
Croce, F., Lenzerini, M.: A framework for explaining query answers in DL-Lite. In: Faron Zucker, C., Ghidini, C., Napoli, A., Toussaint, Y. (eds.) EKAW 2018. LNCS (LNAI), vol. 11313, pp. 83–97. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03667-6_6
Elhalawati, A., Krötzsch, M., Mennicke, S.: An existential rule framework for computing why-provenance on-demand for datalog. In: Governatori, G., Turhan, A.-Y. (eds.) RuleML+RR 2022, LNCS, vol. 13752, pp. 146–163. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-21541-4_10
Horridge, M.: Justification based explanation in ontologies. Ph.D. thesis, University of Manchester, UK (2011). https://www.research.manchester.ac.uk/portal/files/54511395/FULL_TEXT.PDF
Horridge, M., Parsia, B., Sattler, U.: Justification oriented proofs in OWL. In: ISWC (2010). https://doi.org/10.1007/978-3-642-17746-0_23
Kazakov, Y., Klinov, P., Stupnikov, A.: Towards reusable explanation services in protege. In: DL Workshop (2017). http://www.ceur-ws.org/Vol-1879/paper31.pdf
Kazakov, Y., Krötzsch, M., Simančík, F.: The Incredible ELK. J. Autom. Reason. 53(1), 1–61 (2013). https://doi.org/10.1007/s10817-013-9296-3
Koopmann, P.: Signature-based abduction with fresh individuals and complex concepts for description logics. In: IJCAI (2021). https://doi.org/10.24963/ijcai.2021/266
Krötzsch, M., Rudolph, S., Hitzler, P.: Complexities of horn description logics. ACM Trans. Comput. Logic (2013). https://doi.org/10.1145/2422085.2422087
Marnette, B.: Generalized schema-mappings: from termination to tractability. In: PODS (2009). https://doi.org/10.1145/1559795.1559799
McGuinness, D.L.: Explaining reasoning in description logics. Ph.D. thesis, Rutgers University, USA (1996). https://doi.org/10.7282/t3-q0c6-5305
Ortiz, M., Rudolph, S., Simkus, M.: Worst-case optimal reasoning for the Horn-DL fragments of OWL 1 and 2. In: KR (2010). http://aaai.org/ocs/index.php/KR/KR2010/paper/view/1296
Ortiz, M., Rudolph, S., Simkus, M.: Query answering in the Horn fragments of the description logics \(\cal{SHOIQ} \) and \(\cal{SROIQ} \). In: IJCAI (2011). https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-178
Peñaloza, R.: Axiom-pinpointing in description logics and beyond. Ph.D. thesis, Technische Universität Dresden, Germany (2009). https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa-24743
Ramusat, Y., Maniu, S., Senellart, P.: Efficient provenance-aware querying of graph databases with datalog. In: GRADES-NDA ACM Workshop (2022). https://doi.org/10.1145/3534540.3534689
Rosati, R.: On conjunctive query answering in EL. In: DL Workshop (2007). http://ceur-ws.org/Vol-250/paper_83.pdf
Schlobach, S., Cornet, R.: Non-standard reasoning services for the debugging of description logic terminologies. In: IJCAI (2003). http://ijcai.org/Proceedings/03/Papers/053.pdf
Stefanoni, G.: Explaining query answers in lightweight ontologies. Diploma thesis, Technische Universität Wien, Austria (2011). http://www.cs.ox.ac.uk/files/7942/thesis.pdf
Acknowledgments
This work was supported by the DFG grant 389792660 as part of TRR 248 – CPEC (https://perspicuous-computing.science), and QuantLA, GRK 1763 (https://lat.inf.tu-dresden.de/quantla).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Alrabbaa, C., Borgwardt, S., Koopmann, P., Kovtunova, A. (2022). Explaining Ontology-Mediated Query Answers Using Proofs over Universal Models. In: Governatori, G., Turhan, AY. (eds) Rules and Reasoning. RuleML+RR 2022. Lecture Notes in Computer Science, vol 13752. Springer, Cham. https://doi.org/10.1007/978-3-031-21541-4_11
Download citation
DOI: https://doi.org/10.1007/978-3-031-21541-4_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-21540-7
Online ISBN: 978-3-031-21541-4
eBook Packages: Computer ScienceComputer Science (R0)