Abstract
We present the Emi reasoner, based on a new interpretation of the tableau algorithm for reasoning with Description Logics with unique performance characteristics and specialized advantages. Emi turns the tableau inside out, solving the satisfiability problem by adding elements to expressions rather than adding expressions to element node labels. This strategy is inspired by decidable reasoning algorithms for Horn Logics and \(\mathcal{E}\mathcal{L}^{++}\) that run on a loop rather than recursive graph-based strategies used in a tableau reasoner. Because Emi solves the same problem there will be a simple correspondence with tableaux, yet it will feel very different during execution, since the problem is inverted. This inversion makes possible many unique and straightforward optimizations, such as paralellization of many parts of the reasoning task, concurrent ABox expansion, and localized blocking techniques. Each of these optimizations contains a design trade-off that allows Emi to perform extremely well in certain cases, such as instance retrieval, and not as well in others. Our initial evaluations show that even a naive and largely un-optimized implementation of Emi is performant with popular reasoners running on the JVM such as Hermit, Pellet, and jFact.
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.
We refer to properties as roles, unless a distinction is relevant, as this is the standard description logic term. These include both object properties and data properties.
- 2.
Eager Materializing and Iterating Logical Inference Algorithm.
- 3.
When we say ���new element’ this is equivalent to a fresh element symbol. It is written this way because we are avoiding terminology that refers to an infinite set of names and instead refer to what a program really does here, i.e. create something new.
- 4.
Hermit Version 1.4.5.519.
- 5.
Openllet Version 2.6.5.
- 6.
jFact Version 5.0.3.
- 7.
- 8.
Raw data and charts are available for inspection https://tinyurl.com/kgswc2023.
References
Baader, F., Calvanese, D., McGuinness, D., Patel-Schneider, P., Nardi, D.: The Description Logic Handbook: Theory, Implementation and Applications. Cambridge University Press, Cambridge (2003)
Eberhart, A., Hitzler, P.: A functional API for OWL. In: Taylor, K.L., Gonçalves, R.S., Lécué, F., Yan, J. (eds.) Proceedings of the ISWC 2020 Demos and Industry Tracks: From Novel Ideas to Industrial Practice co-located with 19th International Semantic Web Conference (ISWC 2020), Globally online, November 1-6, 2020 (UTC). CEUR Workshop Proceedings, vol. 2721, pp. 315–320. CEUR-WS.org (2020). http://ceur-ws.org/Vol-2721/paper580.pdf
Eberhart, A., Shimizu, C., Chowdhury, S., Sarker, M.K., Hitzler, P.: Expressibility of OWL axioms with patterns. In: Verborgh, R., et al. (eds.) ESWC 2021. LNCS, vol. 12731, pp. 230–245. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77385-4_14
Glimm, B., Horrocks, I., Motik, B., Stoilos, G., Wang, Z.: hermit: an owl 2 reasoner. J. Autom. Reason. 53(3), 245–269 (2014). https://doi.org/10.1007/s10817-014-9305-1, https://doi.org/10.1007/s10817-014-9305-1
Horridge, M., Bechhofer, S.: The OWL API: a java API for working with OWL 2 ontologies. In: Proceedings of the 6th International Conference on OWL: Experiences and Directions, vol. 529, pp. 49–58. OWLED 2009, CEUR-WS.org, Aachen, DEU (2009)
Horrocks, I., Kutz, O., Sattler, U.: The even more irresistible sroiq. In: Proceedings of the Tenth International Conference on Principles of Knowledge Representation and Reasoning, pp. 57–67. KR’06, AAAI Press (2006)
Sirin, E., Parsia, B., Grau, B.C., Kalyanpur, A., Katz, Y.: Pellet: a practical owl-dl reasoner. Web Semant. 5(2), 51–53 (2007). https://doi.org/10.1016/j.websem.2007.03.004
Tsarkov, D., Horrocks, I.: FaCT++ description logic reasoner: system description. In: Furbach, U., Shankar, N. (eds.) IJCAR 2006. LNCS (LNAI), vol. 4130, pp. 292–297. Springer, Heidelberg (2006). https://doi.org/10.1007/11814771_26
Acknowledgement
This material is based upon work supported by the Air Force Office of Scientific Research under award number FA9550-18-1-0386.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Eberhart, A., Zalewski, J., Hitzler, P. (2023). Should I Stay or Should I Go. In: Ortiz-Rodriguez, F., Villazón-Terrazas, B., Tiwari, S., Bobed, C. (eds) Knowledge Graphs and Semantic Web. KGSWC 2023. Lecture Notes in Computer Science, vol 14382. Springer, Cham. https://doi.org/10.1007/978-3-031-47745-4_2
Download citation
DOI: https://doi.org/10.1007/978-3-031-47745-4_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-47744-7
Online ISBN: 978-3-031-47745-4
eBook Packages: Computer ScienceComputer Science (R0)