{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,20]],"date-time":"2025-10-20T10:27:20Z","timestamp":1760956040739,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,6,21]],"date-time":"2020-06-21T00:00:00Z","timestamp":1592697600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,6,21]],"date-time":"2020-06-21T00:00:00Z","timestamp":1592697600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["Consolidator Grant 647289"],"award-info":[{"award-number":["Consolidator Grant 647289"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["K\u00fcnstl Intell"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>An ontology-mediated query (OMQ) consists of a database query paired with an ontology. When evaluated on a database, an OMQ returns not only the answers that are already in the database, but also those answers that can be obtained via logical reasoning using rules from ontology. There are many open questions regarding the complexities of problems related to OMQs. Motivated by the use of ontologies in practice, new reasoning problems which have never been considered in the context of ontologies become relevant, since they can improve the usability of ontology enriched systems. This thesis deals with various reasoning problems that emerge from ontology-mediated querying and it investigates the computational complexity of these problems. We focus on ontologies formulated in Horn description logics, which are a popular choice for ontologies in practice. In particular, the thesis gives results regarding the data complexity of OMQ evaluation by completely classifying complexity and rewritability questions for OMQs based on an EL ontology and a conjunctive query. Furthermore, the query-by-example problem, and the expressibility and verification problem in ontology-based data access are introduced and investigated.<\/jats:p>","DOI":"10.1007\/s13218-020-00674-7","type":"journal-article","created":{"date-parts":[[2020,6,21]],"date-time":"2020-06-21T05:02:37Z","timestamp":1592715757000},"page":"533-537","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Ontology-Mediated Querying with Horn Description Logics"],"prefix":"10.1007","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8051-5749","authenticated-orcid":false,"given":"Leif","family":"Sabellek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,6,21]]},"reference":[{"key":"674_CR1","doi-asserted-by":"crossref","unstructured":"Arenas M, Diaz GI, Kostylev EV (2016) Reverse engineering sparql queries. In: Proceedings of WWW, pp. 239\u2013249.","DOI":"10.1145\/2872427.2882989"},{"key":"674_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1613\/jair.2820","volume":"36","author":"A Artale","year":"2009","unstructured":"Artale A, Calvanese D, Kontchakov R, Zakharyaschev M (2009) The dl-lite family and relations. J Artif Intell Res 36:1\u201369","journal-title":"J Artif Intell Res"},{"key":"674_CR3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511711787","volume-title":"The description logic handbook: theory, implementation, and applications","author":"F Baader","year":"2007","unstructured":"Baader F, Calvanese D, McGuinness DL, Nardi D, Patel-Schneider PF (2007) The description logic handbook: theory, implementation, and applications, 2nd edn. Cambridge University Press, Cambridge","edition":"2"},{"key":"674_CR4","doi-asserted-by":"publisher","DOI":"10.1017\/9781139025355","volume-title":"An introduction to description logics","author":"F Baader","year":"2017","unstructured":"Baader F, Horrocks I, Lutz C, Sattler U (2017) An introduction to description logics. Cambride University Press, Cambridge"},{"key":"674_CR5","unstructured":"Barcel\u00f3 P, Romero M (2017) The complexity of reverse engineering problems for conjunctive queries. In: Proceedings of ICDT."},{"issue":"4","key":"674_CR6","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/2661643","volume":"39","author":"M Bienvenu","year":"2014","unstructured":"Bienvenu M, Cate B, Lutz C, Wolter F (2014) Ontology-based data access: a study through disjunctive datalog, CSP, and MMSNP. ACM Trans Database Syst 39(4):33\u201344","journal-title":"ACM Trans Database Syst"},{"key":"674_CR7","unstructured":"Bienvenu M, Lutz C, Wolter F (2013) First order-rewritability of atomic queries in horn description logics. In: Proceedings of IJCAI, IJCAI\/AAAI, pp. 754\u2013760."},{"key":"674_CR8","unstructured":"Bonifati A, Ciucanu R, Lemay A (2015) Learning path queries on graph databases. In: Proceedings of EDBT, pp. 109\u2013120."},{"issue":"4","key":"674_CR9","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/2818637","volume":"40","author":"A Bonifati","year":"2016","unstructured":"Bonifati A, Ciucanu R, Staworko S (2016) Learning join queries from user examples. ACM Trans Database Syst 40(4):24\u201338","journal-title":"ACM Trans Database Syst"},{"key":"674_CR10","doi-asserted-by":"crossref","unstructured":"Bulatov AA (2017) A dichotomy theorem for nonuniform csps. In: Proceedings of FOCS, pp. 319\u2013330.","DOI":"10.1109\/FOCS.2017.37"},{"key":"674_CR11","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.artint.2012.10.003","volume":"195","author":"D Calvanese","year":"2013","unstructured":"Calvanese D, De Giacomo G, Lembo D, Lenzerini M, Rosati R (2013) Data complexity of query answering in description logics. Artif Intell 195:335\u2013360","journal-title":"Artif Intell"},{"key":"674_CR12","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.artint.2012.08.002","volume":"193","author":"A Cal\u00ed","year":"2012","unstructured":"Cal\u00ed A, Gottlob G, Pieris A (2012) Towards more expressive ontology languages: the query answering problem. Artif Intell 193:87\u2013128","journal-title":"Artif Intell"},{"key":"674_CR13","unstructured":"Cate B, Dalmau V (2015) The product homomorphism problem and applications. In: Proceedings of ICDT, pp. 161\u2013176."},{"key":"674_CR14","unstructured":"Eiter T, Ortiz M, Simkus M, Tran T, Xiao G (2012) Query rewriting for horn-shiq plus rules. In: Proceedings of AAAI, AAAI Press."},{"key":"674_CR15","doi-asserted-by":"publisher","DOI":"10.23638\/LMCS-15(2:15)2019","author":"C Feier","year":"2019","unstructured":"Feier C, Kuusisto A, Lutz C (2019) Rewritability in monadic disjunctive datalog, MMSNP, and expressive description logics. Log Methods Comput Sci. https:\/\/doi.org\/10.23638\/LMCS-15(2:15)2019","journal-title":"Log Methods Comput Sci"},{"key":"674_CR16","unstructured":"Hustadt U, Motik B, Sattler U (2005) Data complexity of reasoning in very expressive description logics. In: Proceedings of IJCAI, Professional Book Center, pp. 466\u2013471."},{"key":"674_CR17","doi-asserted-by":"crossref","unstructured":"Kaminski M, Nenov Y, Grau BC (2014) Datalog rewritability of disjunctive datalog programs and its applications to ontology reasoning. In: Proceedings of AAAI, AAAI Press, pp. 1077\u20131083.","DOI":"10.1007\/978-3-319-11113-1_6"},{"key":"674_CR18","doi-asserted-by":"crossref","unstructured":"Krisnadhi A, Lutz C (2007) Data complexity in the $$\\cal{EL}$$ family of description logics. In: Proceedings of LPAR, LNAI, pp. 333\u2013347.","DOI":"10.1007\/978-3-540-75560-9_25"},{"key":"674_CR19","unstructured":"Lutz C, Seylan I, Wolter F (2015) Ontology-mediated queries with closed predicates. In: Proceedings of IJCAI, AAAI Press, pp. 3120\u20133126."},{"key":"674_CR20","unstructured":"Lutz C, Wolter F (2012) Non-uniform data complexity of query answering in description logics. In: Proceedings of KR, AAAI Press."},{"issue":"4","key":"674_CR21","first-page":"4060","volume":"13","author":"C Lutz","year":"2017","unstructured":"Lutz C, Wolter F (2017) The data complexity of description logic ontologies. Log Methods Comput Sci 13(4):4060","journal-title":"Log Methods Comput Sci"},{"key":"674_CR22","first-page":"133","volume":"10","author":"A Poggi","year":"2008","unstructured":"Poggi A, Lembo D, Calvanese D, Giacomo GD, Lenzerini M, Rosati R (2008) Linking data to ontologies. J Data Semant 10:133\u2013173","journal-title":"J Data Semant"},{"key":"674_CR23","doi-asserted-by":"crossref","unstructured":"Rosati R (2007) The limits of querying ontologies. In: Proceedings of ICDT, LNCS, pp. 164\u2013178.","DOI":"10.1007\/11965893_12"},{"key":"674_CR24","doi-asserted-by":"crossref","unstructured":"Sabellek L (2019) Ontology-mediated querying with horn description logics. Ph.D. thesis, University of Bremen.","DOI":"10.1007\/s13218-020-00674-7"},{"key":"674_CR25","doi-asserted-by":"crossref","unstructured":"Schneider T, \u0160imkus M (2020) Ontologies and data management: a brief survey. K\u00fcnstliche Intelligenz 34, to appear.","DOI":"10.1007\/s13218-020-00686-3"},{"key":"674_CR26","unstructured":"Tobies S (2001) Complexity results and practical algorithms for logics in knowledge representation. Ph.D. thesis, RWTH Aachen University, Germany."},{"issue":"5","key":"674_CR27","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1007\/s00778-013-0349-3","volume":"23","author":"QT Tran","year":"2014","unstructured":"Tran QT, Chan CY, Parthasarathy S (2014) Query reverse engineering. VLDB J 23(5):721\u2013746","journal-title":"VLDB J"},{"key":"674_CR28","unstructured":"Zakharyaschev M, Kikot S, Gerasimova O (2018) Towards a data complexity classification of ontology-mediated queries with covering. In: Proceedings of DL, CEUR Workshop Proceedings, CEUR-WS.org."},{"key":"674_CR29","doi-asserted-by":"crossref","unstructured":"Zhuk D (2017) A proof of CSP dichotomy conjecture. In: Proceedings of FOCS, pp. 331\u2013342","DOI":"10.1109\/FOCS.2017.38"},{"key":"674_CR30","doi-asserted-by":"crossref","unstructured":"Zloof MM (1975) Query-by-example: the invocation and definition of tables and forms. In: Proceedings of VLDB, pp. 1\u201324.","DOI":"10.1145\/1282480.1282482"}],"container-title":["KI - K\u00fcnstliche Intelligenz"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13218-020-00674-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13218-020-00674-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13218-020-00674-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,20]],"date-time":"2021-06-20T23:44:58Z","timestamp":1624232698000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s13218-020-00674-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,21]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["674"],"URL":"https:\/\/doi.org\/10.1007\/s13218-020-00674-7","relation":{},"ISSN":["0933-1875","1610-1987"],"issn-type":[{"type":"print","value":"0933-1875"},{"type":"electronic","value":"1610-1987"}],"subject":[],"published":{"date-parts":[[2020,6,21]]},"assertion":[{"value":"29 November 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 June 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}