Compiling model representations for querying large ABoxes in expressive DLs
Pages 1691 - 1698
Abstract
Answering ontology mediated queries (OMQs) has received much attention in the last decade, but the big gap between practicable algorithms for lightweight ontologies, that are supported by implemented reasoners, and purely theoretical algorithms for expressive ontologies that are not amenable to implementation, has only increased. Towards narrowing the gap, we propose an algorithm to compile a representation of sets of models for ALCHI ontologies, which is sufficient for answering any monotone query. Rather than reasoning for specific ABoxes, or being fully data-independent, we use generic descriptions of families of ABoxes, given by what we call profiles. Our model compilation algorithm runs on TBoxes and sets of profiles, and supports the incremental addition of new profiles. To illustrate the potential of our approach for OMQ answering, we implement a rewriting into an extension of Datalog for OMQs comprising reachability queries, and provide some promising evaluation results.
References
[1]
Shqiponja Ahmetaj, Magdalena Ortiz, and Mantas Simkus. Polynomial datalog rewritings for expressive description logics with closed predicates. In IJCAI 2016, USA, 2016.
[2]
Franz Baader. The description logic handbook: theory, implementation, and applications. Cambridge university press, 2003.
[3]
Labinot Bajraktari, Magdalena Ortiz, and Mantas Simkus. Clopen knowledge bases: Combining description logics and answer set programming. In Proceedings of DL2017, Montpellier, France, 2017.
[4]
Meghyn Bienvenu, Diego Calvanese, Magdalena Ortiz, and Mantas Šimkus. Nested regular path queries in description logics. AAAI Press, 2014.
[5]
Meghyn Bienvenu, Balder ten Cate, Carsten Lutz, and Frank Wolter. Ontology-based data access: A study through disjunctive datalog, CSP, and MMSNP. ACM Trans. Database Syst., 39(4):33:1-33:44, 2014.
[6]
Meghyn Bienvenu, Magdalena Ortiz, and Mantas Simkus. Regular path queries in lightweight description logics: Complexity and algorithms. J. Artif. Intell. Res., 53:315-374, 2015.
[7]
Meghyn Bienvenu, Magdalena Ortiz, and Mantas Šimkus. Regular path queries in lightweight description logics: Complexity and algorithms. J. Artif. Intell. Res. (JAIR), 53:315-374, 2015.
[8]
Gerhard Brewka, Thomas Eiter, and Miroslaw Truszczynski. Answer set programming at a glance. Commun. ACM, 54(12):92-103, 2011.
[9]
Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. Rewriting of regular expressions and regular path queries. J. Comput. Syst. Sci., 64(3):443-465, 2002.
[10]
Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. Reasoning on regular path queries. SIGMOD Record, 32(4):83-92, 2003.
[11]
Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. Dl-lite: Tractable description logics for ontologies. In In AAAI/IAAI 2005, USA, 2005.
[12]
Diego Calvanese, Giuseppe De Giacomo, and Maurizio Lenzerini. Conjunctive query containment and answering under description logic constraints. ACM Trans. Comput. Log., 9(3), 2008.
[13]
Diego Calvanese, Thomas Eiter, and Magdalena Ortiz. Answering regular path queries in expressive description logics via alternating tree-automata. Inf. Comput., 237:12-55, 2014.
[14]
Thomas Eiter, Magdalena Ortiz, and Mantas Šimkus. Conjunctive query answering in the description logic SH using knots. J. Comput. Syst. Sci., (1), 2012.
[15]
Thomas Eiter, Magdalena Ortiz, Mantas Šimkus, Trung-Kien Tran, and Guohui Xiao. Query rewriting for Horn-SHIQ plus rules. AAAI Press, 2012.
[16]
Martin Gebser, Benjamin Kaufmann, Roland Kaminski, Max Ostrowski, Torsten Schaub, and Marius Thomas Schneider. Potassco: The potsdam answer set solving collection. AI Commun., 24(2):107-124, 2011.
[17]
Michael Gelfond and Vladimir Lifschitz. The stable model semantics for logic programming. In Proc. of ICLP/SLP 1988, pages 1070-1080. MIT Press, 1988.
[18]
Birte Glimm, Ian Horrocks, Boris Motik, Giorgos Stoilos, and Zhe Wang. Hermit: An OWL 2 reasoner. J. Autom. Reasoning, 53(3):245-269, 2014.
[19]
Birte Glimm, Yevgeny Kazakov, and Trung-Kien Tran. Ontology materialization by abstraction refinement in horn SHOIF. In In AAAI 2017, USA, 2017.
[20]
Víctor Gutiérrez-Basulto, Yazmin Angélica Ibáñez-García, Roman Kontchakov, and Egor V. Kostylev. Queries with negation and inequalities over lightweight ontologies. J. Web Sem., 35:184-202, 2015.
[21]
Ullrich Hustadt, Boris Motik, and Ulrike Sattler. A decomposition rule for decision procedures by resolution-based calculi. In LPAR 2004, Uruguay, 2004.
[22]
Carsten Lutz. The complexity of conjunctive query answering in expressive description logics. volume 5195 of LNCS, pages 179-193. Springer, 2008.
[23]
Magdalena Ortiz, Sebastian Rudolph, and Mantas Simkus. Query answering in the Horn fragments of the description logics SHOIQ and SROIQ. In IJCAI 2011, Spain, 2011.
[24]
Héctor Pérez-Urbina, Boris Motik, and Ian Horrocks. Tractable query answering and rewriting under description logic constraints. J. Applied Logic, 8(2):186-209, 2010.
[25]
Mariano Rodriguez-Muro, Roman Kontchakov, and Michael Zakharyaschev. Ontology-based data access: Ontop of databases. volume 8218 of LNCS, pages 558-573. Springer, 2013.
[26]
Riccardo Rosati and Alessandro Almatelli. Improving query answering over dl-lite ontologies. In KR 2010, Canada. AAAI Press, 2010.
[27]
Evren Sirin, Bijan Parsia, Bernardo Cuenca Grau, Aditya Kalyanpur, and Yarden Katz. Pellet: A practical OWL-DL reasoner. J. Web Sem., 5(2):51-53, 2007.
[28]
Giorgio Stefanoni, Boris Motik, Markus Krötzsch, and Sebastian Rudolph. The complexity of answering conjunctive and navigational queries over OWL 2 EL knowledge bases. J. Artif. Intell. Res. (JAIR), 51:645-705, 2014.
[29]
Andreas Steigmiller, Thorsten Liebig, and Birte Glimm. Konclude: System description. J. Web Sem., 27:78-85, 2014.
- Compiling model representations for querying large ABoxes in expressive DLs
Recommendations
Querying Large and Expressive Biomedical Ontologies
HPCC-CSS-ICESS '15: Proceedings of the 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security, and 2015 IEEE 12th International Conf on Embedded Software and SystemsReal-world biomedical ontologies like the Foundational Model of Anatomy (FMA) are often of large size and can fall in the category of OWL 2 Full. Meta-modeling is commonly adopted in the FMA with most of its classes and roles also specified as ...
Expressive Languages for Querying the Semantic Web
Best of PODS 2017, Best of ICDT 2017 and Regular PapersThe problem of querying RDF data is a central issue for the development of the Semantic Web. The query language SPARQL has become the standard language for querying RDF since its W3C standardization in 2008. However, the 2008 version of this language ...
Expressive languages for querying the semantic web
PODS '14: Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systemsThe problem of querying RDF data is a central issue for the development of the Semantic Web. The query language SPARQL has become the standard language for querying RDF, since its standardization in 2008. However, the 2008 version of this language ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- Adobe
- IBMR: IBM Research
- ERICSSON
- Microsoft: Microsoft
- AI Journal: AI Journal
Publisher
AAAI Press
Publication History
Published: 13 July 2018
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 21 Nov 2024