{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T06:50:28Z","timestamp":1772607028881,"version":"3.50.1"},"reference-count":43,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2022,5,16]],"date-time":"2022-05-16T00:00:00Z","timestamp":1652659200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,1,20]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Nominal schemas have been proposed as an extension to Description Logics (DL), the knowledge representation paradigm underlying the Web Ontology Language (OWL). They provide for a very tight integration of DL and rules. Nominal schemas can be understood as syntactic sugar on top of OWL. However, this naive perspective leads to inefficient reasoning procedures. In order to develop an efficient reasoning procedure for the language ${\\mathcal {E}\\mathcal {L}\\mathcal {V}^{++}}$, which results from extending the OWL profile language OWL EL with nominal schemas, we propose a transformation from ${\\mathcal {E}\\mathcal {L}\\mathcal {V}^{++}}$ ontologies into Datalog-like rule programs that can be used for satisfiability checking and assertion retrieval. The use of this transformation enables the use of powerful Datalog engines to solve reasoning tasks over ${\\mathcal {E}\\mathcal {L}\\mathcal {V}^{++}}$ ontologies. We implement and then evaluate our approach on several real-world, data-intensive ontologies, and find that it can outperform state-of-the-art reasoners such as Konclude and ELK. As a lesser side result we also provide a self-contained description of a rule-based algorithm for ${\\mathcal {E}\\mathcal {L}^{++}}$, which does not require a normal form transformation.<\/jats:p>","DOI":"10.1093\/logcom\/exac032","type":"journal-article","created":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T19:14:42Z","timestamp":1648581282000},"page":"136-162","source":"Crossref","is-referenced-by-count":2,"title":["An efficient algorithm for reasoning over OWL EL ontologies with nominal schemas"],"prefix":"10.1093","volume":"33","author":[{"given":"David","family":"Carral","sequence":"first","affiliation":[{"name":"LIRMM, Inria , University of Montpellier, CNRS, 161 Rue Ada, 34095, Montpellier, France"}]},{"given":"Joseph","family":"Zalewski","sequence":"additional","affiliation":[{"name":"Data Semantics Laboratory , Department of Computer Science, Kansas State University, 1701D Platt St., Manhattan, KS 66506, USA"}]},{"given":"Pascal","family":"Hitzler","sequence":"additional","affiliation":[{"name":"Data Semantics Laboratory , Department of Computer Science, Kansas State University, 1701D Platt St., Manhattan, KS 66506, USA"}]}],"member":"286","published-online":{"date-parts":[[2022,5,16]]},"reference":[{"key":"2023022314480965300_","volume-title":"Foundations of Databases","author":"Abiteboul","year":"1995"},{"key":"2023022314480965300_","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511711787","volume-title":"The Description Logic Handbook: Theory, Implementation, and Applications","author":"Baader","year":"2007"},{"key":"2023022314480965300_","first-page":"364","article-title":"Pushing the $\\mathcal {E}\\mathcal {L}$ envelope","volume-title":"Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005)","author":"Baader","year":"2005"},{"key":"2023022314480965300_","article-title":"Pushing the $\\mathcal {E}\\mathcal {L}$ envelope further","volume-title":"Proceedings of the 4th OWLED Workshop on OWL: Experiences and Directions. CEUR","author":"Baader","year":"2008"},{"key":"2023022314480965300_","first-page":"339","article-title":"The combined approach to query answering in Horn","volume-title":"Proceedings of the 16th International Conference on Principles of Knowledge Representation and Reasoning (KR 2018)","author":"Carral","year":"2018"},{"key":"2023022314480965300_","first-page":"2736","article-title":"From Horn-SRIQ to Datalog: a data-independent transformation that preserves assertion entailment","volume-title":"Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI 2019)","author":"Carral","year":"2019"},{"key":"2023022314480965300_","first-page":"345","article-title":"Extending description logic rules","volume-title":"The Semantic Web: Research and Applications: 9th Extended Semantic Web Conference, ESWC 2012, Heraklion, Crete, Greece, May 27\u201331, 2012. Proceedings","author":"Carral Mart\u00ednez","year":"2012"},{"key":"2023022314480965300_","article-title":"Reconciling OWL and rules","volume-title":"Technical Report","author":"Carral","year":"2011"},{"key":"2023022314480965300_","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/978-3-642-39666-3_6","article-title":"Towards an efficient algorithm to reason over Description Logics extended with nominal schemas","volume-title":"Proceedings of the 7th International Conference on Web Reasoning and Rule Systems (RR 2013)","author":"Carral","year":"2013"},{"key":"2023022314480965300_","volume-title":"Owl 2 Web Ontology Language Tractable Fragments","author":"Cuenca Grau"},{"key":"2023022314480965300_","first-page":"2971","article-title":"The combined approach to query answering beyond the OWL 2 profiles","volume-title":"Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015)","author":"Feier","year":"2015"},{"key":"2023022314480965300_","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1016\/j.websem.2005.06.005","article-title":"LUBM: a benchmark for OWL knowledge base systems","volume":"3","author":"Guo","year":"2005","journal-title":"Journal of Web Semantics"},{"key":"2023022314480965300_","volume-title":"OWL 2 Web Ontology Language: Primer (Second Edition)","author":"Hitzler"},{"key":"2023022314480965300_","doi-asserted-by":"crossref","DOI":"10.1201\/9781420090512","volume-title":"Foundations of Semantic Web Technologies","author":"Hitzler","year":"2009"},{"key":"2023022314480965300_","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/978-3-540-92673-3_5","article-title":"Ontologies and rules","volume-title":"Handbook on Ontologies","author":"Hitzler","year":"2009"},{"key":"2023022314480965300_","doi-asserted-by":"crossref","first-page":"11","DOI":"10.3233\/SW-2011-0025","article-title":"The OWL API: a java API for OWL ontologies","volume":"2","author":"Horridge","year":"2011","journal-title":"Journal of Web Semantics"},{"key":"2023022314480965300_","volume-title":"SWRL: A Semantic Web Rule Language","author":"Horrocks"},{"key":"2023022314480965300_","first-page":"57","article-title":"The even more irresistible","volume-title":"Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR 2006)","author":"Horrocks","year":"2006"},{"key":"2023022314480965300_","volume-title":"Saturation-Based Decision Procedures for Extensions of the Guarded Fragment","author":"Kazakov","year":"2006"},{"key":"2023022314480965300_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10817-013-9296-3","article-title":"The incredible ELK","volume":"53","author":"Kazakov","year":"2014","journal-title":"Journal of Automated Reasoning"},{"key":"2023022314480965300_","volume-title":"RIF Overview (Second Edition)","author":"Kifer","year":"2013"},{"key":"2023022314480965300_","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/978-3-642-33203-6_20","article-title":"Recent advances in integrating OWL and rules (technical communication)","volume-title":"Web Reasoning and Rule Systems: 6th International Conference, RR 2012, Vienna, Austria, September 10\u201312, 2012. Proceedings","author":"Knorr","year":"2012"},{"key":"2023022314480965300_","first-page":"474","article-title":"Reconciling OWL and non-monotonic rules for the Semantic Web","volume-title":"Proceedings of the 20th European Conference on Artificial Intelligence (ECAI 2012). Frontiers in Artificial Intelligence and Applications","author":"Knorr","year":"2012"},{"key":"2023022314480965300_","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1007\/978-3-642-33203-6_22","article-title":"A tableau algorithm for description logics with nominal schema","volume-title":"Web Reasoning and Rule Systems: 6th International Conference, RR 2012, Vienna, Austria, September 10\u201312, 2012. Proceedings","author":"Krisnadhi","year":"2012"},{"key":"2023022314480965300_","first-page":"382","article-title":"OWL and rules","volume-title":"Reasoning Web. Semantic Technologies for the Web of Data. 7th International Summer School 2011, Tutorial Lectures","author":"Krisnadhi","year":"2011"},{"key":"2023022314480965300_","volume-title":"Description Logic Rules, Studies on the Semantic Web","author":"Kr\u00f6tzsch","year":"2010"},{"key":"2023022314480965300_","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1007\/978-3-540-88564-1_41","article-title":"ELP: tractable rules for OWL 2","volume-title":"The Semantic Web\u2014ISWC 2008","author":"Kr\u00f6tzsch","year":"2008"},{"key":"2023022314480965300_","first-page":"2668","article-title":"Efficient rule-based inferencing for OWL EL","volume-title":"Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011)","author":"Kr\u00f6tzsch","year":"2011"},{"key":"2023022314480965300_","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1145\/1963405.1963496","article-title":"A better uncle for OWL: nominal schemas for integrating rules and ontologies","volume-title":"Proceedings of the 20th International Conference on World Wide Web (WWW 2011)","author":"Kr\u00f6tzsch","year":"2011"},{"key":"2023022314480965300_","article-title":"Nominal schemas in Description Logics: complexities clarified","volume-title":"Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR 2014)","author":"Kr\u00f6tzsch","year":"2014"},{"key":"2023022314480965300_","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1145\/1150402.1150479","article-title":"Sampling from large graphs","volume-title":"Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Leskovec","year":"2006"},{"key":"2023022314480965300_","volume-title":"OWL 2 Web Ontology Language: Profiles","author":"Motik","year":"2009"},{"key":"2023022314480965300_","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.websem.2005.05.001","article-title":"Query answering for OWL-DL with rules","volume":"3","author":"Motik","year":"2005","journal-title":"Journal of Web Semantics"},{"key":"2023022314480965300_","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1613\/jair.2811","article-title":"Hypertableau reasoning for Description Logics","volume":"36","author":"Motik","year":"2009","journal-title":"Journal of Artificial Intelligence Research"},{"key":"2023022314480965300_","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1007\/s10817-017-9406-8","article-title":"The OWL reasoner evaluation (ORE) 2015 competition report","volume":"59","author":"Parsia","year":"2017","journal-title":"Journal of Automated Reasoning"},{"key":"2023022314480965300_","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/j.websem.2007.03.004","article-title":"Pellet: a practical OWL-DL reasoner","volume":"5","author":"Sirin","year":"2007","journal-title":"Journal of Web Semantics"},{"key":"2023022314480965300_","article-title":"Nominal schema absorption","volume-title":"Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013)","author":"Steigmiller","year":"2013"},{"key":"2023022314480965300_","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/s10817-014-9310-4","article-title":"Reasoning with nominal schemas through absorption","volume":"53","author":"Steigmiller","year":"2014","journal-title":"Journal of Automated Reasoning"},{"key":"2023022314480965300_","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1016\/j.websem.2014.06.003","article-title":"Konclude: system description","volume":"27","author":"Steigmiller","year":"2014","journal-title":"Journal of Web Semantics"},{"key":"2023022314480965300_","first-page":"258","article-title":"Column-oriented datalog materialization for large knowledge graphs","volume-title":"Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI 2016)","author":"Urbani","year":"2016"},{"key":"2023022314480965300_","doi-asserted-by":"crossref","first-page":"680","DOI":"10.1007\/978-3-319-94205-6_44","article-title":"Efficient model construction for Horn Logic with VLog","volume-title":"Automated Reasoning: 9th International Joint Conference, IJCAR 2018, Held as Part of the Federated Logic Conference, FloC 2018, Oxford, UK, July 14\u201317, 2018, Proceedings","author":"Urbani","year":"2018"},{"key":"2023022314480965300_","first-page":"1","article-title":"A resolution procedure for Description Logics with nominal schemas","volume-title":"Semantic Technology","author":"Wang","year":"2012"},{"key":"2023022314480965300_","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1613\/jair.4757","article-title":"PAGOdA: pay-as-you-go ontology query answering using a Datalog reasoner","volume":"54","author":"Zhou","year":"2015","journal-title":"Journal of Artificial Intelligence Research"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/33\/1\/136\/49314376\/exac032.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/33\/1\/136\/49314376\/exac032.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,19]],"date-time":"2023-11-19T11:20:19Z","timestamp":1700392819000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/33\/1\/136\/6585765"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,16]]},"references-count":43,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,5,16]]},"published-print":{"date-parts":[[2023,1,20]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exac032","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,1]]},"published":{"date-parts":[[2022,5,16]]}}}